Re: Recamán's sequence and memory usage

potential optimisations:

1) remove consecutive entries between a(0)=0 and m-1 where m is the first missing value. This prevents the sieve from growing beyond resources to support it.

2) use an array instead of a hash -- if the index is numeric, it's an array.

3) calculate the rate of growth of the remaining sieve to test for convergence.

One world, one people

Comment on Re: Recamán's sequence and memory usage

Replies are listed 'Best First'.
Re^2: Recamán's sequence and memory usage by hdb (Monsignor) on Jul 15, 2015 at 11:25 UTC
From my experiments so far with n up to 2e10: The first missing value is tiny compared to the maximum observed number, so not much can be saved here. The observed numbers only cover 1/8 of the whole range, so we are dealing with a sparsely populated array in your proposal. This might not be the best way to store the sequence. The ratio of the maximum number to the sequence number is around 8:1 so not much to be gained here either.	[reply]
Re^3: Recamán's sequence and memory usage by anonymized user 468275 (Curate) on Jul 15, 2015 at 11:57 UTC
In that case it looks like the range of the missing values is divergent. So although the conjecture looks false, it also looks tricky to disprove! One world, one people	[reply]