HAKMEM Item #134

Item 134 of HAKMEM is given as follows:

A Proof

We can observe that longhand numbers satsify the following EBNF:

1digit = 'zero'  | 'one' | 'two' | 'three' | 'four' | 'five' | 'six' | 'seven'
       | 'eight' | 'nine';

teens  = 'eleven'  | 'twelve'    | 'thirteen' | 'fourteen' | 'fifteen'
       | 'sixteen' | 'seventeen' | 'eighteen' | 'nineteen';

tens   = 'twenty' | 'thirty' | 'fourty' | 'fifty' | 'sixty' | 'seventy'
       | 'eighty' | 'ninety';

2digit = 'ten' | teens | (tens, '-', one-digit);

3digit = one-digit, ' ', 'hundred', [' ', two-digit];

# many valid terms are omitted here, but they do not affect the following proof
large-magnitude = 'million' | 'billion' | 'trillion' | <etc>;

longhand = (three-digit | two-digit | one-digit), {large-magnitude three-digit};

The EBNF allows for nonsensical numbers, such as "one million one billion" or "zero billion twenty-zero", but it matches all valid inputs.

Given f(x) = FLATSIZE(LONGHAND(x)), we observe the following for the values of 1digit:

  x  = [0 1 2 3 4 5 6 7 8 9]
f(x) = [4 3 3 5 4 4 3 5 5 4]

We can observe that f(x) has a fixed point at 4 for all single digit numbers, satisfying the property stated in HAKMEM #134.

Furthermore, we can observe the following for sets teens, 2digit, and 3digit:

f(x) <= 9  when x <= 19
f(x) <= 19 when x <= 99
f(x) <= 99 when x <= 999

From this, we can conclude repeated applications of f(x) in [9, 999] will result in a 1digit value, which we know has a single fixpoint at x=4.

To generalize to larger numbers, we can take advantage of how digits are read in groups of three. We can relate the numerical value of x to the greatest number of letters it can possibly contain by observing that f(x) <= h(x) where h(x) = k*ceil(log_10(x)/3), where k is equal to the maximum value of f(x) for a number of format 3digit, large-magnitude.

For x > k, h(x) decreases until it reaches a fixpoint of k. Therefore, assuming that k is less than 999 (there are no words to represent a 3 digit number and a magnitude that come close to 999 characters), the fixpoint of h(x) will exist inside the range that we previously established as having a fixpoint of 4.

This can be trivially extended to any written English description of a number (such as 1.23, π, or √2), due to the fact that the length of a string is always a non-negative integer, so the second iteration will always be covered under the originally stated problem.