Anonymous user
Practical numbers: Difference between revisions
→Python: Alternate version: Code.
(→Python: Alternate version: Code.) |
|||
Line 127:
====Python: Alternate version====
This version has an optimisation that might prove
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 133:
the sets. 720, another Practical number needs just 0.01% of its half a billion sets to prove it is Practical.
Note however that if the number is
<lang python>def is_practical2(x: int, __switch=23) -> bool:
"""
Is x a practical number.
I.e. Can some selection of the proper divisors of x, (other than x), sum
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:
return True
if x % 2:
return False # No Odd number more than 1
mult_4_or_6 = (x % 4 == 0) or (x % 6 == 0)
if x > 2 and not mult_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
if len(f) < __switch:
found = {y for y in {sum(i) for i in ps}
if 1 <= y < x}
else:
found = set()
while len(found) < x - 1:
y = sum(next(ps))
if 1 <= y < x:
found.add(y)
return len(found) == x - 1</lang>
{{out}}
If the above function replaces that in the simple case above then the same results are produced.
672, which is practical and has 23 factors computes 200 times faster.<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.
===Composition of pure functions===
| |||