Problem 168: Number Rotations

Project Euler Problem 168 Solution

EulerSolve provides an optimized solution for Project Euler Problem 168, Number Rotations, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We seek decimal integers $N$ with at least two digits, no trailing zero, and at most 100 digits, such that moving the last digit of $N$ to the front produces an integer multiple of $N$. The required output is the sum of all such numbers modulo $10^5$. If $N$ has digits $x_{d-1}x_{d-2}\dots x_1x_0$, then the rotated number is $x_0x_{d-1}x_{d-2}\dots x_1$. This rotation preserves the number of digits, so the quotient $m=\frac{R}{N}$ must satisfy $1\le m\le 9$. That observation already compresses the search to a small set of multipliers. Mathematical Approach Let $d$ be the number of digits, let $r=x_0$ be the last digit, and write $$N=10q+r,\qquad 1\le r\le 9.$$ The rotation of $N$ is $$R=r\cdot 10^{d-1}+q,$$ and the condition in the problem is $$R=mN,\qquad m\in\{1,2,\dots,9\}.$$ The implementations use two equivalent viewpoints: a closed-form identity that shows there is at most one candidate for each triple $(d,m,r)$, and a carry recurrence that constructs that candidate digit by digit without ever forming a huge integer. One Candidate for Each Length, Multiplier, and Last Digit Starting from $R=mN$, multiply by 10 and eliminate $q$: $$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$$ So every solution must satisfy $$\boxed{(10m-1)N=r(10^d-1).}$$ Therefore $$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$$ This is a crucial simplification....

Detailed mathematical approach

Problem Summary

To right-rotate a number we move its last digit to the front: $142857$ becomes $714285$. The statement notes that $714285=5\times142857$, so $142857$ is a divisor of its right rotation. We must add up all integers $n$ with $10\lt n\lt10^{100}$ that divide their right rotation and give the last five digits of this sum, that is, the sum modulo $10^5$. ^[1] These numbers have between $2$ and $100$ digits. Repdigits, numbers whose digits are all equal such as $11$ or $777$, belong to the set as well: their rotation is the number itself, and every number divides itself.

The whole solution in one sentence: the rotation of a solution is the number times a single digit $m$, and once the length $d$, the multiplier $m$ and the last digit $r$ are chosen, long multiplication by $m$ from right to left forces all the other digits, so we run this short calculation for all $99\cdot81$ triples, keep the candidates whose product really is their rotation and add up their last five digits.

Mathematical Approach

Sections 1 to 7 describe all solutions through one simple equation and connect them with repeating decimals. The programs do not use that equation; they rebuild each candidate digit by digit, and Sections 8 to 10 show that this digit test accepts exactly the right numbers.

1. Small cases

A direct search over all $n\lt10^7$ gives a first picture. For each of the lengths $2$, $3$, $4$, $5$ and $7$ the only solutions are the nine repdigits, such as $11,22,\dots,99$ for two digits. Among the six-digit numbers there are seven more:

$102564$, $128205$, $153846$, $179487$, $205128$ and $230769$, whose rotations are four times the number, for example $410256=4\cdot102564$;
$142857$, whose rotation is five times the number.

The first six are $4,5,\dots,9$ times $25641$, and $39\cdot25641=999999$; similarly $7\cdot142857=999999$. So all seven are simple fractions of $10^6-1$. The next sections explain why.

2. The quotient is a single digit

Let $n$ have $d\ge2$ digits and write $n=10q+r$, where $r$ is the last digit and $q=\lfloor n/10\rfloor\ge1$ is formed by the other digits. The right rotation is

$$R=r\cdot10^{d-1}+q.$$

If $r=0$, then $R=q$ lies strictly between $0$ and $n$, so it is not a multiple of $n$: numbers ending in $0$ never qualify. If $r\ge1$, then $R$ has $d$ digits, so $R\lt10^d\le10n$, and the quotient $m=R/n$ of a solution is an integer with $1\le m\le9$. Every solution is therefore described by three small parameters: its length $d$, its last digit $r\in\{1,\dots,9\}$ and its multiplier $m\in\{1,\dots,9\}$.

3. One equation for every solution

Multiplying the rotation by $10$ gives $10R=r\cdot10^d+10q$${}=r\cdot10^d+n-r$. If $R=mn$, this becomes $10mn=r\cdot10^d+n-r$, that is,

$$(10m-1)\,n=r\,(10^d-1).$$

So each triple $(d,m,r)$ allows at most one candidate, $n=r(10^d-1)/(10m-1)$. For $142857$ we have $d=6$, $m=5$ and $r=7$, and indeed $49\cdot142857=6999993=7\cdot999999$.

4. Exactly which triples give a solution

Conversely, fix $d\ge2$ and digits $m,r\ge1$, and suppose that $10m-1$ divides $r(10^d-1)$, with quotient $n$. Rearranged, the equation reads $n-r=10\,(mn-r\cdot10^{d-1})$. So $n-r$ is a multiple of $10$, which means that $n$ ends in the digit $r$, and $q=(n-r)/10$ satisfies $mn=r\cdot10^{d-1}+q$. This is the rotation of $n$ only if $n$ really has $d$ digits. The upper bound always holds, because $r\le9\le10m-1$ gives $n\le10^d-1$. For the lower bound,

$$\begin{aligned}&(10m-1)\,(n-10^{d-1})\\&\quad=(r-m)\,10^d+10^{d-1}-r,\end{aligned}$$

which is positive if $r\ge m$, since $10^{d-1}\ge10\gt r$, and negative if $r\lt m$, since then $(r-m)\,10^d\le-10^d$. Hence $n\ge10^{d-1}$ exactly when $m\le r$. The case $r\lt m$ does occur: for $(d,m,r)=(6,4,1)$ the quotient is $999999/39=25641$, which has only five digits. Written with six digits, $025641$ satisfies $4\cdot025641=102564$, its rotation as a string, but the true rotation of $25641$ is $12564$, which is not a multiple of $25641$.

Finally, a solution determines its own length, last digit and multiplier, so different triples never produce the same number. Together with Sections 2 and 3 this proves the following description: the numbers asked for are exactly the integers $n=r(10^d-1)/(10m-1)$ with $2\le d\le100$ and $1\le m\le r\le9$ for which the division is exact, and each of them comes from exactly one such triple.

For two digits this can be checked by hand: $10m-1$ must divide $99r$. For $m=1$ this gives the repdigits $n=11r$. For $m\ge2$ the number $10m-1$ is $19$, $29$, $3\cdot13$, $49$, $59$, $3\cdot23$, $79$ or $89$, and the factors $13$, $19$, $23$, $29$, $49$, $59$, $79$, $89$ are coprime to $99$ and larger than any digit, so none of them divides $99r$. This agrees with the search of Section 1.

5. Repeating decimals

Dividing the equation of Section 3 by $(10m-1)(10^d-1)$ gives

$$\frac{n}{10^d-1}=\frac{r}{10m-1}.$$

If a decimal $y$ repeats a block of $d$ digits with integer value $b$ from the decimal point on, then $10^dy=b+y$, because shifting the point by $d$ places leaves the same tail; hence $y=b/(10^d-1)$, the block divided by the number written with $d$ nines. ^[4] So for $m\ge2$ the decimal expansion of the fraction $r/(10m-1)$ consists of the $d$ digits of the solution, repeated forever. For $142857$ the fraction is $7/49=1/7=0.142857\,142857\ldots$, and $142857$ is the classical cyclic number: its products with $1,2,\dots,6$ are all rotations of it, and $7\cdot142857=999999$. ^[5] The condition $m\le r$ of Section 4 means $10r\ge10m-1$, that is, $r/(10m-1)\ge1/10$: the expansion does not start with the digit $0$.

6. Which lengths occur

Let $g=\gcd(10m-1,r)$ be the greatest common divisor of $10m-1$ and $r$, and $k=(10m-1)/g$ the denominator of $r/(10m-1)$ in lowest terms, for example $7$ for $7/49$. Since $k$ and $r/g$ have no common factor, $10m-1$ divides $r(10^d-1)$ exactly when $k$ divides $10^d-1$, that is, when $10^d\equiv1\pmod k$; in general, $a\equiv b\pmod k$ means that $k$ divides $a-b$. Every number $10m-1$ ends in the digit $9$, so $k$ is coprime to $10$. The smallest exponent $\ell\ge1$ with $10^\ell\equiv1\pmod k$ is called the multiplicative order of $10$ modulo $k$, and $10^d\equiv1\pmod k$ holds exactly when $\ell$ divides $d$. ^[6] Indeed, write $d=s\ell+t$ with $0\le t\lt\ell$; then $10^d\equiv10^t$, and $10^t\equiv1$ forces $t=0$ because $\ell$ is the smallest such exponent. For example, the powers $10^1,\dots,10^6$ leave the remainders $3,2,6,4,5,1$ modulo $7$, so the order of $10$ modulo $7$ is $6$. Computing these orders for all pairs $m\le r$ gives:

$m=1$: $k$ divides $9$ and $10\equiv1\pmod9$, so $\ell=1$; every length works, and the solutions are the repdigits;
$m=2$: $k=19$ and $\ell=18$; $m=3$: $k=29$ and $\ell=28$;
$m=4$: $k=39$, or $k=13$ for $r=6$ and $r=9$; in both cases $\ell=6$;
$m=5$: $k=49$ and $\ell=42$, except for $r=7$, where $k=7$ and $\ell=6$;
$m=6$: $k=59$ and $\ell=58$; $m=7$: $k=69$, or $k=23$ for $r=9$, both with $\ell=22$;
$m=8$: $k=79$ and $\ell=13$; $m=9$: $k=89$ and $\ell=44$.

Each order divides $\varphi(k)$, the number of residues modulo $k$ that are coprime to $k$, as Lagrange's theorem requires. ^[6] When $d=j\ell$, the identity

$$\begin{aligned}10^{j\ell}-1&=(10^\ell-1)\\&\quad\cdot(1+10^\ell+\dots+10^{(j-1)\ell})\end{aligned}$$

shows that the solution of length $d$ consists of $j$ copies of the $\ell$-digit block $r(10^\ell-1)/(10m-1)$, for example $142857142857$ for $d=12$.

7. How many solutions there are

Counting the multiples of each order up to $100$ gives the number of solutions for each multiplier: $891$ repdigits for $m=1$, nine for each of the $99$ lengths, and then $40$, $21$, $96$, $24$, $4$, $12$, $14$ and $2$ solutions for $m=2,\dots,9$. In total there are $1104$ solutions, of which $213$ are not repdigits. A number whose product with $m$ is obtained by moving its last digit to the front is called $m$-parasitic, and the smallest one for each $m\ge2$ is the repeating block of a fraction $r/(10m-1)$ with $r\ge m$. ^[2] ^[3] For $m=2$ it is $105263157894736842$, whose double $210526315789473684$ is its rotation; for $m=8$ it has $13$ digits, $1012658227848$. The programs need none of these facts: they simply try every triple.

8. Long multiplication, read backwards

The programs never divide $r(10^d-1)$ by $10m-1$, which would need integers of about $100$ digits, beyond the built-in types of C++ and Java. Instead they rebuild the candidate from the right. Write $n=x_{d-1}\cdots x_1x_0$ in decimal, with $x_0=r$. Long multiplication of $n$ by the digit $m$ also works from the right: position $i$ receives $mx_i$ plus the carry $c_i$ from the previous position, with $c_0=0$, keeps the last digit of this number and passes the rest on as the next carry. ^[7] The rotation $R=x_0x_{d-1}\cdots x_1$ has the digit $x_{i+1}$ in position $i$ for $i\le d-2$ and the digit $x_0=r$ in position $d-1$. So the product $mn$ equals $R$ exactly when the equations

$$mx_i+c_i=x_{i+1}+10\,c_{i+1}$$

hold for $0\le i\le d-2$, together with

$$mx_{d-1}+c_{d-1}=r.$$

The last equation, which we call the closing condition, has no carry on its right side because $R$ has no digit beyond position $d-1$. Since $x_0=r$ and $c_0=0$ are known, the equation for $i=0$ determines $x_1$ as the last digit of $mr$ and $c_1$ as the rest; the equation for $i=1$ then determines $x_2$ and $c_2$, and so on. The rotation property therefore forces every digit of the candidate, one at a time. The numbers involved stay small: if $c_i\le m-1$, then $mx_i+c_i\le9m+m-1=10m-1$, so $c_{i+1}\le m-1$ as well, and no intermediate value exceeds $89$.

9. Why the digit test is exact

Fix $d\ge2$ and digits $m,r\ge1$, and let the recurrence of Section 8 produce the digits $x_1,\dots,x_{d-1}$ and carries $c_1,\dots,c_{d-1}$ from $x_0=r$ and $c_0=0$. We claim that the triple yields a solution if and only if the closing condition holds and the leading digit $x_{d-1}$ is not $0$, and that the solution is then $n=x_{d-1}\cdots x_1x_0$.

Suppose both tests pass. Multiply the equation of position $i$ by $10^i$ and the closing condition by $10^{d-1}$, and add everything up. The left side becomes $mn$ plus the carries $c_i$ weighted by $10^i$. On the right side the digits $x_1,\dots,x_{d-1},r$ stand in the positions $0,\dots,d-1$, so they form $R$; the carries $c_{i+1}$ appear with the weight $10^{i+1}$, which is exactly their weight on the left, and $c_0=0$. The carries cancel, so $mn=R$, and since $x_{d-1}\ne0$, the number $n$ really has $d$ digits and $R$ is its rotation. Conversely, if $n$ is a solution with length $d$, last digit $r$ and multiplier $m$, then long multiplication of $n$ by $m$ produces the digits of $mn=R$, so the digits of $n$ and the carries satisfy all the equations. Because the equations force their values one by one, these are exactly the values the recurrence produces, and $x_{d-1}\ne0$ because $n$ has $d$ digits. This proves the claim.

The same two arguments, without the assumption $x_{d-1}\ne0$, show that the closing condition alone holds exactly when $10m-1$ divides $r(10^d-1)$, and by Section 4 the leading digit is then nonzero exactly when $m\le r$. Both tests are needed: $161$ of the $8019$ triples with $d\le100$ pass the closing condition but end with a leading $0$.

10. Worked example: the digits of $142857$

For $(d,m,r)=(6,5,7)$ the recurrence runs as follows:

$5\cdot7+0=35$: $x_1=5$, $c_1=3$;
$5\cdot5+3=28$: $x_2=8$, $c_2=2$;
$5\cdot8+2=42$: $x_3=2$, $c_3=4$;
$5\cdot2+4=14$: $x_4=4$, $c_4=1$;
$5\cdot4+1=21$: $x_5=1$, $c_5=2$.

The closing condition holds, $5\cdot1+2=7=r$, and the leading digit $x_5=1$ is not $0$. Reading $x_5,\dots,x_0$ gives $142857$, and indeed $5\cdot142857=714285$. Two rejected triples show the other outcomes. For $(2,2,3)$ the only step gives $2\cdot3+0=6$, so $x_1=6$ and $c_1=0$, and the closing value $2\cdot6+0=12$ differs from $3$: the candidate $63$ fails, since its rotation $36$ is not $2\cdot63=126$. For $(6,4,1)$ the steps produce the digits $4,6,5,2,0$ with the carries $0,1,2,2,1$, and the closing value $4\cdot0+1=1$ equals $r$, but the leading digit is $0$: this is the string $025641$ of Section 4, which is correctly rejected.

11. Only the last five digits

Remainders can be added and multiplied in place of the numbers themselves: if $a\equiv b$ and $c\equiv e\pmod M$, then $a+c\equiv b+e$ and $ac\equiv be\pmod M$. ^[8] With $M=10^5$ we may therefore add up the residues of the solutions and reduce the total, and each residue can be built digit by digit: modulo $M$,

$$n\equiv\sum_{i=0}^{d-1}x_i\,(10^i\bmod M).$$

