Problem 405: A Rectangular Tiling

Project Euler Problem 405 Solution

EulerSolve provides an optimized solution for Project Euler Problem 405, A Rectangular Tiling, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $f(n)$ denote the tiling count defined by the problem. The key fact used by the implementation is that this counting sequence already has an exact closed form, so the task is no longer to enumerate tilings but to evaluate that formula at an enormous index. The program is written in terms of $f(10^k)$, and the actual Project Euler instance uses $k=10^{18}$, so the target quantity is $f(10^{10^{18}})\bmod 17^7$. Mathematical Approach Step 1: Start from the closed form The C++, Python, and Java implementations all begin with the identity $$f(n)=1-\frac{(-1)^n}{15}-\frac{4}{3}2^n+\frac{2}{5}4^n.$$ This means the original tiling combinatorics have been compressed into three exponential terms and a constant. Once this formula is known, the whole problem becomes modular arithmetic with very large exponents. Step 2: Why the formula still gives integers Although the expression contains fractions, the result is always an integer. Multiply both sides by $15$: $$15f(n)=15-(-1)^n-20\cdot 2^n+6\cdot 4^n.$$ The right-hand side is divisible by $3$ and by $5$....

Detailed mathematical approach

Problem Summary

A rectangle twice as long as it is wide is tiled by rectangles of the same shape. $T(0)$ is the rectangle itself; every later tiling replaces all tiles at once, each by four tiles of half its length and width: one crosswise at each end of the long side, and the square between them cut by its middle line parallel to that side into the other two, which point like the tile they replace. ^[1] Let $f(n)$ count the points of $T(n)$ where four tiles meet. The statement gives $f(1)=0$, $f(4)=82$ and $f(10^9)\bmod 17^7=126897180$, and asks for $f(10^k)$ with $k=10^{18}$, modulo $17^7$.

The whole solution in one sentence: the four half-size copies of $T(n-1)$ inside $T(n)$ keep their own meeting points and add new ones only where the marks of two neighbouring copies line up, which a rule modulo $3$ counts, giving a recursion whose closed form in $4^n$, $2^n$ and $(-1)^n$ is read modulo $17^7$.

Mathematical Approach

1. The replacement rule in coordinates

Put one tile as $[0,2]\times[0,1]$. The rule replaces it by

$$\begin{aligned}&[0,\tfrac12]\times[0,1],\quad [\tfrac32,2]\times[0,1],\\&[\tfrac12,\tfrac32]\times[0,\tfrac12],\\&[\tfrac12,\tfrac32]\times[\tfrac12,1].\end{aligned}$$

The first two stand crosswise at the ends; the middle square is halved by $y=\tfrac12$. A tile with a vertical long side is treated the same way after a quarter turn. The reflections $x\mapsto2-x$ and $y\mapsto1-y$ map the four new tiles onto each other, so the subdivision depends only on whether the long side is horizontal or vertical, not on how the tile is turned. The subdivided tile has no interior point on four tiles, since $(\tfrac12,\tfrac12)$ and $(\tfrac32,\tfrac12)$ lie on three each; hence $f(0)=f(1)=0$, including the first checkpoint $f(1)=0$.

Each replacement turns one tile into four, so $T(n)$ has $4^n$ congruent tiles of short side $2^{-n}$ times the rectangle's width. Measuring in units of that side, the rectangle is the box $[0,2^{n+1}]\times[0,2^n]$ and every tile is a $2\times1$ or $1\times2$ rectangle with integer corners.

2. What it means for four tiles to meet

Consider the four quadrants around an interior point $P$ of the box. A tile containing $P$ covers one of them if $P$ is a corner of it, two if $P$ lies inside an edge, four if $P$ is interior to it, and the tiles cover each quadrant once. So $f(n)$ counts the points that are corners of exactly four tiles; a corner of two tiles that is an inner edge point of a third lies on three, a T-junction. A boundary point has at most two quadrants inside, so never carries four.

