<jupyter_start><jupyter_text><NAME>Jan 2016revised 2018, 2020 Four 4s, Five 5s, Countdowns, and Equilength Number NamesOn January 1, 2016 <NAME> [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) this New Year's puzzle:> 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: +, -, &times;, ÷. But brackets (parentheses) can be used wherever needed. So, for example, the solution could begin>> `(10 + 9) * (8` ...  or  `10 + (9 * 8)` ...Let's see if we can solve this puzzle, and some of the related ones from Alex's [first](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 [second](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) post.  First the imports we will eventually need.<jupyter_code>from itertools   import product
from functools   import lru_cache
from fractions   import Fraction
from collections import Counter, defaultdict
import re<jupyter_output><empty_output><jupyter_text>Four Basic Operators, No BracketsWe'll start with a  simpler version of the puzzle: a countdown with no brackets.   There are nine blanks,  each of which can be filled by one of four operators, so there are 94 = 262,144 possibilities, few enough that we can enumerate them all, using `itertools.product` to get tuples of operators, and then `str.format` to plug them into blanks, and then `eval` to evaluate the string:<jupyter_code>allops = list(product(('+', '-', '*', '/'), repeat=9))

allops[::30001] # Sample a few ops tuples (every 30,001 one)
'10{}9{}8{}7{}6{}5{}4{}3{}2{}1'.format(*allops[0])
eval(_)<jupyter_output><empty_output><jupyter_text>(*Warning*: don't use eval on strings that you aren't sure are safe from bad effects.)We need to catch errors such as dividing by zero, so I'll define a wrapper function, `evaluate`, to do that, and I'll define `simple_countdown` to put the pieces together:<jupyter_code>def evaluate(exp):
    "eval(exp), or None if there is an arithmetic error."
    try:
        return eval(exp)
    except ArithmeticError:
        return None

def simple_countdown(target, operators=('+', '-', '*', '/')):
    "All solutions to the countdown puzzle (with no brackets)."
    exps = ('10{}9{}8{}7{}6{}5{}4{}3{}2{}1'.format(*ops)
            for ops in product(operators, repeat=9))
    return [exp for exp in exps if evaluate(exp) == target]
simple_countdown(2016)<jupyter_output><empty_output><jupyter_text>Too bad; we did all that work and didn't find a solution. What years *can* we find solutions for? I'll define `simple_countdowns` to take a collection of target years rather than a single one, and return a dict of the form `{year: 'expression'}` for each expression that evaluates to one of the target years. I'll also generalize it to allow any format string, with the default being the countdown string.<jupyter_code>def simple_countdowns(targets, operators=('+', '-', '*', '/'), 
                      fmt='10{}9{}8{}7{}6{}5{}4{}3{}2{}1'):
    "All solutions to the countdown puzzle (with no brackets) in target years."
    exps = (fmt.format(*ops)
            for ops in product(operators, repeat=fmt.count('{}')))
    return {int(evaluate(exp)): exp 
            for exp in exps if evaluate(exp) in targets}

