The same OEIS page has:
Cristian Francu, C program to generate the N-th element in O(sqrt(N))
The program is made publicly available by OEIS:
/* by Cristian Francu on 2019-12-19
C source code that generates the Nth element of A005228.
Runs in O(sqrt(N)) time and uses O(sqrt(N)) memory. Works for N up to
2 billion, but can be made to run up to much higher values using either
128 bit integers, or large numbers.
Description:
- We generate elements linearly, storing them in a queue, as to know when
to skip them. When skipping an element we take it out of the queue.
- We keep track of how many elements we can generate until we reach the
last element in the queue (to skip).
- We stop with linear generation when we can generate at least N elements.
In other words, the last element in the queue minus one is greater or
equal to the desired Nth element.
- This way we will generate about sqrt(N) elements.
- At this point the queue will contain about sqrt(N) elements.
- All the above uses integer computations (four bytes).
- At this point we use a formula to compute the Nth element: it is the sum
of a sequence of consecutive numbers.
- We adjust that summation, subtracting the elements in the queue (except
the last one).
- This last step is also sqrt(N) time since that is the length of the queue.
- This last step uses long long subtractions (8 bytes).
*/
#include <stdio.h>
#define MAXQ 65536
int used[MAXQ];
int main() {
int n, i, l, first, last, inqueue, xc, qlen, maxq;
long long x;
scanf( "%d", &n );
used[first = last = 0] = -1; // sentinel
xc = 1;
l = 1;
inqueue = 0;
i = n - 1;
maxq = 0;
while ( i > inqueue ) {
l++;
if ( l == used[first] ) {
first = (first + 1) % MAXQ;
l++;
}
inqueue += l - 1;
used[last] = xc + l;
last = (last + 1) % MAXQ;
if ( (last - first + MAXQ) % MAXQ > maxq )
maxq = (last - first + MAXQ) % MAXQ;
xc += l;
i--;
inqueue--;
}
// This is the second stage, summation and subtraction of elements in queue.
x = xc;
if ( i > 0 ) {
/* We have i more elements to compute starting with xc to which we have
to add l+1 l+2 ... and so on. However, we will need to add i such
numbers plus extra elements. How many? The number of elements in the
queue minus one (these are the elements we will subtract). So, in fact,
we will add: l+1 l+2 ... l+qlen-1
*/
qlen = (last - first + MAXQ) % MAXQ;
x += (2 * l + i + qlen) * (long long)(i + qlen - 1) / 2;
// Then we subtract all elements in the queue, except the last one.
while ( --qlen ) {
x -= used[first];
first = (first + 1) % MAXQ;
}
}
printf( "%lld\n", x );
return 0;
}This is almost exactly >>33's idea, but with the variation of a circular buffer used as a deque. It is O(sqrt(n)) in both space and runtime, as >>18 is, so >>36 is superior in both orders of growth.