3. Four half-size copies

Fix $n\ge1$ and put $q=2^{n-1}$. One application of the rule splits the box into the end tiles $[0,q]\times[0,2^n]$, $[3q,4q]\times[0,2^n]$ and the middle tiles $[q,3q]\times[0,q]$, $[q,3q]\times[q,2q]$. Each is subdivided $n-1$ more times, so carries a copy of $T(n-1)$, halved and possibly turned by a quarter. Four tiles meeting strictly inside a region belong to that copy alone, so the regions contribute $4f(n-1)$. Every other meeting point lies on one of three shared edges:

the middle edge $y=q$, for $q\lt x\lt3q$;
the two end edges $x=q$ and $x=3q$, for $0\lt y\lt2^n$.

With $g(n)$ for the meeting points on these edges, $f(n)=4f(n-1)+g(n)$. Everything now depends on the marks a subdivided tile leaves on its sides.

4. The marks on the side of a subdivided tile

Take a tile carrying a copy of $T(m)$ and one of its sides. The subdivision leaves marks on it: the points where an inner edge ends. Measured in unit steps from one end, let $D_m$ be the marks on a long side (length $2^{m+1}$) and $S_m$ those on a short side (length $2^m$); corners do not count. Reading the bottom of the subdivided tile of Section 1 from left to right: the short side of the left end tile, a $T(m-1)$ copy; the point $2^{m-1}$ where it meets the middle square; the long side of a middle tile, also a $T(m-1)$ copy; the point $3\cdot2^{m-1}$; the short side of the right end tile. Hence, for $m\ge1$,

$$\begin{aligned}D_m={}&S_{m-1}\cup\{2^{m-1}\}\\&\cup(2^{m-1}+D_{m-1})\\&\cup\{3\cdot 2^{m-1}\}\\&\cup(3\cdot 2^{m-1}+S_{m-1}).\end{aligned}$$

A short side is exactly the long side of one end tile, so $S_m=D_{m-1}$ for $m\ge1$, in the same coordinates. From $D_0=S_0=\varnothing$ we get $D_1=\{1,3\}$, $D_2=\{2,3,5,6\}$ and

$$D_3=\{1,3,4,6,7,9,10,12,13,15\}.$$

For the sizes $A(m)=|D_m|$ the two recursions give $A(m)=A(m-1)+2A(m-2)+2$ for $m\ge2$, with $A(0)=0$ and $A(1)=2$; so $A(m)$ runs $0,2,4,10,20,42,84,170$ for $m=0,\dots,7$.

5. A rule modulo 3 for the marks

These sets look irregular but are not: $x$ lies in $D_m$ exactly when $1\le x\le2^{m+1}-1$ and

$$x\not\equiv 2^m \pmod 3.$$

For $m=3$, $2^3=8\equiv2$, and dropping $2,5,8,11,14$ from $1,\dots,15$ leaves exactly the ten elements of $D_3$.

The proof is induction on $m$. For $m=0$ the only candidate $x=1\equiv2^0$ is excluded and $D_0=\varnothing$; for $m=1$ the recursion gives $\{1,3\}$ and $2^1\equiv2$ excludes only $x=2$. For $m\ge2$ take the five pieces in turn, with $S_{m-1}=D_{m-2}$ and the two induction hypotheses; their ranges cover $1\le x\le2^{m+1}-1$ once each.

In the first piece the excluded class is $2^{m-2}$, and $2^m=4\cdot2^{m-2}$${}\equiv2^{m-2}\pmod3$: the same class.
$x=2^{m-1}$ is a mark, and $2^{m-1}\not\equiv2\cdot2^{m-1}=2^m$ because $2^{m-1}\not\equiv0$.
In the third piece $x=2^{m-1}+y$ with $y\not\equiv2^{m-1}$; and $x\equiv2^m$ means $y\equiv2^m-2^{m-1}\equiv2^{m-1}$, the same condition.
$x=3\cdot2^{m-1}\equiv0$ is a mark, and $2^m\not\equiv0$.
In the last piece $x=3\cdot2^{m-1}+y\equiv y$ with $y\not\equiv2^{m-2}\equiv2^m$, again the condition on $x$.

