Problem 1017: Complementary Sequences

Detailed mathematical approach

Problem Summary

Two strictly increasing sequences \(a=(a_n)_{n\ge0}\) and \(b=(b_n)_{n\ge0}\) are tied together by two rules: \(b_n=a_n+a_{n+1}+a_{n+2}\) for every \(n\), and every positive integer appears in exactly one of the two sequences. They begin

$$\begin{aligned}a&:\ 1,2,3,4,5,7,8,10,11,13,\dots\\b&:\ 6,9,12,16,20,\dots\end{aligned}$$

The bitwise XOR of the numbers \(b_n-1\) over all \(b_n\le20\) is \(5\oplus8\oplus11\oplus15\oplus19=26\), where \(\oplus\) denotes bitwise XOR, and we must find the XOR of \(b_n-1\) over all \(b_n\le10^{18}\). ^[1] Increasing sequences that split the positive integers between them are called complementary, and a relation that ties them together, like the first rule here, is called a complementary equation. ^[2]

There are about \(2.5\cdot10^{17}\) terms to combine, far too many to list. Here is the plan. Write \(b_n=4n+c_n\). The offset \(c_n\) only takes the values \(4\), \(5\) and \(6\), and it stays constant on long blocks of consecutive indices: blocks of \(6\) and blocks of \(4\), of lengths \(1,3,9,27,\dots\), take turns, and between any two of them lies a block of \(5\). The reason is a kind of echo. Complementarity fixes the places where \(a\) skips a number, and they lie close to three times the index of the skipped \(b\)-term, so every change of the offset at an index \(m\) forces the opposite change near \(3m\). Once the blocks are known, each of them contributes an arithmetic progression with difference \(4\), whose XOR has a closed form thanks to the classical pattern of \(0\oplus1\oplus\dots\oplus m\). For the bound \(10^{18}\) the answer combines \(73\) such blocks, the last of them cut at the bound, each in constant time. The sections below prove every step from the definition and check each claim on the first terms.

Mathematical Approach

We first show that the two sequences are completely determined, then locate the places where \(a\) skips a number, derive a rule for the offsets, solve that rule exactly, and finally combine the XOR block by block.

1. The two sequences are forced

Every term is positive, so \(b_n=a_n+a_{n+1}+a_{n+2}\) is larger than \(a_{n+2}\). Since \(a\) is a strictly increasing sequence of positive integers, \(a_0\ge1\), \(a_1\ge2\) and \(a_2\ge3\), so \(b_0\ge1+2+3=6\), and because \(b\) increases, the numbers \(1\) to \(5\) all belong to \(a\). Now walk through \(1,2,3,\dots\) and keep a list of \(b\)-values: as soon as a term \(a_{n+2}\) is known, put \(b_n\) on the list. When the walk reaches a number \(v\), every \(b\)-term \(b_n\le v\) is already on the list, because it only needed \(a_{n+2}\lt b_n\le v\). So \(v\) belongs to \(b\) exactly when it is on the list, and otherwise it is the next term of \(a\). Every step is forced, so there is at most one pair with both properties, and the walk produces one. Each new value \(b_n\) is larger than the number \(a_{n+2}\) that has just been placed, so it never lands on a number that is already decided, and the values \(b_0\lt b_1\lt\cdots\) come out in increasing order because \(a\) increases. The walk never runs out of terms of \(a\) either: if \(a\) stopped growing, only finitely many values would ever be put on the list, and every later number would be a term of \(a\). So both sequences are infinite, no number is in both, and together they contain every positive integer.

The first steps: \(b_0=1+2+3=6\), \(b_1=2+3+4=9\) and \(b_2=3+4+5=12\); the walk skips \(6\), so \(a_5=7\) and \(b_3=4+5+7=16\); then \(a_6=8\) gives \(b_4=5+7+8=20\), the walk skips \(9\), and \(a_7=10\) gives \(b_5=7+8+10=25\). This walk is the direct generator in the self-test of the program. The first terms, together with two derived numbers \(c_n\) and \(g_n\) that the next sections explain, are:

2. Every b-term sits between two a-terms

Consecutive terms of \(b\) are far apart,

