Problem 419: Look and Say Sequence

Project Euler Problem 419 Solution

EulerSolve provides an optimized solution for Project Euler Problem 419, Look and Say Sequence, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $A_1 = 1$, and obtain each later term by reading the previous term as consecutive runs of equal digits. Thus $$1 \to 11 \to 21 \to 1211 \to 111221 \to \cdots.$$ If $a_n$, $b_n$, and $c_n$ denote the numbers of digits $1$, $2$, and $3$ in $A_n$, the goal is to determine $(a_n,b_n,c_n)$ for an enormous index $n$. Directly generating $A_n$ is hopeless because the string length grows exponentially, so the solution must compress the evolution into a fixed-size linear system. Mathematical Approach Step 1: Replace strings by Conway atoms Conway's cosmological theorem states that, after finitely many initial terms, every look-and-say word generated from $1$ can be decomposed into a concatenation of 92 irreducible building blocks, usually called Conway atoms or Conway elements. The crucial point is that each atom has a deterministic one-step decay into a short list of atoms. Let $v_n \in \mathbb{N}^{92}$ be the atom-count vector of $A_n$, where $v_n(i)$ is the number of copies of atom $i$....

Detailed mathematical approach

Problem Summary

The look and say sequence starts with $T_1=1$, and every later word is obtained by reading the previous one aloud as runs of equal digits: $1$ is "one one", so $T_2=11$, and $21$ is "one two and one one", so $T_4=1211$. The words continue $111221$, $312211$, $13112221$, $1113213211$. Let $A(n)$, $B(n)$ and $C(n)$ be the number of ones, twos and threes in $T_n$. The statement gives $A(40)=31254$, $B(40)=20259$ and $C(40)=11625$, and asks for the three counts at $n=10^{12}$, each reduced modulo $2^{30}$ and separated by commas. ^[1]

The whole solution in one sentence: from the eighth word on, every word breaks into pieces taken from a fixed list of $92$ blocks whose neighbours never interact again, so counting digits turns into raising one $92\times92$ integer matrix to the power $n-8$ by repeated squaring modulo $2^{30}$.

Mathematical Approach

1. The word can never be written down

The lengths of the first words are 1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78. ^[3] They grow by about thirty per cent per step: the ratio of consecutive lengths tends to Conway's constant

$$\lambda=1.303577269034\ldots,$$

an algebraic integer of degree $71$. ^[2] ^[4] Already $T_{50}$ has $894\,810$ digits, and since $\log_{10}\lambda=0.11513\ldots$, the word at $n=10^{12}$ has about $10^{1.15\cdot10^{11}}$ digits — its length alone is a number of a hundred billion digits. We must count without ever building the word.

2. Only ones, twos and threes occur

Two claims are proved together: every word uses only the digits $1$, $2$ and $3$, and no run inside a word is longer than $3$. Both hold for $T_1=1$. Assume them for $T_n$ and let its runs have digits $d_1,\ldots,d_k$ and lengths $c_1,\ldots,c_k$. Each $c_i$ is at most $3$, hence a single character, and neighbouring runs differ, so $d_i\ne d_{i+1}$. The reading is therefore $T_{n+1}=c_1d_1c_2d_2\cdots c_kd_k$, which again uses only $1$, $2$ and $3$.

Its positions now alternate between run lengths and digits, so any four consecutive characters are either $c_i,d_i,c_{i+1},d_{i+1}$ or $d_i,c_{i+1},d_{i+1},c_{i+2}$, and both contain $d_i$ and $d_{i+1}$. Were all four equal we would get $d_i=d_{i+1}$, so no run of $T_{n+1}$ exceeds $3$ either and the induction closes. ^[2] Hence three counters suffice.

3. When does a word split?

Write $\operatorname{LS}(W)$ for the result of reading $W$ aloud, so $T_{n+1}=\operatorname{LS}(T_n)$.

Lemma. For non-empty words $U$ and $V$, the identity

$$\operatorname{LS}(UV)=\operatorname{LS}(U)\operatorname{LS}(V)$$

holds if and only if the last character of $U$ differs from the first character of $V$.

Proof. The runs of $UV$ are those of $U$ followed by those of $V$, except that the last run of $U$ and the first run of $V$ merge when their digits agree. Without a merge, reading $UV$ aloud gives the two readings side by side. With a merge, where the boundary runs have lengths $a$ and $b$, the merged reading writes $a+b$ and the shared digit, while the separate readings write $a$, the digit, $b$, the digit. As $a+b$ has at most one digit more than the larger of $a$ and $b$, the merged reading is strictly shorter, so the words differ. $\square$

To check by hand: with $U=V=1$ the condition fails and $\operatorname{LS}(11)=21$ is shorter than $1111$, while with $U=1$, $V=2$ it holds and $\operatorname{LS}(12)=1112$ is $11$ then $12$.

4. Splits that last forever

One split is not enough: the halves must stay separate for all time. Call $U\cdot V$ a permanent split if

$$\operatorname{LS}^k(UV)=\operatorname{LS}^k(U)\operatorname{LS}^k(V)$$

for every $k\ge0$. By the lemma this says that at every step the left half ends in a character different from the one the right half begins with — a condition on infinitely many words, which Section 6 settles with a finite check.

One case can be seen by hand. Reading $22$ aloud gives $22$ again, so a right half equal to $22$ never changes: every word ending in a one or a three splits permanently from a following $22$. By contrast $12\cdot22$ does not split even once, since reading $1222$ gives $1132$ and not $111222$.

5. Conway's ninety-two elements

Conway studied exactly this question and found a periodic table: $92$ words over $\{1,2,3\}$, named after the chemical elements from hydrogen to uranium in what he called audioactive decay, such that reading any one aloud yields a concatenation of words from the same list, every junction a permanent split. ^[2] ^[6] A word with no non-trivial permanent split is an element, one that splits is a compound, and Conway's cosmological theorem says that every non-empty word over $\{1,2,3\}$ without a run of four becomes a concatenation of one or more of these $92$ elements. ^[5] ^[6]

The shortest element is uranium, the single character $3$; the longest are beryllium and rhenium, each $42$ characters. Reading the short ones aloud checks the table by hand,

$$3\to13\to1113\to3113\to132113\to\cdots,$$

uranium, protactinium, thorium, actinium, radium, then francium and radon: the first six readings each give a single element, and the seventh splits radon into holmium and astatine.

6. Where the sequence enters the table

The theorem guarantees that our sequence eventually becomes a product of elements, but not which word is the first. A direct search answers that: none of $T_1,\dots,T_7$ can be cut into elements at all, while

$$T_8=1113213211=11132\cdot13211$$

is hafnium followed by tin, its only decomposition; that junction splits at least once, since hafnium ends in a two and tin begins with a one.

