Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

Re: Recamán's sequence and memory usage

by anonymized user 468275 (Curate)
on Jul 14, 2015 at 18:25 UTC ( [id://1134776]=note: print w/replies, xml ) Need Help??


in reply to 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:

    1. The first missing value is tiny compared to the maximum observed number, so not much can be saved here.
    2. 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.
    3. The ratio of the maximum number to the sequence number is around 8:1 so not much to be gained here either.

[reply]
      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]

In Section Meditations

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://1134776]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others goofing around in the Monastery: (8)
As of 2024-04-19 15:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found