Three consequences follow. The condition is symmetric, since $x\mapsto2^{m+1}-x$ preserves it because $2^{m+1}-2^m=2^m$; so it does not matter from which end a side is read. The midpoint of a long side is $2^m$, which lies in the excluded class, so the middle of a long side is never a mark. And with $L=2^{m+1}-1$: for odd $m$, $3\mid L$ and the three classes share the range equally; for even $m$ one class has a member too many, that of $x=1$, which is then the excluded one. Either way the excluded class has $(2^{m+1}+(-1)^m)/3$ members, so

$$\begin{aligned}A(m)&=L-\frac{2^{m+1}+(-1)^m}{3}\\&=\frac{2^{m+2}-(-1)^m-3}{3},\end{aligned}$$

as in the list above.

6. The middle edge

Above and below the middle edge lie the two middle copies of $T(n-1)$, of which it is a long side of length $2^n$; by the symmetry just proved both carry the marks $D_{n-1}$ at the same places. An interior point is a corner of two tiles below exactly when it is a mark from below, and of two above exactly when it is a mark from above, so the meeting points are the common marks, $A(n-1)$ of them.

7. The two end edges

Assume $n\ge2$, so $D_{n-2}$ is defined; for $n=1$ Section 1 gives $g(1)=0=A(1)-2$. Left of the edge $x=q$ is the end tile, a copy of $T(n-1)$ whose long side this edge is, so the marks from the left are $D_{n-1}$. On the right the two middle copies each meet it along a short side of length $q=2^{n-1}$, with marks $S_{n-1}=D_{n-2}$, and between them sits $y=q$, a corner of both. The marks from the right are thus

$$D_{n-2}\cup\{q\}\cup(q+D_{n-2}).$$

Which are marks from the left too? Not $y=q$: it is the midpoint of the long side on the left. Let $y\in D_{n-2}$, that is $y\not\equiv2^{n-2}$. The classes $2^{n-2}$ and $2^{n-1}$ are the two non-zero classes modulo $3$, so:

$y$ itself lies in $D_{n-1}$ exactly when $y\not\equiv2^{n-1}$, that is when $y\equiv0\pmod3$;
$q+y\equiv2^{n-1}+y$ lies in $D_{n-1}$ exactly when $y\not\equiv0$, that is when $y\equiv2^{n-1}\pmod3$.

Every $y\in D_{n-2}$ meets exactly one of the two conditions, so yields exactly one meeting point, on the lower or the upper half, never both and never neither. Each end edge thus carries $A(n-2)$ points, and over the three edges,

$$\begin{aligned}g(n)&=A(n-1)+2A(n-2)\\&=A(n)-2,\end{aligned}$$

the last step being the recursion for $A$.

8. The recursion, and f(4) by hand

Collecting Sections 3 and 7,

$$\begin{aligned}f(n)&=4f(n-1)+A(n)-2\\&\quad (n\ge1),\\ f(0)&=0.\end{aligned}$$

The increments $A(n)-2$ are $0,2,8,18,40,82$ for $n=1,\dots,6$, so $f(1)=0$ and $f(2)=2$. Those two can be named: for $n=2$ the box is $8\times4$ with $16$ tiles, the middle edge runs at height $2$ from $x=2$ to $x=6$, and the marks $D_1=\{1,3\}$ of a long side of length $4$ put them at $(3,2)$ and $(5,2)$. Then $f(3)=4\cdot2+8=16$ and

$$f(4)=4\cdot16+18=82,$$

the second value in the statement.

9. The closed form