A finite check now makes the bookkeeping exact for all time. Let $S$ be the smallest set of ordered pairs of elements that holds the $33$ distinct pairs of neighbours inside a decay list and the pair hafnium–tin, and is closed under sending $(P,Q)$ to the last element of the decay list of $P$ paired with the first element of the decay list of $Q$. Closing it yields $258$ pairs, in each of which the left word's last character differs from the right word's first character.

Suppose a word is a product $E_{i_1}\cdots E_{i_m}$ of elements whose consecutive pairs all lie in $S$. The lemma applies at every junction, so reading it aloud merely concatenates the decay lists, and every junction of the new product is either a pair inside one decay list or the boundary pair supplied by the closure step, hence again in $S$. Since $T_8$ starts the induction, every $T_n$ with $n\ge8$ is a concatenation of the multiset of elements produced by $n-8$ applications of the decay rule, and digit counts ignore the order.

7. One matrix, raised to a power

For $n\ge8$ let $v_n\in\mathbb{N}^{92}$ count the elements of $T_n$, and let $M$ be the $92\times92$ matrix whose entry $M_{ij}$ counts copies of element $i$ in the decay list of element $j$. Then $v_{n+1}=Mv_n$, with $v_8$ a one in the hafnium and tin coordinates. The matrix is sparse: $143$ of its $8464$ entries are non-zero, with column sums the decay lengths, from $1$ to $6$; exactly one entry exceeds one, the $2$ recording that gallium's decay list holds calcium twice. With $D$ the $3\times92$ matrix whose entry in row $d$, column $i$ is the number of digits $d$ inside element $i$, digit counts add over concatenation, so

$$\begin{aligned}x_n&=\bigl(A(n),B(n),C(n)\bigr)\\&=D\,M^{\,n-8}v_8.\end{aligned}$$

Applying $M$ once per step would need $n-8$ products, so instead we form $M,M^2,M^4,\ldots$ by repeated squaring and apply only the powers picked out by the binary digits of $m=n-8$: at $n=21$, say, $m=13=8+4+1$ and $v_{21}=M^{8}M^{4}Mv_8$. For $m\ge1$ this costs $\lfloor\log_2 m\rfloor$ squarings and one matrix-vector product per set bit. ^[7] Here $m=999\,999\,999\,992$ has $40$ bits, $21$ of them set, so the program does $39$ squarings and $21$ matrix-vector products. Only additions and multiplications occur, both commuting with reduction, so every intermediate entry may be reduced modulo $2^{30}$ at once; the modulus is a power of two, so that reduction is the bit mask $2^{30}-1$ in MASK.

8. A worked example: words eight to twelve

Start from $T_8=1113213211$, one hafnium $11132$ and one tin $13211$. Each decays into a single element for three steps,

$$11132\to311312\to1321131112\to\cdots,$$

giving hafnium, lutetium, ytterbium, thulium on one side, tin, indium, cadmium, silver on the other. So $T_9$, $T_{10}$, $T_{11}$ are still products of two elements, with digit counts the sums of two columns of $D$: ytterbium $1321131112$ has $6$ ones, $2$ twos and $2$ threes, and cadmium $3113112211$ the same, so $A(10)=12$, $B(10)=4$, $C(10)=4$; thulium $11131221133112$ contributes $(8,3,3)$ and silver $132113212221$ contributes $(5,5,2)$, so $A(11)=13$, $B(11)=8$, $C(11)=5$.

At the next step the word splits into more than two pieces for the first time: thulium decays into erbium, calcium and cobalt, silver into palladium. The four columns are $(4,3,2)$, $(1,1,0)$, $(2,2,1)$ and $(11,4,3)$, so $A(12)=18$, $B(12)=10$, $C(12)=6$. Generating the word directly gives

$$T_{12}=3113112221232112111312211312113211,$$

which indeed has $18$ ones, $10$ twos, $6$ threes and $18+10+6=34$ characters. At $n=40$ the same bookkeeping reproduces the statement's checkpoint $31254$, $20259$, $11625$, whose sum $63138$ is the length of $T_{40}$.

How the Code Works

All three programs store the table of Section 5: Python and Java name its arrays ELEMENT_STRINGS, DECAY and DECAY_COUNT, C++ kElementStrings, kDecay and kDecayCount, with six decay slots per element, unused ones padded by $-1$. build_transition_matrix, or buildTransitionMatrix in Java, forms $M$ by adding one to the destination row and source column once per daughter, which is where gallium's two calciums are summed — hence += and not an assignment. All three then scan the element words into a $92\times3$ array, the transpose of $D$: C++ in build_digit_counts, finishing with counts_from_vector, while Python and Java build it inside solve and, unlike C++, test for a three explicitly instead of counting whatever is neither a one nor a two.

multiply_matrix is the schoolbook triple loop in index order $i,k,j$, skipping zero entries of both factors and masking each result entry; apply_matrix is its matrix-vector version. evolve_vector implements Section 7: it applies the current power of $M$ to the vector when the lowest bit of the exponent is set, shifts the exponent right, then squares the power whenever bits remain, set bit or not. solve sets the hafnium and tin coordinates of the start vector to one, evolves by $n-8$ steps and finishes with the weighted sums $Dv_n$. The C++ file adds the checks: look_and_say_step and direct_counts build words naively, solve falls back to them when $n\lt8$, and run_checkpoints verifies $(6,2,2)$ at $n=8$, the statement's values at $n=40$ and that both routes agree at $n=20$; its --n= switch sets the term index $n$, so the exponent is $n-8$, and --skip-checkpoints drops the checks.

A further difference is the accumulator width in apply_matrix, applyMatrix in Java. The powers of $M$ become nearly dense, so one row adds up to $92$ products of values below $2^{30}$, about $1.06\cdot10^{20}$ in all, and the real run reaches $3.43\cdot10^{19}$, past $2^{64}\approx1.84\cdot10^{19}$. C++ therefore accumulates in __uint128_t, a compiler extension. ^[8] Java uses long, a 64-bit signed two's-complement type whose overflowing additions keep the low-order bits of the true sum. ^[8] That is harmless: $2^{30}$ divides $2^{64}$, so the low $30$ bits of a wrapped sum are still the correct residue and the mask recovers it. Python's integers are unbounded, and in multiply_matrix no language can overflow, a single product of two masked entries staying below $2^{60}$. Finally, Python and Java fix $n=10^{12}$ and run no checkpoints, and MOD = 1000000000 at the top of the Python file is never used: the code reduces by MASK throughout, so the modulus applied is $2^{30}$.

Complexity and Verification

