Detailed mathematical approach

Problem Summary

The task is to compute the sum of the first \(10^{18}\) terms of the fractal sequence, modulo \(10^9\). The key observation used by the implementations is that a prefix of length \(n\) does not need to be generated term by term: it can be decomposed into an inherited prefix plus a fresh consecutive tail. The difficulty is therefore not summing values directly, but locating the exact split point where the inherited self-similar part ends and the new tail begins.

Mathematical Approach

Let \(T(n)\) denote the sum of the first \(n\) terms of the sequence. We also introduce two auxiliary quantities:

\(B(n)\), the length of the largest fully resolved inherited prefix contained in the first \(n\) terms;

\(R(n)\), the total number of copied terms forced by the fresh values \(1,2,\dots,n\).

Set the base values

$B(0)=0,\qquad R(0)=0,\qquad T(0)=0.$

Once \(B(n)\) is known, write

$c=n-B(n).$

The first \(n\) terms then split into the first \(B(n)\) terms of the same sequence, followed by the clean block \(1,2,\dots,c\).

Step 1: Locate the Split Point

After the fresh values \(1,2,\dots,k\) have all appeared, they have also generated \(R(k)\) copied terms. So the total occupied prefix length at that stage is

$k+R(k).$

Therefore the correct inherited prefix length is

$B(n)=\max\{k\ge 0:\ k+R(k)\le n\}.$

This formula means that \(B(n)\) is the largest fully completed stage that still fits inside the first \(n\) positions. Because \(R(k)\) is nondecreasing, the predicate \(k+R(k)\le n\) is monotone in \(k\), which is why the implementations can find \(B(n)\) by search rather than by scanning.

Step 2: Count How Many Copied Terms a New Tail Creates

Suppose the fresh tail has length \(c=n-B(n)\). The inherited part has already contributed \(R(B(n))\) copied terms. The new tail is exactly the consecutive block \(1,2,\dots,c\), and each fresh value \(i\) contributes a copied prefix of length

$\lfloor\sqrt{i}\rfloor.$

Hence the copied-term count satisfies the recurrence

$R(n)=R(B(n))+\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor.$

This is the structural heart of the solution: the self-similarity is pushed into the smaller argument \(B(n)\), while the new work depends only on the simple consecutive tail.

Step 3: Replace the Floor-Square-Root Sum by a Closed Form

Computing \(\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor\) term by term would be too slow. Let

$s=\lfloor\sqrt{c}\rfloor.$

For a fixed threshold \(t\), the inequality \(\lfloor\sqrt{i}\rfloor\ge t\) is equivalent to \(i\ge t^2\). So for each \(t\in\{1,\dots,s\}\), exactly \(c-t^2+1\) indices contribute at least \(t\). Counting by thresholds gives

$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=\sum_{t=1}^{s}(c-t^2+1).$

Using

$\sum_{t=1}^{s} t^2=\frac{s(s+1)(2s+1)}{6},$

we obtain the closed form

$\sum_{i=1}^{c}\lfloor\sqrt{i}\rfloor=s(c+1)-\frac{s(s+1)(2s+1)}{6}.$

This turns the expensive tail update into \(O(1)\) arithmetic once \(s\) is known.

Step 4: Derive the Prefix-Sum Recurrence

The tail \(1,2,\dots,c\) contributes the triangular number

$1+2+\cdots+c=\frac{c(c+1)}{2}.$

Therefore

$T(n)=T(B(n))+\frac{c(c+1)}{2}.$

So the whole problem reduces to repeatedly shrinking \(n\) to the smaller argument \(B(n)\), while adding one triangular contribution per level. No explicit sequence construction is needed.

Step 5: Worked Example for \(n=20\)

The local checkpoint is \(T(20)=86\). The split point is determined by

$9+R(9)=20,\qquad 10+R(10)=22>20,$

so

$B(20)=9,\qquad c=20-9=11.$

Hence

$T(20)=T(9)+\frac{11\cdot 12}{2}=T(9)+66.$

Apply the same decomposition again:

$B(9)=4,\qquad T(9)=T(4)+\frac{5\cdot 6}{2}=T(4)+15,$

$B(4)=2,\qquad T(4)=T(2)+\frac{2\cdot 3}{2}=T(2)+3,$

$B(2)=1,\qquad T(2)=T(1)+\frac{1\cdot 2}{2}=T(1)+1,$

$B(1)=0,\qquad T(1)=1.$

Combining everything,

$T(20)=1+1+3+15+66=86,$

which matches the checkpoint used by the implementations. The same recursion also gives the larger checkpoints \(T(10^3)=364089\) and \(T(10^9)=498676527978348241\).

How the Code Works

The C++, Python, and Java implementations memoize three kinds of information for previously solved prefix lengths: the split point \(B(n)\), the exact copied-term count \(R(n)\), and the required prefix sum \(T(n)\) modulo \(10^9\). For a new query \(n\), the implementation first brackets the answer for \(B(n)\) by repeated doubling, then performs binary search on the monotone condition \(k+R(k)\le n\).

Once the split point is known, the implementation computes the floor-square-root sum with the closed formula above, so no \(O(c)\) loop appears. The structural quantities used for comparisons are kept exact, while the running prefix sum is reduced modulo \(10^9\) after each triangular contribution. The non-Python versions also use wider intermediate arithmetic for the square-sum and triangular formulas so that large products remain exact before the final reduction.

Complexity Analysis

Let \(M\) be the number of distinct prefix lengths that are actually memoized while evaluating the target. Each such state is solved once. Determining its split point requires exponential bracketing and then binary search, so the search overhead is \(O(\log n_{\max})\) per new state, where \(n_{\max}\) is the largest queried prefix length. The floor-square-root contribution and the triangular contribution are both \(O(1)\).

Therefore the overall running time is \(O(M\log n_{\max})\), and the memory usage is \(O(M)\). In practice the recursion contracts quickly because every call replaces \(n\) by the smaller value \(B(n)\), which is exactly what makes a target as large as \(10^{18}\) feasible.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=535
2. Square pyramidal number / sum of squares: Wikipedia — Square pyramidal number
3. Triangular number: Wikipedia — Triangular number
4. Binary search algorithm: Wikipedia — Binary search algorithm
5. Memoization: Wikipedia — Memoization