euler63.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "The 5-digit number, $16807=7^5$, is also a fifth power. Similarly, the 9-digit number, $134217728=8^9$, is a ninth power.\n",
   8     "\n",
   9     "How many _n_-digit positive integers exist which are also an *n*th power?\n",
  10     "\n",
  11     "$(\\log_{10} x) + 1 = n ; x = y ^ n$\n",
  12     "\n",
  13     "$log_y x = n = (\\log_{10} x) + 1$\n",
  14     "\n",
  15     "Possibly valid if $ log_y x \\le n = (\\log_{10} x) + 1$\n",
  16     "\n",
  17     "Possibly valid if $\\log_{10} y^n \\le n + 1$\n",
  18     "\n",
  19     "$n \\log_{10} y \\le n + 1$\n",
  20     "\n",
  21     "$\\log_{10} y \\le \\frac{n + 1}{n}$\n",
  22     "\n",
  23     "$y < 10$ as $10^n$ has $n+1$ digits.\n",
  24     "\n",
  25     "$y^n$ has $\\left \\lfloor \\log_{10} y^n \\right \\rfloor + 1 = \\left \\lfloor n \\log_{10} y \\right \\rfloor + 1$ digits.\n",
  26     "\n",
  27     "$\\left \\lfloor n \\log_{10} y \\right \\rfloor + 1 = n$\n",
  28     "\n",
  29     "$n \\left \\lfloor \\log_{10} y \\right \\rfloor = n - 1$\n",
  30     "\n",
  31     "$\\left \\lfloor \\log_{10} y \\right \\rfloor = \\frac{n - 1}{n}$\n",
  32     "\n",
  33     "$\\left \\lfloor \\log_{10} y \\right \\rfloor = 1 - \\frac{1}{n}$\n",
  34     "\n",
  35     "$\\frac{1}{n} = 1 - \\left \\lfloor \\log_{10} y \\right \\rfloor$\n",
  36     "\n",
  37     "${n} = \\frac{1}{1 - \\left \\lfloor \\log_{10} y \\right \\rfloor}$\n",
  38     "\n",
  39     "\n",
  40     "\n",
  41     "\n",
  42     "\n",
  43     "$ n \\log_{10} y  + 1 < n$\n",
  44     "\n",
  45     "$n \\log_{10} y< n - 1$\n",
  46     "\n",
  47     "$ \\log_{10} y < \\frac{n - 1}{n}$\n",
  48     "\n",
  49     "$\\log_{10} y < 1 - \\frac{1}{n}$\n",
  50     "\n",
  51     "$\\frac{1}{n} > 1 -  \\log_{10} y $\n",
  52     "\n",
  53     "${n} < \\frac{1}{1 -  \\log_{10} y}$\n",
  54     "\n",
  55     "${n} = \\left \\lfloor \\frac{1}{1 -  \\log_{10} y} \\right \\rfloor$\n",
  56     "\n",
  57     "| y | n | $y^n$ |\n",
  58     "|-----|\n",
  59     "| 1 | 1 | 1 |\n",
  60     "| 2 | 1 | 2 |\n",
  61     "| 3 | 1 | 3 |\n",
  62     "| 4 | 1 | 4 |\n",
  63     "| 4 | 2 | 16 |\n",
  64     "| 5 | 1 | 5 |\n",
  65     "| 5 | 2 | 25 |\n",
  66     "| 5 | 3 | 125 |\n",
  67     "| 6 | 1 | 6 |\n",
  68     "| 6 | 2 | 36 |\n",
  69     "| 6 | 3 | 216 |\n",
  70     "| 6 | 4 | 1296 |\n"
  71    ]
  72   },
  73   {
  74    "cell_type": "code",
  75    "execution_count": 26,
  76    "metadata": {},
  77    "outputs": [
  78     {
  79      "name": "stdout",
  80      "output_type": "stream",
  81      "text": [
  82       "1, 1\n",
  83       "2, 1\n",
  84       "3, 1\n",
  85       "4, 2\n",
  86       "5, 3\n",
  87       "6, 4\n",
  88       "7, 6\n",
  89       "8, 10\n",
  90       "9, 21\n"
  91      ]
  92     },
  93     {
  94      "data": {
  95       "text/plain": [
  96        "1..9"
  97       ]
  98      },
  99      "execution_count": 26,
 100      "metadata": {},
 101      "output_type": "execute_result"
 102     }
 103    ],
 104    "source": [
 105     "(1..9).each do |y|\n",
 106     "  puts \"#{y}, #{(1 / (1 - Math.log(y, 10))).floor}\"\n",
 107     "end"
 108    ]
 109   },
 110   {
 111    "cell_type": "code",
 112    "execution_count": 25,
 113    "metadata": {},
 114    "outputs": [
 115     {
 116      "data": {
 117       "text/plain": [
 118        "49"
 119       ]
 120      },
 121      "execution_count": 25,
 122      "metadata": {},
 123      "output_type": "execute_result"
 124     }
 125    ],
 126    "source": [
 127     "(1..9).map {|y| (1 / (1 - Math.log(y, 10))).floor}.sum"
 128    ]
 129   },
 130   {
 131    "cell_type": "code",
 132    "execution_count": null,
 133    "metadata": {
 134     "collapsed": true
 135    },
 136    "outputs": [],
 137    "source": []
 138   }
 139  ],
 140  "metadata": {
 141   "kernelspec": {
 142    "display_name": "Ruby 2.4.0",
 143    "language": "ruby",
 144    "name": "ruby"
 145   },
 146   "language_info": {
 147    "file_extension": ".rb",
 148    "mimetype": "application/x-ruby",
 149    "name": "ruby",
 150    "version": "2.4.0"
 151   }
 152  },
 153  "nbformat": 4,
 154  "nbformat_minor": 2
 155 }