$$b_{n+1}-b_n=a_{n+3}-a_n\ge3,$$

because \(a\) increases by at least \(1\) in each of the three steps from \(a_n\) to \(a_{n+3}\). So neither \(b_m-1\) nor \(b_m+1\) is a \(b\)-term, and both are terms of \(a\); for \(m=0\) they are \(5\) and \(7\). Two consequences follow. First, \(a\) never skips two numbers in a row: every step \(a_{i+1}-a_i\) is \(1\) or \(2\), and it is \(2\) exactly when the number \(a_i+1\) in between is a \(b\)-term. Second, we can say at which index each skip happens. If \(a_i=b_m-1\), the numbers \(1,2,\dots,b_m-1\) are the \(i+1\) terms \(a_0,\dots,a_i\) together with the \(m\) terms \(b_0,\dots,b_{m-1}\), so \(b_m-1=(i+1)+m\). The skip over \(b_m\) therefore leaves \(a\) at the index

$$g_m=b_m-m-2,$$

with \(a_{g_m}=b_m-1\) and \(a_{g_m+1}=b_m+1\). We call \(g_0\lt g_1\lt g_2\lt\cdots\) the gap indices: the step \(a_{i+1}-a_i\) is \(2\) when \(i\) is a gap index and \(1\) otherwise. In the table, \(g_0=4\) because \(a_4=5\) and \(a_5=7\) lie on both sides of \(b_0=6\). This is the kind of counting behind the Lambek–Moser theorem on complementary sets: the position of a number in one set is fixed by how many members of the other set lie below it. ^[3]

3. The offsets

How fast do the sequences grow? If \(a_n\) grows like \(\alpha n\), then \(b_n\) grows like \(3\alpha n\), and the numbers up to a large \(x\) contain about \(x/\alpha\) terms of \(a\) and \(x/(3\alpha)\) terms of \(b\). Every number is in exactly one of them, so \(1/\alpha+1/(3\alpha)=1\), which gives \(\alpha=4/3\), and \(b_n\) should stay close to \(4n\). This heuristic is not used in any proof, but it suggests measuring \(b\) against \(4n\):

$$c_n=b_n-4n,\qquad g_n=3n+c_n-2.$$

For \(n=0,\dots,9\) the table shows the offsets \(6,5,4,4,4,5,5,6,6,6\). From now on everything is about them.

4. The step rule

The difference of two consecutive \(b\)-terms is made of three steps of \(a\):

$$b_{n+1}-b_n=\sum_{i=n}^{n+2}\left(a_{i+1}-a_i\right)=3+w_n,$$

where \(w_n\) is the number of gap indices among \(n\), \(n+1\) and \(n+2\). On the other hand \(b_{n+1}-b_n=4+c_{n+1}-c_n\). Comparing the two gives the step rule

$$c_{n+1}-c_n=w_n-1.$$

It also says how far apart consecutive gap indices are: \(g_{m+1}-g_m=3+(c_{m+1}-c_m)\), which is \(2+w_m\ge2\). Two different gap indices are therefore at least \(2\) apart, a window of three consecutive indices contains at most two of them, and so

$$\begin{aligned}w_n&\in\{0,1,2\},\\c_{n+1}-c_n&\in\{-1,0,1\},\\g_{m+1}-g_m&\in\{2,3,4\}.\end{aligned}$$

Call \(m\) a down-step if \(c_{m+1}=c_m-1\), an up-step if \(c_{m+1}=c_m+1\), and flat otherwise. Along a stretch of flat indices the gap indices are exactly \(3\) apart and every window contains exactly one of them. The first two indices are down-steps, \(c_0,c_1,c_2=6,5,4\): the windows \(\{0,1,2\}\) and \(\{1,2,3\}\) lie before the first gap index \(g_0=4\) and contain no gap index at all.

5. Every change has an echo

The step rule ties a change at a small index to a change near three times that index.

