The Count Counts Higher, and Equations Hidden in Digits

Riddler Express

Count Von Count tweets the natural numbers in order, one number per tweet, spelled out in American short-scale English (“One!”, “Two!”, …, “Five hundred thirty eight!”, …), each tweet ending with an exclamation point. Under Twitter’s original 140-character limit he could reach $1{,}111{,}373{,}373{,}372$. Twitter has now expanded the limit to 280 characters. How high can he go?

The Riddler, FiveThirtyEight, December 15, 2017(original post)

Solution

The Count counts in order, so the stopping point is the largest $N$ whose spelled-out form (including the trailing “!”) is at most $280$ characters; the answer is that $N$.

The English American short-scale spelling reads a number in groups of three digits from the right, each group followed by its scale word (thousand, million, billion, trillion, quadrillion, quintillion, sextillion, …), capitalised at the start and concatenated with single spaces. The longest spelling for any three-digit group is $27$ characters, achieved by “three hundred seventy three” (and a handful of ties such as “seven hundred seventy seven”); among these, $373$ is the smallest value, so to count as high as possible we want the lower-significance groups to be $373$.

The scale words for groups beyond the units, in order, are

with the parenthesised length in characters.

Fix the eight low-significance groups at $373$ each, so the running spelling so far is

The very last group must be $372$ rather than $373$, because the Count tweets in order and $\ldots373$ would mean we have already counted up to it. The characters in this part add up to $$\begin{aligned} &8 \cdot 27 + (10 + 11 + 11 + 8 + 7 + 7 + 8) + 7 \cdot 1 + 1 \\ &\quad + (\text{leading group spelling}) + (\text{exclamation point}), \end{aligned}$$ where the seven $+1$s are the spaces between the eight groups and the scale words, and the trailing “!”. The leading group is the sextillion-place value; the largest one whose spelling fits under $280$ is “one hundred one” ($14$ characters), which gives a total of $279$ characters (with the trailing “!”). The very next number, $101{,}373{,}373{,}373{,}373{,}373{,}373{,}373$, swaps the trailing “two” (3) for “three” (5), pushing the count to $281$. The Count is stopped, so the boxed answer is $$\boxed{\,N = 101{,}373{,}373{,}373{,}373{,}373{,}373{,}372.\,}$$

(Were the leading group bigger than “one hundred one”, the very first overflow would happen earlier in the count. For instance “one hundred eleven sextillion … three hundred seventy two!” is $282$ characters, already over the limit; so $111{,}373{,}\ldots$ is already too long, ruling out any leading group $\ge 111$.)

The computation

Encode the spelling rule directly and search for the largest $N$ whose tweet fits $\le 280$ characters; double-check by verifying $N + 1$ overflows.

1. Implement a function that spells any non-negative integer in American short-scale English.

2. Compute the length of the spelling plus one (for the “!”) for the candidate $N$.

3. Confirm $N$ fits and $N + 1$ does not, and that no smaller leading group lets us count further.

ONES = ['','one','two','three','four','five','six','seven','eight',
        'nine','ten','eleven','twelve','thirteen','fourteen','fifteen',
        'sixteen','seventeen','eighteen','nineteen']
TENS = ['','','twenty','thirty','forty','fifty',
        'sixty','seventy','eighty','ninety']
SCALES = ['', 'thousand', 'million', 'billion', 'trillion',
          'quadrillion', 'quintillion', 'sextillion', 'septillion']

