Possibly Wrong

How high can you count in limited space?


I recently saw several different checks, all from the same bank, each with a different dollar amount printed in a fixed-width font, similar to the shortened example below:

**PAY EXACTLY**twelve thousand thirty-four and 56/100****************

Counting asterisks confirmed that the amount fields on each check were all padded to exactly the same length… which made me wonder, what is the largest check that the bank could print, using English words for the dollar amount?

Actually, that’s not quite the question I had in mind. There are very short names for very large numbers, but it’s not very helpful to say that a bank can cut a check for, say, “one googol” dollars, when most smaller amounts would not fit in the same length of field.

So to make the problem less linguistic and more mathematical, let’s instead ask the following more precise question: what is the largest integer such that every dollar amount from zero to can be printed in words using at most characters?

Converting integers into words

For short fields, such as in the case of the bank checks, brute force is sufficient; we just need a function to convert integers into words. This is a pretty common programming problem, with one Python implementation shown below, where integer_name(n) works for any :

units = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven',
    'eight', 'nine', 'ten', 'eleven', 'twelve', 'thirteen', 'fourteen',
    'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen']
tens = ['zero', 'ten', 'twenty', 'thirty', 'forty', 'fifty', 'sixty',
    'seventy', 'eighty', 'ninety']
powers = ['zero', 'thousand', 'million', 'billion', 'trillion',
    'quadrillion', 'quintillion', 'sextillion', 'septillion', 'octillion',
    'nonillion', 'decillion']
hundred = 'hundred'
minus = 'minus'
comma = ','
and_ = ' and'
space = ' '
hyphen = '-'
empty = ''

def small_integer_name(n, use_and=False):
    s = empty
    if n >= 100:
        q, n = divmod(n, 100)
        s = units[q] + space + hundred + (
            (and_ if use_and else empty) + space if n > 0 else empty)
    if n >= 20:
        q, n = divmod(n, 10)
        s += tens[q] + (hyphen if n > 0 else empty)
    return (s + units[n] if n > 0 else s)

def integer_name(n, use_comma=False, use_and=False, power=0):
    if n < 0:
        return minus + space + integer_name(-n, use_comma, use_and)
    elif n == 0:
        return units[0]
    s = empty
    if n >= 1000:
        q, n = divmod(n, 1000)
        s = integer_name(q, use_comma, use_and, power + 1) + (
            (comma if use_comma else empty) + space if n > 0 else empty)
    return (s + small_integer_name(n, use_and) +
            (space + powers[power] if power > 0 else empty) if n > 0 else s)

There are a couple of things to note. First, although typical American style does not include commas separating thousands, or the word and between hundreds and tens (e.g., “one hundred and twenty-three”), it’s nice to have the option here, since it affects the calculation of .

Also, “everything” is a variable, including the hyphen, comma, space, even the empty string. The addition operator is overloaded for string concatenation, but it’s easy to replace the string constants with, say, integer word counts, or syllable counts, or whatever, without changing the code. For example, we can automatically generate lousy haiku:

One hundred twenty-

one thousand seven hundred


Coming back to the bank checks, it turns out that , so that the bank can print a check for any amount up to $1,113,322.99. Which doesn’t seem terribly large– I wonder if they fall back to using numerals if the amount doesn’t fit using words?

Twitter scale

This isn’t a new problem. A couple of years ago, FiveThirtyEight.com’s Riddler posed a problem involving the Twitter account @CountVonCount, of Sesame Street fame, essentially asking for … and then again asking for just last month, in response to the recent increase in maximum length of a tweet from 140 to 280 characters (in each case, less one character to account for an exclamation point).

These field widths are large enough that a brute force approach is no longer feasible. It’s a nice problem to implement a function to compute efficiently and exactly, with results as shown in the figure below.

How high can you count (on the y-axis) spelling each number in words using at most the number of characters on the x-axis?

All of the source code is available at the usual location here.