from pylab import *
%matplotlib inline
factorial(10)
3628800
def factorial(n):
if n==0 or n==1:
return 1
else:
return n * fact(n-1)
[factorial(i) for i in range(0, 10)]
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
def factorial_algorithm(n):
return sum([factorial(int(digit)) for digit in str(n)])
factorial_algorithm(145)
145
n = arange(200)
plot(n, list(map(factorial_algorithm, n)))
plot(n, n, 'r', lw=3)
[<matplotlib.lines.Line2D at 0x106bee390>]
plot(n, list(map(factorial_algorithm, n)))
plot(n, n, 'r', lw=3)
ylim(0, n.max())
(0, 199)
factorial_algorithm(40585)
40585
double_algorithm = lambda n: factorial_algorithm(factorial_algorithm(n))
plot(n, list(map(factorial_algorithm, n)), label='simple')
plot(n, list(map(double_algorithm, n)), label='double')
legend()
<matplotlib.legend.Legend at 0x106e6bda0>
factorial_algorithm(199)
725761
factorial_algorithm(725761)
10923
def chain_length(n):
chain = [n]
iteration = factorial_algorithm(n)
while iteration not in chain:
chain.append(iteration)
iteration = factorial_algorithm(iteration)
return chain
from IPython.html.widgets import interact
interact(lambda n: print(chain_length(n)),
n=(0, 1000))
[20, 3, 6, 720, 5043, 151, 122, 5, 120, 4, 24, 26, 722, 5044, 169, 363601, 1454]
factorial_algorithm(1454)
169
n = arange(1000)
chain_lengths = [len(chain_length(i)) for i in n]
plot(n, chain_lengths)
[<matplotlib.lines.Line2D at 0x107489da0>]
%time chain_lengths = [len(chain_length(i)) for i in n]
CPU times: user 390 ms, sys: 2.54 ms, total: 392 ms Wall time: 396 ms
Essayons de mémoiser cet algorithme.
Condition + 0 :
Condition + 1 :
Condition + 2 :
def first_sieve():
n = arange(1000000)
print(n[array(list(map(factorial_algorithm, n))) == n])
%time first_sieve()
[ 1 2 145 40585] CPU times: user 16.3 s, sys: 79 ms, total: 16.4 s Wall time: 16.4 s
class chain_length_memoized():
def __init__(self):
self.lookup_table = {1:0,
2:0,
145:0,
40585:0,
871:1,
45361:1,
872:1,
45362:1,
169:2,
363601:2,
1454:2}
def compute_chain_length(self, n):
if n in self.lookup_table:
return 1 + self.lookup_table[n]
else:
iteration = factorial_algorithm(n)
self.lookup_table[n] = self.compute_chain_length(iteration)
return 1 + self.lookup_table[n]
clm = chain_length_memoized()
clm.compute_chain_length(0)
2
z = chain_length(0)
print(z, len(z))
[0, 1] 2
for i in range(1000000):
if clm.compute_chain_length(i) == 60:
print(i)
1479 1497 1749 1794 1947 1974 4079 4097 4179 4197 4709 4719 4790 4791 4907 4917 4970 4971 7049 7094 7149 7194 7409 7419 7490 7491 7904 7914 7940 7941 9047 9074 9147 9174 9407 9417 9470 9471 9704 9714 9740 9741 223479 223497 223749 223794 223947 223974 224379 224397 224739 224793 224937 224973 227349 227394 227439 227493 227934 227943 229347 229374 229437 229473 229734 229743 232479 232497 232749 232794 232947 232974 234279 234297 234729 234792 234927 234972 237249 237294 237429 237492 237924 237942 239247 239274 239427 239472 239724 239742 242379 242397 242739 242793 242937 242973 243279 243297 243729 243792 243927 243972 247239 247293 247329 247392 247923 247932 249237 249273 249327 249372 249723 249732 272349 272394 272439 272493 272934 272943 273249 273294 273429 273492 273924 273942 274239 274293 274329 274392 274923 274932 279234 279243 279324 279342 279423 279432 292347 292374 292437 292473 292734 292743 293247 293274 293427 293472 293724 293742 294237 294273 294327 294372 294723 294732 297234 297243 297324 297342 297423 297432 322479 322497 322749 322794 322947 322974 324279 324297 324729 324792 324927 324972 327249 327294 327429 327492 327924 327942 329247 329274 329427 329472 329724 329742 342279 342297 342729 342792 342927 342972 347229 347292 347922 349227 349272 349722 372249 372294 372429 372492 372924 372942 374229 374292 374922 379224 379242 379422 392247 392274 392427 392472 392724 392742 394227 394272 394722 397224 397242 397422 422379 422397 422739 422793 422937 422973 423279 423297 423729 423792 423927 423972 427239 427293 427329 427392 427923 427932 429237 429273 429327 429372 429723 429732 432279 432297 432729 432792 432927 432972 437229 437292 437922 439227 439272 439722 472239 472293 472329 472392 472923 472932 473229 473292 473922 479223 479232 479322 492237 492273 492327 492372 492723 492732 493227 493272 493722 497223 497232 497322 722349 722394 722439 722493 722934 722943 723249 723294 723429 723492 723924 723942 724239 724293 724329 724392 724923 724932 729234 729243 729324 729342 729423 729432 732249 732294 732429 732492 732924 732942 734229 734292 734922 739224 739242 739422 742239 742293 742329 742392 742923 742932 743229 743292 743922 749223 749232 749322 792234 792243 792324 792342 792423 792432 793224 793242 793422 794223 794232 794322 922347 922374 922437 922473 922734 922743 923247 923274 923427 923472 923724 923742 924237 924273 924327 924372 924723 924732 927234 927243 927324 927342 927423 927432 932247 932274 932427 932472 932724 932742 934227 934272 934722 937224 937242 937422 942237 942273 942327 942372 942723 942732 943227 943272 943722 947223 947232 947322 972234 972243 972324 972342 972423 972432 973224 973242 973422 974223 974232 974322
%time len([i for i in range(1000000) if clm.compute_chain_length(i) == 60])
CPU times: user 412 ms, sys: 2.44 ms, total: 414 ms Wall time: 414 ms
402
Finishing thoughts: