11 "from functools import lru_cache, reduce\n",
12 "from itertools import groupby\n",
16 "sys.setrecursionlimit(1000000)"
39 " primes = (2,3,5)\n",
42 " if not any(i % p == 0 for p in primes):\n",
43 " primes += tuple([i])\n",
87 "output_type": "execute_result"
107 "execution_count": 5,
109 "output_type": "execute_result"
113 "max_prime = (target / 10)**0.5\n",
119 "execution_count": 6,
130 "execution_count": 6,
132 "output_type": "execute_result"
136 "max_prime = 500000\n",
137 "primes = sieve(max_prime)\n",
143 "execution_count": 7,
149 "prime_factors_cache = {}\n",
150 "# @lru_cache(maxsize=None)\n",
151 "def prime_factors(n, unused_primes):\n",
152 " if n in prime_factors_cache:\n",
153 " return prime_factors_cache[n]\n",
156 " if n in unused_primes:\n",
157 " pf = tuple([n])\n",
158 " elif n % unused_primes[0] == 0:\n",
159 " pf = tuple([unused_primes[0]]) + prime_factors(n // unused_primes[0], unused_primes)\n",
161 " pf = prime_factors(n, unused_primes[1:])\n",
162 " prime_factors_cache[n] = pf\n",
168 "execution_count": 8,
179 "execution_count": 8,
181 "output_type": "execute_result"
185 "prime_factors(40, primes)"
190 "execution_count": 9,
201 "execution_count": 9,
203 "output_type": "execute_result"
207 "prime_factors(17, primes)"
212 "execution_count": 10,
220 "{5: (5,), 10: (2, 5), 17: (17,), 20: (2, 2, 5), 40: (2, 2, 2, 5)}"
223 "execution_count": 10,
225 "output_type": "execute_result"
229 "# prime_factors.cache_info()\n",
230 "prime_factors_cache"
235 "execution_count": 11,
246 "execution_count": 11,
248 "output_type": "execute_result"
252 "[(p, len(list(i))) for p, i in groupby(prime_factors(40, primes))]"
257 "execution_count": 12,
268 "execution_count": 12,
270 "output_type": "execute_result"
274 "[2**p for p in range(3+1)]"
279 "execution_count": 13,
285 "def prod(iterable):\n",
286 " return reduce(operator.mul, iterable, 1)"
291 "execution_count": 14,
297 "def sum_of_factors(n, primes):\n",
298 " pfs = prime_factors(n, primes)\n",
299 " grouped_pfs = [(p, len(list(i))) for p, i in groupby(pfs)]\n",
300 " prime_sums = [sum(p**i for i in range(e+1)) for p, e in grouped_pfs]\n",
301 " return prod(prime_sums)"
306 "execution_count": 15,
317 "execution_count": 15,
319 "output_type": "execute_result"
323 "sum_of_factors(4, primes)"
328 "execution_count": 16,
335 "output_type": "stream",
351 "for i in range(10):\n",
352 " print(i, sum_of_factors(i, primes) * 10)"
357 "execution_count": null,
366 " if sum_of_factors(i, primes) * 10 >= target :\n",
370 " print(\"failed with i =\", i)\n",
378 "execution_count": 41,
389 "execution_count": 41,
391 "output_type": "execute_result"
395 "max(prime_factors_cache)"
400 "execution_count": 42,
411 "execution_count": 42,
413 "output_type": "execute_result"
422 "execution_count": 43,
430 "(2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 5)"
433 "execution_count": 43,
435 "output_type": "execute_result"
439 "prime_factors_cache[7680]"
444 "execution_count": 44,
455 "execution_count": 44,
457 "output_type": "execute_result"
461 "prod(prime_factors_cache[7680])"
466 "execution_count": 57,
477 "execution_count": 57,
479 "output_type": "execute_result"
488 "execution_count": 58,
499 "execution_count": 58,
501 "output_type": "execute_result"
505 "prime_factors(7687, primes)"
510 "execution_count": 48,
521 "execution_count": 48,
523 "output_type": "execute_result"
527 "sum_of_factors(7681, primes)"
532 "execution_count": 56,
543 "execution_count": 56,
545 "output_type": "execute_result"
549 "sum_of_factors(7687, primes)"
554 "execution_count": 17,
562 "[(2, 5), (3, 2), (5, 1), (7, 2), (11, 1)]"
565 "execution_count": 17,
567 "output_type": "execute_result"
571 "fs = prime_factors(776160, primes)\n",
572 "[(p, len(list(i))) for p, i in groupby(fs)]"
577 "execution_count": 18,
585 "(2, 2, 2, 2, 2, 3, 3, 5, 7, 7, 11)"
588 "execution_count": 18,
590 "output_type": "execute_result"
599 "execution_count": 19,
610 "execution_count": 19,
612 "output_type": "execute_result"
621 "execution_count": 20,
632 "execution_count": 20,
634 "output_type": "execute_result"
638 "sum_of_factors(776160, primes)"
643 "execution_count": null,
653 "display_name": "Python 3",
654 "language": "python",
662 "file_extension": ".py",
663 "mimetype": "text/x-python",
665 "nbconvert_exporter": "python",
666 "pygments_lexer": "ipython3",