# How high can you count in limited space?

Introduction

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',
'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

seventy-seven

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?