With $K=92$ elements and a fixed modulus, a squaring costs $O(K^3)$ operations and a matrix-vector product $O(K^2)$, so the time is $O(K^3\log n)$ and the working storage $O(K^2)$: a squaring holds the current matrix and its result, one C++ matrix being $92\cdot92$ unsigned 64-bit entries, $67\,712$ bytes. Java stores the same $8464$ values with array overhead, Python lists of references to arbitrary-precision integers. For the evolution at $n=10^{12}$ the zero-skipping loops execute $25\,915\,861$ multiply-and-adds in the squarings and $157\,188$ in the matrix-vector products, $26\,073\,049$ in all, against the dense bound $39K^3+21K^2=30\,546\,576$, the final digit conversion and the C++ checkpoints not counted. Built with g++ -O2 on one machine, C++ finishes in $0.02$ seconds including its checkpoints, Java in $0.06$ and Python in $1.5$; all three print the same three numbers.

The following was verified for this article by running code. Every one of the $92$ decay rows is an exact one-step factorisation: reading the element aloud gives exactly the concatenation of the listed elements. The closure of Section 6 has $258$ pairs, none of which can merge. The words $T_1,\dots,T_7$ admit no decomposition into elements and $T_8$ exactly one, and no word up to $T_{40}$ has a run longer than three, as Section 2 predicts. Most importantly, the element bookkeeping with exact unreduced integers reproduces the digit counts of the generated words for every $n$ from $8$ to $50$, the last with $894\,810$ characters, and $A(n)+B(n)+C(n)$ equals the length of $T_n$ throughout, as the rows of $D$ add up to the element lengths. Power iteration on $M$ gives the dominant eigenvalue $1.3035772690$, Conway's constant to ten digits, ^[4] with limiting digit frequencies $0.495071$, $0.320386$ and $0.184543$; direct generation at $n=60$ gives $0.495062$, $0.320365$ and $0.184573$, each within $0.00004$ of its limit. Finally, a simulation of Java's wrapping 64-bit arithmetic agrees with exact arbitrary-precision arithmetic modulo $2^{30}$ at $n=40$, $10^3$, $10^6$, $10^9$ and $10^{12}$.

Footnotes and References

The references below supply the background facts used above. The splitting lemma, the finite closure that proves permanence, the induction from the eighth word and the operation counts are derived in this article.

Project Euler 419 — Look and Say Sequence. The official statement builds the sequence from the word 1, defines A(n), B(n) and C(n) as the counts of ones, twos and threes in the n'th element, gives A(40) = 31254, B(40) = 20259, C(40) = 11625, and asks for the three counts at n = 10¹² modulo 2³⁰.
Wikipedia — Look-and-say sequence. States that from the start 1 no digit beyond 1, 2 and 3 appears; that consecutive lengths have ratio tending to Conway's constant λ = 1.303577269034…, the unique positive real root of a degree-71 polynomial; and that his cosmological theorem splits a sequence into atomic elements that never again interact with their neighbours — 92 of them over the digits 1, 2 and 3, named after the chemical elements up to uranium, with extra transuranic elements needed for other digits.
OEIS A005341 — Length of the n-th term of the Look and Say sequence. Gives the lengths 1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, … quoted in Section 1, and records that they obey a linear recurrence of order 72 whose positive characteristic root is about 1.3035.
OEIS A014715 — Decimal expansion of Conway's constant. Gives λ = 1.30357726903429639125709911215255189… and calls it an algebraic integer of degree 71; its first ten digits are what our power iteration reproduces.
S. B. Ekhad and D. Zeilberger, "Proof of Conway's Lost Cosmological Theorem", Electronic Research Announcements of the AMS 3 (1997), 78–82. A computer-assisted proof for Conway's audioactive operator; its programs build the periodic table of atoms and compute the minimal polynomial and value of Conway's constant.
MathWorld — Look and Say Sequence. Calls a string an element when it cannot be split into independent parts and a compound otherwise, and records that every string of ones, twos and threes with no four identical digits in a row decays into a compound of the 92 elements.
Wikipedia — Exponentiation by squaring. Describes binary exponentiation by repeated squaring for any associative product, square-matrix multiplication included, at ⌊log₂ n⌋ squarings plus further multiplications counted from the one-bits of the exponent. Section 7 derives the exact counts for the loop these solutions use.
The Java Language Specification, §4.2 gives long as a 64-bit signed two's-complement integer, and §15.18.2 that an overflowing integer addition gives the low-order bits of the mathematical sum in two's-complement form. The GCC manual on 128-bit integers documents the unsigned __int128 extension used by the C++ accumulator, and the Python documentation on numeric types states that integers have unlimited precision.

Problem 419 source code

C++

#include <array>
#include <cstdint>
#include <iostream>
#include <string>

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

constexpr int K = 92;
constexpr u64 MOD = 1ULL << 30;
constexpr u64 MASK = MOD - 1ULL;
constexpr u64 TARGET_N = 1000000000000ULL;

struct Options {
    u64 n = TARGET_N;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    try {
        value = static_cast<u64>(std::stoull(tail));
    } catch (...) {
        return false;
    }
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--n=", options.n)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << "\n";
        return false;
    }
    return options.n >= 1;
}

const std::array<const char*, K> kElementStrings = {
    "22",  //  1 H
    "13112221133211322112211213322112",  //  2 He
    "312211322212221121123222112",  //  3 Li
    "111312211312113221133211322112211213322112",  //  4 Be
    "1321132122211322212221121123222112",  //  5 B
    "3113112211322112211213322112",  //  6 C
    "111312212221121123222112",  //  7 N
    "132112211213322112",  //  8 O
    "31121123222112",  //  9 F
    "111213322112",  // 10 Ne
    "123222112",  // 11 Na
    "3113322112",  // 12 Mg
    "1113222112",  // 13 Al
    "1322112",  // 14 Si
    "311311222112",  // 15 P
    "1113122112",  // 16 S
    "132112",  // 17 Cl
    "3112",  // 18 Ar
    "1112",  // 19 K
    "12",  // 20 Ca
    "3113112221133112",  // 21 Sc
    "11131221131112",  // 22 Ti
    "13211312",  // 23 V
    "31132",  // 24 Cr
    "111311222112",  // 25 Mn
    "13122112",  // 26 Fe
    "32112",  // 27 Co
    "11133112",  // 28 Ni
    "131112",  // 29 Cu
    "312",  // 30 Zn
    "13221133122211332",  // 31 Ga
    "31131122211311122113222",  // 32 Ge
    "11131221131211322113322112",  // 33 As
    "13211321222113222112",  // 34 Se
    "3113112211322112",  // 35 Br
    "11131221222112",  // 36 Kr
    "1321122112",  // 37 Rb
    "3112112",  // 38 Sr
    "1112133",  // 39 Y
    "12322211331222113112211",  // 40 Zr
    "1113122113322113111221131221",  // 41 Nb
    "13211322211312113211",  // 42 Mo
    "311322113212221",  // 43 Tc
    "132211331222113112211",  // 44 Ru
    "311311222113111221131221",  // 45 Rh
    "111312211312113211",  // 46 Pd
    "132113212221",  // 47 Ag
    "3113112211",  // 48 Cd
    "11131221",  // 49 In
    "13211",  // 50 Sn
    "3112221",  // 51 Sb
    "1322113312211",  // 52 Te
    "311311222113111221",  // 53 I
    "11131221131211",  // 54 Xe
    "13211321",  // 55 Cs
    "311311",  // 56 Ba
    "11131",  // 57 La
    "1321133112",  // 58 Ce
    "31131112",  // 59 Pr
    "111312",  // 60 Nd
    "132",  // 61 Pm
    "311332",  // 62 Sm
    "1113222",  // 63 Eu
    "13221133112",  // 64 Gd
    "3113112221131112",  // 65 Tb
    "111312211312",  // 66 Dy
    "1321132",  // 67 Ho
    "311311222",  // 68 Er
    "11131221133112",  // 69 Tm
    "1321131112",  // 70 Yb
    "311312",  // 71 Lu
    "11132",  // 72 Hf
    "13112221133211322112211213322113",  // 73 Ta
    "312211322212221121123222113",  // 74 W
    "111312211312113221133211322112211213322113",  // 75 Re
    "1321132122211322212221121123222113",  // 76 Os
    "3113112211322112211213322113",  // 77 Ir
    "111312212221121123222113",  // 78 Pt
    "132112211213322113",  // 79 Au
    "31121123222113",  // 80 Hg
    "111213322113",  // 81 Tl
    "123222113",  // 82 Pb
    "3113322113",  // 83 Bi
    "1113222113",  // 84 Po
    "1322113",  // 85 At
    "311311222113",  // 86 Rn
    "1113122113",  // 87 Fr
    "132113",  // 88 Ra
    "3113",  // 89 Ac
    "1113",  // 90 Th
    "13",  // 91 Pa
    "3"  // 92 U
};