The increment is $A(n)-2$${}=\tfrac43\cdot2^n-\tfrac13(-1)^n-3$, so the recursion is linear with constant coefficients, solved by a particular solution plus the solutions of $f(n)=4f(n-1)$. ^[2] Try $f(n)=a4^n+b2^n+c(-1)^n+d$ and form $f(n)-4f(n-1)$: the $4^n$ part cancels, $b2^n$ leaves $-b2^n$, $c(-1)^n$ leaves $5c(-1)^n$ and $d$ leaves $-3d$. Matching the increment gives $b=-\tfrac43$, $c=-\tfrac1{15}$ and $d=1$; then $f(0)=0$ forces $a=\tfrac25$, and

$$\begin{aligned}15f(n)={}&6\cdot4^n-20\cdot2^n\\&-(-1)^n+15.\end{aligned}$$

The right-hand side is always divisible by $15$. Modulo $3$ the terms $15$ and $6\cdot4^n$ vanish and $2\equiv-1$, so $-(-1)^n-20\cdot2^n$${}\equiv-(-1)^n-(-1)^{n+1}=0$. Modulo $5$ the terms $15$ and $20\cdot2^n$ vanish and $4\equiv-1$, so $-(-1)^n+6\cdot4^n$${}\equiv-(-1)^n+(-1)^n=0$. As a check, $n=4$ gives $(1536-320-1+15)/15=82$.

10. Reading the formula modulo 17 to the seventh

Let $M=17^7=410338673$. An inverse of $a$ modulo $M$ is a $b$ with $ab\equiv1$: modulo $17$, the inverse of $3$ is $6$, since $3\cdot6=18\equiv1$. It exists exactly when $a$ and the modulus are coprime, ^[3] which $3$, $5$ and $15$ are to $M$, so the closed form may be read modulo $M$:

$$\begin{aligned}f(n)\equiv{}&1-(-1)^n\cdot15^{-1}\\&-4\cdot2^n\cdot3^{-1}\\&+2\cdot4^n\cdot5^{-1}\pmod M.\end{aligned}$$

The large powers $2^n$ and $4^n$ are handled by Euler's theorem: for $a$ coprime to $M$, $a^{\varphi(M)}\equiv1$, so a power of $a$ depends on its exponent only modulo $\varphi(M)$. ^[4] Here $\varphi(M)$ counts the integers in $1,\dots,M$ coprime to $M$; as $17$ is prime the others are its $17^6$ multiples, ^[5] so

$$\begin{aligned}\varphi(M)&=17^7-17^6=16\cdot17^6\\&=386201104,\end{aligned}$$

and $2$, $4$ are coprime to $17$. So there are two stages: reduce the exponent to $e=10^k\bmod\varphi(M)$, then evaluate $2^e$, $4^e$ modulo $M$.

Both stages use binary exponentiation: square repeatedly to get the power of the base belonging to each bit of the exponent, multiply in only those whose bit is $1$, and reduce after every product. ^[6] Modulo $17$, for example, $10^2\equiv15$ and $10^4\equiv15^2\equiv4$, so $10^5\equiv4\cdot10\equiv6$. It costs one squaring per bit and needs no coprimality. Euler's theorem also supplies the inverses as $a^{\varphi(M)-1}\bmod M$. The sign needs no work: $10^k$ is even for $k\ge1$, so $(-1)^n=1$; only $k=0$, with $n=1$, is odd.

The statement's checkpoint shows both stages: for $n=10^9$ we have $10^9=2\varphi(M)+227597792$, so $e=227597792$, and the congruence returns $126897180$, the quoted value. That $k$ is itself $10^{18}$ changes nothing: the first stage raises $10$ to that power modulo $\varphi(M)$. One pitfall: the exponent is reduced modulo $\varphi(M)$, never modulo $M$, and only because the bases are coprime to the modulus.

How the Code Works

The C++ program ^[7] keeps Section 10's constants as kMod and kPhi. Options holds the exponent $k$, by default $10^{18}$, and a flag for the checkpoints; parse_arguments reads --k= and --skip-checkpoints and rejects a negative $k$. mod_pow is the square-and-multiply loop, with every product formed in __uint128_t before the reduction, so no product of two residues can overflow.