Every factor $10^i\bmod M$ with $i\ge5$ is $0$, so only the last five digits of each solution contribute. The recurrence must still run up to the top, because only the closing condition and the leading digit decide whether a candidate counts at all.

As a complete small example, take all solutions with at most six digits. The repdigits of length $d$ add up to $(1+2+\dots+9)(10^d-1)/9$${}=5(10^d-1)$, the six multiples of $25641$ add up to $39\cdot25641=999999$, and $142857$ remains, so the sum is

$$\begin{aligned}&5\sum_{d=2}^{6}(10^d-1)+999999+142857\\&\quad=5555475+1142856=6698331.\end{aligned}$$

Its last five digits, $98331$, are what the method returns for six digits, and the C++ program compares this value with a brute force before it computes the real sum.

How the Code Works

All three files run the same triple loop with the digit test of Sections 8 and 9 and the residues of Section 11. The C++ program ^[9] is the most complete. Its Options default to max_digits = 100 and modulo = 100000; parse_arguments accepts --max-digits=, --modulo= and --skip-checkpoints, rejects unknown options, empty values and non-digits, and requires at least $2$ digits and a modulus of at least $1$; parse_int_after_prefix does not guard against values beyond the range of int, so absurdly large numbers are not rejected safely. main returns $1$ when parsing fails, runs the checkpoints unless they are skipped, returns $2$ if one fails, and otherwise prints solve(max_digits, modulo).

search_number_mod(digits, multiplier, last_digit, modulo) handles one triple $(d,m,r)$. It starts with current $=r$, carry $=0$, value_mod $=r\bmod M$ and place_mod $=10\bmod M$. Each pass of the loop over pos $=1,\dots,d-1$ is one equation of Section 8: from next = multiplier * current + carry it takes the new digit next % 10 and the new carry next / 10, adds the digit times place_mod to value_mod and multiplies place_mod by $10$, both modulo $M$. After the loop, leading = multiplier * current + carry is the closing value. The function returns $0$ if current, now the leading digit $x_{d-1}$, is $0$ or if leading differs from $r$, and $n\bmod M$ otherwise. Returning $0$ for a rejected triple is safe, because adding $0$ does not change the sum.

solve(max_digits, modulo) loops over $d=2,\dots,$ max_digits, $m=1,\dots,9$ and $r=1,\dots,9$, without skipping the triples with $r\lt m$ and without the orders of Section 6; the tests reject the triples that fail. It adds the results in an unsigned 64-bit integer that is reduced only at the end, which is safe because the default run adds at most $8019$ values below $10^5$.

run_checkpoints first calls search_number_mod(6, 5, 7, 1000000000). With a modulus larger than the number, the residue is the number itself, which must be $142857$. It then compares solve(6, 100000) with brute_small(6, 100000), which tests every $n$ from $11$ to $999999$ with has_property. That function writes $n$ as a string with std::to_string, skips one-digit numbers and numbers ending in $0$, which never qualify by Section 2, moves the last character to the front, converts the result back with std::stoi and checks rotated_value % n == 0.

The Python and Java files write the same loop inline, in solve() and in main, with the fixed modulus $100000$, lengths up to $100$, no options and no checkpoints, and reduce the total after every addition. Java keeps the digit, the carry and the place value in int and the residue and the total in long. With the fixed modulus the digit arithmetic never exceeds $89$, every residue update and every reduced total stays below $2\cdot10^5$, and the unreduced C++ total stays below $8019\cdot10^5$, far inside 64 bits, so nothing overflows; the 64-bit arithmetic of the C++ version matters mainly for a large modulus given with --modulo=.

Complexity and Verification

For each length $d$ and each of the $81$ pairs $(m,r)$ the loop makes $d-1$ steps of a few integer operations, so the whole computation makes

$$81\sum_{d=2}^{100}(d-1)=81\cdot4950=400950$$

steps. For numbers of up to $D$ digits this is $81D(D-1)/2=O(D^2)$ time with $O(1)$ memory, instead of the $10^{100}$ candidates of a direct search. The C++ checkpoint, a brute force with string conversions over about a million numbers, is more work than the $400950$ steps of the solution itself, and every program still finishes in a fraction of a second. Using the orders of Section 6 would skip most triples, but for $100$ digits this is not worth the extra code.

