Practical numbers: Difference between revisions

Content added Content deleted
m (J implementation)
Line 236: Line 236:
STRETCH GOAL: 666 is Practical.</pre>
STRETCH GOAL: 666 is Practical.</pre>


====Python: Alternate version====
====Python: Faster version====
This version has an optimisation that might prove ''much'' faster in some cases but slower than the above in others.
This version has an optimisation that proves ''much'' faster when testing a range of numbers for Practicality.


A number with a large number of factors, f has <code>2**len(f)</code> sets in its powerset. 672 for example has 23 factors and so 8_388_608 sets in its powerset.<br>
A number with a large number of factors, f has <code>2**len(f)</code> sets in its powerset. 672 for example has 23 factors and so 8_388_608 sets in its powerset.<br>
Line 243: Line 243:
the sets. 720, another Practical number needs just 0.01% of its half a billion sets to prove it is Practical.
the sets. 720, another Practical number needs just 0.01% of its half a billion sets to prove it is Practical.


The inner loop is sensitive to the order of factors passed to the powerset generator and [XXX experimentation shows] that reverse sorting the factors saves the most computation.
Note however that if the number is '''not''' ultimately Practical, with a large number of factors, then the loop to find this is slightly ''slower''.


⚫
<lang python>def is_practical2(x: int, __switch=23) -> bool:
"""
Is x a practical number.


⚫
<lang python>def is_practical5(x: int) -> bool:
I.e. Can some selection of the proper divisors of x, (other than x), sum
"""Practical number test with factor reverse sort and short-circuiting."""
to i for all i in the range 1..x-1 inclusive.


Can short-circuit summations for x with large number of factors >= __switch
"""
if x == 1:
if x == 1:
return True
return True
Line 261: Line 256:
if x > 2 and not mult_4_or_6:
if x > 2 and not mult_4_or_6:
return False # If > 2 then must be a divisor of 4 or 6
return False # If > 2 then must be a divisor of 4 or 6
⚫
f = factors5(x)
⚫
ps = powerset(f) # = 2**len(f) items


⚫
f = sorted(factors5(x), reverse=True)
if len(f) < __switch:
⚫
ps = powerset(f)
found = {y for y in {sum(i) for i in ps}

if 1 <= y < x}
else:
found = set()
found = set()
for nps in ps:
while len(found) < x - 1:
if len(found) < x - 1:
y = sum(next(ps))
y = sum(nps)
if 1 <= y < x:
if 1 <= y < x:
found.add(y)
found.add(y)
else:
break # Short-circuiting the loop.


return len(found) == x - 1</lang>
return len(found) == x - 1


if __name__ == '__main__':
n = 333
print("\n" + is_practical5.__doc__)
p = [x for x in range(1, n + 1) if is_practical5(x)]
print(f"There are {len(p)} Practical numbers from 1 to {n}:")
print(' ', str(p[:10])[1:-1], '...', str(p[-10:])[1:-1])
x = 666
print(f"\nSTRETCH GOAL: {x} is {'not ' if not is_practical(x) else ''}Practical.")
x = 5184
print(f"\nEXTRA GOAL: {x} is {'not ' if not is_practical(x) else ''}Practical.")</lang>


{{out}}
{{out}}
If the above function replaces that in the simple case above then the same results are produced.
Using the definition of factors5 from the simple case above then the following results are obtained.


<pre>Practical number test with factor reverse sort and short-circuiting.
⚫
672, which is practical and has 23 factors computes 200 times faster.<br>
There are 77 Practical numbers from 1 to 333:
1, 2, 4, 6, 8, 12, 16, 18, 20, 24 ... 288, 294, 300, 304, 306, 308, 312, 320, 324, 330

STRETCH GOAL: 666 is Practical.

EXTRA GOAL: 5184 is Practical.</pre>

⚫
5184, which is practical, has 34 factors!<br>


A little further investigation shows that you need to get to 3850, for the first example of a number with 23 or more factors that is not Practical.<br>
A little further investigation shows that you need to get to 3850, for the first example of a number with 23 or more factors that is not Practical.<br>

Around 1/8'th of the integers up to the 10_000'th Practical number have more than 22 factors but are '''not''' practical numbers themselves. (Some of these have 31 factors whilst being divisible by four or six so need the long loop)!
Around 1/8'th of the integers up to the 10_000'th Practical number have more than 22 factors but are '''not''' practical numbers themselves. (Some of these have 31 factors whilst being divisible by four or six so would need the long loop to complete)!


===Composition of pure functions===
===Composition of pure functions===
Retrieved from "https://rosettacode.org/wiki/Practical_numbers"