f_mod_n(n, mod) evaluates Section 10's congruence for a given $n$. It builds inv3 and inv5 as mod_pow(3, mod - mod/17 - 1, mod) and likewise for $5$, multiplies them into inv15, sets sign to mod-1 for odd $n$ and $1$ otherwise, and adds the four terms. It raises $2$ and $4$ directly to $n$; it is called for the three checkpoints and for solve(0). That exponent is $\varphi(\mathrm{mod})-1$ for a power of $17$, not for any modulus — every call here passes kMod.

solve(k) computes n_mod_phi = mod_pow(10, k, kPhi), the first stage; for $k=0$ it hands the case to f_mod_n(1, kMod), because then $n=1$ is odd; otherwise it uses the known parity, takes p2, p4 as $2^{e}$, $4^{e}$ modulo kMod and assembles the same four terms. Unless --skip-checkpoints is given, main first calls run_checkpoints for the statement's three values; a failure writes a diagnostic to standard error and exits with code $2$, leaving standard output empty. Otherwise it prints what solve returns.

Python has the same formula in under thirty lines: its mod_pow delegates to the three-argument pow, evaluated efficiently by the interpreter, ^[8] and arbitrary-precision integers remove every question of overflow. Java uses an explicit modPow loop with long arithmetic and adds kMod before each subtraction; no wider type is needed, since kMod is below $2^{29}$, so a product of two residues stays below $2^{58}$ and 4L * p2 below $2^{31}$. Both fix $k=10^{18}$ and contain no checkpoints, so only the C++ build validates itself.

Complexity and Verification

The method runs a fixed number of modular exponentiations, costing $O(\log k+\log M)$ modular multiplications and $O(1)$ memory. Each bit of an exponent costs a squaring, and each bit that is set one further multiplication. The first stage has the $60$-bit exponent $k=10^{18}$ and the four others stay below $\varphi(M)\lt2^{29}$, so the evaluation needs at most $2\cdot60+4\cdot2\cdot29=352$ multiplications of numbers below $2^{29}$.

For this article the geometry was rebuilt: the rule of Section 1 was applied in integer coordinates for every $n\le9$, producing $4^n$ tiles — $262144$ at $n=9$ — and every corner counted. The points on exactly four tiles numbered $0,0,2,16,82,368,$${}1554,6384,25874,104176$, agreeing with the closed form at every $n$, including the checkpoints $f(1)=0$ and $f(4)=82$; the two points of $T(2)$ were $(3,2)$ and $(5,2)$, as predicted in Section 8.

The intermediate claims were checked too. For all $m\le7$ the marks read off the sides obeyed the congruence rule of Section 5, were symmetric, had sizes $0,2,4,10,20,42,84,170$ and satisfied $S_m=D_{m-1}$ for $m\ge1$. Sorting the meeting points by position for $2\le n\le8$ confirmed the split of Section 3: $4f(n-1)$ inside the four copies, $A(n-1)$ on the middle edge, $2A(n-2)$ on the end edges. The numerator of Section 9 was divisible by $15$ for all $n\le299$, and the modular form matched the exact value for all $n\le59$ and gave $f(10^9)\bmod17^7=126897180$, the third checkpoint — checks beyond the three packaged in the C++ source.

The replacement must follow the official figure and Section 1's coordinates. Cutting a tile along both middle lines gives $f(1)=1$, contrary to the statement; and $f(1)=0$ alone does not pin the rule down, since four strips crosswise to the long side also give $f(1)=0$, but then $f(2)=9$ instead of $2$.

Footnotes and References

The references supply the background facts used above; the mark recursion, the congruence rule modulo $3$, the decomposition of $f$ and all counts are derived here.

