In 2016, Matt Parker published the video Four has Four Letters to YouTube. As per the title, the video is about what happens when you iteratively map a natural number to its length in English (and it also touches briefly on other languages). Namely, all natural numbers eventually reach four, which is a fixed point because it has four letters in its name. Towards the end of the video, he poses the following question: for any given $n$, what is the smallest natural number that takes $n$ iterations to reach four, the smallest $n$-chain? Here, I've answered this question for $n$ up to 9, along the way developing some maths and algorithms that I found quite interesting, and that I hope you do too.

The Trivial Cases: $n\le 6$

The only 0-chain, by construction, is 4, and the smallest $n$-chains for $1\le n\le 5$ are 0, 3, 1, 11, and 23 respectively. These are the same results as what Matt Parker presented in his video, but I'm not quite doing the same thing that he did: he counted letters, but I'm counting characters, including spaces and hyphens. Anyway, this is the point at which Matt Parker stopped in his video, because there are no 6-chains smaller than or equal to 100, and 100 is a point at which English speakers diverge from each other. Different dialects of English, for example, will write 120 as either "one hundred twenty" or "one hundred and twenty". In my Australian English, which uses the latter variant, and counting characters rather than letters, the smallest 6-chain is 113 ("one hundred and thirteen").

The 7-Chain and the Core Algorithm

Finding the smallest 7-chain is where things start to get interesting, where we start to see the basic algorithm that I'll use to find all higher smallest $n$-chains. There are no 7-chains smaller than 1,000, so finding $n$-chains for $n\ge 7$ involves working with the highest-level structure of English number names, which is seen in numbers 1,000 and up.

Names of Numbers Above 1,000

In broad strokes, the name of a number larger than or equal to 1,000 is formed by splitting the number into units with power-of-1,000 place values. For example, 5,200,012 is named "five million two hundred thousand and twelve". It's natural, then, to think of English number naming in base 1,000 more so than in base 10, with the name of a number being composed of the names of its base-1,000 "digits", which I'll call millits (portmanteau of Latin "mille", meaning 1,000, and "digit"). As we saw in the example, number names are composed of the names of their millits interleaved with names for the powers of 1,000, where 1,000 itself is named "thousand" and $1,{000}^{n+1}$ is usually named as some Latin-like name for $n$ suffixed with "-illion" (more on that later). The exact details of how this formation works seem to vary between speakers; by examining my own habits for naming numbers, I produced the following rules:

• Millit-illion blocks are joined with only spaces, not commas or other punctuation. For example, 1,200 is "one thousand two hundred" not "one thousand, two hundred".
• A zero millit that is not the most significant millit is completely omitted from the name, including its -illion name. For example, 1,000,200 is named "one million two hundred".
• A millit less than 100 that is not the most significant millit is prefixed with "and". For example, 2,099 is "two thousand and ninety-nine".

The Core Algorithm: Searching Millit by Millit

Now that I've covered how to name larger numbers, I can go over the core algorithm I'll use to find smallest $n$-chains. This is based on a key observation: any $n$-chain has a name length which is an $(n-1)$-chain, by definition of what it means to be an $n$-chain. Thus, at the highest level, the algorithm for finding the smallest $n$-chain is as follows:

1. Find the smallest number whose name length is at least the smallest $(n-1)$-chain.
   1. Find how many millits long $N$ it must be, by comparing the longest-named number with $N$ millits to the smallest $(n-1)$-chain.
   2. Find which millits the number must have.
2. If the result of the above is an $n$-chain, it must be the smallest $n$-chain.

The millit with the longest name is 373 ("three hundred and seventy-three")¹, at 31 characters long, so the number with the longest name for a given millit count is a number whose millits are all 373, which I call 373-repmillits in analogy to decimal "repdigits". To find how many millits long the smallest 7-chain is, then, I look for the smallest 373-repmillit whose length is at least 113 (the smallest 6-chain):