const std::array<std::array<int, 6>, K> kDecay = {
    {
        { 0, -1, -1, -1, -1, -1},  //  1 H
        {71, 90,  0, 19,  2, -1},  //  2 He
        { 1, -1, -1, -1, -1, -1},  //  3 Li
        {31, 19,  2, -1, -1, -1},  //  4 Be
        { 3, -1, -1, -1, -1, -1},  //  5 B
        { 4, -1, -1, -1, -1, -1},  //  6 C
        { 5, -1, -1, -1, -1, -1},  //  7 N
        { 6, -1, -1, -1, -1, -1},  //  8 O
        { 7, -1, -1, -1, -1, -1},  //  9 F
        { 8, -1, -1, -1, -1, -1},  // 10 Ne
        { 9, -1, -1, -1, -1, -1},  // 11 Na
        {60, 10, -1, -1, -1, -1},  // 12 Mg
        {11, -1, -1, -1, -1, -1},  // 13 Al
        {12, -1, -1, -1, -1, -1},  // 14 Si
        {66, 13, -1, -1, -1, -1},  // 15 P
        {14, -1, -1, -1, -1, -1},  // 16 S
        {15, -1, -1, -1, -1, -1},  // 17 Cl
        {16, -1, -1, -1, -1, -1},  // 18 Ar
        {17, -1, -1, -1, -1, -1},  // 19 K
        {18, -1, -1, -1, -1, -1},  // 20 Ca
        {66, 90,  0, 19, 26, -1},  // 21 Sc
        {20, -1, -1, -1, -1, -1},  // 22 Ti
        {21, -1, -1, -1, -1, -1},  // 23 V
        {22, -1, -1, -1, -1, -1},  // 24 Cr
        {23, 13, -1, -1, -1, -1},  // 25 Mn
        {24, -1, -1, -1, -1, -1},  // 26 Fe
        {25, -1, -1, -1, -1, -1},  // 27 Co
        {29, 26, -1, -1, -1, -1},  // 28 Ni
        {27, -1, -1, -1, -1, -1},  // 29 Cu
        {28, -1, -1, -1, -1, -1},  // 30 Zn
        {62, 19, 88,  0, 19, 29},  // 31 Ga
        {66, 30, -1, -1, -1, -1},  // 32 Ge
        {31, 10, -1, -1, -1, -1},  // 33 As
        {32, -1, -1, -1, -1, -1},  // 34 Se
        {33, -1, -1, -1, -1, -1},  // 35 Br
        {34, -1, -1, -1, -1, -1},  // 36 Kr
        {35, -1, -1, -1, -1, -1},  // 37 Rb
        {36, -1, -1, -1, -1, -1},  // 38 Sr
        {37, 91, -1, -1, -1, -1},  // 39 Y
        {38,  0, 19, 42, -1, -1},  // 40 Zr
        {67, 39, -1, -1, -1, -1},  // 41 Nb
        {40, -1, -1, -1, -1, -1},  // 42 Mo
        {41, -1, -1, -1, -1, -1},  // 43 Tc
        {62, 19, 42, -1, -1, -1},  // 44 Ru
        {66, 43, -1, -1, -1, -1},  // 45 Rh
        {44, -1, -1, -1, -1, -1},  // 46 Pd
        {45, -1, -1, -1, -1, -1},  // 47 Ag
        {46, -1, -1, -1, -1, -1},  // 48 Cd
        {47, -1, -1, -1, -1, -1},  // 49 In
        {48, -1, -1, -1, -1, -1},  // 50 Sn
        {60, 49, -1, -1, -1, -1},  // 51 Sb
        {62, 19, 50, -1, -1, -1},  // 52 Te
        {66, 51, -1, -1, -1, -1},  // 53 I
        {52, -1, -1, -1, -1, -1},  // 54 Xe
        {53, -1, -1, -1, -1, -1},  // 55 Cs
        {54, -1, -1, -1, -1, -1},  // 56 Ba
        {55, -1, -1, -1, -1, -1},  // 57 La
        {56,  0, 19, 26, -1, -1},  // 58 Ce
        {57, -1, -1, -1, -1, -1},  // 59 Pr
        {58, -1, -1, -1, -1, -1},  // 60 Nd
        {59, -1, -1, -1, -1, -1},  // 61 Pm
        {60, 19, 29, -1, -1, -1},  // 62 Sm
        {61, -1, -1, -1, -1, -1},  // 63 Eu
        {62, 19, 26, -1, -1, -1},  // 64 Gd
        {66, 63, -1, -1, -1, -1},  // 65 Tb
        {64, -1, -1, -1, -1, -1},  // 66 Dy
        {65, -1, -1, -1, -1, -1},  // 67 Ho
        {66, 60, -1, -1, -1, -1},  // 68 Er
        {67, 19, 26, -1, -1, -1},  // 69 Tm
        {68, -1, -1, -1, -1, -1},  // 70 Yb
        {69, -1, -1, -1, -1, -1},  // 71 Lu
        {70, -1, -1, -1, -1, -1},  // 72 Hf
        {71, 90,  0, 19, 73, -1},  // 73 Ta
        {72, -1, -1, -1, -1, -1},  // 74 W
        {31, 19, 73, -1, -1, -1},  // 75 Re
        {74, -1, -1, -1, -1, -1},  // 76 Os
        {75, -1, -1, -1, -1, -1},  // 77 Ir
        {76, -1, -1, -1, -1, -1},  // 78 Pt
        {77, -1, -1, -1, -1, -1},  // 79 Au
        {78, -1, -1, -1, -1, -1},  // 80 Hg
        {79, -1, -1, -1, -1, -1},  // 81 Tl
        {80, -1, -1, -1, -1, -1},  // 82 Pb
        {60, 81, -1, -1, -1, -1},  // 83 Bi
        {82, -1, -1, -1, -1, -1},  // 84 Po
        {83, -1, -1, -1, -1, -1},  // 85 At
        {66, 84, -1, -1, -1, -1},  // 86 Rn
        {85, -1, -1, -1, -1, -1},  // 87 Fr
        {86, -1, -1, -1, -1, -1},  // 88 Ra
        {87, -1, -1, -1, -1, -1},  // 89 Ac
        {88, -1, -1, -1, -1, -1},  // 90 Th
        {89, -1, -1, -1, -1, -1},  // 91 Pa
        {90, -1, -1, -1, -1, -1}  // 92 U
    }
};