Project Euler 405 — A Rectangular Tiling. The official statement takes a rectangle twice as long as it is wide, defines T(0) as that rectangle and T(n) by replacing all tiles as a figure shows, lets f(n) count the points where four tiles meet, gives f(1) = 0, f(4) = 82 and f(10⁹) mod 17⁷ = 126897180, and asks for f(10^k) with k = 10¹⁸ mod 17⁷.
Wikipedia — Linear recurrence with constant coefficients. The article explains characteristic roots and the general solution of a homogeneous recurrence. In Section 9 the homogeneous equation f(n) = 4f(n−1) gives the multiple of 4ⁿ, and the terms in 2ⁿ, (−1)ⁿ and 1 form a particular solution, checked by substitution.
Wikipedia — Modular multiplicative inverse. An inverse of a modulo m exists if and only if gcd(a, m) = 1, and for coprime a it can be computed as a^(φ(m)−1) mod m from Euler's theorem — the route the programs take for 3 and 5; the inverse of 15 is their product.
Wikipedia — Euler's theorem. For coprime a and n, a^φ(n) ≡ 1 (mod n); the article states explicitly that exponents may then be taken modulo φ(n), so x ≡ y (mod φ(n)) implies a^x ≡ a^y (mod n) — the first stage of Section 10.
Wikipedia — Euler's totient function. φ(n) counts the integers up to n coprime to n, and for a prime p and k ≥ 1 the article gives φ(p^k) = p^k − p^(k−1), which yields φ(17⁷) = 16 · 17⁶ = 386201104.
Wikipedia — Modular exponentiation. The right-to-left binary, or square-and-multiply, method is described there, with running time O(log exponent). Both stages of Section 10 use it.
C++ — Euler405.cpp. This immutable revision contains mod_pow, f_mod_n, solve and run_checkpoints, and states the closed form of Section 9 in a comment; it is the implementation record for this article.
Python documentation — pow. The three-argument form returns the base to the power of the exponent modulo the third argument, and is, the documentation says, computed more efficiently than taking the power first and reducing.

Problem 405 source code

C++

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