• A down-step echoes as an up-step. If \(m\) is a down-step, then \(g_{m+1}=g_m+2\), so the window \(\{g_m,g_m+1,g_m+2\}\) contains two gap indices, \(w_{g_m}=2\), and \(g_m\) is an up-step.
• An up-step echoes as a down-step. If \(m\) is an up-step, then \(g_{m+1}=g_m+4\), so the window \(\{g_m+1,g_m+2,g_m+3\}\) contains none, \(w_{g_m+1}=0\), and \(g_m+1\) is a down-step.

Nothing else can happen. If a window \(\{n,n+1,n+2\}\) contains two gap indices, they are at least \(2\) apart, so they are \(n\) and \(n+2\): two consecutive gap indices \(g_m=n\) and \(g_{m+1}=n+2\), and \(m\) is a down-step. If a window \(\{n,n+1,n+2\}\) contains no gap index but some gap index lies below \(n\), let \(g_m\) be the largest one; then \(g_{m+1}\ge n+3\) and \(g_{m+1}-g_m\le4\) force \(g_m=n-1\) and \(g_{m+1}=g_m+4\), so \(m\) is an up-step. Only the windows starting at \(0\) and \(1\) are empty with no gap index below them. Written with \(g_m=3m+c_m-2\), this is the

Echo rule. The down-steps are \(0\), \(1\) and the indices \(3m+c_m-1\) for the up-steps \(m\). The up-steps are the indices \(3m+c_m-2\) for the down-steps \(m\). Every other index is flat.

In the table, the down-steps \(0\) and \(1\), with \(c_0=6\) and \(c_1=5\), echo as up-steps at \(0+6-2=4\) and \(3+5-2=6\); indeed \(c_4,c_5=4,5\) and \(c_6,c_7=5,6\). The up-step \(4\), with \(c_4=4\), then echoes as a down-step at \(12+4-1=15\), and the up-step \(6\), with \(c_6=5\), at \(18+5-1=22\).

6. The block theorem

The echo rule only looks backwards. To decide the step at \(n\) it needs the indices \(m\) with \(3m+c_m-2=n\), which can make \(n\) an up-step, and those with \(3m+c_m-2=n-1\), which can make it a down-step. These satisfy \(m+1\le n\): a sequence that obeys the rule changes by at most \(1\) from one index to the next, so if it starts with \(c_0=6\), then \(c_m\ge6-m\) and \(3m+c_m-2\ge2m+4\); for the true offsets this is the bound \(g_m\ge2m+4\) that also follows from Section 4. So two sequences that start with \(c_0=6\) and obey the rule agree term by term: if they agree up to the index \(n\), every \(m\) that can matter for the step at \(n\) has its offset and its step already fixed, so the rule gives both sequences the same step at \(n\). To find the offsets it therefore suffices to guess them and check the guess against the rule. For \(k\ge0\) put

$$\begin{aligned}s_k&=\frac{7\cdot3^k-6-(-1)^k}{8},\\t_k&=s_k+3^k=\frac{15\cdot3^k-6-(-1)^k}{8}.\end{aligned}$$

Both are integers, since \(3^k\) is \(1\) more than a multiple of \(8\) for even \(k\) and \(3\) more for odd \(k\), which makes both numerators multiples of \(8\). The first values are

$$\begin{aligned}s_0,s_1,s_2,\dots&=0,2,7,23,70,212,\dots\\t_0,t_1,t_2,\dots&=1,5,16,50,151,455,\dots\end{aligned}$$

Theorem. For every \(k\ge0\), the offset is \(c_n=6\) for \(s_k\le n\lt t_k\) when \(k\) is even, \(c_n=4\) for \(s_k\le n\lt t_k\) when \(k\) is odd, and \(c_n=5\) for \(t_k\le n\lt s_{k+1}\).

So the indices split into blocks: a high block (\(c=6\)) or a low block (\(c=4\)) of length \(t_k-s_k=3^k\), followed by a middle block (\(c=5\)) of length

$$s_{k+1}-t_k=\frac{3^{k+1}+(-1)^k}{4},$$

and high and low blocks take turns. The first ones are:

Proof. In the pattern of the theorem the offset changes only at the last index of each block: at \(t_k-1\), from the block value to \(5\), and at \(s_{k+1}-1\), from \(5\) to the value of the next block. For even \(k\) both are down-steps (\(6\to5\to4\)), for odd \(k\) both are up-steps (\(4\to5\to6\)). Apply the echo rule to each of them, with the offset that the pattern gives to that index:

