Practical numbers: Difference between revisions

Line 127:

====Python: Alternate 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 might prove ''much'' faster in some cases but slower than the above in others.

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 ~~```~~not~~```~~

Note however that if the number is '''not''' ultimately Practical, with a large number of factors, then the loop to find this is ''slower''.

<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>

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===