const std::array<int, K> kDecayCount = {
    1,  //  1 H
    5,  //  2 He
    1,  //  3 Li
    3,  //  4 Be
    1,  //  5 B
    1,  //  6 C
    1,  //  7 N
    1,  //  8 O
    1,  //  9 F
    1,  // 10 Ne
    1,  // 11 Na
    2,  // 12 Mg
    1,  // 13 Al
    1,  // 14 Si
    2,  // 15 P
    1,  // 16 S
    1,  // 17 Cl
    1,  // 18 Ar
    1,  // 19 K
    1,  // 20 Ca
    5,  // 21 Sc
    1,  // 22 Ti
    1,  // 23 V
    1,  // 24 Cr
    2,  // 25 Mn
    1,  // 26 Fe
    1,  // 27 Co
    2,  // 28 Ni
    1,  // 29 Cu
    1,  // 30 Zn
    6,  // 31 Ga
    2,  // 32 Ge
    2,  // 33 As
    1,  // 34 Se
    1,  // 35 Br
    1,  // 36 Kr
    1,  // 37 Rb
    1,  // 38 Sr
    2,  // 39 Y
    4,  // 40 Zr
    2,  // 41 Nb
    1,  // 42 Mo
    1,  // 43 Tc
    3,  // 44 Ru
    2,  // 45 Rh
    1,  // 46 Pd
    1,  // 47 Ag
    1,  // 48 Cd
    1,  // 49 In
    1,  // 50 Sn
    2,  // 51 Sb
    3,  // 52 Te
    2,  // 53 I
    1,  // 54 Xe
    1,  // 55 Cs
    1,  // 56 Ba
    1,  // 57 La
    4,  // 58 Ce
    1,  // 59 Pr
    1,  // 60 Nd
    1,  // 61 Pm
    3,  // 62 Sm
    1,  // 63 Eu
    3,  // 64 Gd
    2,  // 65 Tb
    1,  // 66 Dy
    1,  // 67 Ho
    2,  // 68 Er
    3,  // 69 Tm
    1,  // 70 Yb
    1,  // 71 Lu
    1,  // 72 Hf
    5,  // 73 Ta
    1,  // 74 W
    3,  // 75 Re
    1,  // 76 Os
    1,  // 77 Ir
    1,  // 78 Pt
    1,  // 79 Au
    1,  // 80 Hg
    1,  // 81 Tl
    1,  // 82 Pb
    2,  // 83 Bi
    1,  // 84 Po
    1,  // 85 At
    2,  // 86 Rn
    1,  // 87 Fr
    1,  // 88 Ra
    1,  // 89 Ac
    1,  // 90 Th
    1,  // 91 Pa
    1  // 92 U
};

using Vector = std::array<u64, K>;
using Matrix = std::array<std::array<u64, K>, K>;

Matrix build_transition_matrix() {
    Matrix m{};
    for (int src = 0; src < K; ++src) {
        for (int j = 0; j < kDecayCount[src]; ++j) {
            const int dst = kDecay[src][j];
            m[static_cast<std::size_t>(dst)][static_cast<std::size_t>(src)] += 1ULL;
        }
    }
    return m;
}

std::array<std::array<u64, 3>, K> build_digit_counts() {
    std::array<std::array<u64, 3>, K> counts{};
    for (int i = 0; i < K; ++i) {
        for (const char ch : std::string(kElementStrings[i])) {
            if (ch == '1') {
                counts[i][0] += 1ULL;
            } else if (ch == '2') {
                counts[i][1] += 1ULL;
            } else {
                counts[i][2] += 1ULL;
            }
        }
    }
    return counts;
}

std::string look_and_say_step(const std::string& s) {
    std::string out;
    out.reserve(s.size() * 2);
    for (std::size_t i = 0; i < s.size();) {
        std::size_t j = i + 1;
        while (j < s.size() && s[j] == s[i]) {
            ++j;
        }
        out.push_back(static_cast<char>('0' + (j - i)));
        out.push_back(s[i]);
        i = j;
    }
    return out;
}

std::array<u64, 3> direct_counts(u64 n) {
    std::string s = "1";
    for (u64 step = 1; step < n; ++step) {
        s = look_and_say_step(s);
    }
    std::array<u64, 3> cnt{0ULL, 0ULL, 0ULL};
    for (const char ch : s) {
        if (ch == '1') {
            ++cnt[0];
        } else if (ch == '2') {
            ++cnt[1];
        } else {
            ++cnt[2];
        }
    }
    return cnt;
}

Matrix multiply_matrix(const Matrix& a, const Matrix& b) {
    Matrix c{};
    for (int i = 0; i < K; ++i) {
        for (int k = 0; k < K; ++k) {
            if (a[i][k] == 0ULL) {
                continue;
            }
            const u64 aik = a[i][k];
            for (int j = 0; j < K; ++j) {
                if (b[k][j] == 0ULL) {
                    continue;
                }
                const u128 cur = static_cast<u128>(c[i][j]) +
                                 static_cast<u128>(aik) * static_cast<u128>(b[k][j]);
                c[i][j] = static_cast<u64>(cur & MASK);
            }
        }
    }
    return c;
}

Vector apply_matrix(const Matrix& m, const Vector& v) {
    Vector out{};
    for (int i = 0; i < K; ++i) {
        u128 acc = 0;
        for (int j = 0; j < K; ++j) {
            if (m[i][j] == 0ULL || v[j] == 0ULL) {
                continue;
            }
            acc += static_cast<u128>(m[i][j]) * static_cast<u128>(v[j]);
        }
        out[i] = static_cast<u64>(acc & MASK);
    }
    return out;
}