• \(k\) even, the down-step \(t_k-1\) has offset \(6\), and its echo is at \(3(t_k-1)+6-2=3t_k+1\);
• \(k\) even, the down-step \(s_{k+1}-1\) has offset \(5\), and its echo is at \(3(s_{k+1}-1)+5-2=3s_{k+1}\);
• \(k\) odd, the up-step \(t_k-1\) has offset \(4\), and its echo is at \(3(t_k-1)+4-1=3t_k\);
• \(k\) odd, the up-step \(s_{k+1}-1\) has offset \(5\), and its echo is at \(3(s_{k+1}-1)+5-1=3s_{k+1}+1\).

The closed forms give \(t_{k+1}-3t_k=(3+(-1)^k)/2\) and \(s_{k+2}-3s_{k+1}=(3-(-1)^k)/2\). For even \(k\) this means \(t_{k+1}=3t_k+2\) and \(s_{k+2}=3s_{k+1}+1\), for odd \(k\) it means \(t_{k+1}=3t_k+1\) and \(s_{k+2}=3s_{k+1}+2\). In both cases the two echoes land exactly on \(t_{k+1}-1\) and \(s_{k+2}-1\), the two changes at the ends of block \(k+1\) and of the middle block after it. They also point the right way: block \(k+1\) is of the other kind, so its two changes are up-steps after an even \(k\) and down-steps after an odd \(k\), which is what the echo rule produces. Conversely, every change of the pattern is one of these echoes, except \(t_0-1=0\) and \(s_1-1=1\), and those two are the down-steps that the echo rule prescribes at \(0\) and \(1\). So the pattern starts with \(c_0=6\) and obeys the echo rule, and therefore it is the sequence of offsets. \(\square\)

The theorem has a self-similar shape. Since \(s_k\approx\tfrac78\cdot3^k\) and \(t_k\approx\tfrac{15}{8}\cdot3^k\), the picture of the offsets around an index \(n\) reappears around \(3n\), stretched by a factor of three and with high and low exchanged; this is the echo rule seen from far away.

7. What the blocks say about a

Section 2 also describes \(a\) directly. The step of \(a\) at \(i\) is \(1\) plus one for each gap index equal to \(i\), so \(a_i=i+1+K(i)\), where \(K(i)\) is the number of gap indices below \(i\). By the theorem \(4\le c_m\le6\), so \(3m+2\le g_m\le3m+4\). Write \(i=3j+r\) with \(0\le r\le2\). The gap indices \(g_m\) with \(m\le j-2\) are at most \(3j-2\lt i\), and those with \(m\ge j\) are at least \(3j+2\ge i\), so only \(g_{j-1}=3j+c_{j-1}-5\) is in doubt, and it lies below \(i\) exactly when \(c_{j-1}\lt5+r\). With \(\delta_i=i+1+\lfloor i/3\rfloor-a_i\) this gives \(\delta_0=\delta_1=\delta_2=0\) and, for \(j\ge1\), the triple rule

$$\begin{aligned}\delta_{3j}&=[c_{j-1}\ge5],\\\delta_{3j+1}&=[c_{j-1}=6],\\\delta_{3j+2}&=0,\end{aligned}$$

where a bracket \([\,\cdot\,]\) is \(1\) when the statement inside it holds and \(0\) otherwise. So every term of \(a\) is \(i+\lfloor i/3\rfloor\) or \(i+\lfloor i/3\rfloor+1\), and \(a\) copies the block pattern of \(b\), stretched by a factor of three: a low block of \(b\) gives a stretch where \(a_i=i+1+\lfloor i/3\rfloor\) holds without exception, a middle block gives repeated triples \((1,0,0)\) of the numbers \(\delta_i\), and a high block repeated triples \((1,1,0)\).