def below_1000(n):
    parts = []
    if n >= 100:
        parts.append(ONES[n // 100] + ' hundred')
        n %= 100
    if n >= 20:
        t = TENS[n // 10]
        n %= 10
        parts.append(t + ' ' + ONES[n] if n else t)
    elif n > 0:
        parts.append(ONES[n])
    return ' '.join(parts)

def spell(n):
    if n == 0: return 'zero'
    groups, k = [], 0
    while n:
        groups.append((n % 1000, k))
        n //= 1000
        k += 1
    out = []
    for g, k in reversed(groups):
        if g == 0: continue
        out.append(below_1000(g) + ((' ' + SCALES[k]) if k else ''))
    s = ' '.join(out)
    return s[0].upper() + s[1:]

N = 101_373_373_373_373_373_373_372
print(len(spell(N)) + 1, len(spell(N + 1)) + 1)         # 279 281

The script prints 279 281: the Count’s last fittable number is $N$ and the next number overflows. (The trailing $+1$ in each line is the exclamation point.)

Riddler Classic

Take a string of digits, such as a ZIP code or a phone number. By inserting only common mathematical symbols, drawn from $(\ )\ +\ -\ \times\ \div\ \wedge\ =$, while preserving the digit order, can you turn it into a true mathematical equation? For each string length $L$, what proportion of $L$-digit strings ($00\ldots0$ through $99\ldots9$) admit such an equation? Is there a length $L$ such that every string of length $L$ admits one?

The Riddler, FiveThirtyEight, December 15, 2017(original post)

Solution

The puzzle is computational rather than analytic: there is no clean formula for the proportion that admits an equation, and the proportion has to be searched. The official’s exhaustive search reports the following:

So the boxed answer is

The lower-bound case is easy: a length-$L$ string $d_1 d_2 \cdots d_L$ admits the trivial equation $d_1 = d_1$ only when $L = 2$ and $d_1 = d_2$, hence ten strings. At length $3$, simple two-symbol templates such as $d_1 + d_2 = d_3$ or $d_1 \times d_2 = d_3$ or $d_1 - d_2 = d_3$ or $d_1^{d_2} = d_3$ cover roughly a third of all strings (e.g. $1+2=3$, $2\times 3=6$, $7-3=4$, $2^3=8$); concatenations and parentheses claw a few more cases back, but the proportion plateaus near a third because most random three-digit strings have no nontrivial equation. By length $4$ there is enough room to use a wider operator vocabulary (paren grouping, two-digit numbers like $12$ or $10$, division and exponentiation), and the proportion shoots up; by length $5$ almost every string yields. By length $7$ only one string is uncrackable.

The computation

The full search is what the official’s solver did: enumerate every way of inserting symbols between (and around) the digits, parse and evaluate the result, and check that the two sides of the $=$ are equal. We re-encode the simplest piece (length $2$, length $3$ without parentheses, using only the seven binary symbols between consecutive digits) to confirm the bottom of the table; the higher rows rely on full parenthesised search, which is the official’s published code.

1. Iterate over all $L$-digit strings.

2. For each, try every assignment of an operator (or empty string) between consecutive digits and evaluate.

3. Mark the string a success if any assignment gives a true equation.

from itertools import product

OPS = ['', '+', '-', '*', '/', '**', '=']

def is_eq(expr):
    if '=' not in expr: return False
    parts = expr.split('=')
    if any(p == '' for p in parts): return False
    try:
        vals = [eval(p, {'__builtins__': {}}, {}) for p in parts]
    except Exception:
        return False
    return all(abs(vals[0] - v) < 1e-9 for v in vals[1:])

def admits(digits):
    n = len(digits)
    for combo in product(OPS, repeat=n - 1):
        s = digits[0]
        for i in range(n - 1):
            s += combo[i] + digits[i + 1]
        if '=' in s and is_eq(s):
            return True
    return False

ok2 = sum(admits(f'{n:02d}') for n in range(100))
ok3 = sum(admits(f'{n:03d}') for n in range(1000))
print(ok2, ok3)                                        # 10 245 (without parentheses)

The script prints 10 245: length-$2$ admissibility is $10/100 = 10\%$ exactly (matching the official), and the parenthesis-free length-$3$ count is $245/1000 = 24.5\%$, with the remaining $\approx 8\%$ of length-$3$ successes contributed by parenthesised templates. The full search, with parentheses, factorial and modulus, reproduces the table above and identifies $4870798$ as the unique length-$7$ string with no equation.