Vector evolve_vector(Vector v, u64 steps) {
    Matrix power = build_transition_matrix();
    u64 e = steps;
    while (e > 0ULL) {
        if (e & 1ULL) {
            v = apply_matrix(power, v);
        }
        e >>= 1ULL;
        if (e > 0ULL) {
            power = multiply_matrix(power, power);
        }
    }
    return v;
}

std::array<u64, 3> counts_from_vector(const Vector& v,
                                      const std::array<std::array<u64, 3>, K>& digit_counts) {
    std::array<u64, 3> out{0ULL, 0ULL, 0ULL};
    for (int i = 0; i < K; ++i) {
        if (v[i] == 0ULL) {
            continue;
        }
        for (int d = 0; d < 3; ++d) {
            const u128 add = static_cast<u128>(out[d]) +
                             static_cast<u128>(v[i]) * static_cast<u128>(digit_counts[i][d]);
            out[d] = static_cast<u64>(add & MASK);
        }
    }
    return out;
}

std::array<u64, 3> solve(u64 n) {
    if (n < 8ULL) {
        return direct_counts(n);
    }

    // The 8th term (1113213211) decomposes as Hf + Sn in Conway's element table.
    Vector v{};
    v[71] = 1ULL;  // Hf (72)
    v[49] = 1ULL;  // Sn (50)

    v = evolve_vector(v, n - 8ULL);
    const auto digit_counts = build_digit_counts();
    return counts_from_vector(v, digit_counts);
}

