Detailed mathematical approach

Problem Summary

For fixed integers \(n>1\) and \(e>1\), a mirror power sequence is defined by

$a_{i+1}=\min(a_i^e,\,n-a_i^e),\qquad a_i>1.$

For each \(n\), let \(C(n)\) be the number of infinite sequences obtained by allowing every exponent \(e>1\). The target function is

$D(N)=\sum_{n=2}^{N} C(n).$

The key point is that different admissible starting values count as different sequences, even when they eventually fall into the same cycle.

Mathematical Approach

The implementation does not simulate sequences term by term. Instead, it classifies every infinite sequence by a smallest cycle value, an exponent \(e\), and a cycle length \(L\).

Step 1: Characterize Every Infinite Sequence

All terms satisfy \(2\le a_i\le n-2\), so an infinite sequence must eventually become periodic. Take the periodic part and let \(a\) be its smallest value.

From that smallest value, the power branch must be chosen repeatedly until the cycle closes; otherwise the sequence would immediately drop below \(a\), contradicting minimality. Therefore the periodic core has the shape

$a \to a^e \to a^{e^2} \to \cdots \to a^{e^{L-1}} \to a,$

for some integer \(L\ge 1\). The final return to \(a\) happens through the mirror branch, so

$n-a^{e^L}=a,$

hence every infinite mirror power sequence is governed by

$\boxed{n=a+a^{e^L}},\qquad a>1,\ e>1,\ L\ge 1.$

Conversely, once this identity holds, the displayed cycle is valid, so the characterization is exact.

Step 2: Bound the Admissible Bases for Each Combined Exponent

Write

$p=e^L.$

For a fixed combined exponent \(p\), define

$B_p(N)=\max\{a\ge 1:\ a+a^p\le N\}.$

Then every admissible base for that \(p\) lies in

$2\le a\le B_p(N).$

The smallest possible base is \(a=2\), so we must have

$2+2^p\le N.$

Therefore only

$2\le p\le P:=\left\lfloor \log_2(N-2)\right\rfloor$

can contribute. This is why the implementations only need a very short exponent table even when \(N=10^{18}\).

Step 3: Count the Starting Values for One Fixed Triple \((a,e,L)\)

For a fixed choice of \(a\), \(e\), and \(L\), the cycle itself contributes \(L\) different starts:

$a,\ a^e,\ a^{e^2},\ \dots,\ a^{e^{L-1}}.$

There can be more starts before the cycle begins. If \(a=b^e\), then starting from \(b\) reaches \(a\) in one step. If \(a=c^{e^2}\), then starting from \(c\) or \(c^e\) also eventually reaches the same cycle, and so on.

Define \(\rho_e(a)\) as the number of values in the integer \(e\)-root chain ending at \(a\). Equivalently, \(\rho_e(a)\) is \(1\) plus the number of times we can repeatedly take an exact integer \(e\)-th root while staying above \(1\).

Then one fixed triple \((a,e,L)\) contributes

$\rho_e(a)+(L-1)$

distinct sequences: \(\rho_e(a)\) starts feeding into the first cycle node \(a\), and the remaining \(L-1\) starts are the other points on the cycle.

If \(a\) is not a perfect \(e\)-th power, then \(\rho_e(a)=1\), so the contribution is exactly \(L\). If \(a=16\) and \(e=2\), then the root chain is \(2\to 4\to 16\), so \(\rho_2(16)=3\).

Step 4: Sum the Root-Chain Contribution Efficiently

For a fixed exponent \(e\), define

$S_e(A)=\sum_{a=2}^{A}\rho_e(a).$

The quantity \(\rho_e(a)\) counts whether \(a\) is an \(e\)-th power, an \(e^2\)-th power, an \(e^3\)-th power, and so on. So we can sum by root depth instead of by base:

$S_e(A)=(A-1)+\left(\left\lfloor A^{1/e}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^2}\right\rfloor-1\right)+\left(\left\lfloor A^{1/e^3}\right\rfloor-1\right)+\cdots.$

The series stops as soon as \(\lfloor A^{1/e^k}\rfloor<2\). This identity is exactly what the implementations evaluate with repeated integer-root computations.

Step 5: Assemble the Final Formula for \(D(N)\)

The case \(L=1\) means \(p=e\). For that layer, the total contribution is simply

$\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr).$

For \(L\ge 2\), each pair \((e,L)\) with \(e^L\le P\) contributes

$\sum_{a=2}^{B_{e^L}(N)} \bigl(\rho_e(a)+(L-1)\bigr)=(L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr).$

Hence

$\boxed{D(N)=\sum_{p=2}^{P} S_p\bigl(B_p(N)\bigr)+\sum_{e=2}^{P}\ \sum_{\substack{L\ge 2\\ e^L\le P}}\left((L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr)\right).}$

This is the counting formula implemented in all three language versions.

Worked Example: \(N=100\)

Here

$P=\left\lfloor \log_2(98)\right\rfloor=6.$

The base bounds are

$B_2=9,\quad B_3=4,\quad B_4=3,\quad B_5=2,\quad B_6=2.$

Now compute the \(L=1\) layer:

$S_2(9)=8+2=10,$

because among \(2,\dots,9\), the extra square roots come from \(4\) and \(9\). Also

$S_3(4)=3,\qquad S_4(3)=2,\qquad S_5(2)=1,\qquad S_6(2)=1.$

So the subtotal for \(L=1\) is

$10+3+2+1+1=17.$

For \(L\ge 2\), the only possibility is \(e=2\), \(L=2\), because \(2^2=4\le 6\) but \(2^3=8>6\). Its contribution is

$ (2-1)(B_4-1)+S_2(B_4)=1\cdot 2+S_2(3)=2+2=4.$

Therefore

$D(100)=17+4=21,$

which matches the implementation checkpoint.

How the Code Works

The C++, Python, and Java implementations follow the same plan. First they compute \(P=\lfloor\log_2(N-2)\rfloor\). Then, for every \(2\le p\le P\), they find \(B_p(N)\) with a monotone binary search on \(a\), using overflow-safe power comparisons to test whether \(a+a^p\le N\).

Next they evaluate the root-chain sum \(S_e(A)\) by repeatedly taking integer \(e\)-th, \(e^2\)-th, \(e^3\)-th roots, again via binary search. The \(L=1\) contribution is added first. After that, they enumerate every \(e\) and every power \(e^L\) with \(L\ge 2\), and add the term

$ (L-1)\bigl(B_{e^L}(N)-1\bigr)+S_e\bigl(B_{e^L}(N)\bigr). $

No explicit sequence simulation is needed anywhere; the entire computation is reduced to safe integer arithmetic, binary search, and short exponent loops.

Complexity Analysis

Let \(P=\lfloor\log_2(N-2)\rfloor\). There are only \(O(P)\) relevant combined exponents, and only \(O(P)\) pairs \((e,L)\) with \(e^L\le P\). Each boundary search or integer-root search is a binary search over \(a\), and each midpoint test uses a bounded-length power computation of size at most \(P\). A safe upper bound is therefore \(O(P^3\log N)\) time, while memory usage is \(O(P)\). For the actual target \(N=10^{18}\), one has \(P\le 59\), so the method is easily fast enough.

Footnotes and References

1. Problem page: Project Euler 617
2. Iterated function: Wikipedia - Iterated function
3. Nth root: Wikipedia - Nth root
4. Perfect power: Wikipedia - Perfect power
5. Binary search algorithm: Wikipedia - Binary search algorithm