Created
March 14, 2018 11:09
-
-
Save christianp/878836f4f436f9d77cc3e6b119fab742 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"A function to work through the $n$ times table until every possible first digit has been seen." | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 96, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"def time_until_all_seen(n):\n", | |
" seen = set()\n", | |
" c = 0\n", | |
" t = n\n", | |
" while len(seen)<9:\n", | |
" c += 1\n", | |
" s=str(t)[0]\n", | |
" seen.add(s)\n", | |
" t += n\n", | |
" return c" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"Look how bad the 13 times table is! But 112 is even worse." | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 95, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"62\n", | |
"81\n" | |
] | |
} | |
], | |
"source": [ | |
"print(time_until_all_seen(13))\n", | |
"print(time_until_all_seen(112))" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"Now do the same thing as above, but keep track of how many times each pair of leading digits is seen" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 98, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
" 1 1 0 2 1 1 1 0 1 1\n", | |
" 1 0 1 1 1 0 2 1 1 1\n", | |
" 0 1 1 1 0 1 1 1 0 2\n", | |
" 1 1 1 0 1 1 1 0 1 1\n", | |
" 1 0 2 1 1 1 0 1 1 1\n", | |
" 0 1 1 1 0 2 1 1 1 0\n", | |
" 1 1 1 0 1 1 1 0 2 1\n", | |
" 1 0 0 0 0 0 0 0 0 0\n", | |
" 0 1 0 0 0 0 0 0 0 0\n" | |
] | |
} | |
], | |
"source": [ | |
"def count_times_seen(n):\n", | |
" times_seen = defaultdict(lambda:0)\n", | |
" seen = set()\n", | |
" c = 0\n", | |
" t = n\n", | |
" while len(seen)<9:\n", | |
" c += 1\n", | |
" s=str(t)[0]\n", | |
" s_more = str(t)[:2]\n", | |
" times_seen[s_more] += 1\n", | |
" seen.add(s)\n", | |
" t += n\n", | |
" for a in range(1,10):\n", | |
" bits = []\n", | |
" for b in range(0,10):\n", | |
" s = str(a)+str(b)\n", | |
" bits.append('{:>2}'.format(times_seen[s]))\n", | |
" print(' '.join(bits))\n", | |
"\n", | |
"count_times_seen(13)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 99, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"111112 to 112499 take 81 steps\n" | |
] | |
} | |
], | |
"source": [ | |
"from itertools import count\n", | |
"first = 111112\n", | |
"for i in count(first):\n", | |
" c = time_until_all_seen(i)\n", | |
" if c!=81:\n", | |
" break\n", | |
"print('{} to {} take 81 steps'.format(first,i-1))" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"How long do numbers of the form $\\left\\lceil \\frac{1}{9} \\cdot 10^n \\right\\rceil$ take?" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 100, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"1 9\n", | |
"2 45\n", | |
"12 42\n", | |
"112 81\n", | |
"1112 81\n", | |
"11112 81\n", | |
"111112 81\n", | |
"1111112 81\n", | |
"11111112 81\n", | |
"111111112 81\n" | |
] | |
} | |
], | |
"source": [ | |
"from math import ceil\n", | |
"for i in range(10):\n", | |
" n = ceil(10**i/9)\n", | |
" print(n, time_until_all_seen(n))" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"The last thing to do is to find the record-setters:" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 102, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"1 9\n", | |
"2 45\n", | |
"13 62\n", | |
"112 81\n" | |
] | |
} | |
], | |
"source": [ | |
"n = 1\n", | |
"best = 0\n", | |
"while best<81:\n", | |
" c = time_until_all_seen(n)\n", | |
" if c>best:\n", | |
" print(n,c)\n", | |
" best = c\n", | |
" n += 1" | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.6.3" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment