Detailed mathematical approach

Problem Summary

An Ulam sequence \(U(a,b)\) starts with \(a\) and \(b\). Every later term is the smallest integer larger than the previous term that can be written in exactly one way as a sum of two distinct earlier terms. In this problem we must evaluate

$S(k)=\sum_{n=2}^{10} u_k\bigl(U(2,2n+1)\bigr),$

so the nine relevant sequences are \(U(2,5),U(2,7),\dots,U(2,21)\). The target index is enormous in the original problem, so a term-by-term generator is useless. The solution works only because this particular family of Ulam sequences has a highly constrained structure.

Mathematical Approach

Fix one sequence \(U(2,v)\) with \(v=2n+1\) odd. The core idea is that the even terms become trivial, and once that happens the odd terms are governed by a linear recurrence over \(\mathbb{F}_2\).

The special even term \(E=2(v+1)\)

For the nine values \(v=5,7,\dots,21\), the implementation exploits a specific fact about \(U(2,v)\): after the initial term \(2\), there is exactly one further even term, namely

$E=2(v+1).$

Beyond that point the new members are odd. This matters because every odd candidate \(x>E\) can only be formed as

$x=2+(x-2),\qquad x=E+(x-E).$

Odd numbers cannot come from odd plus odd, and there are no other even Ulam terms available. Therefore an odd number \(x>E\) enters the sequence exactly when one of \(x-2\) and \(x-E\) is already present and the other is not.

Odd membership becomes an XOR recurrence

Define an indicator for odd membership by

$b_t=\chi(2t+1),$

where \(b_t=1\) if \(2t+1\) belongs to \(U(2,v)\), and \(b_t=0\) otherwise. Also write

$g=v+1,\qquad E=2g.$

For odd \(x=2t+1>E\), the previous observation becomes

$\chi(x)=\chi(x-2)\oplus\chi(x-E),$

which is the same as

$b_t=b_{t-1}\oplus b_{t-g}\qquad (t\ge g).$

So one window of \(g\) consecutive bits determines every later odd term. Instead of thinking about huge integers directly, we can think about a \(g\)-bit state evolving by a deterministic update rule.

Worked example: \(U(2,5)\)

For \(v=5\) we have \(g=6\) and \(E=12\). The beginning of the sequence is

$2,5,7,9,11,12,13,15,19,23,\dots$

Look at the odd numbers in the initial window \(\{1,3,5,7,9,11\}\). Their membership bits are

$b_0,\dots,b_5=(0,0,1,1,1,1).$

Now apply the recurrence \(b_t=b_{t-1}\oplus b_{t-6}\):

$b_6=b_5\oplus b_0=1\oplus 0=1,$

so \(13=2\cdot 6+1\) is in the sequence. Next,

$b_7=b_6\oplus b_1=1\oplus 0=1,$

so \(15\) is in. Then

$b_8=b_7\oplus b_2=1\oplus 1=0,$

so \(17\) is skipped, and

$b_9=b_8\oplus b_3=0\oplus 1=1,$

so \(19\) appears. This is exactly the pattern produced by the brute-force prefix and then continued by the fast method.

Why the bit sequence is eventually periodic

At step \(t\), the recurrence only needs the last \(g\) bits, for example the state

$\bigl(b_{t-g+1},b_{t-g+2},\dots,b_t\bigr).$

The next bit is determined by the oldest and newest entries, so the transition is deterministic. There are only \(2^g\) possible states, hence some state must repeat. Once the same \(g\)-bit state appears again, every later update repeats as well, so the odd-membership sequence has a finite preperiod followed by a pure cycle.

Converting the huge index into an odd rank

The full Ulam sequence is almost all odd, but the exceptional even term \(E\) must still be inserted at the correct position. Its index is

$r_E=2+\#\{x<E:x\equiv 1 \pmod 2,\ x\in U(2,v)\}.$

The first position is occupied by \(2\), then come all odd members below \(E\), and then \(E\) itself. Therefore

$u_1(v)=2,\qquad u_{r_E}(v)=E,$

and every other query is converted to an odd rank

$r_{\mathrm{odd}}= \begin{cases} k-1,&k<r_E,\\ k-2,&k>r_E. \end{cases}$

Prefix sums of the bit sequence tell how many odd Ulam numbers have appeared up to a given odd value. Once the preperiod length and the number of 1-bits per cycle are known, the algorithm can skip whole cycles arithmetically and then locate the exact odd value with one binary search.

How the Code Works

Bootstrapping the recurrence

The C++, Python, and Java implementations first generate only a short brute-force prefix, just far enough to know which odd numbers up to \(2g-1\) are members. That gives one complete seed window \(b_0,\dots,b_{g-1}\) and also determines how many odd members lie below the special even term \(E\).

From there the implementation builds a \(g\)-bit state, computes prefix counts of 1-bits, and stops using ordinary Ulam generation. All later odd membership decisions come from the XOR recurrence.

Detecting the cycle and answering \(u_k\)

Each new bit updates the sliding \(g\)-bit state. The first repeated state gives the beginning and end of the eventual cycle. The implementation stores the number of odd members before the cycle, the number contributed by one cycle, and prefix counts inside the cycle itself.

To answer the query, the implementation handles the special cases \(2\) and \(E\), converts the requested position into an odd rank, skips as many full cycles as possible, and then binary-searches the relevant prefix table to recover the matching odd number \(2t+1\). The C++ and Java implementations do this independently for the nine values of \(v\) in parallel; the Python implementation applies the same logic serially.

Complexity Analysis

For one sequence \(U(2,v)\), the main cost is cycle detection on the \(g=v+1\) bit states. In the worst case this takes \(O(2^g)\) time and \(O(2^g)\) memory for the table that records the first visit to each state. Here \(v\le 21\), so \(g\le 22\) and the state space is at most \(2^{22}=4{,}194{,}304\), which is entirely manageable.

After that preprocessing, finding \(u_k(v)\) is \(O(\log(P+\lambda))\), where \(P\) is the preperiod length and \(\lambda\) is the cycle length, because the remaining work is arithmetic plus one binary search on prefix sums. The full problem repeats this for only nine independent sequences and adds the results.

Footnotes and References

1. Project Euler problem page: Problem 167 - Investigating Ulam Sequences
2. Ulam numbers and Ulam sequences: Wikipedia - Ulam number
3. Recurrence relations: Wikipedia - Recurrence relation
4. Linear recurrences over \(\mathbb{F}_2\): Wikipedia - Linear feedback shift register