The Slightly Spooky Recamán Sequence – Numberphile [video] | Hacker News Reader

The Slightly Spooky Recamán Sequence – Numberphile [video]

youtube.com

4 pointsdanbruc3 comments

The video is okay but not really outstanding, what caught my attention and made me submit the video was the OEIS entry for the sequence [1]. The entry claims results for the sequence up to 10²³⁰ terms including a graph of it [2]. The status report [3] claims 103 missing numbers below 10⁷ and it seems that in order to compute the sequence you have to keep track of all the missing numbers so far.

This all seems quite impossible to me, unless the density of missing numbers drops dramatically, there is no way you could track them for 10²³⁰ iterations. How would you sample 10²³⁰ numbers to produce a meaningful graph of them? And how would you ever get to 10²³⁰ terms in the first place? For comparison, the volume of the universe times its age, both in Planck units, just gets you to 10²⁵⁰, so a universe filled with Planck sized processors each computing a new term every Planck time since the beginning of time would just barely [4] get you there.

I tried to search for ideas how to speed up the calculation, i.e. avoid computing 10²³⁰ terms which is obviously impossible, but could not find anything and I can not think of anything myself. So how is this done or are this just false claims?

[1] https://oeis.org/A005132

[2] https://oeis.org/A005132/a005132.png

[3] https://oeis.org/A005132/a005132_1.txt

[4] Calling a factor of 10²⁰ »barely« might be a bit of a stretch.

I don't really understand the status report either, because on the main page that Benjamin Chaffin says "Even after 10^230 terms, the smallest missing number is still 852655." But that number isn't listed in "holes below 10^7".

As for how it may be calculated, there are several program listings there. None of them seem to be very optimized, but none of them are attributed to him, so he might have a better algorithm. Also he's a processor architect at Intel, so he might have access to some exotic hardware.

The list has 52655 which almost certainly is 852655 sans the initial 8. I also read that he works at Intel and also wrote a paper together with Neil Sloane on some other sequence [1]. But no amount of access to hardware and no more or less straight forward optimization of the code given will bring you anywhere near calculating 10²³⁰ terms. You would need an algorithm that could essentially compute somewhere between 10¹⁰⁰ and 10²⁰⁰ terms per clock cycle to stand any chance. The closest thing I am aware of would by something like hashlife [2], an algorithm to speed up game of life simulations, that can advance a simulation by something on the order of 10²⁰ to 10³⁰ iterations in seconds. But this requires some regularity in the underlying problem to exploit and I was unable to find anything that seems usable in case of the Recamán sequence.

[1] https://arxiv.org/abs/0912.2382v3

[2] https://en.wikipedia.org/wiki/Hashlife

Reply on news.ycombinator.com