From this, we can see that the smallest 7-chain is four millits long (it's a number in the billions), since no number with three or fewer millits has a long enough name to be a 7-chain. To find which specific four-millit number the smallest 7-chain is, I'll modify the millits away from 373 to remove the excess characters. Since we're looking for the smallest number at least 113 characters long, I iterate starting from the most significant millit, since that maximises the value reduction of the number for a given character count reduction. For each millit, I find the smallest value of that millit that keeps the number at least 113 characters long:

Thus, the smallest 7-chain is 1,103,323,373, whose name is "one billion one hundred and three million three hundred and twenty-three thousand three hundred and seventy-three".

Intermission: Terminology

Having just found the smallest 7-chain, the next step is to find the smallest 8-chain. Before I do that, though, I'll declare some shorthand vocabulary for core concepts, to make the following writing more concise. First of all, from now on, I'll refer to the smallest $n$-chain as simply "the n-chain", as opposed to the indefinite form "an $n$-chain". For example, 115 is a 6-chain, but 113 is the 6-chain. Second, I'll use words like "small", "big", "large", and "size" consistently to refer to number magnitude, but "short", "long", and "length" will refer to English name length. For example, 24 is larger but shorter than 23. An exception to this is the adjective phrase "millits long", which refers to millit count and is therefore monotonic to magnitude.

The 8-Chain, Large Number Names, and Computational Search

Since the 7-chain is larger than a billion, the 8-chain is over a billion characters long. This is a very large number indeed, which implies two things. First, we'll need to systematically extend number naming (specifically the $n$-illion sequence) to all natural numbers. Second, the "core algorithm" search for the 8-chain will have² to be done on a computer rather than by hand.

Systematic $n$-illion Names: the CWM System

The $n$-illion naming system that I'll be using here, that appears to be the de facto standard among the few people who care about such things, is a system that was created by John Conway and Allan Wechsler and later modified by Olivier Miakinen[1]. This is often referred to as the "Conway-Wechsler system", but since that could be ambiguous with the version that doesn't have Miakinen's modification, I instead prefer to call it the "Conway-Wechsler-Miakinen system", or CWM system for short. For -illions up to 10-illion ($1,{000}^{11}$), the usual names up to "decillion" are used. For $n$-illion with , $n$ gets split into units, tens, and hundreds, and Latin-derived names for those components get compounded to form the full $n$-illion name. These component names are:

The letters in brackets on either side of a name indicate letters used for joining; any letter present in brackets after one name and before the next name is inserted between the two names. "tre" is a special case, in that the joining letter after it is always "s", even if the shared bracketed letter is "x". Finally, the vowel at the end is removed and "illion" is appended. Here are some examples of CWM names:

• 83-illion is "tresoctogintillion",
• 143-illion is "tresquadragintacentillion",
• 470-illion is "septuagintaquadringentillion", and
• 906-illion is "senongentillion".

Finally, for $n$-illion where $n\ge 1,000$, $n$ is broken into its component millits, whose -illion names are concatenated together, most significant millit first, with the "on" suffix removed from all but the last one. For example, 894,059-illion is named "quattuornonagintaoctingentillinovenquinquagintillion" (894-illi-059-illion). 0-illi is named "nilli", so for example 1,000-illion itself is named "millinillion".

Computational Number Naming and Length Search

So now I'll implement in code the millit-by-millit algorithm that you saw me perform by hand to find the 7-chain. I'll use Rust for this, since I'm interested to learn it, and this seems like a good opportunity to do so. Also, this problem is somewhat computationally demanding, so using a low-level compiled language in general makes sense.

Number Names and Lengths

The first thing I'll do here is write a function to name single-millit numbers:

fn name_under_hundred(n: usize) -> String
{
    assert!(n < 100);

    if n < 20
    {
        return UNITS[n].to_string();
    }

    let units = n % 10;
    let tens = n / 10;

    if units == 0
    {
        return TENS[tens].to_string();
    }

    return format!("{}-{}", TENS[tens], UNITS[units]);
}

fn name_millit(n: usize) -> String
{
    assert!(n < 1_000);

    if n < 100
    {
        return name_under_hundred(n);
    }

    let hundreds = n / 100;
    let units = n % 100;

    if units == 0
    {
        return format!("{} hundred", UNITS[hundreds]);
    }

    return format!(
        "{} hundred and {}",
        UNITS[hundreds],
        name_under_hundred(units)
    );
}

Here, UNITS and TENS are constant arrays of the basic number names. Next, I write code to generate the names of the -illi fragments of CWM -illion names:

fn name_illi(n: usize) -> String
{
    assert!(n < 1_000);

    if n < 10
    {
        return FIRST_ILLIS[n].to_string();
    }

    let units = n % 10;
    let tens = (n / 10) % 10;
    let hundreds = n / 100;

    // push name fragments in reverse order,
    // so they'll be popped in the correct order
    let mut name_fragments: Vec<(&str, &str, &str)> = Vec::new();
    if hundreds > 0 { name_fragments.push(HUNDREDS_ILLIS[hundreds]); }
    if tens > 0 { name_fragments.push(TENS_ILLIS[tens]); }
    if units > 0 { name_fragments.push(UNIT_ILLIS[units]); }

    let mut total_name = String::new();
    let mut total_suffixes: &str = "";
    while name_fragments.len() > 0
    {
        let (prefixes, name, suffixes) = name_fragments.pop().unwrap();
        if let Some(shared_char) = find_shared_char(total_suffixes, prefixes)
        {
            total_name.push(shared_char);
        }
        total_name.push_str(name);
        total_suffixes = suffixes;
    }

    let trailing_char = total_name.pop();
    debug_assert!(matches!(trailing_char, Some('a' | 'e' | 'i' | 'o' | 'u')));
    total_name.push_str("illi");
    return total_name;
}

Here, I once again have constant arrays for the base names of the hundreds, tens, and units place, containing both the names themselves and the joining letters on either side. The function find_shared_char, which I omit here for brevity, contains the logic for finding these joining letters, including handling the aforementioned special case of "tre".

These millit and -illi names are the basic building blocks of all number names. To simplify the higher-level code, I put these functions in a build script and use them to pregenerate tables of values. For example,

writeln!(out, "pub const MILLIT_NAMES: [&str; 1000] = [").unwrap();
for n in 0..1000
{
    writeln!(out, "    \"{}\",", name_millit(n)).unwrap();
}
writeln!(out, "];").unwrap();

writes to the file handle out the Rust source code for an array of the millit names. I also produce an array ILLI_NAMES, as well as integer arrays MILLIT_LENGTHS and ILLI_LENGTHS for the precomputed lengths of these names. All of these go in a module millit_tables, which will be used by the rest of the code.

In my main code, then, I write a function to generate number name strings:

fn name_illion(n: usize) -> String
{
    if n == 0
    {
        return "thousand".to_string();
    }

    let mut millits = millit_helper::to_millits(n);
    let mut name = String::new();
    while millits.len() > 0
    {
        let millit = millits.pop().unwrap();
        name.push_str(millit_tables::ILLI_NAMES[millit as usize]);
    }

    name.push_str("on");
    return name;
}

fn name_number(millits: &[u16]) -> String
{
    if millits.len() == 0
    {
        return "zero".to_string();
    }

    let mut name = String::new();
    for i in (0..millits.len()).rev()
    {
        let millit = millits[i];

        if i != millits.len() - 1
        {
            if millit == 0 { continue; }

            name.push_str(" ");
            if millit < 100
            {
                name.push_str("and ");
            }
        }

        name.push_str(millit_tables::MILLIT_NAMES[millit as usize]);

        if i > 0
        {
            name.push_str(" ");
            name.push_str(&name_illion(i-1));
        }
    }

    return name;
}

As you can see, I'm representing large numbers in base-1,000, as arrays/slices of millits encoded as u16; I use 16-bit integers because they're the smallest type that can fit numbers up to 999. The millits are ordered least-significant-first, so that millits[i] represents the millit with a place value of $1,{000}^i$. I also have another module, millit_helper, where I'll put various helper functions related to this base-1,000 representation; in the code above, you can see the function millit_helper::to_millits, which converts a usize number into this base-1,000 representation.

In order to do the search without explicitly constructing name strings along the way, I also write similar functions that just compute the length of a number. This is similar to the above, but replaces strings with their lengths and string concatenation with integer addition:

fn get_illion_length(n: usize) -> usize
{
    if n == 0
    {
        return "thousand".len();
    }

    let mut remaining_number = n;
    let mut total_length: usize = "on".len();
    while remaining_number > 0
    {
        let millit = remaining_number % 1_000;
        total_length += millit_tables::ILLI_LENGTHS[millit];
        remaining_number /= 1_000;
    }

    return total_length;
}

fn get_number_length(millits: &[u16]) -> usize
{
    if millits.len() == 0
    {
        return "zero".len();
    }

    let mut total_length: usize = 0;
    for i in 0..millits.len()
    {
        let millit = millits[i];
        if i != millits.len() - 1
        {
            if millit == 0 { continue; }

            total_length += 1;
            if millit < 100
            {
                total_length += " and".len();
            }
        }

        total_length += millit_tables::MILLIT_LENGTHS[millit as usize];
        if i > 0
        {
            total_length += 1 + get_illion_length(i-1);
        }
    }

    return total_length;
}

Since integer addition is commutative, unlike string concatenation, these functions need not process the millits most-significant-first, and indeed both of them process them least-significant-first. For get_number_length, this just simplifies the logic a bit, but for get_illion_length, this actually saves a bit of compute, since it's easy to extract millits least-significant-first using iterated modulo and division, avoiding the need to explicitly store all of the millits.

Search Algorithm

Now I implement the actual search, using the function get_number_length. The first step of the search is to find the smallest 373-repmillit whose name has at least the target length, which I implement as a binary search:

fn find_smallest_repmillit(target_length: usize) -> (Vec<u16>, usize)
{
    let length_373 = millit_tables::MILLIT_LENGTHS[373];
    if target_length <= length_373
    {
        return (vec![373], length_373);
    }

    // binary search for the number of millits

    let mut lower_num_millits = 1;
    let mut upper_num_millits = target_length / length_373 + 1;
    let mut upper_repmillit = vec![373; upper_num_millits];
    let mut upper_length = get_number_length(&upper_repmillit);
    while upper_num_millits - lower_num_millits > 1
    {
        let mid_num_millits = (lower_num_millits + upper_num_millits) / 2;
        let mid_repmillit = vec![373; mid_num_millits];
        let mid_length = get_number_length(&mid_repmillit);
        if mid_length >= target_length
        {
            upper_num_millits = mid_num_millits;
            upper_repmillit = mid_repmillit;
            upper_length = mid_length;
        }
        else
        {
            lower_num_millits = mid_num_millits;
        }
    }

    return (upper_repmillit, upper_length);
}

Like any binary search needs to be, this is initialised with an upper bound. Here, I use the target length divided by the length of 373 (plus one for good measure); this is essentially a lower bound on the length of a 373-repmillit where I don't count the -illion names or spaces. Finally, I implement the millit-by-millit search:

pub fn find_smallest_number(
    target_length: usize) -> (Vec<u16>, usize)
{
    let (mut millits, mut length) = find_smallest_repmillit(target_length);

    for i in (0..millits.len()).rev()
    {
        millits[i] = if i == millits.len()-1 {1} else {0};
        length = get_number_length(&millits);
        while (length < target_length) && (millits[i] < 373)
        {
            millits[i] += 1;
            length = get_number_length(&millits);
        }

        if length == target_length
        {
            return (millits, target_length);
        }
    }

    return (millits, length);
}

Results

After all this, I write some "glue" code to search for the smallest number whose length is at least the 7-chain, and to then generate that number's name as a string and save it to a text file. After a few short seconds of searching, the code finds the number 1,001,001,023,373,373,...,373,373, a number 12,684,696 millits long. The length of this number is exactly the 7-chain, and so this number is indeed the 8-chain. Its name begins with "one duodecilliquattuoroctogintasescentilliquattuornonagintasescentillion", and continues for over a billion characters more.

There are two things I want to impress upon you about this result. First of all, the search only took a few seconds, despite the fact that this implementation of the algorithm is actually quite unoptimised. For example, it redoes the number length evaluation for each iteration of the search. Second, the 8-chain itself is a very "compressible" number; of its millions of millits, all but the leading four are 373. These facts together suggest that finding the 9-chain, a number which we expect to be of order ${10}^{{10}^{\text{millions}}}$, might be feasible if I can optimise this search, since its ${10}^{\text{millions}}$ of millits would be similarly compressible and wouldn't all need to be stored explicitly.

Did We Get Lucky?

Recall that the algorithm I've been using to find $n$-chains is "find the smallest number whose length is at least the $(n-1)$-chain, and if that number's length is exactly the $(n-1)$-chain, we've found the $n$-chain", emphasis on the if. This doesn't always happen; the 6-chain, 113, for example, is 24 characters long, but the 5-chain is 23, not 24. The algorithm did succeed when finding the 7-chain and the 8-chain, whose lengths are exactly the 6-chain and the 7-chain respectively, so it raises the question of whether we can expect this to be the case for the 9-chain, or if we just got lucky.

To answer this question, I'll analyse the behaviour of the algorithm for large numbers. Once the first step of the algorithm is complete, and we've found the smallest 373-repmillit of at least our target length, we have a length excess that the second step of the algorithm seeks to minimise by changing the values of the millits. Thus, in order for the final number to be longer than the target length, the algorithm must fail to remove this excess after exhausting all millits. We can always remove at least one character per millit, since there exists a millit, 323, which is one character shorter than 373³. Thus, the amount of length excess we can remove is $\Omega (N)$ where $N$ is the number of millits. By contrast, the length excess is at most the number of the characters that the most significant millit contributes, which is dominated by the $O(\log N)$ growth rate of the leading -illion name. Thus, for sufficiently large numbers, the algorithm always removes all of the length excess, and the number found by the search is always exactly the target length; it wasn't just luck.

Finding the 9-Chain

Now that we know that this algorithm is correct for large numbers, I can go ahead and try to optimise it for finding the 9-chain. As discussed before, the key will be to represent the number "sparsely", with only the total count of millits and the leading millits being stored explicitly, and all following millits assumed to be 373. In fact, only the very last step of the algorithm deals with those leading millits at all; the rest of the algorithm deals only with 373-repmillits. So the bulk of the work in optimising the algorithm is in efficiently evaluating the lengths of 373-repmillits, and searching across these lengths.

Fast 373-Repmillit Lengths

The length of a 373-repmillit whose maximum -illion is $M$ (and whose number of millits is therefore $N=M+2$) is

for $M=0$ this is 72 (the length of 373,373), and each additional millit adds 33 characters (the 31 characters of 373 plus two spaces) plus the length of its -illion. This expression can't handle the $N=1$ case where there are no -illions, but that's fine since we're interested mainly in large numbers here, and this edge case is easy enough to handle separately. Equation 1 can further be decomposed as

where I've added $2M$ outside the summation for the -on suffixes. The core challenge, then, is evaluating that sum of -illis efficiently, since evaluating that sum directly is a non-starter when there are ${10}^{\text{millions}}$ of terms.

Case Where $M$ is a 999-Repmillit

To understand the technique I'll use for this, consider a similar but somewhat simpler problem: what is the sum of the digits in every number from 0 to 999,999? This can be written as

Since this is a "two-dimensional" summation, it's natural to represent its terms in a table, with $n$ being the rows and the digits of $n$ being the columns:

The key observation is that each column contains exactly 100,000 of each digit. The units column changes digit each row and cycles 100,000 times, the tens column changes digit every 10 rows and cycles 10,000 times, and so on. Thus,

Using a similar principle, I can efficiently evaluate Equation 2 for a maximum -illion $M=1,{000}^{ℳ}-1$ which is a 999-repmillit $ℳ$ millits long:

The terms of the summation can be represented in a table like the digits in the simple example from earlier:

This is a bit irregular, unlike the sum-of-digits example, in that there are empty cells where 0-illi ("nilli") would have otherwise gone. If those 0-illis were there, then each column would have exactly ${1000}^{ℳ-1}$ of each -illi. The sum of all of these -illi lengths is therefore

In general, column $i$ (zero-indexed, counting from right to left) has $1,{000}^i$ missing 0-illis; column 0 has one missing, column 1 has 1,000 missing, and so on. Thus, the total number of missing 0-illis is

Substituting this into Equation 6 and then substituting that into Equation 5, we obtain

In order to represent this in a form where its millits can more easily be read out, I'll use 1,000's complement

to turn the subtraction of missing 0-illis in Equation 8 into addition, obtaining

Moving some terms around, this becomes

This representation makes it quite easy to tell what the millits of this number are; the first term has zeros for all but a few leading millits (it's a multiple of a power of 1,000), the second term is a 994-repmillit, and the third term is a single-millit number. To see what I mean, here's the first few values of this as a table:

For $ℳ\ge 3$, the first term's nonzero millits are disjoint from the millits of the following terms, since adding 38 to a 994-repmillit only carries across one millit.

Now that I have this first piece of the optimised algorithm, I can resume programming. First, I take the code I have so far, that I used to find the 8-chain, and move it out into separate modules: number_naming for computing number names and lengths, and small_search for the search algorithm. I'll then write the optimised algorithm code into a new module large_search (you'll see later why I want to hold on to both search codes), whose first inclusion is the code for evaluating Equation 11:

fn get_leading_term_length_373_999(m: usize) -> usize
{
    debug_assert!(m >= 3);
    return 34_994 + m * millit_tables::ILLI_LENGTH_SUMS[999];
}

fn get_millits_length_373_999(m: usize) -> Vec<u16>
{
    debug_assert!(m > 0);
    if m == 1 { return vec![622, 57]; }
    if m == 2 { return vec![32, 175, 80]; }

    let mut millits: Vec<u16> = vec![994; m - 1];
    millits[0] = 32;
    millits[1] = 995;
    let leading_term = get_leading_term_length_373_999(m);
    let leading_millits = millit_helper::to_millits(leading_term);
    millits.extend(leading_millits);
    return millits;
}

Here, I handle the special case of separately from the general case, where I construct the millit array using the pattern we just saw. This code uses a new table of values millit_tables::ILLI_LENGTH_SUMS that I added to the build script, for the cumulative sums of -illi lengths.

Next, I need a function to search for the smallest value of $ℳ$ such that $L_{373}(1,{000}^{ℳ}-1)$ is at least the target length. To do this, I take advantage of the fact that, as $ℳ$ increases, the number of millits in $L_{373}(1,{000}^{ℳ}-1)$ strictly increases, so it's sufficient to just search the number of millits. I therefore write a function that gets the number of millits in $L_{373}(1,{000}^{ℳ}-1)$:

fn get_millit_count_length_373_999(m: usize) -> usize
{
    debug_assert!(m > 0);
    if m == 1 { return 2; }
    if m == 2 { return 3; }

    let leading_term = get_leading_term_length_373_999(m);
    return millit_helper::get_millit_count(leading_term) + m - 1;
}

Not only does this millit count strictly increase with $ℳ$, but in the vast majority of cases, this increase is by only one millit; the only time there's a larger increase is when the number of millits in the leading term increases. Thus, the millit count of $L_{373}(1,{000}^{ℳ}-1)$ is very tightly lower-bounded by $ℳ+1$. I therefore implement the search as a downward linear search starting from $ℳ$ equal to the number of millits in the target length:

fn find_smallest_373_999(target_length: &[u16]) -> (usize, Vec<u16>)
{
    if target_length.len() <= 1
    {
        return (1, get_millits_length_373_999(1));
    }

    // find unique value of m for which the number of millits is not less

    let mut m = target_length.len(); // initial upper bound
    let mut num_millits_m = get_millit_count_length_373_999(m);
    while num_millits_m > target_length.len()
    {
        m -= 1;
        num_millits_m = get_millit_count_length_373_999(m);
    }
    if num_millits_m < target_length.len()
    {
        m += 1;
    }

    // compare length to target length

    let length_m = get_millits_length_373_999(m);
    if millit_helper::compare(&length_m, target_length) >= 0
    {
        return (m, length_m)
    }

    return (m + 1, get_millits_length_373_999(m + 1));
}

Once we've found a value of $ℳ$ where $L_{373}(1,{000}^{ℳ}-1)$ has the same number of millits as the target length, there are two cases: either this length is greater than or equal to the target length, in which case $ℳ$ is the correct search result, or it's less, in which case $ℳ+1$ is the correct search result. This is what the last bit of code does, and it uses the function millit_helper::compare to compare these two base-1,000 numbers:

pub fn compare(a: &[u16], b: &[u16]) -> i8
{
    if a.len() < b.len() { return -1; }
    if a.len() > b.len() { return 1; }

    for i in (0..a.len()).rev()
    {
        if a[i] < b[i] { return -1; }
        if a[i] > b[i] { return 1; }
    }

    return 0;
}

Finding the Millits of $M$

So now we know how to find the number of millits $ℳ$ of the maximum -illion $M$ in the number we're searching for. The next step is to find $M$ itself, which I'll do using a millit-by-millit approach similar to the final step of this whole algorithm. To do this, I'll need to be able to re-evaluate $L_{373}(M)$ when modifying only one of its millits, and since I'll be starting from the 999-repmillit $M=1,{000}^{ℳ}-1$ and iterating from the most significant down, I can assume that all millits less significant than the modified millit are 999.

In order to represent the resulting length modification as an equation, I'll represent the $i$th millit of a number $n$ as $n[i]$, a notation which deliberately resembles array access, since I'm representing large numbers in my code as arrays of millits. To be precise,

Let $M$ and $M^{\prime }$ differ only in one millit $j$ ($M[i]=M^{\prime }[i]\forall i\ne j$), and let all millits of $M$ and $M^{\prime }$ less significant than $j$ be 999 (). Assuming without loss of generality that , the difference in length between the 373-repmillits with maximum -illions $M$ and $M^{\prime }$ is

where I've expanded $M-M^{\prime }$ in the first term using the fact that only millit $j$ differs between them. Once again, most of the complexity is in the sum over -illis. Here's an explicit example of the terms of this sum in a table, with $M^{\prime }=314,159,265,999,999$ and $M=314,159,299,999,999$ ($j=2$):

There are $(M[j]-M^{\prime }[j])\times 1,{000}^j$ (in this case, 34,000,000) rows in this table. For the columns (those on the left), the -illis do not change at all between rows. For the $i=j$ column, there are $1,{000}^j$ of each -illi from $(M^{\prime }[j]+1)$-illi (266-illi) to $M[j]$-illi (299-illi). Finally, for the columns (those on the right), there are $(M[j]-M^{\prime }[j])\times 1,{000}^{i-1}$ (34,000) of each -illi from 0-illi to 999-illi per column. Thus, Equation 13 becomes

For large $j$, this number is a relatively small number multiplied by a large power of 1,000, so only its most significant few millits are nonzero. Thus, when I implement this in code,

fn get_length_difference_max_illions(max_illion: &[u16], j: usize, mj: u16,
    left_illi_lengths: usize) -> (Vec<u16>, usize)
{
    // trivial case of no length difference
    if mj == max_illion[j] { return (vec![0], 0); }

    let lower_millit = cmp::min(mj, max_illion[j]);
    let upper_millit = cmp::max(mj, max_illion[j]);
    let delta_millit = (upper_millit - lower_millit) as usize;

    let upper_sum = millit_tables::ILLI_LENGTH_SUMS[upper_millit as usize];
    let lower_sum = millit_tables::ILLI_LENGTH_SUMS[lower_millit as usize];
    let sum_between = upper_sum - lower_sum;
    let leading_term = delta_millit * (35 + left_illi_lengths) + sum_between;
    if j == 0
    {
        let leading_term_millits = millit_helper::to_millits(leading_term);
        return (leading_term_millits, 0);
    }

    let sum_999 = millit_tables::ILLI_LENGTH_SUMS[999];
    let following_term = delta_millit * j * sum_999;
    let total = 1_000 * leading_term + following_term;
    let total_millits = millit_helper::to_millits(total);
    return (total_millits, j-1);
}

I make the function's return value a tuple consisting of the leading millits as well as the number of trailing zero millits that have been omitted, rather than explicitly storing the full millit representation. Also, instead of explicitly computing the sum of the lengths of the -illis left of $j$, I just have this function take that value as an argument that the caller must provide; you'll see why later.

The function above is the last piece I need in order to implement the millit-by-millit search for the maximum -illion $M$. This is a large function, so I'll break it down. First, I declare the function and write the initial code that sets us up for the iteration over millits:

fn find_max_illion(target_length: &[u16]) -> (Vec<u16>, usize)
{
    let smallest_373_999 = find_smallest_373_999(&target_length);
    let (num_millits, length_repmillit) = smallest_373_999;
    let mut length_excess_millits = millit_helper::subtract(
        length_repmillit, &target_length, 0);
    let mut max_illion: Vec<u16> = vec![999; num_millits];
    let mut left_illis: usize = 0;

    for i in (0..num_millits).rev()
    {

First, I call find_smallest_373_999 to find $ℳ$, then I set up the mutable variables that will be used over the iteration: the remaining length excess, the working millits of $M$, and the sum of the left -illi lengths. This uses a helper function millit_helper::subtract which takes as arguments the operand millits, as well as a currently-unused third argument which I'll explain later. Inside the for loop, the first thing I do for each millit is find the smallest value that that millit can be set to without removing too much length. This is implemented as a binary search:

        // binary search for lowest millit that doesn't remove too much length
        let mut new_millit_lower: u16 = if i == num_millits - 1 {1} else {0};
        let mut new_millit_upper = 999u16;
        let length_difference_result = get_length_difference_max_illions(
            &max_illion, i, new_millit_upper, left_illis);
        let (mut delta_length_upper, mut p_upper) = length_difference_result;
        while new_millit_upper - new_millit_lower > 1
        {
            let new_millit_mid = (new_millit_lower + new_millit_upper) / 2;
            let (delta_length_mid, p_mid) = get_length_difference_max_illions(
                &max_illion, i, new_millit_mid, left_illis);
            let comparison = millit_helper::compare(
                &delta_length_mid, &length_excess_millits[p_mid..]);
            if comparison <= 0
            {
                new_millit_upper = new_millit_mid;
                delta_length_upper = delta_length_mid;
                p_upper = p_mid;
            }
            else
            {
                new_millit_lower = new_millit_mid;
            }
        }

This of course involves a call to millit_helper::compare, where I accommodate the implicit trailing zeroes in the left-hand side by slicing off that many millits from the right-hand side. Once this binary search converges, either new_millit_lower or new_millit_upper is the appropriate value of this millit, so I do a comparison to find out which it is:

        // determine whether to use the upper or lower bound
        let (delta_length_lower, p_lower) = get_length_difference_max_illions(
            &max_illion, i, new_millit_lower, left_illis);
        let comparison = millit_helper::compare(
            &delta_length_lower, &length_excess_millits[p_lower..]);
        let (new_millit, delta_length, p) = if comparison <= 0
        {
            (new_millit_lower, delta_length_lower, p_lower)
        }
        else
        {
            (new_millit_upper, delta_length_upper, p_upper)
        };

Finally, I wrap up this iteration, and update the working variables for the next loop:

        // finish iteration and set up for the next iteration
        max_illion[i] = new_millit;
        left_illis += millit_tables::ILLI_LENGTHS[new_millit as usize];
        length_excess_millits = millit_helper::subtract(
            length_excess_millits, &delta_length, p);

        if millit_helper::compare(&length_excess_millits, &vec![0]) == 0
        {
            break;
        }
    }

Here, we see the third argument of millit_helper::subtract; it's the number of trailing zero millits to assume on the second argument, which allows this function to work with the implicit-trailing-zeroes representation returned by get_length_difference_max_illions. Also, we see above that, after each iteration, the code adds to left_illis the length of new_millit-illi, since the newly-set millit will be left of the working in all following iterations. This saves the function get_length_difference_max_illions from doing redundant work to re-evaluate this sum of lengths on each iteration. Outside the for loop, the code finishes by converting the remaining length excess from a base-1,000 representation to a binary integer, and then returning its results:

    let length_excess = millit_helper::from_millits(&length_excess_millits);
    return (max_illion, length_excess);
}

I then wrap this in a function find_smallest_repmillit which returns the number of millits $N=M+2$ of the 373-repmillit rather than the maximum -illion. This handles the edge case of $N\le 2$, and in the general case, evaluates $N$ from $M$ by adding 2 and handling carrying across millits. (I didn't write an addition function analogous to millit_helper::subtract because this is the only place in the code where base-1,000 addition is used.)

Finding the Leading Millits

Now that I can efficiently find the smallest 373-repmillit for large target lengths, it's time to implement the final step of the algorithm, which is to adjust the leading millits in order to remove as much of this length excess as possible. Working with length excess rather than raw length, as I've been doing so far, is the key optimisation here. The naive implementation I used to find the 8-chain fully re-evaluates the length of the number every time it changes a millit, but it's more efficient to just evaluate the reduction in length that results from changing a millit from 373 to some over value, and compare that to the remaining length excess.

When setting a millit to a nonzero value, the resulting reduction in length is just the length of 373 minus the length of the new millit value. When setting a millit to zero, however, the reduction in length includes the length of the -illion name for that millit, which is made up of millions of -illis. While it's possible to handle this without too much additional compute, it turns out not to be necessary; setting a millit to zero always removes too many characters, and I'll explain why using an inductive argument. First of all, setting the leading millit to zero removes too many characters, since the number that results from that is a shorter 373-repmillit, which the previous step of the algorithm already determined was shorter than the target length. As the algorithm iterates along the millits, both the length of the -illion and the length excess itself get smaller, but the latter shrinks faster than the former. Specifically, setting a millit to one removes 28 characters from the leading millit and 24 characters from all following millits (four less because of the "and" prefix and a space), but there are no -illions that much shorter than their successor⁴. Thus, the length removed by setting a millit to zero starts out larger than the length excess, and remains larger for the entire run of the algorithm.

Knowing that, I can now go ahead and code up this last step of the algorithm. First, I write a short helper function to get the length of a millit including the "and" prefix if it exists:

fn get_millit_length(millit: u16, is_leading: bool) -> usize
{
    let base_length = millit_tables::MILLIT_LENGTHS[millit as usize];
    if is_leading || (millit >= 100)
    {
        return base_length;
    }

    return base_length + " and".len();
}

Next, I write the function that actually finds the leading millits, beginning by setting up some variables and then finding the number of leading ones:

fn find_leading_millits(length_excess: usize, num_millits: usize)
    -> (usize, Vec<u16>, usize)
{
    let length_373 = millit_tables::MILLIT_LENGTHS[373];
    let max_reduction_leading = length_373 - get_millit_length(1, true);
    let max_reduction_following = length_373 - get_millit_length(1, false);
    let mut leading_ones = 0;
    let mut remaining_length_excess = length_excess;
    let mut remaining_millits = num_millits;

    // get number of leading ones
    if (length_excess >= max_reduction_leading) && (remaining_millits > 0)
    {
        leading_ones += 1;
        remaining_millits -= 1;
        remaining_length_excess -= max_reduction_leading;

        let additional_ones = cmp::min(remaining_millits,
            remaining_length_excess / max_reduction_following);
        leading_ones += additional_ones;
        remaining_millits -= additional_ones;
        remaining_length_excess -= additional_ones * max_reduction_following;
    }

I do this using a closed-form expression rather than explicitly iterating over each millit. After the leading ones, the remaining length excess is at most max_reduction_leading (28), so the function as a whole runs in $O(1)$ time. Next is finding the millits after the leading ones that remove this small remaining length excess:

    // find millits in between
    let mut millits_between: Vec<u16> = Vec::new();
    while (remaining_length_excess > 0) && (remaining_millits > 0)
    {
        let is_leading = remaining_millits == num_millits;
        let mut millit: u16 = 1;
        let mut millit_length = get_millit_length(millit, is_leading);
        while length_373 - millit_length > remaining_length_excess
        {
            millit += 1;
            millit_length = get_millit_length(millit, is_leading);
        }

        millits_between.push(millit);
        remaining_length_excess -= length_373 - millit_length;
        remaining_millits -= 1;
    }

    return (leading_ones, millits_between, remaining_length_excess);
}

Finally, I wrap this and the previous step of the algorithm into a single function that does the entire search:

pub fn find_smallest_number(
    target_length: &[u16]) -> (usize, Vec<u16>, Vec<u16>, usize)
{
    let repmillit_result = find_smallest_repmillit(&target_length);
    let (num_millits, repmillit_length_excess) = repmillit_result;
    let num_millits_num = millit_helper::from_millits(&num_millits);

    let (leading_ones, millits_between, length_excess) =
        find_leading_millits(repmillit_length_excess, num_millits_num);

    return (leading_ones, millits_between, num_millits, length_excess);
}

Automated Testing

So now I've written all of the code that can find the 9-chain. The logic is somewhat complex, though, which means there would've been many opportunities to introduce bugs. I'll therefore do some automated testing so that I can be confident that the code is correct.

First of all, I wrote some unit tests in the millit_helper and number_naming modules, but what I really want to test, of course, is the search logic. It's hard to write unit tests for that that cover the size of numbers I'd want to test, so instead I'll do integration testing where I sanity-check the search results and ensure they're consistent between the small_search and large_search implementations.

Up until now, my code had been structured, in Rust terms, as a binary crate, which is just an executable with an entry point inside the main.rs source file. However, to do integration testing, I need a library crate whose public API includes the functionality to be tested. To create a library crate out of my code, I create a lib.rs source file to serve as its entry point, and make the various modules children of that instead of main.rs. I then modify main.rs to import this library crate, making the binary crate a thin wrapper around the library crate.

Now I can begin writing the integration test. First, I write a helper function to convert the "sparse" representation returned by large_search::find_smallest_number into an explicit vector of millits of the kind returned by small_search::find_smallest_number, so that the two results can be directly compared:

fn get_millits_of_sparse_number(num_millits_millits: &[u16],
    leading_ones: usize, millits_between: &[u16]) -> Vec<u16>
{
    let num_millits = millit_helper::from_millits(&num_millits_millits);
    let mut millits = vec![373u16; num_millits];
    for i in 0..leading_ones
    {
        millits[num_millits - i - 1] = 1;
    }

    for i in 0..millits_between.len()
    {
        millits[num_millits - leading_ones - i - 1] = millits_between[i];
    }

    return millits;
}

I then write a function that tests the two search codes for a single given target length:

fn single_target_small_large_consistency_test(target_length: usize)
{
    println!("Testing target length {}", target_length);

    // run small search
    let (small_found_millits, small_length) =
        small_search::find_smallest_number(target_length);

    // evaluate length of small search result and make sure it matches
    let found_length =
        number_naming::get_number_length(&small_found_millits);
    assert!(small_length == found_length);

    // make sure the found number is at least the target length
    assert!(found_length >= target_length);

    // run large search
    let large_search_result = large_search::find_smallest_number(
        &millit_helper::to_millits(target_length));
    let (leading_ones, millits_between, num_millits, large_length_excess) =
        large_search_result;
    let found_length_excess = found_length - target_length;

    // make sure result length of small and large searches match
    assert!(large_length_excess == found_length_excess);

    // make sure small and large search results match
    let large_found_millits = get_millits_of_sparse_number(
        &num_millits, leading_ones, &millits_between);
    assert!(small_found_millits == large_found_millits);
}

Finally, I write a test function that checks every target length from 0 to 99,999, as well as some target lengths in the neighbourhoods of $L_{373}(999,999)$ and $L_{373}(999,999,999)$:

#[test]
#[ignore]
fn test_small_large_consistency()
{
    for target_length in 0..100_000
    {
        single_target_small_large_consistency_test(target_length);
    }

    for target_length in 80_174_032..80_176_032
    {
        single_target_small_large_consistency_test(target_length);
    }

    for target_length in 102_764_995_022..102_764_995_042
    {
        single_target_small_large_consistency_test(target_length);
    }
}

I set this test to be skipped by default using the #[ignore] attribute, since it takes a long time to run (a bit over three hours on my desktop computer, even when using compiler optimisations). Running this for the first time, my fears were confirmed, and my large search code did indeed have bugs, which I then tracked down and fixed. (Don't worry, all of the code snippets I've shown you are the fixed versions after I did this process.)

Results

Running the code that I'm now confident in the correctness of, I find that the 9-chain is 1,001,...,001,013,373,373,...,373, with 6,159,465 leading ones, and a total millit count of 3,493,319,...,004,877,178, a number which is itself 12,684,693 millits long. As expected, the length of this number is exactly the 8-chain.

The description above doesn't fully specify the 9-chain; I haven't told you what the millits under the ellipsis are in the number of millits of the 9-chain. When I looked at those millits, I wasn't able to discern any pattern in them, and there's also no particular value of millit that's more common than any other value:

This incompressibility strongly suggests that finding the 10-chain is intractable, since the number of millits of the 10-chain would itself be ${10}^{\text{millions}}$ of millits long, and these millits can't all be stored in computer memory or otherwise written down.

If you want the full results, including the exact number of millits in the 9-chain, you can download my code and run it yourself.

Conclusion

I've found the $n$-chains up to and including the 9-chain, whose values are:

The first six $n$-chains were trivial. The 7-chain took a bit of work to find by hand, requiring the use of the core millit-by-millit algorithm that I used to find all higher $n$-chains as well. To find the 8-chain, I implemented this core algorithm as a computer program, and we noticed that the 8-chain's millits were highly compressible, which suggested that finding the 9-chain was tractable. Ultimately, I managed to optimise the implementation of the core algorithm to take advantage of this compressibility, and found the 9-chain. The 9-chain turned out not to have any additional compressibility beyond what we saw in the 8-chain, so as far as I can tell, finding the 10-chain is intractable.

References

1. Robert Munafo. Large numbers at mrob. URL: https://www.mrob.com/pub/math/largenum.html#conway-wechsler (visited on 2026-06-04).