advent20-slow.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {
   7     "collapsed": true
   8    },
   9    "outputs": [],
  10    "source": [
  11     "from functools import lru_cache, reduce\n",
  12     "from itertools import groupby\n",
  13     "import operator\n",
  14     "\n",
  15     "import sys\n",
  16     "sys.setrecursionlimit(1000000)"
  17    ]
  18   },
  19   {
  20    "cell_type": "code",
  21    "execution_count": 2,
  22    "metadata": {
  23     "collapsed": true
  24    },
  25    "outputs": [],
  26    "source": [
  27     "target = 33100000"
  28    ]
  29   },
  30   {
  31    "cell_type": "code",
  32    "execution_count": 3,
  33    "metadata": {
  34     "collapsed": true
  35    },
  36    "outputs": [],
  37    "source": [
  38     "def sieve(n):\n",
  39     "    primes = (2,3,5)\n",
  40     "    i = 7\n",
  41     "    while i <= n:\n",
  42     "        if not any(i % p == 0 for p in primes):\n",
  43     "            primes += tuple([i])\n",
  44     "        i += 2\n",
  45     "    return primes"
  46    ]
  47   },
  48   {
  49    "cell_type": "code",
  50    "execution_count": 4,
  51    "metadata": {
  52     "collapsed": false
  53    },
  54    "outputs": [
  55     {
  56      "data": {
  57       "text/plain": [
  58        "(2,\n",
  59        " 3,\n",
  60        " 5,\n",
  61        " 7,\n",
  62        " 11,\n",
  63        " 13,\n",
  64        " 17,\n",
  65        " 19,\n",
  66        " 23,\n",
  67        " 29,\n",
  68        " 31,\n",
  69        " 37,\n",
  70        " 41,\n",
  71        " 43,\n",
  72        " 47,\n",
  73        " 53,\n",
  74        " 59,\n",
  75        " 61,\n",
  76        " 67,\n",
  77        " 71,\n",
  78        " 73,\n",
  79        " 79,\n",
  80        " 83,\n",
  81        " 89,\n",
  82        " 97)"
  83       ]
  84      },
  85      "execution_count": 4,
  86      "metadata": {},
  87      "output_type": "execute_result"
  88     }
  89    ],
  90    "source": [
  91     "sieve(100)"
  92    ]
  93   },
  94   {
  95    "cell_type": "code",
  96    "execution_count": 5,
  97    "metadata": {
  98     "collapsed": false
  99    },
 100    "outputs": [
 101     {
 102      "data": {
 103       "text/plain": [
 104        "1819.3405398660252"
 105       ]
 106      },
 107      "execution_count": 5,
 108      "metadata": {},
 109      "output_type": "execute_result"
 110     }
 111    ],
 112    "source": [
 113     "max_prime = (target / 10)**0.5\n",
 114     "max_prime"
 115    ]
 116   },
 117   {
 118    "cell_type": "code",
 119    "execution_count": 6,
 120    "metadata": {
 121     "collapsed": false
 122    },
 123    "outputs": [
 124     {
 125      "data": {
 126       "text/plain": [
 127        "41538"
 128       ]
 129      },
 130      "execution_count": 6,
 131      "metadata": {},
 132      "output_type": "execute_result"
 133     }
 134    ],
 135    "source": [
 136     "max_prime = 500000\n",
 137     "primes = sieve(max_prime)\n",
 138     "len(primes)"
 139    ]
 140   },
 141   {
 142    "cell_type": "code",
 143    "execution_count": 7,
 144    "metadata": {
 145     "collapsed": true
 146    },
 147    "outputs": [],
 148    "source": [
 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",
 154     "    if n < 2:\n",
 155     "        return tuple()\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",
 160     "    else:\n",
 161     "        pf = prime_factors(n, unused_primes[1:])\n",
 162     "    prime_factors_cache[n] = pf\n",
 163     "    return pf"
 164    ]
 165   },
 166   {
 167    "cell_type": "code",
 168    "execution_count": 8,
 169    "metadata": {
 170     "collapsed": false
 171    },
 172    "outputs": [
 173     {
 174      "data": {
 175       "text/plain": [
 176        "(2, 2, 2, 5)"
 177       ]
 178      },
 179      "execution_count": 8,
 180      "metadata": {},
 181      "output_type": "execute_result"
 182     }
 183    ],
 184    "source": [
 185     "prime_factors(40, primes)"
 186    ]
 187   },
 188   {
 189    "cell_type": "code",
 190    "execution_count": 9,
 191    "metadata": {
 192     "collapsed": false
 193    },
 194    "outputs": [
 195     {
 196      "data": {
 197       "text/plain": [
 198        "(17,)"
 199       ]
 200      },
 201      "execution_count": 9,
 202      "metadata": {},
 203      "output_type": "execute_result"
 204     }
 205    ],
 206    "source": [
 207     "prime_factors(17, primes)"
 208    ]
 209   },
 210   {
 211    "cell_type": "code",
 212    "execution_count": 10,
 213    "metadata": {
 214     "collapsed": false
 215    },
 216    "outputs": [
 217     {
 218      "data": {
 219       "text/plain": [
 220        "{5: (5,), 10: (2, 5), 17: (17,), 20: (2, 2, 5), 40: (2, 2, 2, 5)}"
 221       ]
 222      },
 223      "execution_count": 10,
 224      "metadata": {},
 225      "output_type": "execute_result"
 226     }
 227    ],
 228    "source": [
 229     "# prime_factors.cache_info()\n",
 230     "prime_factors_cache"
 231    ]
 232   },
 233   {
 234    "cell_type": "code",
 235    "execution_count": 11,
 236    "metadata": {
 237     "collapsed": false
 238    },
 239    "outputs": [
 240     {
 241      "data": {
 242       "text/plain": [
 243        "[(2, 3), (5, 1)]"
 244       ]
 245      },
 246      "execution_count": 11,
 247      "metadata": {},
 248      "output_type": "execute_result"
 249     }
 250    ],
 251    "source": [
 252     "[(p, len(list(i))) for p, i in groupby(prime_factors(40, primes))]"
 253    ]
 254   },
 255   {
 256    "cell_type": "code",
 257    "execution_count": 12,
 258    "metadata": {
 259     "collapsed": false
 260    },
 261    "outputs": [
 262     {
 263      "data": {
 264       "text/plain": [
 265        "[1, 2, 4, 8]"
 266       ]
 267      },
 268      "execution_count": 12,
 269      "metadata": {},
 270      "output_type": "execute_result"
 271     }
 272    ],
 273    "source": [
 274     "[2**p for p in range(3+1)]"
 275    ]
 276   },
 277   {
 278    "cell_type": "code",
 279    "execution_count": 13,
 280    "metadata": {
 281     "collapsed": true
 282    },
 283    "outputs": [],
 284    "source": [
 285     "def prod(iterable):\n",
 286     "    return reduce(operator.mul, iterable, 1)"
 287    ]
 288   },
 289   {
 290    "cell_type": "code",
 291    "execution_count": 14,
 292    "metadata": {
 293     "collapsed": true
 294    },
 295    "outputs": [],
 296    "source": [
 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)"
 302    ]
 303   },
 304   {
 305    "cell_type": "code",
 306    "execution_count": 15,
 307    "metadata": {
 308     "collapsed": false
 309    },
 310    "outputs": [
 311     {
 312      "data": {
 313       "text/plain": [
 314        "7"
 315       ]
 316      },
 317      "execution_count": 15,
 318      "metadata": {},
 319      "output_type": "execute_result"
 320     }
 321    ],
 322    "source": [
 323     "sum_of_factors(4, primes)"
 324    ]
 325   },
 326   {
 327    "cell_type": "code",
 328    "execution_count": 16,
 329    "metadata": {
 330     "collapsed": false
 331    },
 332    "outputs": [
 333     {
 334      "name": "stdout",
 335      "output_type": "stream",
 336      "text": [
 337       "0 10\n",
 338       "1 10\n",
 339       "2 30\n",
 340       "3 40\n",
 341       "4 70\n",
 342       "5 60\n",
 343       "6 120\n",
 344       "7 80\n",
 345       "8 150\n",
 346       "9 130\n"
 347      ]
 348     }
 349    ],
 350    "source": [
 351     "for i in range(10):\n",
 352     "    print(i, sum_of_factors(i, primes) * 10)"
 353    ]
 354   },
 355   {
 356    "cell_type": "code",
 357    "execution_count": null,
 358    "metadata": {
 359     "collapsed": false
 360    },
 361    "outputs": [],
 362    "source": [
 363     "i = 7687\n",
 364     "while True:\n",
 365     "    try:\n",
 366     "        if sum_of_factors(i, primes) * 10 >= target :\n",
 367     "            break\n",
 368     "        i += 1\n",
 369     "    except:\n",
 370     "        print(\"failed with i =\", i)\n",
 371     "        break\n",
 372     "    \n",
 373     "i"
 374    ]
 375   },
 376   {
 377    "cell_type": "code",
 378    "execution_count": 41,
 379    "metadata": {
 380     "collapsed": false
 381    },
 382    "outputs": [
 383     {
 384      "data": {
 385       "text/plain": [
 386        "7680"
 387       ]
 388      },
 389      "execution_count": 41,
 390      "metadata": {},
 391      "output_type": "execute_result"
 392     }
 393    ],
 394    "source": [
 395     "max(prime_factors_cache)"
 396    ]
 397   },
 398   {
 399    "cell_type": "code",
 400    "execution_count": 42,
 401    "metadata": {
 402     "collapsed": false
 403    },
 404    "outputs": [
 405     {
 406      "data": {
 407       "text/plain": [
 408        "499979"
 409       ]
 410      },
 411      "execution_count": 42,
 412      "metadata": {},
 413      "output_type": "execute_result"
 414     }
 415    ],
 416    "source": [
 417     "primes[-1]"
 418    ]
 419   },
 420   {
 421    "cell_type": "code",
 422    "execution_count": 43,
 423    "metadata": {
 424     "collapsed": false
 425    },
 426    "outputs": [
 427     {
 428      "data": {
 429       "text/plain": [
 430        "(2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 5)"
 431       ]
 432      },
 433      "execution_count": 43,
 434      "metadata": {},
 435      "output_type": "execute_result"
 436     }
 437    ],
 438    "source": [
 439     "prime_factors_cache[7680]"
 440    ]
 441   },
 442   {
 443    "cell_type": "code",
 444    "execution_count": 44,
 445    "metadata": {
 446     "collapsed": false
 447    },
 448    "outputs": [
 449     {
 450      "data": {
 451       "text/plain": [
 452        "7680"
 453       ]
 454      },
 455      "execution_count": 44,
 456      "metadata": {},
 457      "output_type": "execute_result"
 458     }
 459    ],
 460    "source": [
 461     "prod(prime_factors_cache[7680])"
 462    ]
 463   },
 464   {
 465    "cell_type": "code",
 466    "execution_count": 57,
 467    "metadata": {
 468     "collapsed": false
 469    },
 470    "outputs": [
 471     {
 472      "data": {
 473       "text/plain": [
 474        "True"
 475       ]
 476      },
 477      "execution_count": 57,
 478      "metadata": {},
 479      "output_type": "execute_result"
 480     }
 481    ],
 482    "source": [
 483     "7687 in primes"
 484    ]
 485   },
 486   {
 487    "cell_type": "code",
 488    "execution_count": 58,
 489    "metadata": {
 490     "collapsed": false
 491    },
 492    "outputs": [
 493     {
 494      "data": {
 495       "text/plain": [
 496        "(7687,)"
 497       ]
 498      },
 499      "execution_count": 58,
 500      "metadata": {},
 501      "output_type": "execute_result"
 502     }
 503    ],
 504    "source": [
 505     "prime_factors(7687, primes)"
 506    ]
 507   },
 508   {
 509    "cell_type": "code",
 510    "execution_count": 48,
 511    "metadata": {
 512     "collapsed": false
 513    },
 514    "outputs": [
 515     {
 516      "data": {
 517       "text/plain": [
 518        "7682"
 519       ]
 520      },
 521      "execution_count": 48,
 522      "metadata": {},
 523      "output_type": "execute_result"
 524     }
 525    ],
 526    "source": [
 527     "sum_of_factors(7681, primes)"
 528    ]
 529   },
 530   {
 531    "cell_type": "code",
 532    "execution_count": 56,
 533    "metadata": {
 534     "collapsed": false
 535    },
 536    "outputs": [
 537     {
 538      "data": {
 539       "text/plain": [
 540        "7688"
 541       ]
 542      },
 543      "execution_count": 56,
 544      "metadata": {},
 545      "output_type": "execute_result"
 546     }
 547    ],
 548    "source": [
 549     "sum_of_factors(7687, primes)"
 550    ]
 551   },
 552   {
 553    "cell_type": "code",
 554    "execution_count": 17,
 555    "metadata": {
 556     "collapsed": false
 557    },
 558    "outputs": [
 559     {
 560      "data": {
 561       "text/plain": [
 562        "[(2, 5), (3, 2), (5, 1), (7, 2), (11, 1)]"
 563       ]
 564      },
 565      "execution_count": 17,
 566      "metadata": {},
 567      "output_type": "execute_result"
 568     }
 569    ],
 570    "source": [
 571     "fs = prime_factors(776160, primes)\n",
 572     "[(p, len(list(i))) for p, i in groupby(fs)]"
 573    ]
 574   },
 575   {
 576    "cell_type": "code",
 577    "execution_count": 18,
 578    "metadata": {
 579     "collapsed": false
 580    },
 581    "outputs": [
 582     {
 583      "data": {
 584       "text/plain": [
 585        "(2, 2, 2, 2, 2, 3, 3, 5, 7, 7, 11)"
 586       ]
 587      },
 588      "execution_count": 18,
 589      "metadata": {},
 590      "output_type": "execute_result"
 591     }
 592    ],
 593    "source": [
 594     "fs"
 595    ]
 596   },
 597   {
 598    "cell_type": "code",
 599    "execution_count": 19,
 600    "metadata": {
 601     "collapsed": false
 602    },
 603    "outputs": [
 604     {
 605      "data": {
 606       "text/plain": [
 607        "776160"
 608       ]
 609      },
 610      "execution_count": 19,
 611      "metadata": {},
 612      "output_type": "execute_result"
 613     }
 614    ],
 615    "source": [
 616     "prod(fs)"
 617    ]
 618   },
 619   {
 620    "cell_type": "code",
 621    "execution_count": 20,
 622    "metadata": {
 623     "collapsed": false
 624    },
 625    "outputs": [
 626     {
 627      "data": {
 628       "text/plain": [
 629        "3361176"
 630       ]
 631      },
 632      "execution_count": 20,
 633      "metadata": {},
 634      "output_type": "execute_result"
 635     }
 636    ],
 637    "source": [
 638     "sum_of_factors(776160, primes)"
 639    ]
 640   },
 641   {
 642    "cell_type": "code",
 643    "execution_count": null,
 644    "metadata": {
 645     "collapsed": true
 646    },
 647    "outputs": [],
 648    "source": []
 649   }
 650  ],
 651  "metadata": {
 652   "kernelspec": {
 653    "display_name": "Python 3",
 654    "language": "python",
 655    "name": "python3"
 656   },
 657   "language_info": {
 658    "codemirror_mode": {
 659     "name": "ipython",
 660     "version": 3
 661    },
 662    "file_extension": ".py",
 663    "mimetype": "text/x-python",
 664    "name": "python",
 665    "nbconvert_exporter": "python",
 666    "pygments_lexer": "ipython3",
 667    "version": "3.4.3"
 668   }
 669  },
 670  "nbformat": 4,
 671  "nbformat_minor": 0
 672 }