[seqfan] Re: Interesting discovery by Dan Preston concerning a Recaman-like sequence

[hv at crypt.org]

My code is using a simple bit vector, but I aimed to write it in such
a way that it would be easy to substitute a different approach. Feel
free to have a play:
  https://github.com/hvds/seq/tree/master/A228474

Hugo

Allan Wechsler <acwacw at gmail.com> wrote:
:I don't know anything about what algorithms people are using here. Are we
:using ordinary bit-vectors, with each bit keeping track of whether the
:sequence has hit a particular number? If so, it seems to me (just from
:hand-simulation) that run-length encoding would save several orders of
:magnitude on space, and probably only cost one order of magnitude in time
:(storing the RLE structure as a balanced tree).
:
:On Thu, Mar 21, 2019 at 9:47 AM Hans Havermann <gladhobo at bell.net> wrote:
:
:> I'm running the code (with 11281) as I write, so far without interruption.
:> The printouts of how many iterations have been reached are now >
:> 1.75*10^12. The only issue I have is that the file that is keeping track of
:> the bit vectors is showing at first glance to be > 5.3 TB, which is
:> impossible because the storage drive is only 2 TB and a system check
:> appears to indicate that it still has 1.25 TB of space available.
:>
:> > On Mar 20, 2019, at 12:10 PM, hv at crypt.org wrote:
:> >
:> > I've written some code to attempt this, available via commit b8eef3ea at
:> > <https://github.com/hvds/seq>.
:> >
:> > This keeps a bit vector of the values seen, split into chunks, and spills
:> > chunks to disk to limit the memory use.
:> >
:> > It appears to give correct values for known n, but trying it with 11281
:> it
:> > gives a bus fault a little after 12,213,813,248 (which takes about 5
:> minutes).
:> > That's around the time I run out of disk space, so that may be the whole
:> > of the problem, but there may be a deeper problem.
:>
:>
:> --
:> Seqfan Mailing list - http://list.seqfan.eu/
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/