bool run_checkpoints() {
    const auto c8 = solve(8);
    if (!(c8[0] == 6ULL && c8[1] == 2ULL && c8[2] == 2ULL)) {
        std::cerr << "Checkpoint failed: term 8 counts\n";
        return false;
    }

    const auto c40 = solve(40);
    if (!(c40[0] == 31254ULL && c40[1] == 20259ULL && c40[2] == 11625ULL)) {
        std::cerr << "Checkpoint failed: term 40 counts\n";
        return false;
    }

    const auto c20_direct = direct_counts(20);
    const auto c20_fast = solve(20);
    if (c20_direct != c20_fast) {
        std::cerr << "Checkpoint failed: direct vs fast at term 20\n";
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const auto ans = solve(options.n);
    std::cout << ans[0] << "," << ans[1] << "," << ans[2] << "\n";
    return 0;
}

Python

MOD = 1000000000
K = 92
MASK = (1 << 30) - 1

DECAY = [
    [0, -1, -1, -1, -1, -1],
    [71, 90, 0, 19, 2, -1],
    [1, -1, -1, -1, -1, -1],
    [31, 19, 2, -1, -1, -1],
    [3, -1, -1, -1, -1, -1],
    [4, -1, -1, -1, -1, -1],
    [5, -1, -1, -1, -1, -1],
    [6, -1, -1, -1, -1, -1],
    [7, -1, -1, -1, -1, -1],
    [8, -1, -1, -1, -1, -1],
    [9, -1, -1, -1, -1, -1],
    [60, 10, -1, -1, -1, -1],
    [11, -1, -1, -1, -1, -1],
    [12, -1, -1, -1, -1, -1],
    [66, 13, -1, -1, -1, -1],
    [14, -1, -1, -1, -1, -1],
    [15, -1, -1, -1, -1, -1],
    [16, -1, -1, -1, -1, -1],
    [17, -1, -1, -1, -1, -1],
    [18, -1, -1, -1, -1, -1],
    [66, 90, 0, 19, 26, -1],
    [20, -1, -1, -1, -1, -1],
    [21, -1, -1, -1, -1, -1],
    [22, -1, -1, -1, -1, -1],
    [23, 13, -1, -1, -1, -1],
    [24, -1, -1, -1, -1, -1],
    [25, -1, -1, -1, -1, -1],
    [29, 26, -1, -1, -1, -1],
    [27, -1, -1, -1, -1, -1],
    [28, -1, -1, -1, -1, -1],
    [62, 19, 88, 0, 19, 29],
    [66, 30, -1, -1, -1, -1],
    [31, 10, -1, -1, -1, -1],
    [32, -1, -1, -1, -1, -1],
    [33, -1, -1, -1, -1, -1],
    [34, -1, -1, -1, -1, -1],
    [35, -1, -1, -1, -1, -1],
    [36, -1, -1, -1, -1, -1],
    [37, 91, -1, -1, -1, -1],
    [38, 0, 19, 42, -1, -1],
    [67, 39, -1, -1, -1, -1],
    [40, -1, -1, -1, -1, -1],
    [41, -1, -1, -1, -1, -1],
    [62, 19, 42, -1, -1, -1],
    [66, 43, -1, -1, -1, -1],
    [44, -1, -1, -1, -1, -1],
    [45, -1, -1, -1, -1, -1],
    [46, -1, -1, -1, -1, -1],
    [47, -1, -1, -1, -1, -1],
    [48, -1, -1, -1, -1, -1],
    [60, 49, -1, -1, -1, -1],
    [62, 19, 50, -1, -1, -1],
    [66, 51, -1, -1, -1, -1],
    [52, -1, -1, -1, -1, -1],
    [53, -1, -1, -1, -1, -1],
    [54, -1, -1, -1, -1, -1],
    [55, -1, -1, -1, -1, -1],
    [56, 0, 19, 26, -1, -1],
    [57, -1, -1, -1, -1, -1],
    [58, -1, -1, -1, -1, -1],
    [59, -1, -1, -1, -1, -1],
    [60, 19, 29, -1, -1, -1],
    [61, -1, -1, -1, -1, -1],
    [62, 19, 26, -1, -1, -1],
    [66, 63, -1, -1, -1, -1],
    [64, -1, -1, -1, -1, -1],
    [65, -1, -1, -1, -1, -1],
    [66, 60, -1, -1, -1, -1],
    [67, 19, 26, -1, -1, -1],
    [68, -1, -1, -1, -1, -1],
    [69, -1, -1, -1, -1, -1],
    [70, -1, -1, -1, -1, -1],
    [71, 90, 0, 19, 73, -1],
    [72, -1, -1, -1, -1, -1],
    [31, 19, 73, -1, -1, -1],
    [74, -1, -1, -1, -1, -1],
    [75, -1, -1, -1, -1, -1],
    [76, -1, -1, -1, -1, -1],
    [77, -1, -1, -1, -1, -1],
    [78, -1, -1, -1, -1, -1],
    [79, -1, -1, -1, -1, -1],
    [80, -1, -1, -1, -1, -1],
    [60, 81, -1, -1, -1, -1],
    [82, -1, -1, -1, -1, -1],
    [83, -1, -1, -1, -1, -1],
    [66, 84, -1, -1, -1, -1],
    [85, -1, -1, -1, -1, -1],
    [86, -1, -1, -1, -1, -1],
    [87, -1, -1, -1, -1, -1],
    [88, -1, -1, -1, -1, -1],
    [89, -1, -1, -1, -1, -1],
    [90, -1, -1, -1, -1, -1]
]

DECAY_COUNT = [
    1, 5, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 
    5, 1, 1, 1, 2, 1, 1, 2, 1, 1, 6, 2, 2, 1, 1, 1, 1, 1, 2, 4, 
    2, 1, 1, 3, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 4, 1, 1, 
    1, 3, 1, 3, 2, 1, 1, 2, 3, 1, 1, 1, 5, 1, 3, 1, 1, 1, 1, 1, 
    1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1
]

ELEMENT_STRINGS = [
    "22", "13112221133211322112211213322112", "312211322212221121123222112",
    "111312211312113221133211322112211213322112", "1321132122211322212221121123222112",
    "3113112211322112211213322112", "111312212221121123222112", "132112211213322112",
    "31121123222112", "111213322112", "123222112", "3113322112", "1113222112", "1322112",
    "311311222112", "1113122112", "132112", "3112", "1112", "12", "3113112221133112",
    "11131221131112", "13211312", "31132", "111311222112", "13122112", "32112",
    "11133112", "131112", "312", "13221133122211332", "31131122211311122113222",
    "11131221131211322113322112", "13211321222113222112", "3113112211322112",
    "11131221222112", "1321122112", "3112112", "1112133", "12322211331222113112211",
    "1113122113322113111221131221", "13211322211312113211", "311322113212221",
    "132211331222113112211", "311311222113111221131221", "111312211312113211",
    "132113212221", "3113112211", "11131221", "13211", "3112221", "1322113312211",
    "311311222113111221", "11131221131211", "13211321", "311311", "11131",
    "1321133112", "31131112", "111312", "132", "311332", "1113222", "13221133112",
    "3113112221131112", "111312211312", "1321132", "311311222", "11131221133112",
    "1321131112", "311312", "11132", "13112221133211322112211213322113",
    "312211322212221121123222113", "111312211312113221133211322112211213322113",
    "1321132122211322212221121123222113", "3113112211322112211213322113",
    "111312212221121123222113", "132112211213322113", "31121123222113",
    "111213322113", "123222113", "3113322113", "1113222113", "1322113",
    "311311222113", "1113122113", "132113", "3113", "1113", "13", "3"
]

def build_transition_matrix():
    m = [[0] * K for _ in range(K)]
    for src in range(K):
        for j in range(DECAY_COUNT[src]):
            dst = DECAY[src][j]
            m[dst][src] += 1
    return m

def multiply_matrix(a, b):
    c = [[0] * K for _ in range(K)]
    for i in range(K):
        for k in range(K):
            if a[i][k] == 0: continue
            aik = a[i][k]
            for j in range(K):
                if b[k][j] == 0: continue
                c[i][j] = (c[i][j] + aik * b[k][j]) & MASK
    return c

def apply_matrix(m, v):
    out = [0] * K
    for i in range(K):
        acc = 0
        for j in range(K):
            if m[i][j] == 0 or v[j] == 0: continue
            acc += m[i][j] * v[j]
        out[i] = acc & MASK
    return out

def evolve_vector(v, steps):
    power = build_transition_matrix()
    e = steps
    while e > 0:
        if e & 1:
            v = apply_matrix(power, v)
        e >>= 1
        if e > 0:
            power = multiply_matrix(power, power)
    return v

def solve():
    v = [0] * K
    v[71] = 1 # Hf
    v[49] = 1 # Sn
    
    n = 1000000000000
    v = evolve_vector(v, n - 8)
    
    digit_counts = [[0] * 3 for _ in range(K)]
    for i in range(K):
        for ch in ELEMENT_STRINGS[i]:
            if ch == '1': digit_counts[i][0] += 1
            elif ch == '2': digit_counts[i][1] += 1
            elif ch == '3': digit_counts[i][2] += 1
            
    out = [0, 0, 0]
    for i in range(K):
        if v[i] == 0: continue
        for d in range(3):
            out[d] = (out[d] + v[i] * digit_counts[i][d]) & MASK
            
    return f"{out[0]},{out[1]},{out[2]}"

if __name__ == '__main__':
    print(solve())

Java

public class Euler419 {
    private static final int K = 92;
    private static final long MOD = 1L << 30;
    private static final long MASK = MOD - 1L;

    private static final int[][] DECAY = {
            { 0, -1, -1, -1, -1, -1 }, { 71, 90, 0, 19, 2, -1 }, { 1, -1, -1, -1, -1, -1 },
            { 31, 19, 2, -1, -1, -1 }, { 3, -1, -1, -1, -1, -1 }, { 4, -1, -1, -1, -1, -1 },
            { 5, -1, -1, -1, -1, -1 }, { 6, -1, -1, -1, -1, -1 }, { 7, -1, -1, -1, -1, -1 },
            { 8, -1, -1, -1, -1, -1 }, { 9, -1, -1, -1, -1, -1 }, { 60, 10, -1, -1, -1, -1 },
            { 11, -1, -1, -1, -1, -1 }, { 12, -1, -1, -1, -1, -1 }, { 66, 13, -1, -1, -1, -1 },
            { 14, -1, -1, -1, -1, -1 }, { 15, -1, -1, -1, -1, -1 }, { 16, -1, -1, -1, -1, -1 },
            { 17, -1, -1, -1, -1, -1 }, { 18, -1, -1, -1, -1, -1 }, { 66, 90, 0, 19, 26, -1 },
            { 20, -1, -1, -1, -1, -1 }, { 21, -1, -1, -1, -1, -1 }, { 22, -1, -1, -1, -1, -1 },
            { 23, 13, -1, -1, -1, -1 }, { 24, -1, -1, -1, -1, -1 }, { 25, -1, -1, -1, -1, -1 },
            { 29, 26, -1, -1, -1, -1 }, { 27, -1, -1, -1, -1, -1 }, { 28, -1, -1, -1, -1, -1 },
            { 62, 19, 88, 0, 19, 29 }, { 66, 30, -1, -1, -1, -1 }, { 31, 10, -1, -1, -1, -1 },
            { 32, -1, -1, -1, -1, -1 }, { 33, -1, -1, -1, -1, -1 }, { 34, -1, -1, -1, -1, -1 },
            { 35, -1, -1, -1, -1, -1 }, { 36, -1, -1, -1, -1, -1 }, { 37, 91, -1, -1, -1, -1 },
            { 38, 0, 19, 42, -1, -1 }, { 67, 39, -1, -1, -1, -1 }, { 40, -1, -1, -1, -1, -1 },
            { 41, -1, -1, -1, -1, -1 }, { 62, 19, 42, -1, -1, -1 }, { 66, 43, -1, -1, -1, -1 },
            { 44, -1, -1, -1, -1, -1 }, { 45, -1, -1, -1, -1, -1 }, { 46, -1, -1, -1, -1, -1 },
            { 47, -1, -1, -1, -1, -1 }, { 48, -1, -1, -1, -1, -1 }, { 60, 49, -1, -1, -1, -1 },
            { 62, 19, 50, -1, -1, -1 }, { 66, 51, -1, -1, -1, -1 }, { 52, -1, -1, -1, -1, -1 },
            { 53, -1, -1, -1, -1, -1 }, { 54, -1, -1, -1, -1, -1 }, { 55, -1, -1, -1, -1, -1 },
            { 56, 0, 19, 26, -1, -1 }, { 57, -1, -1, -1, -1, -1 }, { 58, -1, -1, -1, -1, -1 },
            { 59, -1, -1, -1, -1, -1 }, { 60, 19, 29, -1, -1, -1 }, { 61, -1, -1, -1, -1, -1 },
            { 62, 19, 26, -1, -1, -1 }, { 66, 63, -1, -1, -1, -1 }, { 64, -1, -1, -1, -1, -1 },
            { 65, -1, -1, -1, -1, -1 }, { 66, 60, -1, -1, -1, -1 }, { 67, 19, 26, -1, -1, -1 },
            { 68, -1, -1, -1, -1, -1 }, { 69, -1, -1, -1, -1, -1 }, { 70, -1, -1, -1, -1, -1 },
            { 71, 90, 0, 19, 73, -1 }, { 72, -1, -1, -1, -1, -1 }, { 31, 19, 73, -1, -1, -1 },
            { 74, -1, -1, -1, -1, -1 }, { 75, -1, -1, -1, -1, -1 }, { 76, -1, -1, -1, -1, -1 },
            { 77, -1, -1, -1, -1, -1 }, { 78, -1, -1, -1, -1, -1 }, { 79, -1, -1, -1, -1, -1 },
            { 80, -1, -1, -1, -1, -1 }, { 60, 81, -1, -1, -1, -1 }, { 82, -1, -1, -1, -1, -1 },
            { 83, -1, -1, -1, -1, -1 }, { 66, 84, -1, -1, -1, -1 }, { 85, -1, -1, -1, -1, -1 },
            { 86, -1, -1, -1, -1, -1 }, { 87, -1, -1, -1, -1, -1 }, { 88, -1, -1, -1, -1, -1 },
            { 89, -1, -1, -1, -1, -1 }, { 90, -1, -1, -1, -1, -1 }
    };

    private static final int[] DECAY_COUNT = {
            1, 5, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 2, 1, 1, 6, 2,
            2, 1, 1, 1, 1, 1, 2, 4, 2, 1, 1, 3, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 4, 1, 1, 1, 3, 1, 3,
            2, 1, 1, 2, 3, 1, 1, 1, 5, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1
    };

    private static final String[] ELEMENT_STRINGS = {
            "22", "13112221133211322112211213322112", "312211322212221121123222112",
            "111312211312113221133211322112211213322112", "1321132122211322212221121123222112",
            "3113112211322112211213322112", "111312212221121123222112", "132112211213322112",
            "31121123222112", "111213322112", "123222112", "3113322112", "1113222112", "1322112",
            "311311222112", "1113122112", "132112", "3112", "1112", "12", "3113112221133112",
            "11131221131112", "13211312", "31132", "111311222112", "13122112", "32112",
            "11133112", "131112", "312", "13221133122211332", "31131122211311122113222",
            "11131221131211322113322112", "13211321222113222112", "3113112211322112",
            "11131221222112", "1321122112", "3112112", "1112133", "12322211331222113112211",
            "1113122113322113111221131221", "13211322211312113211", "311322113212221",
            "132211331222113112211", "311311222113111221131221", "111312211312113211",
            "132113212221", "3113112211", "11131221", "13211", "3112221", "1322113312211",
            "311311222113111221", "11131221131211", "13211321", "311311", "11131",
            "1321133112", "31131112", "111312", "132", "311332", "1113222", "13221133112",
            "3113112221131112", "111312211312", "1321132", "311311222", "11131221133112",
            "1321131112", "311312", "11132", "13112221133211322112211213322113",
            "312211322212221121123222113", "111312211312113221133211322112211213322113",
            "1321132122211322212221121123222113", "3113112211322112211213322113",
            "111312212221121123222113", "132112211213322113", "31121123222113",
            "111213322113", "123222113", "3113322113", "1113222113", "1322113",
            "311311222113", "1113122113", "132113", "3113", "1113", "13", "3"
    };

    private static long[][] buildTransitionMatrix() {
        long[][] m = new long[K][K];
        for (int src = 0; src < K; ++src) {
            for (int j = 0; j < DECAY_COUNT[src]; ++j) {
                int dst = DECAY[src][j];
                m[dst][src] += 1L;
            }
        }
        return m;
    }

    private static long[][] multiplyMatrix(long[][] a, long[][] b) {
        long[][] c = new long[K][K];
        for (int i = 0; i < K; ++i) {
            for (int k = 0; k < K; ++k) {
                if (a[i][k] == 0)
                    continue;
                long aik = a[i][k];
                for (int j = 0; j < K; ++j) {
                    if (b[k][j] == 0)
                        continue;
                    c[i][j] = (c[i][j] + aik * b[k][j]) & MASK;
                }
            }
        }
        return c;
    }

    private static long[] applyMatrix(long[][] m, long[] v) {
        long[] out = new long[K];
        for (int i = 0; i < K; ++i) {
            long acc = 0;
            for (int j = 0; j < K; ++j) {
                if (m[i][j] == 0 || v[j] == 0)
                    continue;
                acc += m[i][j] * v[j];
            }
            out[i] = acc & MASK;
        }
        return out;
    }

    private static long[] evolveVector(long[] v, long steps) {
        long[][] power = buildTransitionMatrix();
        long e = steps;
        while (e > 0) {
            if ((e & 1L) != 0) {
                v = applyMatrix(power, v);
            }
            e >>= 1L;
            if (e > 0) {
                power = multiplyMatrix(power, power);
            }
        }
        return v;
    }

    public static String solve() {
        long[] v = new long[K];
        v[71] = 1;
        v[49] = 1;

        long n = 1000000000000L;
        v = evolveVector(v, n - 8);

        long[][] digitCounts = new long[K][3];
        for (int i = 0; i < K; ++i) {
            for (int c = 0; c < ELEMENT_STRINGS[i].length(); ++c) {
                char ch = ELEMENT_STRINGS[i].charAt(c);
                if (ch == '1')
                    digitCounts[i][0]++;
                else if (ch == '2')
                    digitCounts[i][1]++;
                else if (ch == '3')
                    digitCounts[i][2]++;
            }
        }

        long[] out = new long[3];
        for (int i = 0; i < K; ++i) {
            if (v[i] == 0)
                continue;
            for (int d = 0; d < 3; ++d) {
                out[d] = (out[d] + v[i] * digitCounts[i][d]) & MASK;
            }
        }

        return out[0] + "," + out[1] + "," + out[2];
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}