Rosetta Code

Practical numbers: Difference between revisions

Page Discussion

Practical numbers (view source)

Revision as of 16:38, 5 April 2021

524 bytes added ,  3 years ago
→‎Python: Faster version
m (J implementation)
Line 236:
STRETCH GOAL: 666 is Practical.</pre>
 
====Python: AlternateFaster version====
This version has an optimisation that might proveproves ''much'' faster in some caseswhen buttesting slowera thanrange theof abovenumbers infor othersPracticality.
 
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:
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_practical2is_practical5(x: int, __switch=23) -> 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:
return True
Line 261 ⟶ 256:
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▼
 
▲ f = sorted(factors5(x), reverse=True)
if len(f) < __switch:
▲ ps = powerset(f) # = 2**len(f) items
found = {y for y in {sum(i) for i in ps}
 
if 1 <= y < x}
else:found = set()
for nps in found = set()ps:
whileif len(found) < x - 1:
y = sum(next(ps)nps)
if 1 <= y < x:
found.add(y)
else:
break # Short-circuiting the loop.
 
return len(found) == x - 1</lang>
 
 
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}}
IfUsing the above functiondefinition replacesof thatfactors5 infrom the simple case above then the samefollowing results are producedobtained.
 
<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>
 
▲6725184, which is practical and, has 2334 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.<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 would need the long loop to complete)!
 
===Composition of pure functions===
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/310354"