namespace {

using i64 = long long;
using u64 = std::uint64_t;
constexpr u64 kMod = 410338673ULL;   // 17^7
constexpr u64 kPhi = 386201104ULL;   // phi(17^7)

struct Options {
    i64 k = 1000000000000000000LL;
    bool run_checkpoints = true;
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    try {
        value = std::stoll(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_i64_after_prefix(arg, "--k=", options.k)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.k >= 0;
}

u64 mod_pow(u64 base, u64 exp, u64 mod) {
    u64 result = 1 % mod;
    u64 cur = base % mod;
    u64 e = exp;
    while (e > 0) {
        if (e & 1ULL) {
            result = static_cast<u64>((__uint128_t)result * cur % mod);
        }
        cur = static_cast<u64>((__uint128_t)cur * cur % mod);
        e >>= 1ULL;
    }
    return result;
}

u64 f_mod_n(const u64 n, const u64 mod) {
    // Closed form:
    // f(n) = 1 - (-1)^n / 15 - (4/3) * 2^n + (2/5) * 4^n.
    const u64 inv3 = mod_pow(3, mod - mod / 17 - 1, mod);
    const u64 inv5 = mod_pow(5, mod - mod / 17 - 1, mod);
    const u64 inv15 = static_cast<u64>((__uint128_t)inv3 * inv5 % mod);

    const u64 sign = (n & 1ULL) ? (mod - 1ULL) : 1ULL;
    const u64 p2 = mod_pow(2, n, mod);
    const u64 p4 = mod_pow(4, n, mod);

    u64 ans = 1ULL;
    ans = (ans + mod - static_cast<u64>((__uint128_t)sign * inv15 % mod)) % mod;
    ans = (ans + mod - static_cast<u64>((__uint128_t)4ULL * p2 % mod * inv3 % mod)) % mod;
    ans = (ans + static_cast<u64>((__uint128_t)2ULL * p4 % mod * inv5 % mod)) % mod;
    return ans;
}

u64 solve(i64 k) {
    // n = 10^k, and we need f(n) mod 17^7.
    // For 2^n and 4^n modulo 17^7, reduce exponent modulo phi(17^7).
    const u64 n_mod_phi = mod_pow(10, static_cast<u64>(k), kPhi);

    // For k>=1, n is even => (-1)^n = 1. For k=0, n=1 is odd.
    if (k == 0) {
        return f_mod_n(1ULL, kMod);
    }

    // Use n_mod_phi for exponentiations; parity is known even.
    const u64 inv3 = mod_pow(3, kPhi - 1, kMod);
    const u64 inv5 = mod_pow(5, kPhi - 1, kMod);
    const u64 inv15 = static_cast<u64>((__uint128_t)inv3 * inv5 % kMod);
    const u64 p2 = mod_pow(2, n_mod_phi, kMod);
    const u64 p4 = mod_pow(4, n_mod_phi, kMod);

    u64 ans = 1ULL;
    ans = (ans + kMod - inv15) % kMod;  // (-1)^n = 1
    ans = (ans + kMod - static_cast<u64>((__uint128_t)4ULL * p2 % kMod * inv3 % kMod)) % kMod;
    ans = (ans + static_cast<u64>((__uint128_t)2ULL * p4 % kMod * inv5 % kMod)) % kMod;
    return ans;
}

bool run_checkpoints() {
    if (f_mod_n(1ULL, kMod) != 0ULL) {
        std::cerr << "Checkpoint failed: f(1)\n";
        return false;
    }
    if (f_mod_n(4ULL, kMod) != 82ULL) {
        std::cerr << "Checkpoint failed: f(4)\n";
        return false;
    }
    if (f_mod_n(1000000000ULL, kMod) != 126897180ULL) {
        std::cerr << "Checkpoint failed: f(10^9) mod 17^7\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.k) << '\n';
    return 0;
}

Python

def mod_pow(base, exp, mod):
    return pow(base, exp, mod)

def solve():
    kMod = 410338673 # 17^7
    kPhi = 386201104 # phi(17^7)
    k = 1000000000000000000

    n_mod_phi = mod_pow(10, k, kPhi)

    inv3 = mod_pow(3, kPhi - 1, kMod)
    inv5 = mod_pow(5, kPhi - 1, kMod)
    inv15 = (inv3 * inv5) % kMod

    p2 = mod_pow(2, n_mod_phi, kMod)
    p4 = mod_pow(4, n_mod_phi, kMod)

    ans = 1
    ans = (ans - inv15) % kMod
    ans = (ans - 4 * p2 * inv3) % kMod
    ans = (ans + 2 * p4 * inv5) % kMod

    return str((ans + kMod) % kMod)

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

Java

public class Euler405 {
    private static final long kMod = 410338673L; // 17^7
    private static final long kPhi = 386201104L; // phi(17^7)

    private static long modPow(long base, long exp, long mod) {
        long result = 1 % mod;
        long cur = base % mod;
        long e = exp;
        while (e > 0) {
            if ((e & 1L) != 0L) {
                result = (result * cur) % mod;
            }
            cur = (cur * cur) % mod;
            e >>= 1L;
        }
        return result;
    }

    public static String solve() {
        long k = 1000000000000000000L;

        long nModPhi = modPow(10, k, kPhi);

        long inv3 = modPow(3, kPhi - 1, kMod);
        long inv5 = modPow(5, kPhi - 1, kMod);
        long inv15 = (inv3 * inv5) % kMod;

        long p2 = modPow(2, nModPhi, kMod);
        long p4 = modPow(4, nModPhi, kMod);

        long ans = 1L;
        ans = (ans + kMod - inv15) % kMod;
        ans = (ans + kMod - (((4L * p2) % kMod) * inv3) % kMod) % kMod;
        ans = (ans + (((2L * p4) % kMod) * inv5) % kMod) % kMod;

        return String.valueOf(ans);
    }

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