{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "at_OswnbKEA2",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Peter Norvig
Jan 2016
revised 2018, 2020, 2021, 2023
\n",
"\n",
"# Number Expression Puzzles: Countdowns, Four 4s, Five 5s, ...\n",
"\n",
"In this notebook we solve a range of related puzzles that all involve making mathematical expressions by combining numbers and operations in various ways to make target numeric values. First some imports, and then we can look at the first problem."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"id": "M4UuEIKOKEA4"
},
"outputs": [],
"source": [
"from collections import Counter, defaultdict, namedtuple\n",
"from fractions import Fraction\n",
"from itertools import product, permutations, combinations_with_replacement\n",
"from math import sqrt, factorial, floor, ceil\n",
"from operator import add, sub, mul, neg, truediv as div\n",
"from typing import List, Tuple, Dict, Union, Sequence, Collection, Set, Optional\n",
"import functools\n",
"import re\n",
"\n",
"cache = functools.lru_cache(None)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "acj0YasvKEA5",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"# Countdown to 2016\n",
"\n",
"On January 1, 2016 this New Year's puzzle was [posed](http://www.theguardian.com/science/2016/jan/04/can-you-solve-it-complete-the-equation-10-9-8-7-6-5-4-3-2-1-2016), and subsequently [answered](http://www.theguardian.com/science/2016/jan/04/did-you-solve-it-complete-the-equation-10-9-8-7-6-5-4-3-2-1-2016), by [Alex Bellos](http://www.alexbellos.com/):\n",
"\n",
"*Fill in the blanks so that this equation makes arithmetical sense:*\n",
"\n",
"*10 ␣ 9 ␣ 8 ␣ 7 ␣ 6 ␣ 5 ␣ 4 ␣ 3 ␣ 2 ␣ 1 = 2016*\n",
"\n",
"*You are allowed to use *only* the four basic arithmetical operations: +, -, ×, ÷. But brackets (parentheses) can be used wherever needed. So, for example, the solution could begin as either:*\n",
"\n",
"*(10 + 9) × (8 ...*
\n",
"*10 + (9 × 8) ...*"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "Ief1-PqFKEA6",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"To solve this specific problem, I'll first solve the more general problem: \n",
"\n",
"- *Given any sequence of numbers, place operations and brackets to form a dict of `{value: expression}` for every value that can be made.*\n",
"\n",
"I'll define `expressions(numbers)` to return an **expression table**: a dict of `{value: expression}` for all expressions (strings) whose numeric value is a `value` that can be made using all the `numbers` in left-to-right order. For example:\n",
"\n",
" expressions((3, 2)) = {1: '(3-2)', 1.5: '(3/2)', 5: '(3+2)', 6: '(3*2)'}\n",
"\n",
"I'll use the idea of [**dynamic programming**](https://en.wikipedia.org/wiki/Dynamic_programming): break the problem down into simpler subparts, compute an answer for each subpart, and remember intermediate results (with `cache`) so we don't need to re-compute them later. How do we break the problem into parts? If there is only one number, then there is only one expression, the number itself. If there are multiple numbers, then consider all ways of splitting the numbers into two parts, finding all the expressions that can be made with each part, and combining pairs of expressions with any of the four operations (taking care not to divide by 0). Here is the definition:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"id": "dyr0KdidKEA6"
},
"outputs": [],
"source": [
"Numbers = Tuple[int] # A sequence of integers, like (10, 9, 8)\n",
"Exp = str # An expression is represented as a string, like '(10+(9-8))'\n",
"ExpTable = Dict[float, Exp] # A table is a dict, like {11: '(10+(9-8))', ...}\n",
" \n",
"@cache\n",
"def expressions(numbers: Numbers) -> ExpTable:\n",
" \"\"\"Return a {value: exp} table for expressions that can be made from `numbers` with +-*/.\"\"\"\n",
" if len(numbers) == 1: \n",
" return {numbers[0]: str(numbers[0])}\n",
" else: \n",
" table = {}\n",
" for (Lnums, Rnums) in splits(numbers):\n",
" for (L, R) in product(expressions(Lnums), expressions(Rnums)):\n",
" Lexp, Rexp = '(' + expressions(Lnums)[L], expressions(Rnums)[R] + ')'\n",
" if R != 0: \n",
" table[L / R] = Lexp + '/' + Rexp\n",
" table[L * R] = Lexp + '*' + Rexp\n",
" table[L - R] = Lexp + '-' + Rexp\n",
" table[L + R] = Lexp + '+' + Rexp\n",
" return table\n",
" \n",
"def splits(sequence) -> List[Tuple[Sequence, Sequence]]:\n",
" \"\"\"Split sequence into two non-empty parts, in all ways.\"\"\"\n",
" return [(sequence[:i], sequence[i:]) \n",
" for i in range(1, len(sequence))]"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "Ief1-PqFKEA6",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"If we call `expressions((3, 2, 1))`, then as we trace through the execution, at one particular point we get (among other things):\n",
"\n",
" len(numbers) == 3\n",
" Lnums = (3, 2)\n",
" Rnums = (1,)\n",
" L = 6\n",
" R = 1\n",
" Lexp = '((3*2)'\n",
" Rexp = '1)' \n",
" table[7] = '((3*2)+1)'\n",
"\n",
"Some tests to make sure we got this right:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"button": false,
"id": "8Ur6YFeGKEA7",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"assert expressions((1,)) == {1: '1'}\n",
"assert expressions((2,)) == {2: '2'}\n",
"assert expressions((3,)) == {3: '3'}\n",
"assert expressions((2, 1)) == {1: '(2-1)', 2: '(2*1)', 3: '(2+1)'}\n",
"assert expressions((3, 2)) == {1.5: '(3/2)', 6: '(3*2)', 1: '(3-2)', 5: '(3+2)'}\n",
"assert expressions((3, 2, 1)) == {0: '((3-2)-1)', 0.5: '((3/2)-1)', 1: '((3-2)*1)',\n",
" 1.5: '((3/2)*1)', 2: '((3-2)+1)', 2.5: '((3/2)+1)', 3: '(3*(2-1))',\n",
" 4: '((3+2)-1)', 5: '((3+2)*1)', 6: '((3+2)+1)', 7: '((3*2)+1)', 9: '(3*(2+1))'}\n",
"assert expressions((3, 2, 1))[7] == '((3*2)+1)'\n",
"\n",
"assert splits((3, 2, 1)) == [((3,), (2, 1)), ((3, 2), (1,))]\n",
"assert splits((5, 4, 3, 2, 1)) == [\n",
" ((5,), (4, 3, 2, 1)), \n",
" ((5, 4), (3, 2, 1)), \n",
" ((5, 4, 3), (2, 1)), \n",
" ((5, 4, 3, 2), (1,))]"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "awUDaaP4KEA7",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"That looks good. Let's solve the whole puzzle.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"button": false,
"id": "ORmQCY2sKEA8",
"new_sheet": false,
"outputId": "fd340dd3-57ca-4d9a-8cca-fbc203530c71",
"run_control": {
"read_only": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 21.9 s, sys: 667 ms, total: 22.6 s\n",
"Wall time: 22.7 s\n"
]
},
{
"data": {
"text/plain": [
"'(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)'"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c10 = (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) # A countdown from 10 to 1\n",
"\n",
"%time expressions(c10)[2016]"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "PmeB8wYnKEA8",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"We have an answer! And in just seconds, thanks to dynamic programming! Here are solutions for nearby years:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"id": "8FuBcRp1KEA8",
"outputId": "7b1e4c8b-4299-48c1-a023-2b5f1340de89"
},
"outputs": [
{
"data": {
"text/plain": [
"{2010: '((((((10+(((9*8)-7)*6))*5)+4)+3)+2)+1)',\n",
" 2011: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)-1)',\n",
" 2012: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)*1)',\n",
" 2013: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)+1)',\n",
" 2014: '(((((((10+((9*8)*7))-6)-5)*4)+3)-2)+1)',\n",
" 2015: '(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)*1)',\n",
" 2016: '(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)',\n",
" 2017: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)-1)',\n",
" 2018: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)*1)',\n",
" 2019: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)+1)',\n",
" 2020: '(((((10+((9+((8+7)*6))*5))*4)+3)-2)-1)',\n",
" 2021: '((((((((10-9)+(8*7))*6)-5)*4)*3)/2)-1)',\n",
" 2022: '((((((((10-9)+(8*7))*6)-5)*4)*3)/2)*1)',\n",
" 2023: '(((((10*(((9*8)*(7-6))-5))+4)*3)+2)-1)',\n",
" 2024: '(((((10*(((9*8)*(7-6))-5))+4)*3)+2)*1)',\n",
" 2025: '(((((10*(((9*8)*(7-6))-5))+4)*3)+2)+1)',\n",
" 2026: '((((10+((((9*8)*7)*(6-5))*4))+3)-2)-1)',\n",
" 2027: '((((10+((((9*8)*7)*(6-5))*4))+3)-2)*1)',\n",
" 2028: '((((10+((((9*8)*7)*(6-5))*4))+3)-2)+1)',\n",
" 2029: '(((((((10*9)+8)*7)*6)-((5*4)*3))/2)+1)'}"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"{y: expressions(c10)[y] for y in range(2010, 2030)}"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "Jnc1EI-jKEA9",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"# Counting Countdown Solutions\n",
"\n",
"Alex Bellos had another challenge: \n",
"\n",
"- *I was half hoping a computer scientist would let me know exactly how many distinct solutions there are with only the four basic operations.*\n",
"\n",
"As it stands, my program can't answer that question, because I only keep one expression for each value. \n",
"\n",
"Also, I'm not sure what it means to be a distinct solution. For example, are `((10+9)+8)` and `(10+(9+8))` different, or are they same, because they both are equivalent to `(10+9+8)`? I think the notion of \"distinct solution\" is just inherently ambiguous. My choice is that two expressions are distinct if they are not exactly the same character string. But I won't argue with anyone who prefers a different definition of \"distinct solution.\"\n",
"\n",
"So how can I count expressions? I can mimic `expressions`, but make a table of counts, rather than of expression strings. There is only 1 way to make a single number into an expression, and in general, combining two subexpressions into a larger expression using an operation can be done in a number of ways equal to the product of the ways each of the two subexpressions can be made:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"button": false,
"id": "vFwgTkX5KEA9",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"@cache\n",
"def expression_counts(numbers: Numbers) -> Counter:\n",
" \"Return a Counter of {value: count} for every value that can be made from numbers.\"\n",
" table = Counter()\n",
" if len(numbers) == 1: \n",
" table[numbers[0]] = 1\n",
" else: \n",
" for (Lnums, Rnums) in splits(numbers):\n",
" for L, R in product(expression_counts(Lnums), expression_counts(Rnums)):\n",
" count = expression_counts(Lnums)[L] * expression_counts(Rnums)[R]\n",
" if R != 0:\n",
" table[L / R] += count\n",
" table[L + R] += count\n",
" table[L - R] += count\n",
" table[L * R] += count\n",
" return table"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"id": "yQylOo2sKEA9"
},
"outputs": [],
"source": [
"assert expression_counts((3,)) == Counter({3: 1})\n",
"assert expression_counts((3, 2, 1))[1] == 5 # (3-2)*1, (3-2)/1, 3-(2*1), 3-(2/1), 3/(2+1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "Ebxd9uiqKEA-",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Looks good to me. Now let's see if we can answer Alex's question."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"button": false,
"id": "7ZxGAm3BKEA-",
"new_sheet": false,
"outputId": "9805792d-f64d-4301-8bbe-cac1b2379602",
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"30066"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expression_counts(c10)[2016]"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "wjZxXvo3KEA-",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"This claims there are 30,066 distinct expressions for 2016. Is that the answer Alex wanted?\n",
"\n",
"# The Trouble with Round-off Error\n",
"\n",
"**I think 30,066 is wrong.** The trouble is: round-off error.\n",
"\n",
"Let's find all the values in `expressions(c10)` that are very near to 2016, within ±0.0000000001:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"button": false,
"id": "YdcGqKnQKEA-",
"new_sheet": false,
"outputId": "afd74608-0f7f-491c-ebd9-d2ab3af4dcba",
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"{2016.0000000000002: '((((10*((9*(8+7))-(6/(5+4))))*3)/2)+1)',\n",
" 2016.0: '(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)',\n",
" 2015.9999999999995: '((((((10*9)*8)*7)*((6/5)-(4-3)))*2)*1)',\n",
" 2015.999999999997: '(((10*9)*8)/(7-(6-(((5/(4+3))/2)-1))))',\n",
" 2016.0000000000005: '(((((10*9)*8)*((((7*6)/5)-4)-3))*2)*1)',\n",
" 2016.0000000000018: '((((((10*9)*8)*7)*(((6/5)-4)+3))*2)*1)',\n",
" 2016.0000000000023: '(10*((9*8)/((7-(6-((5/(4+3))/2)))-1)))',\n",
" 2015.9999999999998: '((10*((9*(((8-(7/6))*5)-(4*3)))+2))+1)',\n",
" 2015.9999999999993: '(10*(((((9*8)*7)*6)/5)*(((4/3)-2)+1)))',\n",
" 2016.000000000002: '(((10*9)*8)/((7-(6-((5/(4+3))/2)))-1))',\n",
" 2015.999999999999: '((((10*9)*(8+7))-6)/(((5-(4/3))-2)-1))'}"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"{y: expressions(c10)[y]\n",
" for y in expressions(c10)\n",
" if abs(y - 2016) < 1e-10}"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "63M4_WGXKEA-",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"I suspect that all of these actually should be *exactly* equal to 2016. To determine if they are, I could re-do *all* the calculations using exact rational arithmetic, as provided by the `fractions.Fraction` class. From experience I know that would be at least an order of magnitude slower, so instead I'll just verify the small set of expressions in the output above. I'll define `exact(exp)` to return a string that, when passed to `eval`, will exactly calculate `exp` using rational arithmetic:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"id": "CyTarLLEKEA-",
"outputId": "da5d0ef3-f4d5-4be5-99ee-192fe0efad6e"
},
"outputs": [
{
"data": {
"text/plain": [
"'Fraction(1)/(Fraction(5)-Fraction(2))'"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def exact(exp) -> str: return re.sub(r\"([0-9]+)\", r\"Fraction(\\1)\", exp)\n",
"\n",
"exact('1/(5-2)')"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"id": "ij0zaBmYKEA-"
},
"outputs": [],
"source": [
"assert eval(exact('1/(5-2)')) == Fraction(1, 3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Irm6kO0NKEA-"
},
"source": [
"Now I can count up all the expressions in the `expression_counts(c10)` table that are near 2016, but with `exact` computation to check that the expressions evaluate to exactly 2016:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"id": "V29kQB9DKEA-",
"outputId": "71a1824a-763d-4a9c-8462-beb881773d08"
},
"outputs": [
{
"data": {
"text/plain": [
"44499"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sum(expression_counts(c10)[y] \n",
" for y, exp in expressions(c10).items()\n",
" if abs(y - 2016) < 1e-3 and eval(exact(exp)) == 2016)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "eYF0lV23KEA_",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"I can claim that the answer is **44,499**, but I don't have complete confidence in that claim. It was easy to verify that `'(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)'` is a correct solution for `expressions(c10)[2016]` by doing simple arithmetic. But there is no simple test to verify that 44,499 is correct; I would want code reviews and tests, and hopefully an independent implementation. And of course, if you have a different definition of \"distinct solution,\" you will get a different answer."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "SfUXmDX7KEA_"
},
"source": [
"# Four 4s\n",
"\n",
"Alex Bellos continued his column with a related puzzle:\n",
" \n",
"> The most famous “fill in the gaps in the equation” puzzle is known as [**four fours**](https://en.wikipedia.org/wiki/Four_fours), because every equation is of the form\n",
">\n",
"> 4 ␣ 4 ␣ 4 ␣ 4 = x\n",
">\n",
"> In the classic form of the puzzle you must find a solution for x = 0 to 9 using just addition, subtraction, multiplication and division (and brackets).\n",
"\n",
"This puzzle goes back to a [1914 publication](https://archive.org/details/mathematicalrecr00ball) by the famed mathematician/magician [W. W. Rouse Ball](https://en.wikipedia.org/wiki/W._W._Rouse_Ball). The solution is easy:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"id": "EtbIiPJtKEA_",
"outputId": "86fcbddb-4773-4132-e7f4-9dda388881c2"
},
"outputs": [
{
"data": {
"text/plain": [
"{0: '(((4-4)-4)+4)',\n",
" 1: '(((4/4)-4)+4)',\n",
" 2: '((4/(4+4))*4)',\n",
" 3: '(((4+4)+4)/4)',\n",
" 4: '(((4-4)*4)+4)',\n",
" 5: '(((4*4)+4)/4)',\n",
" 6: '(((4+4)/4)+4)',\n",
" 7: '((4-(4/4))+4)',\n",
" 8: '(((4+4)/4)*4)',\n",
" 9: '(((4/4)+4)+4)'}"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"{i: expressions((4, 4, 4, 4))[i] for i in range(10)}"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "nVixjOMmKEA_"
},
"source": [
"Note that I didn't do anything special to take advantage of the fact that in `(4, 4, 4, 4)` the digits are all the same. Happily, `@cache` does that for me automatically! If I split that into `(4, 4)` and `(4, 4)`, when it comes time to do the second half of the split, the result will already be in the cache, and so won't be recomputed."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Aq98pwf4KEA_"
},
"source": [
"# Additional Math Operations\n",
"\n",
"Bellos then writes:\n",
" \n",
"- *You can introduce **new mathematical operations** such as powers, square roots, concatenation and decimals, or the factorial symbol, `!`.*\n",
"\n",
"It seems there many variations of these ***mathematical expression*** puzzles, all with slightly different rules for what operations are allowed, what expression values are to be made, what digits the expressions are composed of, and whether those digits may be **concatenated**, **permuted**, or contain a **decimal point**. Some variants allow **unary operations** (e.g. `√9` or `3!`).\n",
"\n",
"Allowing additional operations introduces some issues; here's how I'll handle them:\n",
"\n",
"- **Imaginary numbers**: `√-1` (I won't allow imaginary numbers.)\n",
"- **Irrational numbers**: `√2` (I'll use floating point approximations.)\n",
"- **Round-off error**:`49*(1/49) == 0.9999999999999999` (I'll try to round off appropriately, but might make errors.)\n",
"- **Overflow**: `10.^(9.^8.)` raises `OverflowError` (I'll drop overflow results, but might miss good results.)\n",
"- **Huge integers**: `10^(9*(8+7))` uses more bytes of storage than all the molecules in the universe. (I'll avoid generating huge integers.)\n",
"- **Unlikely numbers**: `(.9^(8!))^(√7)` is a valid rational number, but unlikely to eventually lead to an integer. (I'll drop unlikely operations.)\n",
"- **Deeply nested unary operations**: `√√√√√√√√(4!!!!!!!!)` is legal; where do you end? (I'll limit nesting to 2 unary operations).\n",
"\n",
"\n",
"I will use a one-character code to describe each allowable operation. There are three kinds of operations: binary (two arguments), unary (one argument), and digit (operates on a string of digits). This table gives the one-character codes, operation names, and examples:\n",
"\n",
"\n",
"|Binary Operations|Unary Operations|Digit Operations|\n",
"|--------------|--------------|-------|\n",
"|`+` addition: 1 + 2 = 3 |`_` unary minus: -4 = -4|`.` decimal point: 1.23|\n",
"|`-` subtraction: 3 - 2 = 1 |`√` square root: √4 = 2|`,` concatenation of digits: 123|\n",
"|`*` multiplication: 2 * 3 = 6|`!` factorial: 4! = 24 |\n",
"|`/` division: 6 / 3 = 2 |`⌊` floor:⌊4.4⌋ = 4|\n",
"|`^` exponentiation: 2 ^ 3 = 8|`⌈` ceiling: ⌈4.4⌉ = 5|\n",
"\n",
"\n",
"I will define the data type `Operation` to hold a description of each operation: the code symbol; the arity (binary or unary); a Python function to call to do the calculation; a format string (for unary operations); and a predicate that says when the operation is applicable. The applicability test can avoid both errors and results that are unlikely to be helpful. For example:\n",
" - Division is applicable when the right side is not zero.\n",
" - Square root is only applicable to a small range of positive numbers that become integers when multiplied by 10!.\n",
" - Factorial is only applicable to integers 0 to 9 (bigger numbers are unlikely to be useful).\n",
"\n",
"For binary operations, the symbol is used to construct the expression string, but for unary ops the `fmt` field gives a format string; this allows us to have prefix and postfix unary operations. "
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"id": "YO8f1DE_KEA_"
},
"outputs": [],
"source": [
"Operation = namedtuple('Operation', 'symbol, func, fmt, applicable', defaults=[None, lambda *args: True])\n",
"\n",
"OPERATIONS = {\n",
" 2: {Operation('+', add),\n",
" Operation('-', sub),\n",
" Operation('*', mul),\n",
" Operation('/', div, None, lambda L, R: R != 0),\n",
" Operation('^', pow, None, lambda L, R: (-10 <= R <= 10) and (L > 0 or R == int(R)))},\n",
" 1: {Operation('√', sqrt, '√{}', lambda v: 0 < v <= 256 and (3628800. * v).is_integer()),\n",
" Operation('!', factorial, '{}!', lambda v: v in range(10)),\n",
" Operation('_', neg, '-{}'),\n",
" Operation('⌊', floor, '⌊{}⌋'),\n",
" Operation('⌈', ceil, '⌈{}⌉')}}"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "GbpkLTRLKEA_"
},
"source": [
"I'll define the function `operate` to compute an arithmetic operation, catch any errors, and try to correct round-off errors. The idea is that since my expressions start with integers, results that are very close to an integer probably are an integer. So I'll correct `(49*(1/49))` to be `1.0`. Of course, an expression like `(1+(10^-99))` is also very close to `1.0`, but is not equal to `1`. I'll try to avoid such expressions by silently dropping (returning `None` from `operate`) any intermediate value whose absolute value is outside the range of 10-10 to 1010 (except of course I will accept an exact 0)."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"id": "JvaPXzvYKEA_"
},
"outputs": [],
"source": [
"def operate(operation, *args) -> Optional[float]: \n",
" \"Return op(*args), trying to correct for roundoff error, or `None` if too big/small/erroneous.\"\n",
" if operation.applicable(*args):\n",
" try:\n",
" val = operation.func(*args)\n",
" except (ArithmeticError, ValueError):\n",
" return None\n",
" return (0.0 if val == 0 else\n",
" None if isinstance(val, complex) else\n",
" None if not (1e-10 < abs(val) < 1e10) else\n",
" round(val) if abs(val - round(val)) < 1e-12 else\n",
" val)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "8iIQXnyCKEA_"
},
"source": [
"# Refactoring `expressions`\n",
"\n",
"I'll take this opportunity to refactor `expressions` to use the new `OPERATIONS`. The new `expressions` takes four arguments:\n",
"- `numbers`: as before, an ordered tuple of component integers from which to make expressions.\n",
"- `ops`: a character string containing the allowable operation character codes. Default `OPS`, which is `'+-*/^_√!.,'`.\n",
"- `nesting`: the maximum nesting level of unary operations. Default `2`, so `'3!!'` is ok, but `'3!!!'` is not.\n",
"- `permute`: whether the `numbers` may be permuted. If true then `(2, 3)` can produce `'3^2'`.\n",
"\n",
"I introduce three subfunctions, corresponding to the three types of operations:\n",
"- `digit_expressions(digits, ops)`: returns a table of expressions made with all the digits, in the given order.\n",
" - If `','` is in `ops` allow concatenation of digits (e.g. `{44: '44'}`).\n",
" - If `'.'` is in ops allow decimals (e.g. `{4.4: '4.4', 0.44: '.44'}`. \n",
" - If `digits` is a single digit, always allow it (e.g. `{4: '4'}`).\n",
"- `add_binary_expressions(table, numbers, ops, nesting)`: use binary operations, like `{5: '(2+3)'}`.\n",
"- `add_unary_expressions(table, ops, nesting)`: use unary operations, like `√4` and `4!`. \n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"button": false,
"id": "valCpAKPKEA_",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"OPS = '+-*/^_√!.,' # Default set of operations; omits floor and ceiling.\n",
"\n",
"@cache\n",
"def expressions(numbers: Numbers, ops=OPS, nesting=2, permute=False) -> ExpTable:\n",
" \"Return {value: expr} for all expressions that can be made from numbers using ops.\"\n",
" table = {}\n",
" orderings = (permutations(numbers) if permute else [numbers]) # Handle permutations once at top level\n",
" for nums in orderings:\n",
" table.update(digit_expressions(nums, ops))\n",
" add_binary_expressions(table, nums, ops, nesting)\n",
" return add_unary_expressions(table, ops, nesting)\n",
"\n",
"@cache\n",
"def digit_expressions(digits: Numbers, ops: str) -> ExpTable:\n",
" \"\"\"Return {value: expr} for expressions made with all the digits, maybe with a decimal point.\"\"\"\n",
" D = cat(digits)\n",
" table = {}\n",
" if len(digits) == 1 or (',' in ops and not D.startswith('0')): \n",
" table[int(D)] = D\n",
" if '.' in ops: \n",
" for L, R in splits(D, 0):\n",
" if len(L) < 2 or not L.startswith('0'): # Disallow '00.7'; allow '0.07'\n",
" decimal = L + '.' + R\n",
" table[float(decimal)] = decimal\n",
" return table\n",
"\n",
"def cat(items) -> str: \"concatenate\"; return ''.join(map(str, items))\n",
"\n",
"def add_binary_expressions(table, numbers, ops, nesting) -> ExpTable:\n",
" \"Add binary expressions by splitting numbers and combining with an op.\"\n",
" binary_ops = operations(2, ops)\n",
" for (Lnums, Rnums) in splits(numbers):\n",
" Ltable = expressions(Lnums, ops, nesting, False)\n",
" Rtable = expressions(Rnums, ops, nesting, False)\n",
" for (L, R) in product(Ltable, Rtable):\n",
" Lexp, Rexp = '(' + Ltable[L], Rtable[R] + ')'\n",
" for op in binary_ops:\n",
" assign(table, operate(op, L, R), Lexp + op.symbol + Rexp)\n",
" return table\n",
" \n",
"def add_unary_expressions(table, ops: str, nesting: int) -> ExpTable:\n",
" \"Add unary expressions (e.g. -v, √v and v!) to table\"\n",
" unary_ops = operations(1, ops)\n",
" for _ in range(nesting):\n",
" for v in tuple(table):\n",
" for op in unary_ops:\n",
" assign(table, operate(op, v), op.fmt.format(table[v]))\n",
" return table\n",
"\n",
"def operations(arity: int, ops: str) -> List[Operation]:\n",
" \"\"\"All the operations in OPERATIONS with given arity whose code symbol is one of `ops`.\"\"\"\n",
" return [op for op in OPERATIONS[arity] if op.symbol in ops]\n",
"\n",
"def splits(sequence, start=1) -> List[Tuple[Sequence, Sequence]]:\n",
" \"\"\"Split sequence into two parts, in all ways.\n",
" If start=1, the two parts are non-empty. If start=0, allow empty left part.\"\"\"\n",
" return [(sequence[:i], sequence[i:]) \n",
" for i in range(start, len(sequence))]"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "hgPctP5mKEA_"
},
"source": [
"The function `assign` adds a `{val: exp}` entry to `table`, but if there is already an entry for `val`, it prefers the shorter entry."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"id": "AEynbSq9KEA_"
},
"outputs": [],
"source": [
"def assign(table: dict, val: Optional[float], exp: str): \n",
" \"Assign table[val] = exp, unless val is None or we already have a shorter exp.\"\n",
" if val is not None and (val not in table or len(exp) < len(table[val])): \n",
" table[val] = exp"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "G6lWcOR2KEA_"
},
"source": [
"That's a lot of new code; let's have some tests:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"id": "mJJ8AxFXKEA_"
},
"outputs": [],
"source": [
"assert digit_expressions((1, 2), ',.') == {12: '12', 0.12: '.12', 1.2: '1.2'}\n",
"assert digit_expressions((1, 2), ',') == {12: '12'}\n",
"assert digit_expressions((1, 2), '.') == {.12: '.12', 1.2: '1.2'}\n",
"assert digit_expressions((1, 2), '') == {} \n",
"assert digit_expressions((0, 1, 2), ',.') == {0.012: '.012', 0.12: '0.12'}\n",
"assert digit_expressions((0, 0, 7), ',.') == {0.007: '.007', 0.07: '0.07'}\n",
"assert digit_expressions((7, 0, 0), ',.') == {0.7: '.700', 7.0: '7.00', 70.0: '70.0', 700: '700'}\n",
"\n",
"assert add_unary_expressions({16: '16'}, '_', 2) == {16: '16', -16: '-16'}\n",
"assert add_unary_expressions({16: '16'}, OPS, 2) == {\n",
" 16: '16', -16: '-16', 4: '√16', -4: '-√16', 2: '√√16', 24: '√16!'}\n",
"\n",
"add_binary_expressions({1: '1', 2: '2'}, (1, 2), '+-*/', 2) == {\n",
" 1: '1', 2: '2', 3: '(1+2)', 0.5: '(1/2)', -1: '(1-2)'}\n",
"\n",
"assert expressions((3, 2), '+-*,') == {32.0: '32', 5: '(3+2)', 1: '(3-2)', 6: '(3*2)'}"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{1: '1', 2: '2', 0.5: '(1/2)', -1: '(1-2)', 3: '(1+2)'}"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"add_binary_expressions({1: '1', 2: '2'}, (1, 2), '+-*/', 2)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "FRTRNPuAKEBA",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"I'll define a function to print a table of consecutive integers (starting at 0) that can be made by a sequence of numbers:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"button": false,
"id": "ndmqhDXnKEBA",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"outputs": [],
"source": [
"def show(numbers: tuple, limit=None, ops=OPS, permute=False, nesting=2):\n",
" \"\"\"Print expressions for integers from 0 up to limit or the first unmakeable integer.\n",
" Break output into `cols` columns.\"\"\"\n",
" table = expressions(numbers, ops, nesting, permute)\n",
" print(f'Can make 0 to {unmakeable(table)-1} with {numbers}, ops=\"{ops}\", permute={permute}.'\n",
" f' [{len(table):,} table entries]\\n')\n",
" N = limit or unmakeable(table)\n",
" show_columns([f'{i:3}: {unbracket(table[i])}' for i in range(N)])\n",
"\n",
"def show_columns(items, linelength=116):\n",
" \"\"\"Print the items in as many columns that will fit within `linelength`.\"\"\"\n",
" width = max(map(len, items))\n",
" cols = linelength // width\n",
" rows = (len(items) - 1) // cols + 1\n",
" for row in range(rows):\n",
" print(*[str(item).ljust(width) for item in items[row::rows]])\n",
" \n",
"def unmakeable(table) -> int:\n",
" \"\"\"The integer i such that table makes every integer from 0 to i - 1, but not i.\"\"\"\n",
" for i in range(len(table) + 1):\n",
" if i not in table:\n",
" return i\n",
" \n",
"def unbracket(exp: str) -> str:\n",
" \"Strip outer parens from exp, if they are there\"\n",
" return (exp[1:-1] if exp.startswith('(') and exp.endswith(')') else exp)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "wozlX9EmKEBA",
"tags": []
},
"source": [
"# Four 4s with New Mathematical Operations"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"id": "N43Lq2hKKEBA",
"outputId": "51a24d77-2e45-453b-b329-0e9f24b4efed"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Can make 0 to 72 with (4, 4, 4, 4), ops=\"+-*/^_√!.,\", permute=False. [721,878 table entries]\n",
"\n",
" 0: 44-44 15: 4+(44/4) 30: (4+(4+4))/.4 45: 44+(4/4) 60: 44+(4*4) \n",
" 1: 44/44 16: .4*(44-4) 31: 4!+((4+4!)/4) 46: 4-(√4-44) 61: (4/4)+(4!/.4) \n",
" 2: (4+44)/4! 17: (4!+44)/4 32: 44-(4!/√4) 47: 4!+(4!-(4/4)) 62: (4*(4*4))-√4 \n",
" 3: √((44/4)-√4) 18: (44/√4)-4 33: 4+(4!+(√4/.4)) 48: 44+√(4*4) 63: ((4^4)-4)/4 \n",
" 4: 4!-(44-4!) 19: 4!-(4+(4/4)) 34: 44-(4/.4) 49: 44+(√4/.4) 64: 4!-(4-44) \n",
" 5: (44-4!)/4 20: (44-4)/√4 35: 4!+(44/4) 50: 4+(√4+44) 65: (4+(4^4))/4 \n",
" 6: √(44-(4+4)) 21: (4+4.4)/.4 36: 44-(4+4) 51: (.4-(4-4!))/.4 66: 4!-(√4-44) \n",
" 7: (44/4)-4 22: √4/(4/44) 37: 4!+((4!+√4)/√4) 52: 4+(4+44) 67: √4+((4!+√4)/.4)\n",
" 8: 4+(4.4-.4) 23: (√4+44)/√4 38: 44-(4+√4) 53: 4!+(4!+(√4/.4)) 68: 44+√(4*4)! \n",
" 9: (44/4)-√4 24: 4+(44-4!) 39: 44-(√4/.4) 54: 44+(4/.4) 69: 4+((4!+√4)/.4) \n",
" 10: 44/4.4 25: 4!+(4^(4-4)) 40: 44-√(4*4) 55: 44/(.4+.4) 70: 4!+(√4+44) \n",
" 11: 44/√(4*4) 26: 4+(44/√4) 41: (.4+(4*4))/.4 56: 44+(4!/√4) 71: (4!+4.4)/.4 \n",
" 12: (4+44)/4 27: 4+(4!-(4/4)) 42: √4-(4-44) 57: ((.4+4!)/.4)-4 72: 4+(4!+44) \n",
" 13: 4!-(44/4) 28: 44-(4*4) 43: 44-(4/4) 58: ((4^4)-4!)/4 \n",
" 14: 4.4+(.4*4!) 29: 4+(4!+(4/4)) 44: √44*√44 59: (4!/.4)-(4/4) \n"
]
}
],
"source": [
"show((4, 4, 4, 4))"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "QJM1oLz4KEBA",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"We can also solve the \"2016 with four fours\" puzzle:"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"button": false,
"id": "ZWCn9F1_KEBA",
"new_sheet": false,
"outputId": "445baaed-5cf4-428c-fb23-a64d3d5f3aec",
"run_control": {
"read_only": false
}
},
"outputs": [
{
"data": {
"text/plain": [
"'((4+4)!/(4!-4))'"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expressions((4, 4, 4, 4), OPS, 2)[2016]"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "uDSx_LGeKEBA",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"In a [separate video](https://www.youtube.com/embed/Noo4lN-vSvw), Alex Bellos shows how to form **every** integer from 0 to infinity using four 4s, if unlimited numbers of square root and `log` functions are allowed. The solution comes from Paul Dirac (although [Dirac originally developed it](https://nebusresearch.wordpress.com/2014/04/18/how-dirac-made-every-number/) for the \"four 2s\" problem).\n",
"\n",
"Donald Knuth [conjectured](https://www.tandfonline.com/doi/abs/10.1080/0025570X.1964.11975546) that with floor, square root and factorial, you can make any positive integer with just **one** 4. (We would need more efficient ways of dealing with very large numbers to make progress on Knuth's problem.)"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "uDSx_LGeKEBA",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"Below are some popular variant problems:\n",
"\n",
"# Four 2s"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"id": "e807aDInKEBA",
"outputId": "e672d88a-bc1d-456d-da6b-b720c878e939"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Can make 0 to 30 with (2, 2, 2, 2), ops=\"+-*/^_√!.,\", permute=False. [112,539 table entries]\n",
"\n",
" 0: 22-22 6: √((22/2)-2)! 12: (2+22)/2 18: 22-(2^2) 24: 2+(√22^2) 30: (2+(2^2))/.2 \n",
" 1: 22/22 7: 2+(2/(2*.2)) 13: 2+(22/2) 19: (2+(2-.2))/.2 25: (2-2.2)^-2 \n",
" 2: (2^2)!-22 8: 2+(2+(2^2)) 14: (2^(2^2))-2 20: 22-(√2^2) 26: 2+(2+22) \n",
" 3: √((22/2)-2) 9: (22/2)-2 15: (2+(2/2))/.2 21: 22-(2/2) 27: 22+(√.2^-2) \n",
" 4: .2*(22-2) 10: 22/2.2 16: 2*(2*(2^2)) 22: √22*√22 28: 2+(2+(2^2)!) \n",
" 5: 2+(2+(2/2)) 11: 22/(√2^2) 17: 22-(√.2^-2) 23: 22+(2/2) 29: 2+(2+(.2^-2))\n"
]
}
],
"source": [
"show((2, 2, 2, 2))"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "_AuWPOGXKEBA"
},
"source": [
"# Four 9s"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"id": "Ll4xl6TOKEBA",
"outputId": "850ea56d-da8b-4f1f-c684-ba75f1c60afb"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Can make 0 to 61 with (9, 9, 9, 9), ops=\"+-*/^_√!.,\", permute=False. [791,279 table entries]\n",
"\n",
" 0: 99-99 13: 9+(√9+(9/9)) 26: (9*√9)-(9/9) 39: √9!+(99/√9) 52: √9!*(9-(√9/9)) \n",
" 1: 99/99 14: √9+(99/9) 27: 9*√(9.9-.9) 40: (9-√9)!/(9+9) 53: (9*√9!)-(9/9) \n",
" 2: (99/9)-9 15: (99-9)/√9! 28: 9+(9+(9/.9)) 41: (.9+(√9!*√9!))/.9 54: 9*(9-(9/√9)) \n",
" 3: √√(99-(9+9)) 16: (99-√9)/√9! 29: 9+((9+9)/.9) 42: 9+(99/√9) 55: 99/(.9+.9) \n",
" 4: √9+(9^(9-9)) 17: √9!+(99/9) 30: (99-9)/√9 43: √9+(√9!/(.9/√9!)) 56: 9!/(9*(9-√9)!) \n",
" 5: (99/9)-√9! 18: 99-(9*9) 31: (99-√9!)/√9 44: (9*√9!)-(9/.9) 57: √9*(9+(9/.9)) \n",
" 6: √((9+99)/√9) 19: 9+(9+(9/9)) 32: (99-√9)/√9 45: 99-(9*√9!) 58: √9!*(9+(√9!/9)) \n",
" 7: 9-((9+9)/9) 20: 9+(99/9) 33: √9/(9/99) 46: (9/.9)+(√9!*√9!) 59: ((9*√9!)-.9)/.9 \n",
" 8: (99/9)-√9 21: (9+9.9)/.9 34: (√9+99)/√9 47: √9*(9+(√9!/.9)) 60: 9/(.9/(9-√9)) \n",
" 9: √(99-(9+9)) 22: 9+(√9+(9/.9)) 35: (√9!+99)/√9 48: √9!*(9-(9/9)) 61: (.9+(9*√9!))/.9 \n",
" 10: 99/9.9 23: √9+((9+9)/.9) 36: (9+99)/√9 49: 9+(√9!/(.9/√9!)) \n",
" 11: 99/√(9*9) 24: (99/√9)-9 37: (9/.9)+(9*√9) 50: ((9*√9!)-9)/.9 \n",
" 12: (9+99)/9 25: 9+(√9!+(9/.9)) 38: √9!*(√9+(√9/.9)) 51: 9*(9-(√9/.9)) \n"
]
}
],
"source": [
"show((9, 9, 9, 9))"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "PfcnRnoAKEBA"
},
"source": [
"# Four 5s"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"button": false,
"id": "Mmed82RmKEBA",
"new_sheet": false,
"outputId": "cbc51a80-8fff-43cd-fa56-390c201f3d4e",
"run_control": {
"read_only": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Can make 0 to 38 with (5, 5, 5, 5), ops=\"+-*/^_√!.,\", permute=False. [345,331 table entries]\n",
"\n",
" 0: 55-55 7: 5+((5+5)/5) 14: (5!/5)-(5+5) 21: (5+5.5)/.5 28: .5+(5*5.5) 35: (5!+55)/5 \n",
" 1: 55/55 8: 5.5+(5*.5) 15: (5*5)-(5+5) 22: 55/(5*.5) 29: 5+(5-(5/5))! 36: (.5*5!)-(5!/5)\n",
" 2: 5!/(5+55) 9: 5+(5-(5/5)) 16: 5+(55/5) 23: 55-(.5^-5) 30: 55-(5*5) 37: 5+(.5^-√(5*5))\n",
" 3: 5.5-(5*.5) 10: 55/5.5 17: 5+(5!/(5+5)) 24: √(5+(55/5))! 31: 55-(5!/5) 38: ((5!/5)-5)/.5 \n",
" 4: √(5+(55/5)) 11: 5.5+5.5 18: ((5!-5)/5)-5 25: .5*(55-5) 32: (5.5-5)^-5 \n",
" 5: (.5*5!)-55 12: (5+55)/5 19: (5!-(5*5))/5 26: (5/5)+(5*5) 33: .5*(5!*.55) \n",
" 6: (55/5)-5 13: (5!-55)/5 20: 5*(5-(5/5)) 27: (5*5.5)-.5 34: 5+(5+(5!/5)) \n"
]
}
],
"source": [
"show((5, 5, 5, 5))"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"id": "-5Qpw6s3KEBA",
"new_sheet": false,
"run_control": {
"read_only": false
}
},
"source": [
"\n",
"# Countdown to New Year's\n",
"\n",
"Now another type of New Year's countdown puzzle. On December 31 2017, [Michael Littman](http://cs.brown.edu/~mlittman/) posted this:\n",
"\n",
"> 2+0+1×8, 2+0-1+8, (2+0-1)×8, |2-0-1-8|, -2-0+1×8, -(2+0+1-8), √|2+0-18|, 2+0+1^8, 20-18, 2^(0×18), 2×0×1×8... Happy New Year!\n",
"\n",
"Can we replicate that countdown? For 2018 and for following years?"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10: 2-(0-(1*8)) 20-(1+9) 20/(2-0) 20/(2/1) 20/√(2+2) √(20*(2+3)) 20*(2/4) \n",
" 9: 2+(0-(1-8)) (2*0)+(1*9) (20/2)-0! (20/2)-1 (20-2)/2 2+(0!+(2*3)) (20-2)/√4 \n",
" 8: (2*0)+(1*8) (2*0)-(1-9) 2-(0-(2+0!)!) 2-(0-(2+1)!) (20/2)-2 20-(2*3!) (20/2)-√4 \n",
" 7: (2*0)-(1-8) (20+1)/√9 (2*(0!+2))+0! (2*(0!+2))+1 2+(0!+(2+2)) (20/2)-3 2+√(0!+24) \n",
" 6: √(2*(0+18)) (2+(0/19)!)! (2+(0/20)!)! (2+(0/21)!)! √((20-2)*2) (-20+23)! (20/2)-4 \n",
" 5: 2-(0-√(1+8)) 20/(1+√9) 2-(0-(2+0!)) 2-(0-(2+1)) 20/(2+2) √(2-(0-23)) 20/(2+√4) \n",
" 4: √(-2-(0-18)) √(20-(1+√9)) 2-(0-(2-0)) 2-(0-(2/1)) √(20-(2+2)) 20/(2+3) -20+24 \n",
" 3: 2+(0/18)! 2+(0/19)! 2+(0/20)! 2+(0/21)! 2+(0/22)! -20+23 2+(0/24)! \n",
" 2: 20-18 2-(0/19) 2-(0/20) 2-(0/21) -20+22 2-(0/23) √(-20+24) \n",
" 1: 2-(0/18)! 20-19 20/20 -20+21 2-(0/22)! 2-(0/23)! 2-(0/24)! \n",
" 0: 2*(0/18) 2*(0/19) 20-20 2*(0/21) 2*(0/22) 2*(0/23) 2*(0/24) \n"
]
}
],
"source": [
"def countdowns(years: Sequence[int]):\n",
" \"\"\"Print a countdown of expressions with values from 10 to 0, using the digits (in order) of each year.\"\"\"\n",
" def countdown(i, year): return f\"{unbracket(expressions(digits(year), ops='+-*/_√!,')[i]):16}\"\n",
" for i in reversed(range(11)):\n",
" print(f'{i:2d}:', *[countdown(i, year) for year in years])\n",
" \n",
"def digits(n: int) -> Numbers: return tuple(int(d) for d in str(n))\n",
" \n",
"countdowns(range(2018, 2025))"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "PPs4y4mxKEBB"
},
"source": [
"# Can you make 24?\n",
"\n",
"In the [538 Riddler for July 10th 2020](https://fivethirtyeight.com/features/can-you-make-24/), Zach Wissner-Gross asks \"Can you make 24? from the digits (2, 3, 3, 4), in any order, with just the five binary operations.\" 24 is an interesting number: it is abundant, superabundant, semiperfect, and is the number of blackbirds baked in a pie.\n",
"\n",
"Solving Zach's puzzle is easy enough:"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'(((3^2)-3)*4)'"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"expressions((2, 3, 3, 4), '+-*/^', permute=True)[24]"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "PPs4y4mxKEBB"
},
"source": [
"For extra credit, Zach asks for **multiple ways** to make 24. \n",
"\n",
"We haven't dealt with reporting multiple ways to make a number; the `ExpTable` only keeps one. I'll try collecting one expression from each permutation of the numbers. If there are multiple ways from a single permutation we won't keep more than one of those, so this approach won't give you every way, but it should be good enough to answer Zach's question."
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"id": "dLZMMnH-KEBB",
"outputId": "9e964cef-f10d-49fd-faf6-bc171de07344"
},
"outputs": [
{
"data": {
"text/plain": [
"{'(((3^2)-3)*4)',\n",
" '(((4/2)^3)*3)',\n",
" '(3*((4/2)^3))',\n",
" '(3*(4^(3/2)))',\n",
" '(3/((2/4)^3))',\n",
" '(4*((3^2)-3))'}"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def can_make(total: int, numbers: tuple, ops='+-*/^') -> Set[Exp]:\n",
" \"\"\"Can we make the total from the numbers (in any order)? Return a set of expressions.\"\"\"\n",
" return {expressions(nums, ops).get(total)\n",
" for nums in permutations(numbers)} - {None}\n",
"\n",
"can_make(24, (2, 3, 3, 4))"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "sNnNDjCvKEBB"
},
"source": [
"Readers suggested other interesting tuples of numbers:"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"id": "snhb7k8OKEBB",
"outputId": "44f3cf49-aa56-4900-f510-3eedb4970307"
},
"outputs": [
{
"data": {
"text/plain": [
"{'(((2*8)-8)*3)',\n",
" '((2^(8-3))-8)',\n",
" '((2^3)+(8+8))',\n",
" '((8-(3+2))*8)',\n",
" '((8^2)/(8/3))',\n",
" '(3*((8^2)/8))',\n",
" '(3/(2/(8+8)))',\n",
" '(3/(8/(8^2)))',\n",
" '(8*(8-(3+2)))',\n",
" '(8+((2^3)+8))',\n",
" '(8+(8+(2^3)))'}"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"can_make(24, (2, 3, 8, 8))"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"id": "gia8RdaUKEBB",
"outputId": "46852452-3ebd-4718-ad7a-52d4fc6de9bf"
},
"outputs": [
{
"data": {
"text/plain": [
"{'(((10-3)*2)+10)',\n",
" '((2*(10-3))+10)',\n",
" '((2^10)-(10^3))',\n",
" '(10+((10-3)*2))',\n",
" '(10+(2*(10-3)))',\n",
" '(10-((3-10)*2))',\n",
" '(10-(2*(3-10)))'}"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"can_make(24, (2, 3, 10, 10))"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"id": "VhhMQ33sKEBB",
"outputId": "66fe6857-f940-409b-aa2a-04fdb00e064e"
},
"outputs": [
{
"data": {
"text/plain": [
"{'(8/(3-(8/3)))'}"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"can_make(24, (3, 3, 8, 8))"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"id": "nbcNqMdFKEBB",
"outputId": "e3d17354-e297-4ded-9193-5fe615902072"
},
"outputs": [
{
"data": {
"text/plain": [
"{'(((3*6)-6)*2)',\n",
" '(((3+2)*6)-6)',\n",
" '(((3+6)*2)+6)',\n",
" '(2*(6*(6/3)))',\n",
" '(2*(6/(3/6)))',\n",
" '(2/(3/(6*6)))',\n",
" '(6*(2/(3/6)))',\n",
" '(6*(2^(6/3)))',\n",
" '(6*(6*(2/3)))',\n",
" '(6*(6/(3/2)))',\n",
" '(6/(3/(2*6)))',\n",
" '(6/(3/(6*2)))'}"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"can_make(24, (2, 3, 6, 6))"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"id": "L8SAsmSrKEBB",
"outputId": "33874782-4dcd-460e-dfaf-140fe71bf502"
},
"outputs": [
{
"data": {
"text/plain": [
"{'((5^2)-(0^0))'}"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"can_make(24, (0, 0, 2, 5))"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "77JudWtrKEBB"
},
"source": [
"This relies on 00 = 1, which Python agrees with, but some mathematicians treat as [undefined](https://en.wikipedia.org/wiki/Zero_to_the_power_of_zero).\n",
"\n",
"**Nicolas Schank** asked for the following in the Facebook \"omg math\" group:"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"id": "VDlW5eWVKEBB",
"outputId": "d2d3e78c-485f-407a-8888-579ba423f1d2"
},
"outputs": [
{
"data": {
"text/plain": [
"{'(10-(6/(13-11))!)!'}"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"can_make(24, (13, 11, 10, 6), '+-*/^!')"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"id": "5GYEEXhnKEBB",
"outputId": "bdee3db6-f560-4b4f-ba2a-036b4d8ee1b3"
},
"outputs": [
{
"data": {
"text/plain": [
"{'(8/((1^9)+1))!', '(8/(1+(1^9)))!'}"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"can_make(24, (9, 8, 1, 1), '+-*/^!')"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"id": "pqZLLXXCKEBB",
"outputId": "97da7ef1-2033-45d0-f636-1ea7bc14d126"
},
"outputs": [
{
"data": {
"text/plain": [
"{'(9!/(7!+(7!+7!)))'}"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"can_make(24, (9, 7, 7, 7), '+-*/^!')"
]
},
{
"cell_type": "markdown",
"metadata": {
"jp-MarkdownHeadingCollapsed": true,
"tags": []
},
"source": [
"**Aarati Marino** writes \"the kids and I just devised a cool game to play in the car this morning. Just take the last 4 digits of the license plate in front of you, and use addition, subtraction, multiplication, and division to make 24.\" \n",
"\n",
"We can find all the license plates for which there is a solution:"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"466 out of 715 distinct license plates can be solved:\n",
"\n",
"0038: 0-(0-(3*8)) 1149: (1-4)*(1-9) 1458: (1+5)*(8-4) 2348: (2-(3-4))*8 3355: (5*5)-(3/3) 4477: (4-(4/7))*7 \n",
"0046: 0-(0-(4*6)) 1155: 1*((5*5)-1) 1459: ((4-1)*5)+9 2349: 2/(3/(4*9)) 3356: 3+((3*5)+6) 4478: 4+((4*7)-8) \n",
"0128: 0+((1+2)*8) 1156: 1*((5-1)*6) 1466: ((1+4)*6)-6 2355: 2-(3-(5*5)) 3357: 3*((3*5)-7) 4479: 4*(4-(7-9)) \n",
"0136: 0+((1+3)*6) 1157: (1+1)*(5+7) 1467: (1-(4-7))*6 2356: (2-(3-5))*6 3359: (3+3)*(9-5) 4488: 4+(4+(8+8)) \n",
"0137: 0+((1+7)*3) 1158: (5-(1+1))*8 1468: (1-(4-6))*8 2357: 2+((3*5)+7) 3366: 3*((6/3)+6) 4489: (4*9)-(4+8) \n",
"0138: 0+(1*(3*8)) 1166: (1+1)*(6+6) 1469: 6*(9-(1+4)) 2358: (2*(3+5))+8 3367: 3-((3-6)*7) 4555: 4*(5+(5/5)) \n",
"0139: 0-((1-9)*3) 1168: 6/((1+1)/8) 1477: (1+7)*(7-4) 2359: 2*(3*(9-5)) 3368: ((3*3)-6)*8 4556: 4*(5/(5/6)) \n",
"0145: 0+((1+5)*4) 1169: ((1+1)*9)+6 1478: 1*((7-4)*8) 2366: 2/(3/(6*6)) 3369: (3*3)+(6+9) 4557: 4*(7-(5/5)) \n",
"0146: 0+(1*(4*6)) 1188: ((1+1)*8)+8 1479: (1-9)*(4-7) 2367: ((2*7)-6)*3 3377: (3+(3/7))*7 4558: (4-(5/5))*8 \n",
"0147: 0-((1-7)*4) 1224: (1+2)*(2*4) 1488: 1*((4*8)-8) 2368: ((2+8)*3)-6 3378: (3*3)+(7+8) 4559: 4-(5*(5-9)) \n",
"0148: 0-((1-4)*8) 1225: (1+5)*(2+2) 1489: 1+((4*8)-9) 2369: 2*(6-(3-9)) 3379: 3+(7/(3/9)) 4566: 4*(5+(6/6)) \n",
"0155: 0-(1-(5*5)) 1226: 1*(2*(2*6)) 1555: (5-(1/5))*5 2377: (2*7)+(3+7) 3388: 8/(3-(8/3)) 4567: 4*(5-(6-7)) \n",
"0156: 0-((1-5)*6) 1227: 2*(2*(7-1)) 1556: ((1+5)*5)-6 2378: 2*(7-(3-8)) 3389: (3*(3+8))-9 4568: (4+(5-6))*8 \n",
"0226: 0+(2*(2*6)) 1228: (2-(1-2))*8 1559: (1+5)*(9-5) 2379: 2*((3*7)-9) 3399: 3+(3+(9+9)) 4569: 4+(5+(6+9)) \n",
"0234: 0+(2*(3*4)) 1229: (1+(2+9))*2 1566: 1*((5*6)-6) 2388: ((2*8)-8)*3 3444: ((3+4)*4)-4 4577: 4*(5+(7/7)) \n",
"0236: 0+((2+6)*3) 1233: (1+3)*(2*3) 1567: 1+((5*6)-7) 2389: 8/(2/(9-3)) 3445: 3+((4*4)+5) 4578: 4*(5-(7-8)) \n",
"0238: (0/2)+(3*8) 1234: 1*(2*(3*4)) 1568: (1-(5-8))*6 2399: (2*3)+(9+9) 3446: (3+(4/4))*6 4579: (4*7)+(5-9) \n",
"0239: 0+(2*(3+9)) 1235: (1+2)*(3+5) 1569: 1*(6*(9-5)) 2444: 2*(4+(4+4)) 3447: 3*((4/4)+7) 4588: 4*(5+(8/8)) \n",
"0244: 0+((2+4)*4) 1236: 1*((2+6)*3) 1578: (1-(5-7))*8 2445: ((2+5)*4)-4 3448: 3*(4/(4/8)) 4589: 4*(5-(8-9)) \n",
"0246: (0/2)+(4*6) 1237: 1+(2+(3*7)) 1579: (1-7)*(5-9) 2446: 2+((4*4)+6) 3449: 3*(9-(4/4)) 4599: 4*(5+(9/9)) \n",
"0248: 0+(2*(4+8)) 1238: (1+3)*(8-2) 1588: 1*((8-5)*8) 2447: 2*(4*(7-4)) 3455: 3-(4-(5*5)) 4666: 4*(6/(6/6)) \n",
"0257: 0+(2*(5+7)) 1239: 1*(2*(3+9)) 1589: (1-9)*(5-8) 2448: (2+(4/4))*8 3456: (3-(4-5))*6 4667: 4*(6/(7-6)) \n",
"0258: 0-((2-5)*8) 1244: 1*((2+4)*4) 1599: 1+(5+(9+9)) 2449: (4*(9-2))-4 3457: (3*4)+(5+7) 4668: 4+(6+(6+8)) \n",
"0266: 0+(2*(6+6)) 1245: (2-(1-5))*4 1666: ((6-1)*6)-6 2455: (2*(5+5))+4 3458: 3/((5-4)/8) 4669: (4*9)-(6+6) \n",
"0268: 0+(6/(2/8)) 1246: (2-1)*(4*6) 1668: 6/(1-(6/8)) 2456: (2*(4+5))+6 3459: 3*(4-(5-9)) 4677: 4*(6/(7/7)) \n",
"0269: 0+((2*9)+6) 1247: (1-(2-7))*4 1669: (1-(6-9))*6 2457: 4/(2/(5+7)) 3466: (3*4)+(6+6) 4678: (4+(6-7))*8 \n",
"0288: 0+((2*8)+8) 1248: 1*(2*(4+8)) 1679: (1+7)*(9-6) 2458: 2*((4*5)-8) 3468: 3*(4*(8-6)) 4679: 6/(4/(7+9)) \n",
"0334: 0+((3+3)*4) 1249: ((1+9)*2)+4 1688: (1-(6-8))*8 2459: (2+4)*(9-5) 3469: (3-(6-9))*4 4688: 4*(6/(8/8)) \n",
"0335: 0+(3*(3+5)) 1255: 1-(2-(5*5)) 1689: 1+(6+(8+9)) 2466: (2-(4-6))*6 3477: 3-((4-7)*7) 4689: 4*(6/(9-8)) \n",
"0337: 0+(3+(3*7)) 1256: (1-(2-5))*6 1699: 1*(6+(9+9)) 2467: 2+((4*7)-6) 3478: (4*(7-3))+8 4699: 4*(6/(9/9)) \n",
"0338: (0/3)+(3*8) 1257: 1*(2*(5+7)) 1779: 1+(7+(7+9)) 2468: 2/(4/(6*8)) 3479: (3*(4+7))-9 4777: 4*(7-(7/7)) \n",
"0339: 0-(3-(3*9)) 1258: 1*((5-2)*8) 1788: 1+(7+(8+8)) 2469: (2+(4/6))*9 3489: 3+(4+(8+9)) 4778: 4*(7+(7-8)) \n",
"0344: 0+(3*(4+4)) 1259: ((1+2)*5)+9 1789: 1*(7+(8+9)) 2477: (2*(7+7))-4 3499: (3*(9-4))+9 4788: 4*(7-(8/8)) \n",
"0346: (0/3)+(4*6) 1266: 1*(2*(6+6)) 1799: 7-(1-(9+9)) 2478: ((2*7)-8)*4 3556: (3+(5/5))*6 4789: 4*(7+(8-9)) \n",
"0348: (0/4)+(3*8) 1267: (1-7)*(2-6) 1888: 1*(8+(8+8)) 2479: (2*4)+(7+9) 3557: 3*((5/5)+7) 4799: 4*(7-(9/9)) \n",
"0349: 0-((3-9)*4) 1268: 1/(2/(6*8)) 1889: 8-(1-(8+9)) 2488: (2*4)+(8+8) 3558: 3*(5/(5/8)) 4888: (4-(8/8))*8 \n",
"0358: (0/5)+(3*8) 1269: 1*((2*9)+6) 2223: 2*(2*(2*3)) 2489: 8*(9-(2+4)) 3559: 3*(9-(5/5)) 4889: (4+(8-9))*8 \n",
"0359: 0+((3*5)+9) 1277: ((7*7)-1)/2 2224: 2*(2*(2+4)) 2499: 2+(4+(9+9)) 3566: (3-(5-6))*6 4899: (4-(9/9))*8 \n",
"0366: 0+((3*6)+6) 1278: 1+((2*8)+7) 2225: 2*(2+(2*5)) 2557: (2*7)+(5+5) 3567: 3*(6-(5-7)) 5555: (5*5)-(5/5) \n",
"0367: 0-((3-7)*6) 1279: 1+((2*7)+9) 2227: 2*((2*7)-2) 2558: (2+(5/5))*8 3568: 3/((6-5)/8) 5556: 5+((5*5)-6) \n",
"0368: 0-((3-6)*8) 1288: 1*((2*8)+8) 2228: 2*(2+(2+8)) 2559: (2*5)+(5+9) 3569: 3*(5-(6-9)) 5559: 5+(5+(5+9)) \n",
"0378: (0/7)+(3*8) 1289: (2*8)-(1-9) 2229: 2+(2*(2+9)) 2566: ((2*5)-6)*6 3578: 3-((5-8)*7) 5566: (5*5)-(6/6) \n",
"0388: (0/8)+(3*8) 1333: (1+3)*(3+3) 2233: 2*(2*(3+3)) 2567: (2-(5-7))*6 3579: 3+(5+(7+9)) 5567: (5*5)+(6-7) \n",
"0389: 0+(8/(3/9)) 1334: 1*((3+3)*4) 2234: (2+(2+4))*3 2568: 2+((5*6)-8) 3588: 3+(5+(8+8)) 5568: 5+(5+(6+8)) \n",
"0445: 0+(4+(4*5)) 1335: 1*(3*(3+5)) 2235: ((2*5)-2)*3 2569: (5/(2/6))+9 3589: (3*9)+(5-8) 5577: 5+(5+(7+7)) \n",
"0446: (0/4)+(4*6) 1336: ((1+6)*3)+3 2236: 2*((2*3)+6) 2577: (2*5)+(7+7) 3599: (3-9)*(5-9) 5578: (5*5)+(7-8) \n",
"0447: 0-(4-(4*7)) 1337: 1*(3+(3*7)) 2237: 2*(2+(3+7)) 2578: ((2*5)-7)*8 3666: (3+(6/6))*6 5588: (5*5)-(8/8) \n",
"0448: 0+((4*4)+8) 1338: ((1+8)*3)-3 2238: 2+(2*(3+8)) 2579: (5*7)-(2+9) 3667: 3*((6/6)+7) 5589: (5*5)+(8-9) \n",
"0456: (0/5)+(4*6) 1339: 1*((3*9)-3) 2239: (2+(2/3))*9 2588: (5*8)-(2*8) 3668: 3*(6/(6/8)) 5599: (5*5)-(9/9) \n",
"0466: (0/6)+(4*6) 1344: 1*(3*(4+4)) 2244: 2*((2*4)+4) 2589: 2+(5+(8+9)) 3669: 3+(6+(6+9)) 5666: (5-(6/6))*6 \n",
"0467: (0/7)+(4*6) 1345: 1+(3+(4*5)) 2245: 2+(2+(4*5)) 2666: (2*6)+(6+6) 3677: 3*(7-(6-7)) 5667: 5+(6+(6+7)) \n",
"0468: 0-((4-8)*6) 1346: 6/(1-(3/4)) 2246: 2*(2+(4+6)) 2667: (6+(6*7))/2 3678: 3+(6+(7+8)) 5668: 6-((5-8)*6) \n",
"0469: (0/9)+(4*6) 1347: ((1+3)*7)-4 2247: 2+(2*(4+7)) 2668: (2+(6/6))*8 3679: 3*(6-(7-9)) 5669: (6*9)-(5*6) \n",
"0478: 0-((4-7)*8) 1348: ((1+3)*4)+8 2248: (2*(2*4))+8 2669: (2+6)*(9-6) 3688: (3+(8/8))*6 5677: (5-(7/7))*6 \n",
"0488: 0+((4*8)-8) 1349: 1+((3*9)-4) 2249: 2+((2*9)+4) 2678: (2-(6-7))*8 3689: (3-(8-9))*6 5678: (5+7)*(8-6) \n",
"0566: 0+((5*6)-6) 1356: 1+((3*6)+5) 2255: 2*(2+(5+5)) 2679: 2+(6+(7+9)) 3699: (3*9)+(6-9) 5679: 6-((5-7)*9) \n",
"0569: 0-((5-9)*6) 1357: (1+5)*(7-3) 2256: 2+(2*(5+6)) 2688: 2+(6+(8+8)) 3777: 3*(7+(7/7)) 5688: (5+(6-8))*8 \n",
"0588: 0-((5-8)*8) 1358: 1+((3*5)+8) 2257: (2*5)+(2*7) 2689: 2/(6/(8*9)) 3778: 3*(7/(7/8)) 5689: (5+(8-9))*6 \n",
"0689: 0-((6-9)*8) 1359: 1*((3*5)+9) 2258: (2*(5+8))-2 2699: (2+(6/9))*9 3779: 3*(9-(7/7)) 5699: (5*(9-6))+9 \n",
"0699: 0+(6+(9+9)) 1366: 1*((3*6)+6) 2259: 2*(5-(2-9)) 2778: 2+(7+(7+8)) 3788: 3*(7+(8/8)) 5779: (5+7)*(9-7) \n",
"0789: 0+(7+(8+9)) 1367: 1*(6*(7-3)) 2266: (2+6)/(2/6) 2788: (2-(7-8))*8 3789: 3*(7-(8-9)) 5788: ((7-5)*8)+8 \n",
"0888: 0+(8+(8+8)) 1368: 1*((6-3)*8) 2267: (2*(2+7))+6 2789: (2*(7+9))-8 3799: 3*(7+(9/9)) 5789: (5+(7-9))*8 \n",
"1118: (1+(1+1))*8 1369: (1-9)*(3-6) 2268: (2*(2+6))+8 2888: (2+(8/8))*8 3888: 3*(8/(8/8)) 5888: (5*8)-(8+8) \n",
"1126: (1+1)*(2*6) 1377: (1-7)*(3-7) 2269: 2*((2*9)-6) 2889: (2-(8-9))*8 3889: 3*(8/(9-8)) 5889: 8/((8-5)/9) \n",
"1127: (1+2)*(1+7) 1378: 3/(1-(7/8)) 2277: 2*(7-(2-7)) 2899: (2+(9/9))*8 3899: 3*(8/(9/9)) 6666: 6+(6+(6+6)) \n",
"1128: 1*((1+2)*8) 1379: (1+7)/(3/9) 2278: 2+((2*7)+8) 3333: (3*(3*3))-3 3999: 3*(9-(9/9)) 6668: 6*(6+(6-8)) \n",
"1129: (1+2)*(9-1) 1388: ((1+3)*8)-8 2288: (2*(2*8))-8 3334: 3+(3*(3+4)) 4444: 4+(4+(4*4)) 6669: 6*(6*(6/9)) \n",
"1134: (1+1)*(3*4) 1389: 1/(3/(8*9)) 2289: (2*9)-(2-8) 3335: (3*3)+(3*5) 4445: 4*((4/4)+5) 6679: 6*(6+(7-9)) \n",
"1135: (1+3)*(1+5) 1399: (9-1)/(3/9) 2333: 2*(3+(3*3)) 3336: 3+(3+(3*6)) 4446: 4*(4/(4/6)) 6688: 6/((8-6)/8) \n",
"1136: 1*((1+3)*6) 1444: ((1+4)*4)+4 2335: 2*((3*5)-3) 3337: 3*((3/3)+7) 4447: (4+4)*(7-4) 6689: 6-((6-8)*9) \n",
"1137: 1*((1+7)*3) 1445: 1*(4+(4*5)) 2336: 2*(3+(3+6)) 3338: 3*(3/(3/8)) 4448: (4-(4/4))*8 6789: 6*(8/(9-7)) \n",
"1138: 1/(1/(3*8)) 1446: ((1+6)*4)-4 2337: 2*(3*(7-3)) 3339: 3*(9-(3/3)) 4449: 4-(4*(4-9)) 6799: 6-((7-9)*9) \n",
"1139: (1+1)*(3+9) 1447: 1+((4*4)+7) 2338: (2+(3/3))*8 3344: 3*((3*4)-4) 4455: (4+(4/5))*5 6888: 8-((6-8)*8) \n",
"1144: (1+(1+4))*4 1448: 1*((4*4)+8) 2339: ((2+3)*3)+9 3345: ((3/3)+5)*4 4456: 4/((5-4)/6) 6889: (8+8)/(6/9) \n",
"1145: 1*((1+5)*4) 1449: (1-(4-9))*4 2344: ((2+3)*4)+4 3346: 3/(3/(4*6)) 4457: 4*(4-(5-7)) 6899: 8/(6/(9+9)) \n",
"1146: 1/(1/(4*6)) 1455: 4-((1-5)*5) 2345: 2*(3+(4+5)) 3347: 3*(4-(3-7)) 4458: (4+(4-5))*8 7889: 8-((7-9)*8) \n",
"1147: 1*(4*(7-1)) 1456: 4/(1-(5/6)) 2346: 2+((3*6)+4) 3348: (3+3)*(8-4) 4468: 4*(4-(6-8)) \n",
"1148: (1+1)*(4+8) 1457: 1+((4*7)-5) 2347: (2-(3-7))*4 3349: 3*(3-(4-9)) 4469: 4*(4/(6/9)) \n"
]
}
],
"source": [
"def show_plates(digits=4, target=24):\n",
" \"\"\"Show all license plates that can make 24.\"\"\"\n",
" plates = list(combinations_with_replacement(range(10), 4))\n",
" def solve(plate): return expressions(plate, ops='+-*/', permute=True).get(24)\n",
" solved = [f\"{cat(plate)}: {unbracket(solve(plate))} \" \n",
" for plate in plates if solve(plate)]\n",
" print(f'{len(solved)} out of {len(plates)} distinct license plates can be solved:\\n')\n",
" show_columns(solved)\n",
" \n",
"show_plates()"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "pdDW9gGHKEBB"
},
"source": [
"# Making 6 from 3 Digits\n",
"\n",
"Another Facebook \"omg math\" problem:\n",
"\n",
" *For each digit, find a way to express 6 using only that digit exactly three times and arithmetic operations. E.g., for the digit 2, `'2+2+2'` = 6.*\n",
"\n",
"This is easy if \"arithmetic operations\" include square root and factorial:"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"id": "CoKnbYBxKEBB",
"outputId": "dd72b838-7b22-4080-9b29-739585881ce7"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"6: (0!+(0!+0!))!\n",
"6: (1+(1+1))!\n",
"6: (2+(2+2))\n",
"6: ((3*3)-3)\n",
"6: (4+(4/√4))\n",
"6: (5+(5/5))\n",
"6: (6/(6/6))\n",
"6: (7-(7/7))\n",
"6: (8-√√(8+8))\n",
"6: (9-(9/√9))\n"
]
}
],
"source": [
"for n in range(10):\n",
" print(f\"6: {expressions((n, n, n), '+-*/√!').get(6)}\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "eFFOUF7EKEBB",
"tags": []
},
"source": [
"# Even More Fours: The Power of Floor and Ceiling\n",
"\n",
"With the standard set of `OPS`, we got all the integers up to 72 with four 4s. If we add the floor and ceiling operations, we get a big jump: suddenly, all the results of a division or a square root that didn't form an integer can now be coerced into integers. Instead of getting the integers only up to 72, we now get all the way up to **1644**, although it takes a full minute to get there. \n",
"\n",
"I'll just show the first 300, to save space: "
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"id": "jbJsFkNZKEBC",
"outputId": "fea9ae24-2e75-4a11-8098-162790f91625"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Can make 0 to 1644 with (4, 4, 4, 4), ops=\"+-*/^_√!.,⌊⌈\", permute=False. [1,205,301 table entries]\n",
"\n",
" 0: 44-44 60: 44+(4*4) 120: ⌈4.444⌉! 180: 4+(4*44) 240: √4*⌈4.44⌉! \n",
" 1: 44/44 61: ⌈(.44^-⌈4.4⌉)⌉ 121: (44/4)^√4 181: ⌊(4*(√√4+44))⌋ 241: (.4+(4*4!))/.4 \n",
" 2: √⌊4.444⌋ 62: ⌊(√√4*44.4)⌋ 122: √4+⌈4.44⌉! 182: ⌈(4*(√√4+44))⌉ 242: √4+(4/(.4/4!)) \n",
" 3: 4-⌈.444⌉ 63: ⌈(√√4*44.4)⌉ 123: ⌈(4*(4!+√44))⌉ 183: 4!+⌊(4!*√44)⌋ 243: (4-⌈.4⌉)^⌈4.4⌉ \n",
" 4: ⌊4.444⌋ 64: 4!-(4-44) 124: 4+⌈4.44⌉! 184: 4*(√4+44) 244: 4+(4/(.4/4!)) \n",
" 5: ⌈4.444⌉ 65: (4+(4^4))/4 125: ⌈(44*√(4+4))⌉ 185: ⌈((44-4)^√√4)⌉ 245: (√4+(4*4!))/.4 \n",
" 6: ⌊√44.44⌋ 66: ⌊(44/√.44)⌋ 126: ⌊√44⌋+⌈4.4⌉! 186: ⌈((4+4!)*√44)⌉ 246: (4^4)-(4/.4) \n",
" 7: ⌈√44.44⌉ 67: ⌈(44/√.44)⌉ 127: ⌈√44⌉+⌈4.4⌉! 187: ⌊(4.4^4)⌋/√4 247: ⌊(4^(4-(.4^4)))⌋ \n",
" 8: 4+⌊4.44⌋ 68: 4!+⌊44.4⌋ 128: √4^⌈√44.4⌉ 188: (4!*(4+4))-4 248: (4^4)-(4+4) \n",
" 9: 4+⌈4.44⌉ 69: 4!+⌈44.4⌉ 129: 4!+⌊(4!*4.4)⌋ 189: ⌊(⌈4.44⌉!/√.4)⌋ 249: (4^4)-⌈√44⌉ \n",
" 10: 44/4.4 70: 4!+(√4+44) 130: (4+(4^4))/√4 190: (4!*(4+4))-√4 250: (4^4)-⌊√44⌋ \n",
" 11: 44/⌊4.4⌋ 71: ⌈(44.4/√.4)⌉ 131: ⌈(4!*(4!/4.4))⌉ 191: ⌊(√4!*44)⌋-4! 251: (4^4)-⌈4.4⌉ \n",
" 12: (4+44)/4 72: 4+(4!+44) 132: 44*(4-⌈.4⌉) 192: 4*(4+44) 252: (4^4)-⌊4.4⌋ \n",
" 13: 4!-(44/4) 73: 4+⌊(44/√.4)⌋ 133: ⌈((4!-4)*√44)⌉ 193: ⌊(44*4.4)⌋ 253: ⌊(4!*(4!*.44))⌋ \n",
" 14: ⌈(√44+√44)⌉ 74: 4+⌈(44/√.4)⌉ 134: 4!+(44/.4) 194: ⌈(44*4.4)⌉ 254: √4-(4-(4^4)) \n",
" 15: 4+(44/4) 75: ⌊((4+44)/√.4)⌋ 135: ⌊(4!/.44)⌋/.4 195: ⌊(√4!*(44-4))⌋ 255: (4^4)-(4/4) \n",
" 16: 4*⌊4.44⌋ 76: ⌈4.4⌉!-44 136: √4*(4!+44) 196: 4+(4!*(4+4)) 256: 4^⌊4.44⌋ \n",
" 17: ⌊(4*4.44)⌋ 77: ⌈(44*(4^.4))⌉ 137: ⌈(4!/(.4*.44))⌉ 197: ⌈(44*√(4!-4))⌉ 257: (4^4)+(4/4) \n",
" 18: ⌈(4*4.44)⌉ 78: ⌊(4*(4!-4.4))⌋ 138: √4*⌊(44/√.4)⌋ 198: √4*⌊(√4^√44)⌋ 258: 4-(√4-(4^4)) \n",
" 19: ⌈(444/4!)⌉ 79: ⌈(4*(4!-4.4))⌉ 139: ⌊(4^(4-.44))⌋ 199: ⌈(√4*(√4^√44))⌉ 259: ⌊(√44/(.4^4))⌋ \n",
" 20: 4*⌈4.44⌉ 80: 4*(44-4!) 140: 44+(4*4!) 200: 4!+(4*44) 260: 4+(4^⌊4.4⌋) \n",
" 21: ⌈44.4⌉-4! 81: (4-(4/4))^4 141: ⌈((.4^-4.4)/.4)⌉ 201: ⌊(4!*(4+4.4))⌋ 261: (4^4)+⌈4.4⌉ \n",
" 22: √4/(4/44) 82: ⌊((4/.44)^√4)⌋ 142: (4!*⌊√44⌋)-√4 202: ⌈(4!*(4+4.4))⌉ 262: (4^4)+⌊√44⌋ \n",
" 23: 4!-⌈.444⌉ 83: 44+⌊(.4^-4)⌋ 143: ((4!*4!)-4)/4 203: ⌊(44*(4+√.4))⌋ 263: (4^4)+⌈√44⌉ \n",
" 24: ⌊4.444⌋! 84: (√4*44)-4 144: 4!*⌊√44.4⌋ 204: ⌈(44*(4+√.4))⌉ 264: 44*⌊√44⌋ \n",
" 25: 4!+⌈.444⌉ 85: ⌈(4*(√4^4.4))⌉ 145: (4+(4!*4!))/4 205: ⌊(√4!*(44-√4))⌋ 265: ⌈(4!*4.4)⌉/.4 \n",
" 26: 4+(44/√4) 86: (√4*44)-√4 146: √4+(4!*⌊√44⌋) 206: ⌊(44^√√4)⌋-4 266: (4^4)+(4/.4) \n",
" 27: ⌈(4*√44.4)⌉ 87: (√4*44)-⌈.4⌉ 147: ⌊(44^(√4^.4))⌋ 207: ⌈(44^√√4)⌉-4 267: ⌊(4!*(√4!/.44))⌋ \n",
" 28: 44-(4*4) 88: 44+44 148: 4+(4!*⌊√44⌋) 208: ⌈(4.4^(4-.4))⌉ 268: ⌊(4!^(4*.44))⌋ \n",
" 29: 4!+⌈4.44⌉ 89: ⌈(√4*44.4)⌉ 149: ⌊(.4*(4.4^4))⌋ 209: ⌈(√⌈4.4⌉^√44)⌉ 269: ⌈(4!^(4*.44))⌉ \n",
" 30: ⌈4.44⌉!/4 90: √4*⌈44.4⌉ 150: .4*⌈(4.4^4)⌉ 210: ⌊(44^√(4/√4))⌋ 270: ⌈(4!^(4^√(4/4!)))⌉\n",
" 31: 4!+⌈√44.4⌉ 91: ⌈(444/√4!)⌉ 151: ⌊(4!*√(44-4))⌋ 211: ⌊(√4!*44)⌋-4 271: ⌊((√4!^4.4)/4)⌋ \n",
" 32: √4^⌈4.44⌉ 92: 4+(√4*44) 152: (4*44)-4! 212: (4^4)-44 272: 4*(4!+44) \n",
" 33: ⌊(4*(4+4.4))⌋ 93: ⌊((4.4^4)/4)⌋ 153: ⌊(4!*(√4+4.4))⌋ 213: ⌊(44.4^√√4)⌋ 273: ⌊(4^(4!^.44))⌋ \n",
" 34: 44-(4/.4) 94: ⌈((4.4^4)/4)⌉ 154: (4!-√4)*⌈√44⌉ 214: ⌈(44.4^√√4)⌉ 274: ⌈(4^(4!^.44))⌉ \n",
" 35: 4!+(44/4) 95: (4*4!)-(4/4) 155: ⌊(4!*√44)⌋-4 215: 4+⌈(44^√√4)⌉ 275: 44/(.4*.4) \n",
" 36: 44-(4+4) 96: 4*⌊4.44⌋! 156: 4*⌊(44-√4!)⌋ 216: 4*⌊(4!/.44)⌋ 276: 4*⌊(44/√.4)⌋ \n",
" 37: 44-⌈√44⌉ 97: (4/4)+(4*4!) 157: ⌈(4*(44-√4!))⌉ 217: ⌊(√4!*44.4)⌋ 277: ⌈(4!*(√4!+√44))⌉ \n",
" 38: 44-⌊√44⌋ 98: ⌊(44*√⌈4.4⌉)⌋ 158: ⌊(44*(4-.4))⌋ 218: ⌈(√4!*44.4)⌉ 278: ⌊(4/(√.4/44))⌋ \n",
" 39: 44-⌈4.4⌉ 99: ⌊(4^√(44/4))⌋ 159: ⌊(4!*√44.4)⌋ 219: 4+⌊(√4!*44)⌋ 279: ⌈(4/(√.4/44))⌉ \n",
" 40: 44-⌊4.4⌋ 100: 44/.44 160: 4*(44-4) 220: 44*⌈4.4⌉ 280: ⌊(√.4*444)⌋ \n",
" 41: ⌈44.4⌉-4 101: ⌊(√4^√44.4)⌋ 161: ⌈((4-.44)^4)⌉ 221: ⌈(√4!*⌈44.4⌉)⌉ 281: ⌈(√.4*444)⌉ \n",
" 42: √4-(4-44) 102: ⌈(√4^√44.4)⌉ 162: √4+⌈(4!*√44)⌉ 222: 444/√4 282: 4!+(√4+(4^4)) \n",
" 43: 44-(4/4) 103: 4+⌊(√4^√44)⌋ 163: 4+⌊(4!*√44)⌋ 223: ⌈(4^4.4)⌉/√4 283: ⌈((4+(.4/4))^4)⌉ \n",
" 44: ⌊44.44⌋ 104: 44+(4!/.4) 164: 44+⌈4.4⌉! 224: (4+4)*(4+4!) 284: 4+(4!+(4^4)) \n",
" 45: ⌈44.44⌉ 105: (44-√4)/.4 165: ⌈(√4!+(4!*√44))⌉ 225: ⌊(4/(.4^4.4))⌋ 285: ⌊(⌈√44⌉!^√.44)⌋ \n",
" 46: 4+(44-√4) 106: (44/.4)-4 166: ⌊(4!*√(4+44))⌋ 226: ⌈(4/(.4^4.4))⌉ 286: ⌊(√4!^(4-.44))⌋ \n",
" 47: √4+⌈44.4⌉ 107: ⌈(4!*4.44)⌉ 167: ⌈(4!*√(4+44))⌉ 227: 4+⌈((4^√4!)/4)⌉ 287: ⌈(√4!^(4-.44))⌉ \n",
" 48: 4+⌊44.4⌋ 108: (44/.4)-√4 168: 4*(44-√4) 228: (4^4)-(4+4!) 288: 4!*(4+(4+4)) \n",
" 49: 4+⌈44.4⌉ 109: (44-.4)/.4 169: ⌊√(4*44)⌋^√4 229: ⌈(4^(4-(√4/4!)))⌉ 289: ⌊(4*4.4)⌋^√4 \n",
" 50: 44+⌊√44⌋ 110: ⌊44.4⌋/.4 170: (4!+44)/.4 230: (4^4)-(4!+√4) 290: (⌈4.4⌉!-4)/.4 \n",
" 51: 44+⌈√44⌉ 111: 444/4 171: ⌈(4*(44-√√4))⌉ 231: ⌊(.44^-√44)⌋ 291: ⌊(44*√44)⌋ \n",
" 52: 4+(4+44) 112: 4!+(√4*44) 172: (4*44)-4 232: ⌈(.44^-√44)⌉ 292: ⌈(44*√44)⌉ \n",
" 53: ⌊(4*√(4*44))⌋ 113: ⌈(.44*(4^4))⌉ 173: ⌊(4*(44-√.4))⌋ 233: ⌈(44*√(4+4!))⌉ 293: (4^4)+⌊(4!/√.4)⌋ \n",
" 54: 44+(4/.4) 114: 4+(44/.4) 174: (4*44)-√4 234: 4!+⌊(44^√√4)⌋ 294: ⌊(4^(4+(.4/4)))⌋ \n",
" 55: ⌈(4!/.444)⌉ 115: (√4+44)/.4 175: (4*44)-⌈.4⌉ 235: ⌊(√4!*(4+44))⌋ 295: (⌈4.4⌉!-√4)/.4 \n",
" 56: 44+(4!/√4) 116: ⌈4.44⌉!-4 176: 4*⌊44.4⌋ 236: 4-(4!-(4^4)) 296: (⌈4.4⌉!/.4)-4 \n",
" 57: ⌈(√√4*(44-4))⌉ 117: ⌈(44*√⌈√44⌉)⌉ 177: ⌊(4*44.4)⌋ 237: ⌊(√.4*(4.4^4))⌋ 297: ⌈(√√4*⌊(44^√√4)⌋)⌉\n",
" 58: ⌊(.4^-4.44)⌋ 118: ⌈4.44⌉!-√4 178: ⌈(4*44.4)⌉ 238: ⌊((4+44)^√√4)⌋ 298: (⌈4.4⌉!/.4)-√4 \n",
" 59: ⌈(.4^-4.44)⌉ 119: ⌈4.4⌉!-(4/4) 179: ⌈(4*(√.4+44))⌉ 239: ⌈((4+44)^√√4)⌉ 299: (⌈4.4⌉!-.4)/.4 \n",
"CPU times: user 14.4 s, sys: 120 ms, total: 14.5 s\n",
"Wall time: 14.6 s\n"
]
}
],
"source": [
"%time show((4, 4, 4, 4), limit=300, ops=OPS + \"⌊⌈\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "4isEhtVGKEBC",
"tags": []
},
"source": [
"We could get up to **2892** with nesting level 3, but that takes multiple minutes.\n",
"\n",
"# Even More Fives: Five 5s\n",
"\n",
"In the [xkcd forum](http://forums.xkcd.com/viewtopic.php?f=14&t=116813&start=280) they took up the problem of **five 5s** and got all the integers up to 298, using the \"[double factorial function](https://en.wikipedia.org/wiki/Double_factorial)\" and [π function](https://en.wikipedia.org/wiki/Prime-counting_function). We can get up to 171, using just the default operations, but with five digits it does take about seven minutes, whereas all the other puzzles with four or three digits (and without floor and ceiling) took less than a minute. I suspect you could go much further using floor and ceiling, but that computation would take even longer, so for now let's stick with our default set of operations:"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"id": "4MHPG5L8KEBC",
"outputId": "63bffec7-8b22-4bb2-cd44-6fd03f124ccf"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Can make 0 to 171 with (5, 5, 5, 5, 5), ops=\"+-*/^_√!.,\", permute=False. [14,827,653 table entries]\n",
"\n",
" 0: 5*(55-55) 43: 55-(5!/(5+5)) 86: (55/.5)-(5!/5) 129: (5!-55.5)/.5 \n",
" 1: 5^(55-55) 44: 55-(55/5) 87: (555-5!)/5 130: 5!+(55/5.5) \n",
" 2: 55/(5*5.5) 45: (5*5!)-555 88: 5/((.5^5)/.55) 131: 5!+(5.5+5.5) \n",
" 3: √(5!-(555/5)) 46: 55-((5-.5)/.5) 89: 5!+((5!/5)-55) 132: 5!*(.55+.55) \n",
" 4: 5-(55/55) 47: 55-√((.5^-5)/.5) 90: 5!-(55-(5*5)) 133: 5!+((5!-55)/5) \n",
" 5: 5.55-.55 48: 5!/(5*(5.5-5)) 91: (5*5)+(5!*.55) 134: (5!/5)+(55/.5) \n",
" 6: 5+(55/55) 49: 55-(.5+5.5) 92: 5+(55+(.5^-5)) 135: (5!+555)/5 \n",
" 7: ((5+55)/5)-5 50: 55.5-5.5 93: .5+(5!-(5*5.5)) 136: 5+(5!+(55/5)) \n",
" 8: .5*(5+(55/5)) 51: .5-(5-55.5) 94: 5!-((5/5)+(5*5)) 137: 5+(5!/(5/5.5)) \n",
" 9: 5!-(555/5) 52: 55-(.5+(5*.5)) 95: (55/.55)-5 138: .5+(5*(5*5.5)) \n",
" 10: 5!-(55+55) 53: 55.5-(5*.5) 96: 5!-√(5+(55/5))! 139: ((.5+5.5)!/5)-5 \n",
" 11: 55/(5.5-.5) 54: 55-(5^(5-5)) 97: 5!-(55-(.5^-5)) 140: .5*(5+(5*55)) \n",
" 12: 5!/(55/5.5) 55: .5*(55+55) 98: 5!-(55/(5*.5)) 141: 5!+((5+5.5)/.5) \n",
" 13: (5+(5+55))/5 56: 55+(5^(5-5)) 99: (55-5.5)/.5 142: 5!+(55/(5*.5)) \n",
" 14: (5*5)-(55/5) 57: 55+((5+5)/5) 100: (55/.5)-(5+5) 143: 5!+(55-(.5^-5)) \n",
" 15: 5+(55/5.5) 58: (5*.5)+55.5 101: (55.5-5)/.5 144: ((55/5)-5)!/5 \n",
" 16: 5+(5.5+5.5) 59: 5-((5/5)-55) 102: 5+(5!+((5-5!)/5)) 145: 5!+(.5*(55-5)) \n",
" 17: 5+((5+55)/5) 60: 5+(√55*√55) 103: 55+(5!/(5*.5)) 146: 5!+((5/5)+(5*5)) \n",
" 18: 5+((5!-55)/5) 61: 5.5+55.5 104: 5!-(5+(55/5)) 147: 5!-(.5-(5*5.5)) \n",
" 19: (5*5)-(.5+5.5) 62: (55-(5!/5))/.5 105: 55-(5-55) 148: .5+(5!+(5*5.5)) \n",
" 20: 55/(5*.55) 63: 5.5-(.5*(5-5!)) 106: (555/5)-5 149: 5+((.5+5.5)!/5) \n",
" 21: 5+(5+(55/5)) 64: 5!-(.5+55.5) 107: 5!-((5!-55)/5) 150: 5*(55-(5*5)) \n",
" 22: (55+55)/5 65: .5+(5!-55.5) 108: 5!-((5+55)/5) 151: 5!-((5!/5)-55) \n",
" 23: (5+(55/.5))/5 66: 55+(55/5) 109: 5!-(5.5+5.5) 152: 5!+((5.5-5)^-5) \n",
" 24: (5-(55/55))! 67: 55+(5!/(5+5)) 110: (555-5)/5 153: 5!+(.5*(5!*.55)) \n",
" 25: 55-(5+(5*5)) 68: 5.5+(.5*(5+5!)) 111: 555/√(5*5) 154: 5+(5+(5!+(5!/5))) \n",
" 26: 55-(5+(5!/5)) 69: 5+(.5^(-.5-5.5)) 112: (5+555)/5 155: 5*(55-(5!/5)) \n",
" 27: 5+(55/(5*.5)) 70: 5+(5+(5+55)) 113: 5!-(5+((5+5)/5)) 156: (5!+(5!*5.5))/5 \n",
" 28: .5*(.5+55.5) 71: 55+(.5/(.5^5)) 114: 5+(5!-(55/5)) 157: (.5^-5)+(5*(5*5)) \n",
" 29: 5+√(5+(55/5))! 72: 5!*((5.5/5)-.5) 115: 5+(55+55) 158: (55+(5!/5))/.5 \n",
" 30: 5*((55/5)-5) 73: (5*5)+(5!/(5*.5)) 116: 5+(555/5) 159: (5/(.5^5))-(5/5) \n",
" 31: 55-(5-(5/5))! 74: 55-(5-(5!/5)) 117: 5!-(5.5-(5*.5)) 160: 5/((5.5-5)^5) \n",
" 32: √.5^(55/-5.5) 75: 55-(5-(5*5)) 118: 5!-(5!/(5+55)) 161: (5/5)+(5/(.5^5)) \n",
" 33: .55*(5+55) 76: 5+(5+(5!*.55)) 119: 5!-(55/55) 162: 5+(5+(5!+(.5^-5))) \n",
" 34: (5!-(5-55))/5 77: 5+(.5*(5!+(5!/5))) 120: (5.55-.55)! 163: 5!-(5-(5!/(5*.5))) \n",
" 35: 5+(55-(5*5)) 78: 55-((5-5!)/5) 121: 5!+(55/55) 164: 5!+(.5*(5!-(.5^-5)))\n",
" 36: (5*5)+(55/5) 79: 55+(5-(5/5))! 122: 5!+(5!/(5+55)) 165: 55+(55/.5) \n",
" 37: 5+((5.5-5)^-5) 80: 5*(5+(55/5)) 123: 5!+(5.5-(5*.5)) 166: 5!-((5-5!)/(5*.5)) \n",
" 38: 5+(.5*(5!*.55)) 81: 5+(.5*(5!+(.5^-5))) 124: 5!+√(5+(55/5)) 167: 5!-((5-(5!/.5))/5) \n",
" 39: 55-(.5/(.5^5)) 82: 55-(5-(.5^-5)) 125: 5*(.5*(55-5)) 168: (5!+(.5+5.5)!)/5 \n",
" 40: 55-(5+(5+5)) 83: (.5*5!)-((5-5!)/5) 126: 5!+((55/5)-5) 169: 5!+((5*5)+(5!/5)) \n",
" 41: 5!-(55+(5!/5)) 84: 5+(55+(5!/5)) 127: (5!/(5/5.5))-5 170: 5!-(√(5*5)-55) \n",
" 42: (5+5.5)/(.5*.5) 85: 5+(55+(5*5)) 128: 5!+(5.5+(5*.5)) 171: (5.5/(.5^5))-5 \n",
"CPU times: user 2min 21s, sys: 2.05 s, total: 2min 23s\n",
"Wall time: 2min 24s\n"
]
}
],
"source": [
"%time show((5, 5, 5, 5, 5))"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "9HYipLxUKEBC"
},
"source": [
"# f(n): Unmakeable from (1, ..., *n*)\n",
"\n",
"The facebook group \"actually good math problems\" posed the problem of determining the values of `f(n)`, which is defined to be the smallest positive integer that can not be made from (in our terms) `expressions(range(n + 1), '+-*/^,', permute=True)`. Computing up to `f(5)` is fast, but computing that `f(6) = 9562` requires hundreds of billions of combinations and would take about 100 minutes to run; it would require significant work to make it more efficient, or to move on to `f(7)`."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [],
"source": [
"@cache\n",
"def f(n, ops='+-*/^,') -> int:\n",
" \"\"\"The smallest integer inexpressible in digits 0 thru n.\"\"\"\n",
" return unmakeable(expressions(range(n + 1), ops, permute=True))"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"f(0) = 1\n",
"f(1) = 2\n",
"f(2) = 4\n",
"f(3) = 25\n",
"f(4) = 175\n",
"f(5) = 1099\n"
]
}
],
"source": [
"for n in range(6):\n",
" print(f'f({n}) = {f(n)}')"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "9HYipLxUKEBC"
},
"source": [
"# What's Next?\n",
"\n",
"One exercise would be adding even more operations, such as:\n",
"\n",
"- **Nth root**: `3√8` = 2\n",
"- **Percent**: `50%` = 0.5\n",
"- **Absolute value**: `|1-3|` = 2 (redundant if you have unary minus, but add it if you like it)\n",
"- **Repeating decimal**: `.4...` = .44444444... = 4/9\n",
"- **Comparison operations**: `1>(2<3)` = 0, because `(2<3)` is True, which is treated as `1`, and `1>1` is False, or `0`\n",
"- **Double factorial**: `9!!` = 9 × 7 × 5 × 3 × 1 = 945; not the same as `(9!)!`\n",
"- **Gamma function**: `Γ(n)` = (n − 1)! and works for non-integers\n",
"- **Prime counting function**: `π(n)` = number of primes ≲ n; e.g. `π(5)` = 3\n",
"- **Transcendental functions**: `log`, `sin` `cos`, `tan`, `arcsin`, ... \n",
"- **Degree symbol**: `180°` = π\n",
"- **Log to base**: `log_10(100)` = 2\n",
"- **Matrix notation**: with determinant symbol to get a number.\n",
"- **Combinations and Permutations**: `6 C_ 2` = 15; `6 P_ 2` = 30\n",
"\n",
"Another approach would be to look around for related puzzles and solve them. What do you want to do?"
]
}
],
"metadata": {
"colab": {
"provenance": []
},
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.8.15"
}
},
"nbformat": 4,
"nbformat_minor": 4
}