For this article the following checks were run, separately from the published programs:

An arithmetic brute force over all $n\lt10^{12}$ finds exactly the predicted numbers: nine repdigits of every length, the seven six-digit numbers of Section 1 and their twelve-digit repetitions.
For all $8019$ triples with $2\le d\le100$, the recurrence accepts exactly the triples of Section 4 and produces the exact big-integer quotients $r(10^d-1)/(10m-1)$; the closing condition alone holds exactly when the division is exact.
Each of the $1104$ accepted numbers has $d$ digits, and its rotated decimal string equals $m\cdot n$. The counts, orders and repetitions agree with Sections 6 and 7, the smallest solution for each $m\ge2$ is the one listed in OEIS A092697, and the $124$ non-repdigit solutions with at most $58$ digits are exactly the $124$ terms of the A034089 b-file. ^[3]
The three published programs print the same value, the residue modulo $10^5$ of the exact big-integer sum of the $1104$ solutions. With --max-digits=6 the C++ program prints $98331$, the residue of $6698331$ from Section 11.

Footnotes and References

The references below supply the background facts used above; the equation for the solutions, the condition $m\le r$, the counts and the exactness of the digit test are derived in this article.

Project Euler 168 — Number Rotations. The official statement explains right rotation with 142857, whose rotation 714285 is 5 × 142857, and asks for the last five digits of the sum of all integers n with 10 < n < 10¹⁰⁰ that divide their right rotation.
Wikipedia — Parasitic number. Multiplying an n-parasitic number by n moves its last digit to the front; leading zeros are usually not allowed. The article builds such numbers from the period of k/(10n − 1) with a digit k ≥ n and lists the smallest ones for n = 1, …, 9, also called Dyson numbers.
OEIS A092697 lists the least n-parasitic numbers for n = 1, …, 9, with a formula through the order of 10 modulo (10n − 1)/gcd(k, 10n − 1) for digits k ≥ n. OEIS A034089 lists the numbers that are proper divisors of their right rotation, that is, the solutions other than repdigits, generated by the periods of i/(10k − 1) with 2 ≤ k ≤ i ≤ 9 and their repetitions; its b-file lists 124 terms.
Wikipedia — Repeating decimal. A block of n digits repeated from the decimal point on equals the block, read as an integer, divided by the number written with n nines; 1/7 = 0.142857… has a period of six digits.
Wikipedia — Cyclic number. In the best-known cyclic number, 142857, the products with 1 to 6 are rotations of the number, and 142857 × 7 = 999999.
Wikipedia — Multiplicative order. For coprime a and n, the order of a modulo n is the smallest k ≥ 1 with aᵏ ≡ 1 (mod n), and it divides φ(n). Order (group theory) states that aᵏ is the identity exactly when the order of a divides k.
Wikipedia — Multiplication algorithm. In the pseudocode of long multiplication each position adds the incoming carry to the digit product, keeps the result modulo the base and passes the quotient on as the next carry; with a one-digit multiplier this is the recurrence of Section 8.
Wikipedia — Modular arithmetic. Congruence is compatible with addition and multiplication, so reducing after every operation or only at the end gives the same remainder.
C++ — Euler168.cpp. The linked immutable revision contains search_number_mod, solve, brute_small and run_checkpoints. It is the implementation record for this article.

Problem 168 source code

C++

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

