euler58.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Diagonals\n",
   8     "\n",
   9     "```\n",
  10     "37 36 35 34 33 32 31\n",
  11     "38 17 16 15 14 13 30\n",
  12     "39 18  5  4  3 12 29\n",
  13     "40 19  6  1  2 11 28\n",
  14     "41 20  7  8  9 10 27\n",
  15     "42 21 22 23 24 25 26\n",
  16     "43 44 45 46 47 48 49\n",
  17     "```\n",
  18     "\n",
  19     "Down-right goes as 1, 9, 25, 49: (2i+1)^2, starting from i=0\n",
  20     "\n",
  21     "Down left goes as 1 7 21 43: (2i+1)^2 - 2i\n",
  22     "\n",
  23     "Up left goes 1 5 17 37: (2i + 1)^2 - 4i\n",
  24     "\n",
  25     "Up right goes 1 3 13 31: (2i + 1)^2 - 6i\n"
  26    ]
  27   },
  28   {
  29    "cell_type": "code",
  30    "execution_count": 1,
  31    "metadata": {},
  32    "outputs": [
  33     {
  34      "data": {
  35       "text/plain": [
  36        "9973"
  37       ]
  38      },
  39      "execution_count": 1,
  40      "metadata": {},
  41      "output_type": "execute_result"
  42     }
  43    ],
  44    "source": [
  45     "require_relative 'primes'\n",
  46     "primes = Primes.instance\n",
  47     "# primes.load_primes \"primes_2000000.txt\"\n",
  48     "primes.primes.last"
  49    ]
  50   },
  51   {
  52    "cell_type": "code",
  53    "execution_count": 2,
  54    "metadata": {},
  55    "outputs": [
  56     {
  57      "data": {
  58       "text/plain": [
  59        "[1, 9, 25, 49, 81]"
  60       ]
  61      },
  62      "execution_count": 2,
  63      "metadata": {},
  64      "output_type": "execute_result"
  65     }
  66    ],
  67    "source": [
  68     "(0...5).map {|i| (2 * i + 1) ** 2}"
  69    ]
  70   },
  71   {
  72    "cell_type": "code",
  73    "execution_count": 3,
  74    "metadata": {},
  75    "outputs": [
  76     {
  77      "data": {
  78       "text/plain": [
  79        "[1, 7, 21, 43, 73]"
  80       ]
  81      },
  82      "execution_count": 3,
  83      "metadata": {},
  84      "output_type": "execute_result"
  85     }
  86    ],
  87    "source": [
  88     "(0...5).map {|i| (2 * i + 1) ** 2 - 2 * i}"
  89    ]
  90   },
  91   {
  92    "cell_type": "code",
  93    "execution_count": 4,
  94    "metadata": {},
  95    "outputs": [
  96     {
  97      "data": {
  98       "text/plain": [
  99        "[1, 5, 17, 37, 65]"
 100       ]
 101      },
 102      "execution_count": 4,
 103      "metadata": {},
 104      "output_type": "execute_result"
 105     }
 106    ],
 107    "source": [
 108     "(0...5).map {|i| (2 * i + 1) ** 2 - 4 * i}"
 109    ]
 110   },
 111   {
 112    "cell_type": "code",
 113    "execution_count": 5,
 114    "metadata": {},
 115    "outputs": [
 116     {
 117      "data": {
 118       "text/plain": [
 119        "[1, 3, 13, 31, 57]"
 120       ]
 121      },
 122      "execution_count": 5,
 123      "metadata": {},
 124      "output_type": "execute_result"
 125     }
 126    ],
 127    "source": [
 128     "(0...5).map {|i| (2 * i + 1) ** 2 - 6 * i}"
 129    ]
 130   },
 131   {
 132    "cell_type": "code",
 133    "execution_count": 6,
 134    "metadata": {},
 135    "outputs": [
 136     {
 137      "data": {
 138       "text/plain": [
 139        ":diagonals"
 140       ]
 141      },
 142      "execution_count": 6,
 143      "metadata": {},
 144      "output_type": "execute_result"
 145     }
 146    ],
 147    "source": [
 148     "def diagonals(n)\n",
 149     "  [1] + (1...n).flat_map {|i| [\n",
 150     "      (2 * i + 1) ** 2,\n",
 151     "      (2 * i + 1) ** 2 - 2 * i,\n",
 152     "      (2 * i + 1) ** 2 - 4 * i,\n",
 153     "      (2 * i + 1) ** 2 - 6 * i\n",
 154     "      ]}\n",
 155     "end"
 156    ]
 157   },
 158   {
 159    "cell_type": "code",
 160    "execution_count": 7,
 161    "metadata": {},
 162    "outputs": [
 163     {
 164      "data": {
 165       "text/plain": [
 166        ":diagonal_tips"
 167       ]
 168      },
 169      "execution_count": 7,
 170      "metadata": {},
 171      "output_type": "execute_result"
 172     }
 173    ],
 174    "source": [
 175     "def diagonal_tips(n)\n",
 176     "  [# (2 * n + 1) ** 2,\n",
 177     "   (2 * n + 1) ** 2 - 2 * n,\n",
 178     "   (2 * n + 1) ** 2 - 4 * n,\n",
 179     "   (2 * n + 1) ** 2 - 6 * n]\n",
 180     "end"
 181    ]
 182   },
 183   {
 184    "cell_type": "code",
 185    "execution_count": 8,
 186    "metadata": {},
 187    "outputs": [
 188     {
 189      "data": {
 190       "text/plain": [
 191        "[1, 9, 7, 5, 3, 25, 21, 17, 13]"
 192       ]
 193      },
 194      "execution_count": 8,
 195      "metadata": {},
 196      "output_type": "execute_result"
 197     }
 198    ],
 199    "source": [
 200     "diagonals(3)"
 201    ]
 202   },
 203   {
 204    "cell_type": "code",
 205    "execution_count": 9,
 206    "metadata": {},
 207    "outputs": [
 208     {
 209      "data": {
 210       "text/plain": [
 211        "9"
 212       ]
 213      },
 214      "execution_count": 9,
 215      "metadata": {},
 216      "output_type": "execute_result"
 217     }
 218    ],
 219    "source": [
 220     "diagonals(3).length"
 221    ]
 222   },
 223   {
 224    "cell_type": "code",
 225    "execution_count": 10,
 226    "metadata": {},
 227    "outputs": [
 228     {
 229      "data": {
 230       "text/plain": [
 231        "[7, 5, 3, 17, 13]"
 232       ]
 233      },
 234      "execution_count": 10,
 235      "metadata": {},
 236      "output_type": "execute_result"
 237     }
 238    ],
 239    "source": [
 240     "diagonals(3).select {|n| n.prime?}"
 241    ]
 242   },
 243   {
 244    "cell_type": "code",
 245    "execution_count": 11,
 246    "metadata": {},
 247    "outputs": [
 248     {
 249      "data": {
 250       "text/plain": [
 251        "26241"
 252       ]
 253      },
 254      "execution_count": 11,
 255      "metadata": {},
 256      "output_type": "execute_result"
 257     }
 258    ],
 259    "source": [
 260     "l = 1\n",
 261     "tip_primes = diagonal_tips(l).select {|n| primes.is_prime? n}\n",
 262     "prime_count = tip_primes.length\n",
 263     "while prime_count * 10 > (4 * l + 1)\n",
 264     "  # puts l if l % 500 == 0\n",
 265     "  l += 1\n",
 266     "  tip_primes = diagonal_tips(l).select {|n| primes.is_prime? n}\n",
 267     "  prime_count += tip_primes.length\n",
 268     "end\n",
 269     "l * 2 + 1 # side length"
 270    ]
 271   },
 272   {
 273    "cell_type": "code",
 274    "execution_count": null,
 275    "metadata": {
 276     "collapsed": true
 277    },
 278    "outputs": [],
 279    "source": []
 280   }
 281  ],
 282  "metadata": {
 283   "kernelspec": {
 284    "display_name": "Ruby 2.4.0",
 285    "language": "ruby",
 286    "name": "ruby"
 287   },
 288   "language_info": {
 289    "file_extension": ".rb",
 290    "mimetype": "application/x-ruby",
 291    "name": "ruby",
 292    "version": "2.4.0"
 293   }
 294  },
 295  "nbformat": 4,
 296  "nbformat_minor": 2
 297 }