simple_countdowns(range(1900, 2100))<jupyter_output><empty_output><jupyter_text>Interesting: in the 20th and 21st centuries, there are only two "golden eras" where the bracketless countdown equation works: the three year period centered on 1980, and the seven year period that is centered on 2016, but omits 2016.   Four  Basic Operators, With BracketsNow we return to the original problem. Can I make use of what I have so far? Well, my second version of `simple_countdown` accepts different format strings, so I could give it all possible bracketed format strings and let it fill in all possible operator combinations. How long would that take? I happen to remember that the number of bracketings of *n* operands is the nth [Catalan number](https://oeis.org/A000108), which I looked up and found to be 4862. A single call to `simple_countdown` took about 2 seconds, so we could do 4862 calls in about 160 minutes. That's not terrible, but (a) it would still take work to generate all the bracketings, and (b) I think I can find another way that is much faster.I'll restate the problem as: given the sequence of numbers (10, 9, ... 1), create an expression whose value is 2016. But to get there I'll solve a more general problem: given any sequence of numbers, like `(10, 9, 8)`, what `{value: expression}` pairs can I make with them? I'll define  `expressions(numbers)` to return a dict of `{value: expression}` for all expressions (strings) whose numeric value is `value`, and can be made from `numbers`, for example:    expressions((10,)) ⇒ {10: '10'}    expressions((9, 8)) ⇒ {1: '(9-8)', 1.125: '(9/8)', 17: '(9+8)', 72: '(9*8)'}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 so we don't need to re-compute them later. How do we break the problem into parts? `expressions((10, 9, 8))` should consist of all the ways of splitting `(10, 9, 8)` into two parts, finding all the expressions that can be made with each part, and combining pairs of expressions with any of the four operators:    expressions((10, 9, 8)) ⇒ {11: '(10+(9-8))', 27: '(10+(9+8))', 720: '(10*(9*8))', ...}First the function `splits`:<jupyter_code>c10 = (10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

def splits(sequence):
    "Split sequence into two non-empty parts, in all ways."
    return [(sequence[:i], sequence[i:]) 
            for i in range(1, len(sequence))]
splits(c10)<jupyter_output><empty_output><jupyter_text>Now the function `expressions`:<jupyter_code>@lru_cache(None)
def expressions(numbers: tuple) -> dict:
    "Return {value: expr} for all expressions that can be made from numbers."
    if len(numbers) == 1: 
        return {numbers[0]: str(numbers[0])}
    else: 
        result = {}
        for (Lnums, Rnums) in splits(numbers):
            for (L, R) in product(expressions(Lnums), expressions(Rnums)):
                Lexp =  '(' + expressions(Lnums)[L]
                Rexp =        expressions(Rnums)[R] + ')'
                result[L * R] = Lexp + '*' + Rexp
                result[L - R] = Lexp + '-' + Rexp
                result[L + R] = Lexp + '+' + Rexp
                if R != 0: 
                    result[L / R] = Lexp + '/' + Rexp
        return result<jupyter_output><empty_output><jupyter_text>For example, at one point in a call to `expressions((10, 9, 8))` we would have:     Lnums, Rnums = (10),   (9, 8)     L,     R     = 10,     1     Lexp,  Rexp  = '(10',  '(9-8))'This would lead to us adding the following four entries to `result`:     result[10] = '(10*(9-8))'     result[9]  = '(10-(9-8))'     result[11] = '(10+(9-8))'     result[10] = '(10/(9-8))'     The decorator `@lru_cache` takes care of storing the intermediate results. Rather than catching errors, we just avoid division by 0.Let's give it a try:<jupyter_code>expressions((10,))
expressions((9, 8))
expressions((10, 9, 8))<jupyter_output><empty_output><jupyter_text>That looks reasonable. Let's solve the whole puzzle. Countdown to 2016: A Solution<jupyter_code>%time expressions(c10)[2016]<jupyter_output>CPU times: user 24 s, sys: 617 ms, total: 24.6 s
Wall time: 24.9 s<jupyter_text>We have an answer! And in seconds, not hours, thanks to dynamic programming! Here are solutions for nearby years:<jupyter_code>{y: expressions(c10)[y] for y in range(2010, 2026)}<jupyter_output><empty_output><jupyter_text>Counting Solutions<NAME> had another challenge:  > I was half hoping a computer scientist would let me know exactly how many solutions [to the Countdown problem] there are with only the four basic operations. Maybe someone will. 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)`? Similarly, are `((3-2)-1)` and `(3-(2+1)` different, or the same because they both are equivalent to `(3 + -2 + -1)`? I think the notion of "distinct solution" is just inherently ambiguous. My choice is to count each of these as distinct: every expression has exactly ten numbers, nine operators, and nine pairs of brackets, and if an expression differs in any character, it is different. But I won't argue with anyone who prefers a different definition of "distinct solution."So how can I count expressions? One approach would be to go back to enumerating every equation (all 4862 &times; 49 = 1.2 bilion of them) and checking which ones equal 2016. That would take about 40 hours with my Python program. A better approach is to mimic `expressions`, but to make a table of counts, rather than expression strings. I want:    counts[(10, 9, 8)][27] == 2    because there are 2 ways to make 27 with the numbers `(10, 9, 8)`, namely, `((10+9)+8)` and `(10+(9+8))`. And in general, if there are `Lcount` ways to make `L` using `Lnums` and `Rcount` ways to make `R` using `Rnums` then there are `Lcount * Rcount` ways of making `L * R` using `Lnums` followed by `Rnums`. So we have:<jupyter_code>@lru_cache(None)
def counts(numbers: tuple) -> Counter:
    "Return a Counter of {value: count} for every value that can be made from numbers."
    if len(numbers) == 1: # Only one way to make an expression out of a single number
        return Counter(numbers)
    else: 
        result = Counter()
        for (Lnums, Rnums) in splits(numbers):
            for L in counts(Lnums):
                for R in counts(Rnums):
                    count = counts(Lnums)[L] * counts(Rnums)[R]
                    result[L + R] += count
                    result[L - R] += count
                    result[L * R] += count
                    if R != 0:
                        result[L / R] += count
        return result
counts((2, 2)) # corresponds to {0: '2-2', 1.0: '2/2', 4: '2+2' or '2*2'}
counts((10, 9, 8))[27] # (10+9)+8 or 10+(9+8)<jupyter_output><empty_output><jupyter_text>Looks good to me. Now let's see if we can answer Alex's question.<jupyter_code>counts(c10)[2016]<jupyter_output><empty_output><jupyter_text>This says there are 30,066 distinct expressions for 2016. Is that the answer for Alex? What About Round-off Error?Let's find all the values in `counts(c10)` that are very near to `2016`, within ±0.0000000001:<jupyter_code>{y: counts(c10)[y] 
 for y in counts(c10)
 if abs(y - 2016) < 1e-10}<jupyter_output><empty_output><jupyter_text>I suspect that all of these actually should be *exactly* equal to 2016. If they were, then the total count would be:<jupyter_code>sum(_.values())<jupyter_output><empty_output><jupyter_text>To be absolutely sure, I could re-do *all* the calculations using exact rational arithmetic, as provided by the `Fraction` class. From experience I know that would be an order of magnitude slower if used everywhere, so instead I'll just verify the small set of expressions in the output above. The function `exact(exp)` returns a string that will exactly calculate `exp`:<jupyter_code>def exact(exp): return re.sub(r"([0-9]+)", r"Fraction(\1)", exp)

exact('1/(2+3)')
eval(_)<jupyter_output><empty_output><jupyter_text>Here are all the expressions near 2016:<jupyter_code>[(eval(exact(exp)), exp)
 for y, exp in expressions(c10).items()
 if abs(y - 2016) < 1e-10]<jupyter_output><empty_output><jupyter_text>They all evaluate to `Fraction(2016, 1)`, which is  `2016/1`  or just `2016`. This gives me more confidence in the  44,499 count, but I wouldn't accept it as definitive until it was independently verified and passed an extensive test suite. And of course, if you have a different definition of "distinct solution," you will get a different answer; there are multiple possible definitions that are all very reasonable.  Four 4sAlex Bellos continues with a related puzzle:    > The most famous “fill in the gaps in the equation” puzzle is known as the [four fours](https://en.wikipedia.org/wiki/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](https://archive.org/details/mathematicalrecr00ball) by the "most famous" mathematician/magician [W. W. Rouse Ball](https://en.wikipedia.org/wiki/W._W._Rouse_Ball). The solution is easy:<jupyter_code>{i: expressions((4, 4, 4, 4))[i] for i in range(10)}<jupyter_output><empty_output><jupyter_text>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, `lru_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.  New Mathematical OperationsBellos then writes:    > If you want to show off, you can introduce **new mathematical operations** such as powers, square roots, concatenation and decimals, ... or use the factorial symbol, `!`.Bellos is suggesting the following operations:- **Powers**: `(4 ^ 4)` is 4 to the fourth power, or 256.- **Square roots:** `√4` is the square root of 4, or 2.- **Concatenation:** `44` is forty-four.- **Decimals:** `4.4` is four and four tenths.- **Factorials** `4!` is 4 × 3 × 2 × 1, or 24.There are some complications to deal with:- **Irrationals**: `√2` is an irrational number; so we can't do exact rational arithmetic.- **Imaginaries**: `√-1` is an imaginary number; do we want to deal with that?- **Overflow**: `(10. ^ (9. ^ 8.))`, as a `float`, gives an `OverflowError`.- **Out of memory**: [`(10 ^ (9 ^ (8 * 7)))`](http://www.wolframalpha.com/input/?i=10+%5E+9+%5E+56), as an `int`, gives an `OutOfMemoryError` (even if your memory uses every atom on Earth).- **Infinite expressions**: We could add an infinite number of square root and/or factorial signs to any expression: `√√√√√√(4!!!!!!!!)`...- **Round-off error**: `(49*(1/49))` evaluates to `0.9999999999999999`, not `1`.We could try to manage this with *symbolic algebra*, perhaps using [SymPy](http://www.sympy.org/en/index.html), but that seems complicated, so instead I will make some arbitrary decisions:- Use floating point approximations for everything, rational or irrational.- Disallow irrationals.- Disallow overflow errors (a type of arithmetic error).- Put limits on what is allow for exponentiation.- Allow only two nested unary operations to avoid infinite expressions.I'll define the function `do` to do an arithmetic computation, catch any errors, and try to correct round-off errors. The idea is that since my expressions start with integers, any result that is very close to an integer is probably actually that 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 it should not be rounded off. Instead, I'll try to avoid such expressions by silently dropping any value whose magnitude is outside the range of 10-10 to 1010 (except of course I will accept an exact 0).<jupyter_code>from operator import add, sub, mul, truediv as div
from math import sqrt, factorial

def do(op, *args): 
    "Return op(*args), trying to correct for roundoff error, or `None` on Error or too big/small."
    try:
        val = op(*args)
        return (val        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)
    except (ArithmeticError, ValueError):
        return None
assert do(div, 12, 4) == 3 and do(div, 12, 0) == None
assert do(mul, 49, do(div, 1, 49)) == 1
assert do(pow, 10, -99) == None<jupyter_output><empty_output><jupyter_text>I'll take this opportunity to refactor `expressions` to have these subfunctions:- `digit_expressions(result, numbers)`: returns a dict like {0.44: '.44', 4.4: '4.4', 44.0: '44'}- `add_unary_expressions(result)`: add expressions like `√44` and `4!` to `result` and return `result`. - `add_binary_expressions(result, numbers)`: add expressions like `4+√44` and `4^4` to `result` and return `result`.<jupyter_code>@lru_cache(None)
def expressions(numbers: tuple) -> dict:
    "Return {value: expr} for all expressions that can be made from numbers."
    return add_unary_expressions(add_binary_expressions(digit_expressions(numbers), numbers))

def digit_expressions(digits: tuple) -> dict:
    "All ways of making numbers from these digits (in order), and a decimal point."
    D = ''.join(map(str, digits))
    exps = [(D[:i] + '.' + D[i:]).rstrip('.')
            for i in range(len(D) + 1)
            if not (D.startswith('0') and i > 1)]
    return {float(exp): exp for exp in exps}
      
def add_binary_expressions(result: dict, numbers: tuple) -> dict:
    "Add binary expressions by splitting numbers and combining with an op."
    for (Lnums, Rnums) in splits(numbers):
        for (L, R) in product(expressions(Lnums), expressions(Rnums)):
            Lexp = '(' + expressions(Lnums)[L]
            Rexp =       expressions(Rnums)[R] + ')'
            assign(result, do(div, L, R), Lexp + '/' + Rexp)
            assign(result, do(mul,     L, R), Lexp + '*'  + Rexp)
            assign(result, do(add,     L, R), Lexp + '+'  + Rexp)
            assign(result, do(sub,     L, R), Lexp + '-'  + Rexp)
            if -10 <= R <= 10 and (L > 0 or int(R) == R):
                assign(result, do(pow, L, R), Lexp + '^' + Rexp)
    return result
                
def add_unary_expressions(result: dict, nesting_level=2) -> dict:
    "Add unary expressions: -v, √v and v! to result"
    for _ in range(nesting_level):
        for v in tuple(result):
            exp = result[v]
            if -v not in result:
                assign(result, -v, '-' + exp)
            if 0 < v <= 100 and 120 * v == round(120 * v): 
                assign(result, sqrt(v), '√' + exp)
            if 3 <= v <= 6 and v == int(v):
                assign(result, factorial(v), exp + '!')
    return result<jupyter_output><empty_output><jupyter_text>The  function `assign` will silently drop expressions whose value is `None`, and if two expressions have the same value, `assign` keeps the one with the lower "weight"&mdash;a measure of the characters in the expression. This shows simpler expressions in favor of complex ones: for four 4s, the entry for `0` will be `44-44`, not something like `-√((-√4*--4)*(-√4--√4))`.<jupyter_code>def assign(result: dict, value: float, exp: str): 
    "Assign result[value] = exp, unless we already have a lighter exp or value is None."
    if (value is not None 
        and (value not in result or weight(exp) < weight(result[value]))): 
        result[value] = exp
        
PENALTIES = defaultdict(int, {'√':7, '!':5, '.':1, '^':3, '/':1, '-':1})
        
def weight(exp: str) -> int: return len(exp) + sum(PENALTIES[c] for c in exp)<jupyter_output><empty_output><jupyter_text>I'll define a function to print a table of consecutive integers (starting at 0) that can be made by a sequence of numbers:<jupyter_code>def show(numbers: tuple, upto=10000, clear=True):
    """Print expressions for integers from 0 up to limit or the first unmakeable integer."""
    if clear: expressions.cache_clear() # To free up memory
    print('{:,} entries for {}\n'.format(len(expressions(numbers)), numbers))
    for i in range(upto + 1): 
        if i not in expressions(numbers):
            return i
        print('{:4} = {}'.format(i, unbracket(expressions(numbers)[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)
%time show((4, 4, 4, 4))<jupyter_output>705,959 entries for (4, 4, 4, 4)

   0 = 44-44
   1 = 44/44
   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 = (44/4)-4
   8 = 4+(4*(4/4))
   9 = 4+(4+(4/4))
  10 = 44/4.4
  11 = (4/4)+(4/.4)
  12 = (4+44)/4
  13 = 4!-(44/4)
  14 = (4+(.4*4))/.4
  15 = 4+(44/4)
  16 = .4*(44-4)
  17 = (4/4)+(4*4)
  18 = .4+(.4*44)
  19 = (4+(4-.4))/.4
  20 = 4*(4+(4/4))
  21 = (4+4.4)/.4
  22 = √4*(44/4)
  23 = ((4*4!)-4)/4
  24 = 4+(4+(4*4))
  25 = (4+(4*4!))/4
  26 = (4/.4)+(4*4)
  27 = 4+(4!-(4/4))
  28 = 44-(4*4)
  29 = 4+(4/(.4*.4))
  30 = (4+(4+4))/.4
  31 = 4!+((4+4!)/4)
  32 = (4*4)+(4*4)
  33 = 4!+((4-.4)/.4)
  34 = 44-(4/.4)
  35 = 4!+(44/4)
  36 = 44-(4+4)
  37 = ((.4+4!)/.4)-4!
  38 = 44-(4!/4)
  39 = ((4*4)-.4)/.4
  40 = 44-√(4*4)
  41 = (.4+(4*4))/.4
  42 = √4+(44-4)
  43 = 44-(4/4)
  44 = 4+(44-4)
  45 = 44+(4/4)
  46 = 4+(44-√4)
  47 = 4!+(4!-(4/4))
  48 = 4*(4+(4+4))
  49 = 44+(√4/.4)
  50 = (4+(4*4))/.4
  51 = (.4+(4!-4))/.4
  52 = 4+[...]<jupyter_text>We can also solve the "2016 with four fours" puzzle:<jupyter_code>expressions((4, 4, 4, 4))[2016]<jupyter_output><empty_output><jupyter_text>In a [separate video](https://www.youtube.com/embed/Noo4lN-vSvw), <NAME> shows  how to form **every** integer from 0 to infinity using four 4s, if the square root and `log` functions are allowed. The solution comes from <NAME> (although [Dirac originally developed it](https://nebusresearch.wordpress.com/2014/04/18/how-dirac-made-every-number/) for the "four 2s" problem).<NAME> has [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.Below are some popular variants: Four 2s<jupyter_code>show((2, 2, 2, 2))<jupyter_output>109,747 entries for (2, 2, 2, 2)

   0 = 22-22
   1 = 22/22
   2 = 2+(2*(2-2))
   3 = (2+(2*2))/2
   4 = .2*(22-2)
   5 = 2+(2+(2/2))
   6 = 2*(2+(2/2))
   7 = 2+(2/(.2*2))
   8 = 2+(2+(2*2))
   9 = (22/2)-2
  10 = 22/2.2
  11 = (2/2)+(2/.2)
  12 = (2+22)/2
  13 = 2+(22/2)
  14 = 2+(2+(2/.2))
  15 = (2+(2/2))/.2
  16 = 2*(2*(2*2))
  17 = 22-(√.2^-2)
  18 = 22-(2*2)
  19 = (2+(2-.2))/.2
  20 = 22-√(2*2)
  21 = 22-(2/2)
  22 = 2+(22-2)
  23 = 22+(2/2)
  24 = 2*(2+(2/.2))
  25 = 2/(.2*(.2*2))
  26 = 2+(2+22)
  27 = 22+(√.2^-2)
  28 = 2+(2+(2*2)!)
  29 = 2+(2+(.2^-2))
  30 = (2+(2*2))/.2<jupyter_text>Four 9s<jupyter_code>show((9, 9, 9, 9))<jupyter_output>539,849 entries for (9, 9, 9, 9)

   0 = 99-99
   1 = 99/99
   2 = (99/9)-9
   3 = (9+(9+9))/9
   4 = 9-(9/(.9+.9))
   5 = √9+((9+9)/9)
   6 = ((9+(9+9))/9)!
   7 = 9-((9+9)/9)
   8 = ((9*9)-9)/9
   9 = 9+(9*(9-9))
  10 = 99/9.9
  11 = 9+((9+9)/9)
  12 = (9+99)/9
  13 = 9+(√9+(9/9))
  14 = 9+(9/(.9+.9))
  15 = 9+((9+9)/√9)
  16 = 9+((9/.9)-√9)
  17 = 9+(9-(9/9))
  18 = 99-(9*9)
  19 = 9+(9+(9/9))
  20 = 9+(99/9)
  21 = (9+9.9)/.9
  22 = 9+(√9+(9/.9))
  23 = √9+((9+9)/.9)
  24 = (99/√9)-9
  25 = 9+(√9!+(9/.9))
  26 = (9*√9)-(9/9)
  27 = 9+(9+√(9*9))
  28 = 9+(9+(9/.9))
  29 = 9+((9+9)/.9)
  30 = (9+(9+9))/.9
  31 = (.9+(9*√9))/.9
  32 = (99-√9)/√9
  33 = √9*(99/9)
  34 = (√9+99)/√9
  35 = (√9!+99)/√9
  36 = 9+(9+(9+9))
  37 = (9/.9)+(9*√9)
  38 = √9!*(√9+(√9/.9))
  39 = 9+(9*(√9/.9))
  40 = (9+(9*√9))/.9
  41 = (.9+(√9!*√9!))/.9
  42 = 9+(99/√9)
  43 = √9+(√9!*(√9!/.9))
  44 = (9*√9!)-(9/.9)
  45 = 9*(9/(.9+.9))
  46 = (9/.9)+(√9!*√9!)
  47 = √9*(9+(√9!/.9))
  48 = √9!*(9-(9/9))
  49 = [...]<jupyter_text>Four 5s<jupyter_code>show((5, 5, 5, 5))<jupyter_output>202,937 entries for (5, 5, 5, 5)

   0 = 55-55
   1 = 55/55
   2 = (5/5)+(5/5)
   3 = (5+(5+5))/5
   4 = ((5*5)-5)/5
   5 = 5+(5*(5-5))
   6 = (55/5)-5
   7 = 5+((5+5)/5)
   8 = 5.5+(.5*5)
   9 = 5+(5-(5/5))
  10 = 55/5.5
  11 = 5.5+5.5
  12 = (5+55)/5
  13 = .5+(.5*(5*5))
  14 = 5+((5-.5)/.5)
  15 = (5*5)-(5+5)
  16 = 5+(55/5)
  17 = 5+(5!/(5+5))
  18 = (5-.5)/(.5*.5)
  19 = (5+(5-.5))/.5
  20 = 5+(5+(5+5))
  21 = (5+5.5)/.5
  22 = 55/(.5*5)
  23 = .5+(5*(5-.5))
  24 = (5*5)-(5/5)
  25 = .5*(55-5)
  26 = (5/5)+(5*5)
  27 = (.5*55)-.5
  28 = .5+(.5*55)
  29 = (5!+(5*5))/5
  30 = 55-(5*5)
  31 = 55-(5!/5)
  32 = ((5+5)/5)^5
  33 = .5*(5!*.55)
  34 = 5+(5+(5!/5))
  35 = 5+(5+(5*5))
  36 = (5!+(.5*5!))/5
  37 = (.5^-5)+√(5*5)
  38 = ((5!/5)-5)/.5<jupyter_text>Five 5s<jupyter_code>%time show((5, 5, 5, 5, 5), clear=False)<jupyter_output>7,624,387 entries for (5, 5, 5, 5, 5)

   0 = 5*(55-55)
   1 = 5^(55-55)
   2 = 55/(.5*55)
   3 = .5*((55/5)-5)
   4 = 5-(55/55)
   5 = 5*(55/55)
   6 = 5+(55/55)
   7 = ((5+55)/5)-5
   8 = .5*(5+(55/5))
   9 = (55-(5+5))/5
  10 = (55/5)-(5/5)
  11 = 5*(55/(5*5))
  12 = (5/5)+(55/5)
  13 = (5+(5+55))/5
  14 = (5*5)-(55/5)
  15 = 5+(55/5.5)
  16 = 5+(5.5+5.5)
  17 = 5+((5+55)/5)
  18 = 5.5+(.5*(5*5))
  19 = (5*5)-(.5+5.5)
  20 = 55/(5*.55)
  21 = 5+(5+(55/5))
  22 = (55+55)/5
  23 = (5+(55/.5))/5
  24 = (5+55)/(.5*5)
  25 = 55-(5+(5*5))
  26 = 5*(5+(5/(5*5)))
  27 = 5+(55/(.5*5))
  28 = .5*(.5+55.5)
  29 = 5+((5*5)-(5/5))
  30 = 5*((55/5)-5)
  31 = .5+(5.5+(5*5))
  32 = (5+(55/5))/.5
  33 = .55*(5+55)
  34 = (5!+(55-5))/5
  35 = 5+(55-(5*5))
  36 = (5*5)+(55/5)
  37 = 5+(((5+5)/5)^5)
  38 = .5+(5*(5+(.5*5)))
  39 = ((5*5)-5.5)/.5
  40 = 55-(5+(5+5))
  41 = (5!*.55)-(5*5)
  42 = (5+5.5)/(.5*.5)
  43 = 55-(5!/(5+5))
  44 = 55-(55/5)
  45 = (5*5)+((5*5)-5)
  46 = 55+((.5-5)/.5)
  47 = (5*([...]<jupyter_text>Countdown to 2018On January 1 2018, [<NAME>](http://cs.brown.edu/~mlittman/) 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), sqrt(|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?<jupyter_code>show((2,0,1,8), 10)
show((2,0,1,9), 10)
show((2,0,2,0), 10)<jupyter_output>373 entries for (2, 0, 2, 0)

   0 = 202*0
   1 = 20/20
   2 = 2+(0*20)
   3 = 2+(.02^0)
   4 = .20*20
   5 = (2^0)/.20
   6 = (2+(.02^0))!<jupyter_text>Uh-oh! I knew 2020 was a bad year! The two zeroes don't give us much to work with, and we can't make all the integers in the countdown. But I can turn a 0 into a 1 with `cos(0)`; maybe that will be enough? Let's try it. I'll modify `add_unary_expressions` to assign values for `sin` and `cos`:<jupyter_code>from math import sin, cos, pi

def add_unary_expressions(result: dict, nesting_level=2) -> dict:
    "Add unary expressions: -v, √v and v! to result dict."
    for _ in range(nesting_level):
        for v in tuple(result):
            exp = result[v]
            if -v not in result:
                assign(result, -v, '-' + exp)
            if 0 < v <= 100 and 120 * v == round(120 * v): 
                assign(result, sqrt(v), '√' + exp)
            if 3 <= v <= 6 and v == int(v):
                assign(result, factorial(v), exp + '!')
            if abs(v) in (0, 30, 45, 60, 90, 180, 270, 360):
                assign(result, sin(v * pi / 180), 'sin(' + exp + ')')
                assign(result, cos(v * pi / 180), 'cos(' + exp + ')')
    return result

PENALTIES.update(s=1, i=1, n=1, c=1, o=1)
show((2, 0, 2, 0), 10, clear=True) # Clear the cache so we get new results for (2, 0) etc.
show((2, 0, 2, 1), 10)<jupyter_output>38,975 entries for (2, 0, 2, 1)

   0 = 2*(0*21)
   1 = -20+21
   2 = 2+(0*21)
   3 = 2+((0*2)+1)
   4 = 2.0*(2*1)
   5 = 2.0+(2+1)
   6 = 2.0*(2+1)
   7 = 2+(0.2^-1)
   8 = 2.0^(2+1)
   9 = (20/2)-1
  10 = 20/(2*1)<jupyter_text>Making 6 from 3 Digits<NAME> postedd the following in the Facebook "omg math" group.> For each digit from 1 to 9, find at least one way to express 6 using only that digit exactly three times and arithmetic operations. For instance, using the digit 2, 2+2^2=6.It turns out what I already have handles this well:<jupyter_code>{n: expressions((n, n, n))[6] for n in range(1, 10)}<jupyter_output><empty_output><jupyter_text>What's Next?One exercise would be adding even more operators, such as:- **Floor and Ceiling**: `⌊5.5⌋` = 5, `⌈5.5⌉` = 6- **Nth root**: `3√8` = 2- **Percent**: `5%` = 5/100- **Repeating decimal**: `.4...` = .44444444... = 4/9- **Double factorial**: `9!!` = 9 × 7 × 5 × 3 × 1 = 945; not the same as `(9!)!`- **Gamma function**: `Γ(n)` = (n − 1)!- **Prime counting function**: `π(n)` = number of primes ≲ n; `π(5)` = 3- **Transcendental functions**: besides `sin` and `cos`, there's `log`, `tan`, `arcsin`, ...In the [xkcd forum](http://forums.xkcd.com/viewtopic.php?f=14&t=116813&start=280) they got up to 298 for five fives, using the double factorial and π functions. What would you like to do? ______ Equilength Number NamesThe internet [claims](https://www.reddit.com/r/Showerthoughts/comments/3h8wpx/four_is_the_only_number_that_has_the_same_amount/) that "*Four is the only number that has the same amount of letters as its value.*" But "Four" is not a number; it is a *name* for a number. We'll call it an **equilength number name**.Other languages have different equilength number names. In German there's "vrei", in Spanish and Portuguese "cinco", and in Pinyin Chinese "èr" and "sān". French does not have an equilength number name.There are also *number expressions* such as "two plus nine" that are equilength (in letters, not in string length). Let's search for them. I want to define a function similar to `expressions` to generate new expressions and their values. But instead of being required to use a specific set of numbers in creating the expression, I am free to use any numbers in the language. So I will define `equilength_expressions(language, c)` as follows:- The input `language` is a pair of components:   - The `operators`, a dict with entries in the form `{add: ['plus', 'and']}`.   - The `integers`, a dict of the form `{(0, 4): 'zero', (1, 3): 'one', ...}`.- The input `c` tells how many times to `combine` expressions, using the operators of the language. There are an infinite number of possible expressions, so with `c=0` we just get integers like `'one'`; with `c=1` we get a combinations of two integers, like `'(one plus two)`; with `c=2` we get combinations of any previously-defined expression, like `((one plus two) times (four minus three))`. I wouldn't recommend going beyond 2 unless you're willing to wait a long time.- Like `expressions`, `equilength_expressions` returns a dict such as `{4: 'four'}`.- However, internally, `equilength_expressions` keeps a `table` with keys that are`(numeric_value, number_of_letters)` pairs, and values that are string expressions, for example `{(3, 10): "one plus two", (11, 11): '(two plus nine)'}`. The dict only keeps one entry for each such key; it would be unneccessary to report that both `'two plus nine'` and `'nine plus two'` are equilength expressions. - We call `combine` to make larger expressions; it generates all combinations that don't divide by zero. If we allowed operations like `"factorial"` and `"to the power of"` then we would have to be more careful.<jupyter_code>def make_key(value, exp):  return (value, sum(ch.isalpha() for ch in exp))
def make_item(value, exp): return (make_key(value, exp), exp)

def names(text): return [word.replace('-', ' ') for word in text.split()]

def language(operators, integers):
    """A language is a pair such as: ({add: ['add'],...}, {(0, 4): 'zero',...})."""
    return ({op: names(operators[op]) for op in operators},
            {make_key(i, w): w for i, w in enumerate(names(integers))})
def equilength_expressions(language, c=1):
    """Combine expressions in the language with each other (using operators) c times.
    Then report all {n: expression} entries where expression has n letters."""
    operators, table = language
    for _ in range(c):
        table = {**table, **combine(operators, table)}
    return {n: table[n, v] 
            for n, v in sorted(table) 
            if n == v}
    
def combine(operators, table):
    """Return table like {(3, 10): "(one plus two)"} by combining table entries with operators."""
    return dict(make_item(do(OP, L, R), f'({Lexp} {OPexp} {Rexp})')
                for (R, _), Rexp in table.items()
                for OP in operators
                if not (OP == div and R == 0)
                for (L, _), Lexp in table.items()
                for OPexp in operators[OP])<jupyter_output><empty_output><jupyter_text>Now the names for operators and the first few integers in English, Spanish, Pinyin Chinese and German:<jupyter_code>english = language({add: 'plus and added-to', sub: 'minus less take-away', 
                    mul: 'times multiplied-by', div: 'divided-by over',
                    lambda x, y: y-x: 'subtracted-from'},
    '''zero one two three four five six seven eight nine ten eleven twelve thirteen 
    fourteen fifteen sixteen seventeen eighteen nineteen twenty''')

spanish = language({add: 'más', sub: 'menos', mul: 'por', div: 'dividido-entre dividido-por'},
    '''cero uno dos tres cuatro cinco seis siete ocho nueve diez once doce trece catorce 
    quince dieciséis diecisiete dieciocho diecinueve veinte veintiuno veintidós veintitrés 
    veinticuatro veinticinco veintiséis veintisiete veintiocho veintinueve treinta''')

chinese = language({add: 'jiā', sub: 'jiǎn', mul: 'chéng', div: 'chú chú-yǐ'},
    'ling yī èr sān sì wŭ liù qī bā jiŭ shí shí-yī shí-èr shí-sān shí-sì shí-wǔ shí-liù shí-qī')

german = language({add: 'und plus', sub: 'weniger minus', mul: 'mal multipliziert', div: 'durch'},
    '''null eins zwei drei vier fünf sechs sieben acht neun zehn elf zwölf dreizehn 
    vierzehn funfzehn sechszehn siebzehn achtzehn neunzehn zwanzig einundzwanzig zweiundzwanzig 
    dreiundzwanzig vierundzwanzig fünfundzwanzig sechsundzwanzig siebenundzwanzig achtundzwanzig''')<jupyter_output><empty_output><jupyter_text>Multilingual Equilength ExpressionsWe are ready to find equilength numbers and expressions:<jupyter_code>equilength_expressions(english, 0)
equilength_expressions(english, 1)
equilength_expressions(spanish, 1)
equilength_expressions(chinese, 1)
equilength_expressions(german, 1)<jupyter_output><empty_output><jupyter_text>Longer Multilingual Equilength Expressions¶Now for expressions with 2 combination steps. These take a few minutes each, so I will `%time` them:<jupyter_code>%time equilength_expressions(english, 2)
%time equilength_expressions(spanish, 2)
%time equilength_expressions(chinese, 2)
%time equilength_expressions(german, 2)<jupyter_output>CPU times: user 5min 7s, sys: 4.02 s, total: 5min 11s
Wall time: 5min 20s
{'fraction_non_alphanumeric': 0.16403667615187836, 'fraction_numerical': 0.07326607455951252, 'mean_word_length': 3.4157888056860006, 'pattern_counts': {'":': 0, '<': 144, '<?xml version=': 0, '>': 155, 'https://': 9, 'lorem ipsum': 0, 'www.': 8, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 3, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '32', 'dir': 'jupyter-structured-clean-dedup', 'id': '445072', 'license': 'MIT', 'n_tokens_mistral': 13959, 'n_tokens_neox': 12549, 'n_words': 4301, 'path': 'ipynb/Countdown.ipynb', 'repo_name': 'SiDDyy007/pytudes', 'size': '34839'}