This sequence \(a\) is in the OEIS as A394576, numbered from \(1\): its \(a(n)\) is our \(a_{n-1}\), and its \(d(n)=\lfloor(4n-1)/3\rfloor-a(n)\) is our \(\delta_{n-1}\). ^[4] Its definition is the walk of Section 1 in other words: each new term is the smallest number above the previous one that is not a sum of three consecutive earlier terms, and these sums are exactly the values of \(b\), so the entry lists our \(a\) at every index. The entry records three statements as conjectures: \(d(n)\ge0\); \(d\) vanishes on "stable blocks" of length \(9^{k-1}+2\) that start at \(n=(7\cdot9^{k-1}+1)/8\); and between the \((k-1)\)-th and the \(k\)-th of them, for \(k\ge2\), \(d\) spells the word \(X^{A}Y^{B}X^{C}(1)\) with \(X=(1,0,0)\), \(Y=(1,1,0)\), \(A=(9^{k-2}-1)/4\), \(B=9^{k-2}\) and \(C=3(9^{k-2}-1)/4\). The triple rule turns the theorem into exactly these statements. The first stable block is \(n=1,2,3\), our \(i=0,1,2\); it ends there because \(\delta_3=[c_0\ge5]=1\). For \(k\ge2\), the low block number \(2k-3\) contains \(3^{2k-3}\) indices of \(b\); their triples give \(3^{2k-2}\) consecutive zeros of \(d\), and together with the two zeros that end the triple \((1,0,0)\) just before them they form a stable block of length \(9^{k-1}+2\). In the numbering of the OEIS it starts at \(n=S(k)\) and ends at \(n=E(k)\), where

$$\begin{aligned}S(k)&=3s_{2k-3}+2=\frac{7\cdot9^{k-1}+1}{8}\\E(k)&=3t_{2k-3}+3=\frac{15\cdot9^{k-1}+9}{8}.\end{aligned}$$

Between the \((k-1)\)-th and the \(k\)-th stable block lie the triples of the middle block after the low block \(2k-5\), of length \((3^{2k-4}-1)/4=A\), of the high block \(2k-4\), of length \(3^{2k-4}=B\), and of the middle block after it, of length \((3^{2k-3}+1)/4=C+1\), whose last triple gives only its leading \(1\) to the word between the two stable blocks. For \(k=2\) the first of these middle blocks is absent, since \(A=0\): the word is the triple \(Y\) of the high block \(0\) followed by the leading \(1\) of the triple of the middle block after it. So the block theorem proves all three statements for every \(n\).

8. The XOR of one block

On a block with constant offset \(c\), the numbers to combine are \(b_n-1=4n+(c-1)\). Write \(c-1=4q+r\) with \(0\le r\le3\), that is \((q,r)=(1,1)\) for \(c=6\), \((1,0)\) for \(c=5\) and \((0,3)\) for \(c=4\). Then

$$b_n-1=4(n+q)+r,$$

so the two lowest binary digits of \(b_n-1\) are those of \(r\), and the digits above them are the binary digits of \(n+q\). XOR works on each binary digit separately, it is associative and commutative, and every number cancels itself, \(x\oplus x=0\). ^[5] For the indices \(u\le n\le v\) of a block this gives

$$\bigoplus_{n=u}^{v}\left(b_n-1\right)=4\Bigl(\,\bigoplus_{j=u+q}^{v+q}j\Bigr)\oplus\varepsilon r,$$

where \(\varepsilon\) is \(1\) when the number \(v-u+1\) of combined terms is odd and \(0\) when it is even. The XOR of consecutive integers that remains has a closed form. Let \(P(m)=0\oplus1\oplus\dots\oplus m\). For even \(j\) the numbers \(j\) and \(j+1\) differ only in their last binary digit, so \(j\oplus(j+1)=1\), and four consecutive numbers that start at a multiple of \(4\) cancel, because \(4i\oplus(4i+1)=1\) and \((4i+2)\oplus(4i+3)=1\). Hence \(P(4i-1)=0\), and adding the next one, two or three numbers gives the classical pattern ^[6]

$$\begin{aligned}P(4i)&=4i,&P(4i+1)&=1,\\P(4i+2)&=4i+3,&P(4i+3)&=0.\end{aligned}$$

The XOR of the integers from \(x\) to \(y\) is then \(P(y)\oplus P(x-1)\), because the common beginning \(0\oplus\dots\oplus(x-1)\) cancels, with \(P(-1)=0\) for \(x=0\). So every block costs a fixed amount of work, however long it is.

The example of the statement fits this scheme. The terms \(b_n\le20\) are \(b_0\), in the high block with \(q=r=1\), giving \(5=4\cdot1+1\); \(b_1\), in the middle block, giving \(8=4\cdot2+0\); and \(b_2,b_3,b_4\), in the low block with \(q=0\) and \(r=3\). The low block gives \(4\,(2\oplus3\oplus4)\oplus3=4\cdot5\oplus3=23\), which is indeed \(11\oplus15\oplus19\), and \(5\oplus8\oplus23=26\).

9. Cutting at the bound

Since \(b\) increases, the terms with \(b_n\le N\) form a beginning \(b_0,b_1,\dots\) of the sequence, so it suffices to walk through the blocks in order: high block \(0\), middle block, low block \(1\), middle block, high block \(2\), and so on. In a block with offset \(c\) that starts at the index \(u\), the term \(b_n=4n+c\) is included exactly when \(n\le\lfloor(N-c)/4\rfloor\). If the whole block passes this test, its XOR is combined into the result and the walk goes on. Otherwise only the indices from \(u\) up to \(\lfloor(N-c)/4\rfloor\) are included, none at all if \(N\lt4u+c\), and the walk stops, because every later term is larger. The lengths come for free: the high or low block \(k\) has length \(3^k\) and the middle block after it has length \((3\cdot3^k+(-1)^k)/4\), so a running power of \(3\) is all the walk needs.

The block \(k\) starts at the value \(b_{s_k}\approx4s_k\approx\tfrac72\cdot3^k\). For \(N=10^{18}\) the walk therefore meets the high and low blocks \(k=0,1,\dots,36\) and the \(36\) middle blocks between them: \(73\) block XORs in all. The last one is cut, since \(4s_{36}+6\le10^{18}\lt4(t_{36}-1)+6\): the high block \(36\) starts below the bound and ends above it.

How the Code Works

The C++ program ^[7] follows Sections 8 and 9. prefix_xor is the function \(P\) with its four cases. block_xor(first, count, offset) handles \(\ell\) consecutive indices (count) from the index \(u\) (first) on in a block with offset \(c\): it splits \(c-1\) into \(q=\lfloor(c-1)/4\rfloor\) and \(r=(c-1)\bmod4\), takes the XOR of the integers from \(u+q\) to \(u+q+\ell-1\) with two calls of prefix_xor, shifts it two places to the left and adds \(r\) when \(\ell\) is odd. solve(limit) is the walk for the bound \(N\) (limit): the lambda consume(size, offset) cuts a block at the last admissible index \(\lfloor(N-c)/4\rfloor\), XORs what remains into the result and reports whether the block was complete, and the loop alternates high and low blocks of length \(3^k\) (length) with middle blocks of length \((3\cdot3^k+1)/4\) after a high block and \((3\cdot3^k-1)/4\) after a low one, which is \((3^{k+1}+(-1)^k)/4\), until a block is cut.

The remaining functions check the theorem far beyond the reach of a direct computation. boundary_offset(index) returns the offset of an index by stepping through the block boundaries with the recurrences from the proof, starting from \(t_0=1\) and \(s_1=2\). count_b(limit) counts the \(b\)-terms up to a limit \(N\): by the theorem \(4n+c_n\le N\) for every \(n\le\lfloor N/4\rfloor-2\) and \(4n+c_n\gt N\) for every \(n\ge\lfloor N/4\rfloor\), so the count is \(\lfloor N/4\rfloor\) or one less, depending on the single term with index \(\lfloor N/4\rfloor-1\). complement_term(index) finds \(a_i\) among its two candidates \(i+\lfloor i/3\rfloor\) and \(i+\lfloor i/3\rfloor+1\) from Section 7: the smaller one is \(a_i\) exactly when at least \(i+1\) numbers up to it are not \(b\)-terms.

run_tests, started with --self-test, checks the empty range and the example of the statement, then generates \(a\) and \(b\) from the definition by the walk of Section 1 up to \(10^6\), comparing every \(b\)-term with the theorem and the XOR for every limit up to \(10^6\) with solve, and checks that the generated sequences begin with the terms listed in the statement. After that it tests the defining property itself at huge indices. check_index takes \(b_i\) from the theorem, takes \(a_i\), \(a_{i+1}\) and \(a_{i+2}\) from complement_term, that is, as terms of the complement of \(b\), requires \(b_i=a_i+a_{i+1}+a_{i+2}\), and then runs check_limit at the limits \(b_i-1\), \(b_i\) and \(b_i+1\). check_limit requires that the XOR changes between the limits \(L-1\) and \(L\) by exactly \(L-1\) when \(L\) is a \(b\)-term and not at all otherwise. check_index runs at every index within \(4\) of a block boundary up to the top of the \(64\)-bit range, at \(4096\) pseudo-random indices from a xorshift generator and at the largest index \(i\) with \(4i+6\lt2^{64}\); check_limit also runs at \(4096\) pseudo-random limits, at the limits \(2^e-1\), \(2^e\) and \(2^e+1\) for \(0\le e\le63\), at \(2^{64}-1\) and at \(10^{18}\). Without arguments the program prints the answer for \(10^{18}\); given a limit, it prints the XOR for that limit instead. The arithmetic is unsigned \(64\)-bit and exact on every path the program takes. consume compares the limit with the offset before it subtracts, so every limit below \(6\) gives the empty XOR; the cut index \(\lfloor(N-c)/4\rfloor\) is below \(2^{62}\); and even for the limit \(2^{64}-1\) the walk stops inside block \(39\), so no block length exceeds \(3^{39}\lt2^{62}\). boundary_offset is only called for indices up to \(\lfloor(2^{64}-7)/4\rfloor\) and complement_term for indices up to two more, since count_b receives limits up to \(2^{64}-1\) but passes on only \(\lfloor N/4\rfloor-1\); for these indices boundary_offset stops at the block boundary \(t_{39}\lt2^{63}\) at the latest, after it has computed the next boundary \(s_{40}\), which lies between \(2^{63}\) and \(2^{64}\). The helpers are not meant for arbitrary \(64\)-bit indices. Only the xorshift generator relies on wrap-around.

The Python and Java versions follow the C++ program function by function, with the same self-test. Python integers have no fixed size, so only the xorshift generator is reduced to \(64\) bits by hand. Java has no unsigned integer type: the values are kept in long variables read as unsigned \(64\)-bit numbers. Wherever that reading matters, because limits, results, states of the xorshift generator and the boundary \(s_{40}\) exceed \(2^{63}\), the program uses Long.compareUnsigned, Long.divideUnsigned, Long.remainderUnsigned, the shift >>>, the masks & 3 and & 1 and Long.toUnsignedString; addition, subtraction, multiplication, equality and the bitwise operations act on the stored bit patterns with the ordinary operators, which gives the same bits as unsigned arithmetic.

Complexity and Verification

The walk visits about \(2\log_3 N\) blocks and spends a fixed amount of work on each, so the time grows like \(\log N\) and the memory is constant; for \(N=10^{18}\) these are the \(73\) blocks of Section 9. Measured as the median wall-clock time of repeated runs of the whole program on an Apple M4 Max, the C++ program built with clang++ -std=c++20 -O3 finishes in about two milliseconds, the Python version on CPython \(3.11\) in about \(0.02\) seconds and the Java version on OpenJDK \(17\) in about \(0.03\) seconds, almost all of it spent starting the process, the interpreter or the virtual machine. The self-tests take about \(0.04\) seconds in C++, \(0.1\) seconds in Java and \(11\) seconds in Python, mostly in the direct comparison of the first million limits.

All three programs print the same value and pass their self-tests. Further checks, which are not part of the published solutions, confirm the mathematics rather than the code. A separate brute-force program that knows only the definition generated every \(b\)-term up to \(10^{10}\), that is \(2\,499\,999\,999\) of them: every offset agreed with the theorem, every step of \(a\) was \(1\) or \(2\) with the steps of \(2\) exactly at the gap indices \(b_m-m-2\), and the running XOR agreed with an independently written block formula at every limit up to \(2\cdot10^7\) and at \(152\,436\) further limits, among them every \(b\)-term near a block boundary and the number just after it. A second program does without the theorem altogether. It computes single terms from complementarity alone, through

$$b_n=3n+6+K(n)+K(n+1)+K(n+2),$$

with \(K(i)\) the number of indices \(m\) with \(b_m-m-2\lt i\), which only needs terms with indices about three times smaller, and at \(6378\) indices up to \(3\cdot10^{17}\), including the indices within \(3\) of every block boundary from \(k=10\) to \(k=36\), it reproduced the offsets of the theorem. The statements of Sections 2 to 5 (the gap indices, the step rule, the bounds on the steps and both directions of the echo rule) were checked term by term on the first \(2\cdot10^6\) terms, and the triple rule of Section 7 on the first \(6\cdot10^6\) terms of \(a\), together with the \(10\,000\) terms of the OEIS table and the three statements of the OEIS entry. Finally, a third, independently written version of the block formula agrees with the C++ program at \(2356\) distinct limits: random \(64\)-bit limits, limits next to block boundaries throughout the \(64\)-bit range, and \(10^{18}\).

Footnotes and References

The references below supply background facts. The gap indices, the step rule, the echo rule, the block theorem and its proof, the description of \(a\) and the block-by-block XOR are derived explicitly in this article.

1. Project Euler 1017 — Complementary Sequences. The official statement: two strictly increasing sequences \(a=(a_n)_{n\ge0}\) and \(b=(b_n)_{n\ge0}\) with \(b_n=a_n+a_{n+1}+a_{n+2}\) for each \(n\), such that every positive integer appears in exactly one of them. It lists the first terms of both sequences, gives the XOR of \(b_n-1\) over all \(b_n\le20\) as \(26\), and asks for the XOR of \(b_n-1\) over all \(b_n\le10^{18}\).
2. Clark Kimberling — Complementary Equations, Journal of Integer Sequences 10 (2007), Article 07.1.4. Its abstract calls increasing sequences that partition the positive integers complementary sequences and equations that involve both of them complementary equations; the article surveys other families of such equations, not the one of this problem.
3. Wikipedia — Lambek–Moser theorem. The theorem describes the partitions of the positive integers into two complementary sets through a non-decreasing, unbounded function \(f\) from the positive integers to the non-negative integers and the function \(f^*\) that counts the positive integers \(x\) with \(f(x)\lt n\); the \(n\)-th members of the two sets are \(f(n)+n\) and \(f^*(n)+n\). Section 2 uses counting of this kind.
4. OEIS A394576. The sequence that starts with \(a(1)=1\) and takes as each next term the smallest number above the previous one that keeps every sum \(a(k)+a(k+1)+a(k+2)\) out of the sequence; its terms are those of \(a\), numbered from \(1\), and the \(10\,000\) terms of its table agree with the walk of Section 1. Its comments state as conjectures the bound \(a(n)\le\lfloor(4n-1)/3\rfloor\), the stable blocks, supported there by data up to \(n=5\cdot10^6\), and the words between consecutive stable blocks quoted in Section 7.
5. Wikipedia — Exclusive or. Exclusive or is commutative and associative, and with one input fixed it is an involution, so applying it twice gives back the other input; applied bit by bit to two strings of \(n\) bits, it is addition in the vector space \((\mathbb{Z}/2\mathbb{Z})^n\).
6. OEIS A003815. The sequence with \(a(0)=0\) and \(a(n)=a(n-1)\oplus n\), that is \(0\oplus1\oplus\dots\oplus n\); its formulas include \(a(4n+1)=1\), \(a(4n+2)=4n+3\), \(a(4n+3)=0\) and \(a(4n+4)=4n+4\), the pattern of \(P\) in Section 8.
7. C++ — Euler1017.cpp. The linked immutable C++ revision contains prefix_xor, block_xor, solve, boundary_offset, count_b, complement_term and the checks run by --self-test. It is the implementation record for this article.