namespace {

using u64 = std::uint64_t;

struct Options {
    int max_digits = 100;
    int modulo = 100000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    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_int_after_prefix(arg, "--max-digits=", options.max_digits) ||
            parse_int_after_prefix(arg, "--modulo=", options.modulo)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.max_digits >= 2 && options.modulo >= 1;
}

u64 search_number_mod(const int digits, const int multiplier, const int last_digit, const int modulo) {
    u64 value_mod = static_cast<u64>(last_digit % modulo);
    int current = last_digit;
    int carry = 0;
    int place_mod = 10 % modulo;
    for (int pos = 1; pos < digits; ++pos) {
        const int next = multiplier * current + carry;
        carry = next / 10;
        current = next % 10;
        value_mod = (value_mod + static_cast<u64>(current) * static_cast<u64>(place_mod)) %
                    static_cast<u64>(modulo);
        place_mod = static_cast<int>((static_cast<u64>(place_mod) * 10ULL) %
                                     static_cast<u64>(modulo));
    }

    const int leading = multiplier * current + carry;
    if (current == 0 || leading != last_digit) {
        return 0;
    }
    return value_mod;
}

u64 solve(const int max_digits, const int modulo) {
    u64 sum = 0;
    for (int digits = 2; digits <= max_digits; ++digits) {
        for (int multiplier = 1; multiplier <= 9; ++multiplier) {
            for (int last_digit = 1; last_digit <= 9; ++last_digit) {
                sum += search_number_mod(digits, multiplier, last_digit, modulo);
            }
        }
    }
    return sum % static_cast<u64>(modulo);
}

bool has_property(const int n) {
    const std::string s = std::to_string(n);
    if (s.size() <= 1) {
        return false;
    }
    if (s.back() == '0') {
        return false;
    }
    const std::string rotated = s.back() + s.substr(0, s.size() - 1);
    const int rotated_value = std::stoi(rotated);
    return (rotated_value % n) == 0;
}

u64 brute_small(const int max_digits, const int modulo) {
    int upper = 1;
    for (int i = 0; i < max_digits; ++i) {
        upper *= 10;
    }
    u64 sum = 0;
    for (int n = 11; n < upper; ++n) {
        if (has_property(n)) {
            sum = (sum + static_cast<u64>(n % modulo)) % static_cast<u64>(modulo);
        }
    }
    return sum;
}

bool run_checkpoints() {
    if (search_number_mod(6, 5, 7, 1000000000) != 142857ULL) {
        std::cerr << "Checkpoint failed for 142857 sample" << '\n';
        return false;
    }
    if (solve(6, 100000) != brute_small(6, 100000)) {
        std::cerr << "Checkpoint failed for brute cross-check at max-digits=6" << '\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;
    }
    std::cout << solve(options.max_digits, options.modulo) << '\n';
    return 0;
}

Python

# Problem 168: Number Rotations
# Sum (mod 10^5) of all n (2+ digits, <= 10^100) where the last digit moves to front
# and the result equals n * multiplier for some 1 <= multiplier <= 9.

def solve():
    MOD = 100000
    total = 0
    for digits in range(2, 101):
        for m in range(1, 10):
            for last in range(1, 10):
                # Build the number digit by digit from right
                # n = ...d2 d1 d0, rotated = d0 d_{k-1} ... d1
                # rotated = m * n
                val_mod = last % MOD
                current = last
                carry = 0
                place_mod = 10 % MOD
                for pos in range(1, digits):
                    nxt = m * current + carry
                    carry = nxt // 10
                    current = nxt % 10
                    val_mod = (val_mod + current * place_mod) % MOD
                    place_mod = (place_mod * 10) % MOD
                leading = m * current + carry
                if current == 0 or leading != last:
                    continue
                total = (total + val_mod) % MOD
    print(total)

solve()

Java

public class Euler168 {
    public static void main(String[] args) {
        int MOD = 100000;
        long total = 0;
        for (int digits = 2; digits <= 100; digits++)
            for (int m = 1; m <= 9; m++)
                for (int last = 1; last <= 9; last++) {
                    long val = last % MOD;
                    int cur = last, carry = 0, place = 10 % MOD;
                    for (int pos = 1; pos < digits; pos++) {
                        int nxt = m * cur + carry;
                        carry = nxt / 10;
                        cur = nxt % 10;
                        val = (val + (long) cur * place) % MOD;
                        place = (int) ((long) place * 10 % MOD);
                    }
                    int leading = m * cur + carry;
                    if (cur == 0 || leading != last)
                        continue;
                    total = (total + val) % MOD;
                }
        System.out.println(total);
    }
}