## 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.