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.
from collections import Counter, defaultdict, namedtuple
from fractions import Fraction
from itertools import product, permutations, combinations_with_replacement
from math import sqrt, factorial, floor, ceil
from operator import add, sub, mul, neg, truediv as div
from typing import List, Tuple, Dict, Union, Sequence, Collection, Set, Optional
import functools
import re
cache = functools.lru_cache(None)
On January 1, 2016 this New Year's puzzle was posed, and subsequently answered, by Alex Bellos:
Fill in the blanks so that this equation makes arithmetical sense:
10 ␣ 9 ␣ 8 ␣ 7 ␣ 6 ␣ 5 ␣ 4 ␣ 3 ␣ 2 ␣ 1 = 2016
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:*
(10 + 9) × (8 ...
10 + (9 × 8) ...
To solve this specific problem, I'll first solve the more general problem:
{value: expression}
for every value that can be made.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:
expressions((3, 2)) = {1: '(3-2)', 1.5: '(3/2)', 5: '(3+2)', 6: '(3*2)'}
I'll use the idea of 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:
Numbers = Tuple[int] # A sequence of integers, like (10, 9, 8)
Exp = str # An expression is represented as a string, like '(10+(9-8))'
ExpTable = Dict[float, Exp] # A table is a dict, like {11: '(10+(9-8))', ...}
@cache
def expressions(numbers: Numbers) -> ExpTable:
"""Return a {value: exp} table for expressions that can be made from `numbers` with +-*/."""
if len(numbers) == 1:
return {numbers[0]: str(numbers[0])}
else:
table = {}
for (Lnums, Rnums) in splits(numbers):
for (L, R) in product(expressions(Lnums), expressions(Rnums)):
Lexp, Rexp = '(' + expressions(Lnums)[L], expressions(Rnums)[R] + ')'
if R != 0:
table[L / R] = Lexp + '/' + Rexp
table[L * R] = Lexp + '*' + Rexp
table[L - R] = Lexp + '-' + Rexp
table[L + R] = Lexp + '+' + Rexp
return table
def splits(sequence) -> List[Tuple[Sequence, Sequence]]:
"""Split sequence into two non-empty parts, in all ways."""
return [(sequence[:i], sequence[i:])
for i in range(1, len(sequence))]
If we call expressions((3, 2, 1))
, then as we trace through the execution, at one particular point we get (among other things):
len(numbers) == 3
Lnums = (3, 2)
Rnums = (1,)
L = 6
R = 1
Lexp = '((3*2)'
Rexp = '1)'
table[7] = '((3*2)+1)'
Some tests to make sure we got this right:
assert expressions((1,)) == {1: '1'}
assert expressions((2,)) == {2: '2'}
assert expressions((3,)) == {3: '3'}
assert expressions((2, 1)) == {1: '(2-1)', 2: '(2*1)', 3: '(2+1)'}
assert expressions((3, 2)) == {1.5: '(3/2)', 6: '(3*2)', 1: '(3-2)', 5: '(3+2)'}
assert expressions((3, 2, 1)) == {0: '((3-2)-1)', 0.5: '((3/2)-1)', 1: '((3-2)*1)',
1.5: '((3/2)*1)', 2: '((3-2)+1)', 2.5: '((3/2)+1)', 3: '(3*(2-1))',
4: '((3+2)-1)', 5: '((3+2)*1)', 6: '((3+2)+1)', 7: '((3*2)+1)', 9: '(3*(2+1))'}
assert expressions((3, 2, 1))[7] == '((3*2)+1)'
assert splits((3, 2, 1)) == [((3,), (2, 1)), ((3, 2), (1,))]
assert splits((5, 4, 3, 2, 1)) == [
((5,), (4, 3, 2, 1)),
((5, 4), (3, 2, 1)),
((5, 4, 3), (2, 1)),
((5, 4, 3, 2), (1,))]
That looks good. Let's solve the whole puzzle.
c10 = (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) # A countdown from 10 to 1
%time expressions(c10)[2016]
CPU times: user 21.9 s, sys: 667 ms, total: 22.6 s Wall time: 22.7 s
'(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)'
We have an answer! And in just seconds, thanks to dynamic programming! Here are solutions for nearby years:
{y: expressions(c10)[y] for y in range(2010, 2030)}
{2010: '((((((10+(((9*8)-7)*6))*5)+4)+3)+2)+1)', 2011: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)-1)', 2012: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)*1)', 2013: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)+1)', 2014: '(((((((10+((9*8)*7))-6)-5)*4)+3)-2)+1)', 2015: '(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)*1)', 2016: '(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)', 2017: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)-1)', 2018: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)*1)', 2019: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)+1)', 2020: '(((((10+((9+((8+7)*6))*5))*4)+3)-2)-1)', 2021: '((((((((10-9)+(8*7))*6)-5)*4)*3)/2)-1)', 2022: '((((((((10-9)+(8*7))*6)-5)*4)*3)/2)*1)', 2023: '(((((10*(((9*8)*(7-6))-5))+4)*3)+2)-1)', 2024: '(((((10*(((9*8)*(7-6))-5))+4)*3)+2)*1)', 2025: '(((((10*(((9*8)*(7-6))-5))+4)*3)+2)+1)', 2026: '((((10+((((9*8)*7)*(6-5))*4))+3)-2)-1)', 2027: '((((10+((((9*8)*7)*(6-5))*4))+3)-2)*1)', 2028: '((((10+((((9*8)*7)*(6-5))*4))+3)-2)+1)', 2029: '(((((((10*9)+8)*7)*6)-((5*4)*3))/2)+1)'}
Alex Bellos had another challenge:
As it stands, my program can't answer that question, because I only keep one expression for each value.
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."
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:
@cache
def expression_counts(numbers: Numbers) -> Counter:
"Return a Counter of {value: count} for every value that can be made from numbers."
table = Counter()
if len(numbers) == 1:
table[numbers[0]] = 1
else:
for (Lnums, Rnums) in splits(numbers):
for L, R in product(expression_counts(Lnums), expression_counts(Rnums)):
count = expression_counts(Lnums)[L] * expression_counts(Rnums)[R]
if R != 0:
table[L / R] += count
table[L + R] += count
table[L - R] += count
table[L * R] += count
return table
assert expression_counts((3,)) == Counter({3: 1})
assert expression_counts((3, 2, 1))[1] == 5 # (3-2)*1, (3-2)/1, 3-(2*1), 3-(2/1), 3/(2+1)
Looks good to me. Now let's see if we can answer Alex's question.
expression_counts(c10)[2016]
30066
This claims there are 30,066 distinct expressions for 2016. Is that the answer Alex wanted?
I think 30,066 is wrong. The trouble is: round-off error.
Let's find all the values in expressions(c10)
that are very near to 2016, within ±0.0000000001:
{y: expressions(c10)[y]
for y in expressions(c10)
if abs(y - 2016) < 1e-10}
{2016.0000000000002: '((((10*((9*(8+7))-(6/(5+4))))*3)/2)+1)', 2016.0: '(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)', 2015.9999999999995: '((((((10*9)*8)*7)*((6/5)-(4-3)))*2)*1)', 2015.999999999997: '(((10*9)*8)/(7-(6-(((5/(4+3))/2)-1))))', 2016.0000000000005: '(((((10*9)*8)*((((7*6)/5)-4)-3))*2)*1)', 2016.0000000000018: '((((((10*9)*8)*7)*(((6/5)-4)+3))*2)*1)', 2016.0000000000023: '(10*((9*8)/((7-(6-((5/(4+3))/2)))-1)))', 2015.9999999999998: '((10*((9*(((8-(7/6))*5)-(4*3)))+2))+1)', 2015.9999999999993: '(10*(((((9*8)*7)*6)/5)*(((4/3)-2)+1)))', 2016.000000000002: '(((10*9)*8)/((7-(6-((5/(4+3))/2)))-1))', 2015.999999999999: '((((10*9)*(8+7))-6)/(((5-(4/3))-2)-1))'}
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:
def exact(exp) -> str: return re.sub(r"([0-9]+)", r"Fraction(\1)", exp)
exact('1/(5-2)')
'Fraction(1)/(Fraction(5)-Fraction(2))'
assert eval(exact('1/(5-2)')) == Fraction(1, 3)
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:
sum(expression_counts(c10)[y]
for y, exp in expressions(c10).items()
if abs(y - 2016) < 1e-3 and eval(exact(exp)) == 2016)
44499
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.
Alex Bellos continued his column with a related puzzle:
The most famous “fill in the gaps in the equation” puzzle is known as four fours, because every equation is of the form
4 ␣ 4 ␣ 4 ␣ 4 = x
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).
This puzzle goes back to a 1914 publication by the famed mathematician/magician W. W. Rouse Ball. The solution is easy:
{i: expressions((4, 4, 4, 4))[i] for i in range(10)}
{0: '(((4-4)-4)+4)', 1: '(((4/4)-4)+4)', 2: '((4/(4+4))*4)', 3: '(((4+4)+4)/4)', 4: '(((4-4)*4)+4)', 5: '(((4*4)+4)/4)', 6: '(((4+4)/4)+4)', 7: '((4-(4/4))+4)', 8: '(((4+4)/4)*4)', 9: '(((4/4)+4)+4)'}
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.
Bellos then writes:
!
.*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!
).
Allowing additional operations introduces some issues; here's how I'll handle them:
√-1
(I won't allow imaginary numbers.)√2
(I'll use floating point approximations.)49*(1/49) == 0.9999999999999999
(I'll try to round off appropriately, but might make errors.)10.^(9.^8.)
raises OverflowError
(I'll drop overflow results, but might miss good results.)10^(9*(8+7))
uses more bytes of storage than all the molecules in the universe. (I'll avoid generating huge integers.)(.9^(8!))^(√7)
is a valid rational number, but unlikely to eventually lead to an integer. (I'll drop unlikely operations.)√√√√√√√√(4!!!!!!!!)
is legal; where do you end? (I'll limit nesting to 2 unary operations).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:
Binary Operations | Unary Operations | Digit Operations |
---|---|---|
+ addition: 1 + 2 = 3 |
_ unary minus: -4 = -4 |
. decimal point: 1.23 |
- subtraction: 3 - 2 = 1 |
√ square root: √4 = 2 |
, concatenation of digits: 123 |
* multiplication: 2 * 3 = 6 |
! factorial: 4! = 24 |
|
/ division: 6 / 3 = 2 |
⌊ floor:⌊4.4⌋ = 4 |
|
^ exponentiation: 2 ^ 3 = 8 |
⌈ ceiling: ⌈4.4⌉ = 5 |
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:
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.
Operation = namedtuple('Operation', 'symbol, func, fmt, applicable', defaults=[None, lambda *args: True])
OPERATIONS = {
2: {Operation('+', add),
Operation('-', sub),
Operation('*', mul),
Operation('/', div, None, lambda L, R: R != 0),
Operation('^', pow, None, lambda L, R: (-10 <= R <= 10) and (L > 0 or R == int(R)))},
1: {Operation('√', sqrt, '√{}', lambda v: 0 < v <= 256 and (3628800. * v).is_integer()),
Operation('!', factorial, '{}!', lambda v: v in range(10)),
Operation('_', neg, '-{}'),
Operation('⌊', floor, '⌊{}⌋'),
Operation('⌈', ceil, '⌈{}⌉')}}
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).
def operate(operation, *args) -> Optional[float]:
"Return op(*args), trying to correct for roundoff error, or `None` if too big/small/erroneous."
if operation.applicable(*args):
try:
val = operation.func(*args)
except (ArithmeticError, ValueError):
return None
return (0.0 if val == 0 else
None if isinstance(val, complex) else
None if not (1e-10 < abs(val) < 1e10) else
round(val) if abs(val - round(val)) < 1e-12 else
val)
expressions
¶I'll take this opportunity to refactor expressions
to use the new OPERATIONS
. The new expressions
takes four arguments:
numbers
: as before, an ordered tuple of component integers from which to make expressions.ops
: a character string containing the allowable operation character codes. Default OPS
, which is '+-*/^_√!.,'
.nesting
: the maximum nesting level of unary operations. Default 2
, so '3!!'
is ok, but '3!!!'
is not.permute
: whether the numbers
may be permuted. If true then (2, 3)
can produce '3^2'
.I introduce three subfunctions, corresponding to the three types of operations:
digit_expressions(digits, ops)
: returns a table of expressions made with all the digits, in the given order.','
is in ops
allow concatenation of digits (e.g. {44: '44'}
).'.'
is in ops allow decimals (e.g. {4.4: '4.4', 0.44: '.44'}
.digits
is a single digit, always allow it (e.g. {4: '4'}
).add_binary_expressions(table, numbers, ops, nesting)
: use binary operations, like {5: '(2+3)'}
.add_unary_expressions(table, ops, nesting)
: use unary operations, like √4
and 4!
.OPS = '+-*/^_√!.,' # Default set of operations; omits floor and ceiling.
@cache
def expressions(numbers: Numbers, ops=OPS, nesting=2, permute=False) -> ExpTable:
"Return {value: expr} for all expressions that can be made from numbers using ops."
table = {}
orderings = (permutations(numbers) if permute else [numbers]) # Handle permutations once at top level
for nums in orderings:
table.update(digit_expressions(nums, ops))
add_binary_expressions(table, nums, ops, nesting)
return add_unary_expressions(table, ops, nesting)
@cache
def digit_expressions(digits: Numbers, ops: str) -> ExpTable:
"""Return {value: expr} for expressions made with all the digits, maybe with a decimal point."""
D = cat(digits)
table = {}
if len(digits) == 1 or (',' in ops and not D.startswith('0')):
table[int(D)] = D
if '.' in ops:
for L, R in splits(D, 0):
if len(L) < 2 or not L.startswith('0'): # Disallow '00.7'; allow '0.07'
decimal = L + '.' + R
table[float(decimal)] = decimal
return table
def cat(items) -> str: "concatenate"; return ''.join(map(str, items))
def add_binary_expressions(table, numbers, ops, nesting) -> ExpTable:
"Add binary expressions by splitting numbers and combining with an op."
binary_ops = operations(2, ops)
for (Lnums, Rnums) in splits(numbers):
Ltable = expressions(Lnums, ops, nesting, False)
Rtable = expressions(Rnums, ops, nesting, False)
for (L, R) in product(Ltable, Rtable):
Lexp, Rexp = '(' + Ltable[L], Rtable[R] + ')'
for op in binary_ops:
assign(table, operate(op, L, R), Lexp + op.symbol + Rexp)
return table
def add_unary_expressions(table, ops: str, nesting: int) -> ExpTable:
"Add unary expressions (e.g. -v, √v and v!) to table"
unary_ops = operations(1, ops)
for _ in range(nesting):
for v in tuple(table):
for op in unary_ops:
assign(table, operate(op, v), op.fmt.format(table[v]))
return table
def operations(arity: int, ops: str) -> List[Operation]:
"""All the operations in OPERATIONS with given arity whose code symbol is one of `ops`."""
return [op for op in OPERATIONS[arity] if op.symbol in ops]
def splits(sequence, start=1) -> List[Tuple[Sequence, Sequence]]:
"""Split sequence into two parts, in all ways.
If start=1, the two parts are non-empty. If start=0, allow empty left part."""
return [(sequence[:i], sequence[i:])
for i in range(start, len(sequence))]
The function assign
adds a {val: exp}
entry to table
, but if there is already an entry for val
, it prefers the shorter entry.
def assign(table: dict, val: Optional[float], exp: str):
"Assign table[val] = exp, unless val is None or we already have a shorter exp."
if val is not None and (val not in table or len(exp) < len(table[val])):
table[val] = exp
That's a lot of new code; let's have some tests:
assert digit_expressions((1, 2), ',.') == {12: '12', 0.12: '.12', 1.2: '1.2'}
assert digit_expressions((1, 2), ',') == {12: '12'}
assert digit_expressions((1, 2), '.') == {.12: '.12', 1.2: '1.2'}
assert digit_expressions((1, 2), '') == {}
assert digit_expressions((0, 1, 2), ',.') == {0.012: '.012', 0.12: '0.12'}
assert digit_expressions((0, 0, 7), ',.') == {0.007: '.007', 0.07: '0.07'}
assert digit_expressions((7, 0, 0), ',.') == {0.7: '.700', 7.0: '7.00', 70.0: '70.0', 700: '700'}
assert add_unary_expressions({16: '16'}, '_', 2) == {16: '16', -16: '-16'}
assert add_unary_expressions({16: '16'}, OPS, 2) == {
16: '16', -16: '-16', 4: '√16', -4: '-√16', 2: '√√16', 24: '√16!'}
add_binary_expressions({1: '1', 2: '2'}, (1, 2), '+-*/', 2) == {
1: '1', 2: '2', 3: '(1+2)', 0.5: '(1/2)', -1: '(1-2)'}
assert expressions((3, 2), '+-*,') == {32.0: '32', 5: '(3+2)', 1: '(3-2)', 6: '(3*2)'}
add_binary_expressions({1: '1', 2: '2'}, (1, 2), '+-*/', 2)
{1: '1', 2: '2', 0.5: '(1/2)', -1: '(1-2)', 3: '(1+2)'}
I'll define a function to print a table of consecutive integers (starting at 0) that can be made by a sequence of numbers:
def show(numbers: tuple, limit=None, ops=OPS, permute=False, nesting=2):
"""Print expressions for integers from 0 up to limit or the first unmakeable integer.
Break output into `cols` columns."""
table = expressions(numbers, ops, nesting, permute)
print(f'Can make 0 to {unmakeable(table)-1} with {numbers}, ops="{ops}", permute={permute}.'
f' [{len(table):,} table entries]\n')
N = limit or unmakeable(table)
show_columns([f'{i:3}: {unbracket(table[i])}' for i in range(N)])
def show_columns(items, linelength=116):
"""Print the items in as many columns that will fit within `linelength`."""
width = max(map(len, items))
cols = linelength // width
rows = (len(items) - 1) // cols + 1
for row in range(rows):
print(*[str(item).ljust(width) for item in items[row::rows]])
def unmakeable(table) -> int:
"""The integer i such that table makes every integer from 0 to i - 1, but not i."""
for i in range(len(table) + 1):
if i not in table:
return i
def unbracket(exp: str) -> str:
"Strip outer parens from exp, if they are there"
return (exp[1:-1] if exp.startswith('(') and exp.endswith(')') else exp)
show((4, 4, 4, 4))
Can make 0 to 72 with (4, 4, 4, 4), ops="+-*/^_√!.,", permute=False. [721,878 table entries] 0: 44-44 15: 4+(44/4) 30: (4+(4+4))/.4 45: 44+(4/4) 60: 44+(4*4) 1: 44/44 16: .4*(44-4) 31: 4!+((4+4!)/4) 46: 4-(√4-44) 61: (4/4)+(4!/.4) 2: (4+44)/4! 17: (4!+44)/4 32: 44-(4!/√4) 47: 4!+(4!-(4/4)) 62: (4*(4*4))-√4 3: √((44/4)-√4) 18: (44/√4)-4 33: 4+(4!+(√4/.4)) 48: 44+√(4*4) 63: ((4^4)-4)/4 4: 4!-(44-4!) 19: 4!-(4+(4/4)) 34: 44-(4/.4) 49: 44+(√4/.4) 64: 4!-(4-44) 5: (44-4!)/4 20: (44-4)/√4 35: 4!+(44/4) 50: 4+(√4+44) 65: (4+(4^4))/4 6: √(44-(4+4)) 21: (4+4.4)/.4 36: 44-(4+4) 51: (.4-(4-4!))/.4 66: 4!-(√4-44) 7: (44/4)-4 22: √4/(4/44) 37: 4!+((4!+√4)/√4) 52: 4+(4+44) 67: √4+((4!+√4)/.4) 8: 4+(4.4-.4) 23: (√4+44)/√4 38: 44-(4+√4) 53: 4!+(4!+(√4/.4)) 68: 44+√(4*4)! 9: (44/4)-√4 24: 4+(44-4!) 39: 44-(√4/.4) 54: 44+(4/.4) 69: 4+((4!+√4)/.4) 10: 44/4.4 25: 4!+(4^(4-4)) 40: 44-√(4*4) 55: 44/(.4+.4) 70: 4!+(√4+44) 11: 44/√(4*4) 26: 4+(44/√4) 41: (.4+(4*4))/.4 56: 44+(4!/√4) 71: (4!+4.4)/.4 12: (4+44)/4 27: 4+(4!-(4/4)) 42: √4-(4-44) 57: ((.4+4!)/.4)-4 72: 4+(4!+44) 13: 4!-(44/4) 28: 44-(4*4) 43: 44-(4/4) 58: ((4^4)-4!)/4 14: 4.4+(.4*4!) 29: 4+(4!+(4/4)) 44: √44*√44 59: (4!/.4)-(4/4)
We can also solve the "2016 with four fours" puzzle:
expressions((4, 4, 4, 4), OPS, 2)[2016]
'((4+4)!/(4!-4))'
In a separate video, 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 for the "four 2s" problem).
Donald Knuth conjectured 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.)
Below are some popular variant problems:
show((2, 2, 2, 2))
Can make 0 to 30 with (2, 2, 2, 2), ops="+-*/^_√!.,", permute=False. [112,539 table entries] 0: 22-22 6: √((22/2)-2)! 12: (2+22)/2 18: 22-(2^2) 24: 2+(√22^2) 30: (2+(2^2))/.2 1: 22/22 7: 2+(2/(2*.2)) 13: 2+(22/2) 19: (2+(2-.2))/.2 25: (2-2.2)^-2 2: (2^2)!-22 8: 2+(2+(2^2)) 14: (2^(2^2))-2 20: 22-(√2^2) 26: 2+(2+22) 3: √((22/2)-2) 9: (22/2)-2 15: (2+(2/2))/.2 21: 22-(2/2) 27: 22+(√.2^-2) 4: .2*(22-2) 10: 22/2.2 16: 2*(2*(2^2)) 22: √22*√22 28: 2+(2+(2^2)!) 5: 2+(2+(2/2)) 11: 22/(√2^2) 17: 22-(√.2^-2) 23: 22+(2/2) 29: 2+(2+(.2^-2))
show((9, 9, 9, 9))
Can make 0 to 61 with (9, 9, 9, 9), ops="+-*/^_√!.,", permute=False. [791,279 table entries] 0: 99-99 13: 9+(√9+(9/9)) 26: (9*√9)-(9/9) 39: √9!+(99/√9) 52: √9!*(9-(√9/9)) 1: 99/99 14: √9+(99/9) 27: 9*√(9.9-.9) 40: (9-√9)!/(9+9) 53: (9*√9!)-(9/9) 2: (99/9)-9 15: (99-9)/√9! 28: 9+(9+(9/.9)) 41: (.9+(√9!*√9!))/.9 54: 9*(9-(9/√9)) 3: √√(99-(9+9)) 16: (99-√9)/√9! 29: 9+((9+9)/.9) 42: 9+(99/√9) 55: 99/(.9+.9) 4: √9+(9^(9-9)) 17: √9!+(99/9) 30: (99-9)/√9 43: √9+(√9!/(.9/√9!)) 56: 9!/(9*(9-√9)!) 5: (99/9)-√9! 18: 99-(9*9) 31: (99-√9!)/√9 44: (9*√9!)-(9/.9) 57: √9*(9+(9/.9)) 6: √((9+99)/√9) 19: 9+(9+(9/9)) 32: (99-√9)/√9 45: 99-(9*√9!) 58: √9!*(9+(√9!/9)) 7: 9-((9+9)/9) 20: 9+(99/9) 33: √9/(9/99) 46: (9/.9)+(√9!*√9!) 59: ((9*√9!)-.9)/.9 8: (99/9)-√9 21: (9+9.9)/.9 34: (√9+99)/√9 47: √9*(9+(√9!/.9)) 60: 9/(.9/(9-√9)) 9: √(99-(9+9)) 22: 9+(√9+(9/.9)) 35: (√9!+99)/√9 48: √9!*(9-(9/9)) 61: (.9+(9*√9!))/.9 10: 99/9.9 23: √9+((9+9)/.9) 36: (9+99)/√9 49: 9+(√9!/(.9/√9!)) 11: 99/√(9*9) 24: (99/√9)-9 37: (9/.9)+(9*√9) 50: ((9*√9!)-9)/.9 12: (9+99)/9 25: 9+(√9!+(9/.9)) 38: √9!*(√9+(√9/.9)) 51: 9*(9-(√9/.9))
show((5, 5, 5, 5))
Can make 0 to 38 with (5, 5, 5, 5), ops="+-*/^_√!.,", permute=False. [345,331 table entries] 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 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) 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)) 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 4: √(5+(55/5)) 11: 5.5+5.5 18: ((5!-5)/5)-5 25: .5*(55-5) 32: (5.5-5)^-5 5: (.5*5!)-55 12: (5+55)/5 19: (5!-(5*5))/5 26: (5/5)+(5*5) 33: .5*(5!*.55) 6: (55/5)-5 13: (5!-55)/5 20: 5*(5-(5/5)) 27: (5*5.5)-.5 34: 5+(5+(5!/5))
Now another type of New Year's countdown puzzle. On December 31 2017, Michael Littman posted this:
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!
Can we replicate that countdown? For 2018 and for following years?
def countdowns(years: Sequence[int]):
"""Print a countdown of expressions with values from 10 to 0, using the digits (in order) of each year."""
def countdown(i, year): return f"{unbracket(expressions(digits(year), ops='+-*/_√!,')[i]):16}"
for i in reversed(range(11)):
print(f'{i:2d}:', *[countdown(i, year) for year in years])
def digits(n: int) -> Numbers: return tuple(int(d) for d in str(n))
countdowns(range(2018, 2025))
10: 2-(0-(1*8)) 20-(1+9) 20/(2-0) 20/(2/1) 20/√(2+2) √(20*(2+3)) 20*(2/4) 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 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 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) 6: √(2*(0+18)) (2+(0/19)!)! (2+(0/20)!)! (2+(0/21)!)! √((20-2)*2) (-20+23)! (20/2)-4 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) 4: √(-2-(0-18)) √(20-(1+√9)) 2-(0-(2-0)) 2-(0-(2/1)) √(20-(2+2)) 20/(2+3) -20+24 3: 2+(0/18)! 2+(0/19)! 2+(0/20)! 2+(0/21)! 2+(0/22)! -20+23 2+(0/24)! 2: 20-18 2-(0/19) 2-(0/20) 2-(0/21) -20+22 2-(0/23) √(-20+24) 1: 2-(0/18)! 20-19 20/20 -20+21 2-(0/22)! 2-(0/23)! 2-(0/24)! 0: 2*(0/18) 2*(0/19) 20-20 2*(0/21) 2*(0/22) 2*(0/23) 2*(0/24)
In the 538 Riddler for July 10th 2020, 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.
Solving Zach's puzzle is easy enough:
expressions((2, 3, 3, 4), '+-*/^', permute=True)[24]
'(((3^2)-3)*4)'
For extra credit, Zach asks for multiple ways to make 24.
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.
def can_make(total: int, numbers: tuple, ops='+-*/^') -> Set[Exp]:
"""Can we make the total from the numbers (in any order)? Return a set of expressions."""
return {expressions(nums, ops).get(total)
for nums in permutations(numbers)} - {None}
can_make(24, (2, 3, 3, 4))
{'(((3^2)-3)*4)', '(((4/2)^3)*3)', '(3*((4/2)^3))', '(3*(4^(3/2)))', '(3/((2/4)^3))', '(4*((3^2)-3))'}
Readers suggested other interesting tuples of numbers:
can_make(24, (2, 3, 8, 8))
{'(((2*8)-8)*3)', '((2^(8-3))-8)', '((2^3)+(8+8))', '((8-(3+2))*8)', '((8^2)/(8/3))', '(3*((8^2)/8))', '(3/(2/(8+8)))', '(3/(8/(8^2)))', '(8*(8-(3+2)))', '(8+((2^3)+8))', '(8+(8+(2^3)))'}
can_make(24, (2, 3, 10, 10))
{'(((10-3)*2)+10)', '((2*(10-3))+10)', '((2^10)-(10^3))', '(10+((10-3)*2))', '(10+(2*(10-3)))', '(10-((3-10)*2))', '(10-(2*(3-10)))'}
can_make(24, (3, 3, 8, 8))
{'(8/(3-(8/3)))'}
can_make(24, (2, 3, 6, 6))
{'(((3*6)-6)*2)', '(((3+2)*6)-6)', '(((3+6)*2)+6)', '(2*(6*(6/3)))', '(2*(6/(3/6)))', '(2/(3/(6*6)))', '(6*(2/(3/6)))', '(6*(2^(6/3)))', '(6*(6*(2/3)))', '(6*(6/(3/2)))', '(6/(3/(2*6)))', '(6/(3/(6*2)))'}
can_make(24, (0, 0, 2, 5))
{'((5^2)-(0^0))'}
This relies on 00 = 1, which Python agrees with, but some mathematicians treat as undefined.
Nicolas Schank asked for the following in the Facebook "omg math" group:
can_make(24, (13, 11, 10, 6), '+-*/^!')
{'(10-(6/(13-11))!)!'}
can_make(24, (9, 8, 1, 1), '+-*/^!')
{'(8/((1^9)+1))!', '(8/(1+(1^9)))!'}
can_make(24, (9, 7, 7, 7), '+-*/^!')
{'(9!/(7!+(7!+7!)))'}
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."
We can find all the license plates for which there is a solution:
def show_plates(digits=4, target=24):
"""Show all license plates that can make 24."""
plates = list(combinations_with_replacement(range(10), 4))
def solve(plate): return expressions(plate, ops='+-*/', permute=True).get(24)
solved = [f"{cat(plate)}: {unbracket(solve(plate))} "
for plate in plates if solve(plate)]
print(f'{len(solved)} out of {len(plates)} distinct license plates can be solved:\n')
show_columns(solved)
show_plates()
466 out of 715 distinct license plates can be solved: 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 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) 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)) 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)) 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) 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)) 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)) 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)) 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 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)) 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)) 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)) 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 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)) 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)) 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)) 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) 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)) 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)) 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)) 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)) 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)) 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)) 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) 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)) 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 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)) 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)) 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)) 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)) 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)) 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)) 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)) 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)) 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)) 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 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 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 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) 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) 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)) 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) 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) 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)) 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)) 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) 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) 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) 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) 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 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)) 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) 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) 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 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) 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) 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 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 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 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) 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 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 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) 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) 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)) 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)) 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)) 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)) 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) 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) 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)) 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) 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) 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) 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)) 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) 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)) 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))
Another Facebook "omg math" problem:
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.
This is easy if "arithmetic operations" include square root and factorial:
for n in range(10):
print(f"6: {expressions((n, n, n), '+-*/√!').get(6)}")
6: (0!+(0!+0!))! 6: (1+(1+1))! 6: (2+(2+2)) 6: ((3*3)-3) 6: (4+(4/√4)) 6: (5+(5/5)) 6: (6/(6/6)) 6: (7-(7/7)) 6: (8-√√(8+8)) 6: (9-(9/√9))
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.
I'll just show the first 300, to save space:
%time show((4, 4, 4, 4), limit=300, ops=OPS + "⌊⌈")
Can make 0 to 1644 with (4, 4, 4, 4), ops="+-*/^_√!.,⌊⌈", permute=False. [1,205,301 table entries] 0: 44-44 60: 44+(4*4) 120: ⌈4.444⌉! 180: 4+(4*44) 240: √4*⌈4.44⌉! 1: 44/44 61: ⌈(.44^-⌈4.4⌉)⌉ 121: (44/4)^√4 181: ⌊(4*(√√4+44))⌋ 241: (.4+(4*4!))/.4 2: √⌊4.444⌋ 62: ⌊(√√4*44.4)⌋ 122: √4+⌈4.44⌉! 182: ⌈(4*(√√4+44))⌉ 242: √4+(4/(.4/4!)) 3: 4-⌈.444⌉ 63: ⌈(√√4*44.4)⌉ 123: ⌈(4*(4!+√44))⌉ 183: 4!+⌊(4!*√44)⌋ 243: (4-⌈.4⌉)^⌈4.4⌉ 4: ⌊4.444⌋ 64: 4!-(4-44) 124: 4+⌈4.44⌉! 184: 4*(√4+44) 244: 4+(4/(.4/4!)) 5: ⌈4.444⌉ 65: (4+(4^4))/4 125: ⌈(44*√(4+4))⌉ 185: ⌈((44-4)^√√4)⌉ 245: (√4+(4*4!))/.4 6: ⌊√44.44⌋ 66: ⌊(44/√.44)⌋ 126: ⌊√44⌋+⌈4.4⌉! 186: ⌈((4+4!)*√44)⌉ 246: (4^4)-(4/.4) 7: ⌈√44.44⌉ 67: ⌈(44/√.44)⌉ 127: ⌈√44⌉+⌈4.4⌉! 187: ⌊(4.4^4)⌋/√4 247: ⌊(4^(4-(.4^4)))⌋ 8: 4+⌊4.44⌋ 68: 4!+⌊44.4⌋ 128: √4^⌈√44.4⌉ 188: (4!*(4+4))-4 248: (4^4)-(4+4) 9: 4+⌈4.44⌉ 69: 4!+⌈44.4⌉ 129: 4!+⌊(4!*4.4)⌋ 189: ⌊(⌈4.44⌉!/√.4)⌋ 249: (4^4)-⌈√44⌉ 10: 44/4.4 70: 4!+(√4+44) 130: (4+(4^4))/√4 190: (4!*(4+4))-√4 250: (4^4)-⌊√44⌋ 11: 44/⌊4.4⌋ 71: ⌈(44.4/√.4)⌉ 131: ⌈(4!*(4!/4.4))⌉ 191: ⌊(√4!*44)⌋-4! 251: (4^4)-⌈4.4⌉ 12: (4+44)/4 72: 4+(4!+44) 132: 44*(4-⌈.4⌉) 192: 4*(4+44) 252: (4^4)-⌊4.4⌋ 13: 4!-(44/4) 73: 4+⌊(44/√.4)⌋ 133: ⌈((4!-4)*√44)⌉ 193: ⌊(44*4.4)⌋ 253: ⌊(4!*(4!*.44))⌋ 14: ⌈(√44+√44)⌉ 74: 4+⌈(44/√.4)⌉ 134: 4!+(44/.4) 194: ⌈(44*4.4)⌉ 254: √4-(4-(4^4)) 15: 4+(44/4) 75: ⌊((4+44)/√.4)⌋ 135: ⌊(4!/.44)⌋/.4 195: ⌊(√4!*(44-4))⌋ 255: (4^4)-(4/4) 16: 4*⌊4.44⌋ 76: ⌈4.4⌉!-44 136: √4*(4!+44) 196: 4+(4!*(4+4)) 256: 4^⌊4.44⌋ 17: ⌊(4*4.44)⌋ 77: ⌈(44*(4^.4))⌉ 137: ⌈(4!/(.4*.44))⌉ 197: ⌈(44*√(4!-4))⌉ 257: (4^4)+(4/4) 18: ⌈(4*4.44)⌉ 78: ⌊(4*(4!-4.4))⌋ 138: √4*⌊(44/√.4)⌋ 198: √4*⌊(√4^√44)⌋ 258: 4-(√4-(4^4)) 19: ⌈(444/4!)⌉ 79: ⌈(4*(4!-4.4))⌉ 139: ⌊(4^(4-.44))⌋ 199: ⌈(√4*(√4^√44))⌉ 259: ⌊(√44/(.4^4))⌋ 20: 4*⌈4.44⌉ 80: 4*(44-4!) 140: 44+(4*4!) 200: 4!+(4*44) 260: 4+(4^⌊4.4⌋) 21: ⌈44.4⌉-4! 81: (4-(4/4))^4 141: ⌈((.4^-4.4)/.4)⌉ 201: ⌊(4!*(4+4.4))⌋ 261: (4^4)+⌈4.4⌉ 22: √4/(4/44) 82: ⌊((4/.44)^√4)⌋ 142: (4!*⌊√44⌋)-√4 202: ⌈(4!*(4+4.4))⌉ 262: (4^4)+⌊√44⌋ 23: 4!-⌈.444⌉ 83: 44+⌊(.4^-4)⌋ 143: ((4!*4!)-4)/4 203: ⌊(44*(4+√.4))⌋ 263: (4^4)+⌈√44⌉ 24: ⌊4.444⌋! 84: (√4*44)-4 144: 4!*⌊√44.4⌋ 204: ⌈(44*(4+√.4))⌉ 264: 44*⌊√44⌋ 25: 4!+⌈.444⌉ 85: ⌈(4*(√4^4.4))⌉ 145: (4+(4!*4!))/4 205: ⌊(√4!*(44-√4))⌋ 265: ⌈(4!*4.4)⌉/.4 26: 4+(44/√4) 86: (√4*44)-√4 146: √4+(4!*⌊√44⌋) 206: ⌊(44^√√4)⌋-4 266: (4^4)+(4/.4) 27: ⌈(4*√44.4)⌉ 87: (√4*44)-⌈.4⌉ 147: ⌊(44^(√4^.4))⌋ 207: ⌈(44^√√4)⌉-4 267: ⌊(4!*(√4!/.44))⌋ 28: 44-(4*4) 88: 44+44 148: 4+(4!*⌊√44⌋) 208: ⌈(4.4^(4-.4))⌉ 268: ⌊(4!^(4*.44))⌋ 29: 4!+⌈4.44⌉ 89: ⌈(√4*44.4)⌉ 149: ⌊(.4*(4.4^4))⌋ 209: ⌈(√⌈4.4⌉^√44)⌉ 269: ⌈(4!^(4*.44))⌉ 30: ⌈4.44⌉!/4 90: √4*⌈44.4⌉ 150: .4*⌈(4.4^4)⌉ 210: ⌊(44^√(4/√4))⌋ 270: ⌈(4!^(4^√(4/4!)))⌉ 31: 4!+⌈√44.4⌉ 91: ⌈(444/√4!)⌉ 151: ⌊(4!*√(44-4))⌋ 211: ⌊(√4!*44)⌋-4 271: ⌊((√4!^4.4)/4)⌋ 32: √4^⌈4.44⌉ 92: 4+(√4*44) 152: (4*44)-4! 212: (4^4)-44 272: 4*(4!+44) 33: ⌊(4*(4+4.4))⌋ 93: ⌊((4.4^4)/4)⌋ 153: ⌊(4!*(√4+4.4))⌋ 213: ⌊(44.4^√√4)⌋ 273: ⌊(4^(4!^.44))⌋ 34: 44-(4/.4) 94: ⌈((4.4^4)/4)⌉ 154: (4!-√4)*⌈√44⌉ 214: ⌈(44.4^√√4)⌉ 274: ⌈(4^(4!^.44))⌉ 35: 4!+(44/4) 95: (4*4!)-(4/4) 155: ⌊(4!*√44)⌋-4 215: 4+⌈(44^√√4)⌉ 275: 44/(.4*.4) 36: 44-(4+4) 96: 4*⌊4.44⌋! 156: 4*⌊(44-√4!)⌋ 216: 4*⌊(4!/.44)⌋ 276: 4*⌊(44/√.4)⌋ 37: 44-⌈√44⌉ 97: (4/4)+(4*4!) 157: ⌈(4*(44-√4!))⌉ 217: ⌊(√4!*44.4)⌋ 277: ⌈(4!*(√4!+√44))⌉ 38: 44-⌊√44⌋ 98: ⌊(44*√⌈4.4⌉)⌋ 158: ⌊(44*(4-.4))⌋ 218: ⌈(√4!*44.4)⌉ 278: ⌊(4/(√.4/44))⌋ 39: 44-⌈4.4⌉ 99: ⌊(4^√(44/4))⌋ 159: ⌊(4!*√44.4)⌋ 219: 4+⌊(√4!*44)⌋ 279: ⌈(4/(√.4/44))⌉ 40: 44-⌊4.4⌋ 100: 44/.44 160: 4*(44-4) 220: 44*⌈4.4⌉ 280: ⌊(√.4*444)⌋ 41: ⌈44.4⌉-4 101: ⌊(√4^√44.4)⌋ 161: ⌈((4-.44)^4)⌉ 221: ⌈(√4!*⌈44.4⌉)⌉ 281: ⌈(√.4*444)⌉ 42: √4-(4-44) 102: ⌈(√4^√44.4)⌉ 162: √4+⌈(4!*√44)⌉ 222: 444/√4 282: 4!+(√4+(4^4)) 43: 44-(4/4) 103: 4+⌊(√4^√44)⌋ 163: 4+⌊(4!*√44)⌋ 223: ⌈(4^4.4)⌉/√4 283: ⌈((4+(.4/4))^4)⌉ 44: ⌊44.44⌋ 104: 44+(4!/.4) 164: 44+⌈4.4⌉! 224: (4+4)*(4+4!) 284: 4+(4!+(4^4)) 45: ⌈44.44⌉ 105: (44-√4)/.4 165: ⌈(√4!+(4!*√44))⌉ 225: ⌊(4/(.4^4.4))⌋ 285: ⌊(⌈√44⌉!^√.44)⌋ 46: 4+(44-√4) 106: (44/.4)-4 166: ⌊(4!*√(4+44))⌋ 226: ⌈(4/(.4^4.4))⌉ 286: ⌊(√4!^(4-.44))⌋ 47: √4+⌈44.4⌉ 107: ⌈(4!*4.44)⌉ 167: ⌈(4!*√(4+44))⌉ 227: 4+⌈((4^√4!)/4)⌉ 287: ⌈(√4!^(4-.44))⌉ 48: 4+⌊44.4⌋ 108: (44/.4)-√4 168: 4*(44-√4) 228: (4^4)-(4+4!) 288: 4!*(4+(4+4)) 49: 4+⌈44.4⌉ 109: (44-.4)/.4 169: ⌊√(4*44)⌋^√4 229: ⌈(4^(4-(√4/4!)))⌉ 289: ⌊(4*4.4)⌋^√4 50: 44+⌊√44⌋ 110: ⌊44.4⌋/.4 170: (4!+44)/.4 230: (4^4)-(4!+√4) 290: (⌈4.4⌉!-4)/.4 51: 44+⌈√44⌉ 111: 444/4 171: ⌈(4*(44-√√4))⌉ 231: ⌊(.44^-√44)⌋ 291: ⌊(44*√44)⌋ 52: 4+(4+44) 112: 4!+(√4*44) 172: (4*44)-4 232: ⌈(.44^-√44)⌉ 292: ⌈(44*√44)⌉ 53: ⌊(4*√(4*44))⌋ 113: ⌈(.44*(4^4))⌉ 173: ⌊(4*(44-√.4))⌋ 233: ⌈(44*√(4+4!))⌉ 293: (4^4)+⌊(4!/√.4)⌋ 54: 44+(4/.4) 114: 4+(44/.4) 174: (4*44)-√4 234: 4!+⌊(44^√√4)⌋ 294: ⌊(4^(4+(.4/4)))⌋ 55: ⌈(4!/.444)⌉ 115: (√4+44)/.4 175: (4*44)-⌈.4⌉ 235: ⌊(√4!*(4+44))⌋ 295: (⌈4.4⌉!-√4)/.4 56: 44+(4!/√4) 116: ⌈4.44⌉!-4 176: 4*⌊44.4⌋ 236: 4-(4!-(4^4)) 296: (⌈4.4⌉!/.4)-4 57: ⌈(√√4*(44-4))⌉ 117: ⌈(44*√⌈√44⌉)⌉ 177: ⌊(4*44.4)⌋ 237: ⌊(√.4*(4.4^4))⌋ 297: ⌈(√√4*⌊(44^√√4)⌋)⌉ 58: ⌊(.4^-4.44)⌋ 118: ⌈4.44⌉!-√4 178: ⌈(4*44.4)⌉ 238: ⌊((4+44)^√√4)⌋ 298: (⌈4.4⌉!/.4)-√4 59: ⌈(.4^-4.44)⌉ 119: ⌈4.4⌉!-(4/4) 179: ⌈(4*(√.4+44))⌉ 239: ⌈((4+44)^√√4)⌉ 299: (⌈4.4⌉!-.4)/.4 CPU times: user 14.4 s, sys: 120 ms, total: 14.5 s Wall time: 14.6 s
We could get up to 2892 with nesting level 3, but that takes multiple minutes.
In the xkcd forum they took up the problem of five 5s and got all the integers up to 298, using the "double factorial function" and π 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:
%time show((5, 5, 5, 5, 5))
Can make 0 to 171 with (5, 5, 5, 5, 5), ops="+-*/^_√!.,", permute=False. [14,827,653 table entries] 0: 5*(55-55) 43: 55-(5!/(5+5)) 86: (55/.5)-(5!/5) 129: (5!-55.5)/.5 1: 5^(55-55) 44: 55-(55/5) 87: (555-5!)/5 130: 5!+(55/5.5) 2: 55/(5*5.5) 45: (5*5!)-555 88: 5/((.5^5)/.55) 131: 5!+(5.5+5.5) 3: √(5!-(555/5)) 46: 55-((5-.5)/.5) 89: 5!+((5!/5)-55) 132: 5!*(.55+.55) 4: 5-(55/55) 47: 55-√((.5^-5)/.5) 90: 5!-(55-(5*5)) 133: 5!+((5!-55)/5) 5: 5.55-.55 48: 5!/(5*(5.5-5)) 91: (5*5)+(5!*.55) 134: (5!/5)+(55/.5) 6: 5+(55/55) 49: 55-(.5+5.5) 92: 5+(55+(.5^-5)) 135: (5!+555)/5 7: ((5+55)/5)-5 50: 55.5-5.5 93: .5+(5!-(5*5.5)) 136: 5+(5!+(55/5)) 8: .5*(5+(55/5)) 51: .5-(5-55.5) 94: 5!-((5/5)+(5*5)) 137: 5+(5!/(5/5.5)) 9: 5!-(555/5) 52: 55-(.5+(5*.5)) 95: (55/.55)-5 138: .5+(5*(5*5.5)) 10: 5!-(55+55) 53: 55.5-(5*.5) 96: 5!-√(5+(55/5))! 139: ((.5+5.5)!/5)-5 11: 55/(5.5-.5) 54: 55-(5^(5-5)) 97: 5!-(55-(.5^-5)) 140: .5*(5+(5*55)) 12: 5!/(55/5.5) 55: .5*(55+55) 98: 5!-(55/(5*.5)) 141: 5!+((5+5.5)/.5) 13: (5+(5+55))/5 56: 55+(5^(5-5)) 99: (55-5.5)/.5 142: 5!+(55/(5*.5)) 14: (5*5)-(55/5) 57: 55+((5+5)/5) 100: (55/.5)-(5+5) 143: 5!+(55-(.5^-5)) 15: 5+(55/5.5) 58: (5*.5)+55.5 101: (55.5-5)/.5 144: ((55/5)-5)!/5 16: 5+(5.5+5.5) 59: 5-((5/5)-55) 102: 5+(5!+((5-5!)/5)) 145: 5!+(.5*(55-5)) 17: 5+((5+55)/5) 60: 5+(√55*√55) 103: 55+(5!/(5*.5)) 146: 5!+((5/5)+(5*5)) 18: 5+((5!-55)/5) 61: 5.5+55.5 104: 5!-(5+(55/5)) 147: 5!-(.5-(5*5.5)) 19: (5*5)-(.5+5.5) 62: (55-(5!/5))/.5 105: 55-(5-55) 148: .5+(5!+(5*5.5)) 20: 55/(5*.55) 63: 5.5-(.5*(5-5!)) 106: (555/5)-5 149: 5+((.5+5.5)!/5) 21: 5+(5+(55/5)) 64: 5!-(.5+55.5) 107: 5!-((5!-55)/5) 150: 5*(55-(5*5)) 22: (55+55)/5 65: .5+(5!-55.5) 108: 5!-((5+55)/5) 151: 5!-((5!/5)-55) 23: (5+(55/.5))/5 66: 55+(55/5) 109: 5!-(5.5+5.5) 152: 5!+((5.5-5)^-5) 24: (5-(55/55))! 67: 55+(5!/(5+5)) 110: (555-5)/5 153: 5!+(.5*(5!*.55)) 25: 55-(5+(5*5)) 68: 5.5+(.5*(5+5!)) 111: 555/√(5*5) 154: 5+(5+(5!+(5!/5))) 26: 55-(5+(5!/5)) 69: 5+(.5^(-.5-5.5)) 112: (5+555)/5 155: 5*(55-(5!/5)) 27: 5+(55/(5*.5)) 70: 5+(5+(5+55)) 113: 5!-(5+((5+5)/5)) 156: (5!+(5!*5.5))/5 28: .5*(.5+55.5) 71: 55+(.5/(.5^5)) 114: 5+(5!-(55/5)) 157: (.5^-5)+(5*(5*5)) 29: 5+√(5+(55/5))! 72: 5!*((5.5/5)-.5) 115: 5+(55+55) 158: (55+(5!/5))/.5 30: 5*((55/5)-5) 73: (5*5)+(5!/(5*.5)) 116: 5+(555/5) 159: (5/(.5^5))-(5/5) 31: 55-(5-(5/5))! 74: 55-(5-(5!/5)) 117: 5!-(5.5-(5*.5)) 160: 5/((5.5-5)^5) 32: √.5^(55/-5.5) 75: 55-(5-(5*5)) 118: 5!-(5!/(5+55)) 161: (5/5)+(5/(.5^5)) 33: .55*(5+55) 76: 5+(5+(5!*.55)) 119: 5!-(55/55) 162: 5+(5+(5!+(.5^-5))) 34: (5!-(5-55))/5 77: 5+(.5*(5!+(5!/5))) 120: (5.55-.55)! 163: 5!-(5-(5!/(5*.5))) 35: 5+(55-(5*5)) 78: 55-((5-5!)/5) 121: 5!+(55/55) 164: 5!+(.5*(5!-(.5^-5))) 36: (5*5)+(55/5) 79: 55+(5-(5/5))! 122: 5!+(5!/(5+55)) 165: 55+(55/.5) 37: 5+((5.5-5)^-5) 80: 5*(5+(55/5)) 123: 5!+(5.5-(5*.5)) 166: 5!-((5-5!)/(5*.5)) 38: 5+(.5*(5!*.55)) 81: 5+(.5*(5!+(.5^-5))) 124: 5!+√(5+(55/5)) 167: 5!-((5-(5!/.5))/5) 39: 55-(.5/(.5^5)) 82: 55-(5-(.5^-5)) 125: 5*(.5*(55-5)) 168: (5!+(.5+5.5)!)/5 40: 55-(5+(5+5)) 83: (.5*5!)-((5-5!)/5) 126: 5!+((55/5)-5) 169: 5!+((5*5)+(5!/5)) 41: 5!-(55+(5!/5)) 84: 5+(55+(5!/5)) 127: (5!/(5/5.5))-5 170: 5!-(√(5*5)-55) 42: (5+5.5)/(.5*.5) 85: 5+(55+(5*5)) 128: 5!+(5.5+(5*.5)) 171: (5.5/(.5^5))-5 CPU times: user 2min 21s, sys: 2.05 s, total: 2min 23s Wall time: 2min 24s
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)
.
@cache
def f(n, ops='+-*/^,') -> int:
"""The smallest integer inexpressible in digits 0 thru n."""
return unmakeable(expressions(range(n + 1), ops, permute=True))
for n in range(6):
print(f'f({n}) = {f(n)}')
f(0) = 1 f(1) = 2 f(2) = 4 f(3) = 25 f(4) = 175 f(5) = 1099
One exercise would be adding even more operations, such as:
3√8
= 250%
= 0.5|1-3|
= 2 (redundant if you have unary minus, but add it if you like it).4...
= .44444444... = 4/91>(2<3)
= 0, because (2<3)
is True, which is treated as 1
, and 1>1
is False, or 0
9!!
= 9 × 7 × 5 × 3 × 1 = 945; not the same as (9!)!
Γ(n)
= (n − 1)! and works for non-integersπ(n)
= number of primes ≲ n; e.g. π(5)
= 3log
, sin
cos
, tan
, arcsin
, ...180°
= πlog_10(100)
= 26 C_ 2
= 15; 6 P_ 2
= 30Another approach would be to look around for related puzzles and solve them. What do you want to do?