Solution

Answer: 57808202

Let $S$ be the set of all 123-numbers.

A decimal number belongs to $S$ iff:

every digit is in ${1,2,3}$, and
for each digit that appears, its frequency also belongs to $S$.

For example:

$33\in S$ because digit $3$ appears $2$ times and $2\in S$.
$1112\in S$ because the counts are:
digit $1$: $3$ times,
digit $2$: $1$ time,

and both $1,3\in S$.

We seek

$$F(111111111111222333),$$

the $111111111111222333$-rd 123-number in increasing order.

1. Mathematical analysis

A crucial recursive observation

If a number has:

$a$ copies of digit $1$,
$b$ copies of digit $2$,
$c$ copies of digit $3$,

then the number is valid iff

$$a,b,c \in {0}\cup S.$$

For a fixed triple $(a,b,c)$, the number of valid strings is simply the multinomial count

$$\binom{a+b+c}{a,b,c} = \frac{(a+b+c)!}{a!b!c!}.$$

So the entire problem reduces to:

enumerate admissible count triples,
count how many valid strings exist for each total length,
unrank lexicographically.

Which count values can matter?

The target index is about $10^{17}$, so the answer length is not huge.

Computing cumulative counts by length shows:

all valid numbers of length $\le 37$ total

$$85,645,659,280,376,850,$$

while including length $38$ exceeds the target.

Thus the answer has length $38$.

Now observe:

any admissible count must itself be a 123-number $\le 38$,
the only such values are

$$1,2,3,11,12,13,21,22,23,31,32,33.$$

So we only need these 12 values (plus 0).

Counting all valid length-38 numbers

We consider all triples

$$(a,b,c)$$

with

$$a+b+c=38$$

and each component in

$${0,1,2,3,11,12,13,21,22,23,31,32,33}.$$

For each triple, add

$$\frac{38!}{a!b!c!}.$$

This gives

$$84,604,808,105,550,180$$

valid 123-numbers of length $38$.

The desired index inside length $38$ is therefore

$$111111111111222333 - 85645659280376850 = 25465451830845483.$$

Lexicographic unranking

Numbers of fixed length are ordered lexicographically.

We construct the answer digit by digit.

At each position:

try placing $1$,
count how many completions exist,
if the target index exceeds that count, subtract and try $2$,
otherwise keep $1$ and continue.

The number of completions after choosing a prefix is again a multinomial count using the remaining digit frequencies.

This yields the unique result:

$$13312122322122222113311233331213131323.$$

Finally compute modulo $123123123$:

$$13312122322122222113311233331213131323 \equiv 57808202 \pmod{123123123}.$$

2. Python implementation

from math import comb
from functools import lru_cache

TARGET = 111_111_111_111_222_333
MOD = 123_123_123

# All 123-numbers <= 38
VALID = [0, 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33]

@lru_cache(None)
def multinomial(a, b, c):
    """
    Number of strings containing:
        a copies of '1'
        b copies of '2'
        c copies of '3'
    """
    n = a + b + c
    return comb(n, a) * comb(n - a, b)

def count_length(L):
    """
    Count all 123-numbers of total length L.
    """
    total = 0

    for a in VALID:
        for b in VALID:
            c = L - a - b

            if c in VALID:
                total += multinomial(a, b, c)

    return total

# ------------------------------------------------------------
# Step 1: determine the answer length
# ------------------------------------------------------------

cumulative = 0
length = 0

while True:
    length += 1
    cnt = count_length(length)

    if cumulative + cnt >= TARGET:
        break

    cumulative += cnt

# Index inside this length block
k = TARGET - cumulative

# ------------------------------------------------------------
# Step 2: enumerate all admissible count triples
# ------------------------------------------------------------

triples = []

for a in VALID:
    for b in VALID:
        c = length - a - b

        if c in VALID:
            triples.append((a, b, c))

# ------------------------------------------------------------
# Step 3: lexicographic unranking
# ------------------------------------------------------------

answer_digits = []

for _ in range(length):

    for digit in "123":

        total = 0
        next_triples = []

        for a, b, c in triples:

            aa, bb, cc = a, b, c

            if digit == "1":
                if aa == 0:
                    continue
                aa -= 1

            elif digit == "2":
                if bb == 0:
                    continue
                bb -= 1

            else:
                if cc == 0:
                    continue
                cc -= 1

            total += multinomial(aa, bb, cc)
            next_triples.append((aa, bb, cc))

        if k > total:
            k -= total
        else:
            answer_digits.append(digit)
            triples = next_triples
            break

answer = int("".join(answer_digits))

print("F(n) =", answer)
print("Modulo =", answer % MOD)

3. Code walkthrough

`multinomial(a,b,c)`

Computes

$$\frac{(a+b+c)!}{a!b!c!}$$

using binomial coefficients:

comb(n, a) * comb(n - a, b)

`count_length(L)`

Enumerates every admissible triple:

(a,b,c)

with total length $L$, then sums the multinomial counts.

Determining the answer length

We accumulate counts by length until the cumulative total reaches the target index.

This reveals:

length = 38

Lexicographic construction

For each digit position:

tentatively place 1,
count all completions,
if too small, skip them,
otherwise keep 1.

Repeat for 2 and 3.

This is standard combinatorial unranking.

4. Verification against the examples

The program reproduces:

$F(4)=11$
$F(10)=31$
$F(40)=1112$
$F(1000)=1223321$
$F(6000)=2333333333323$

exactly as stated.

The final number has length $38$, which is consistent with the growth rate of the counts.

Answer: 57808202

Project Euler Problem 698