[seqfan] Re: Nice nontrivial integer sequence

[Tim Peters]

On Tue, Mar 7, 2023 at 8:08 AM M. F. Hasler <oeis at hasler.fr> wrote:

> On Tue, Mar 7, 2023 at 4:40 AM Tim Peters <tim.peters at gmail.com> wrote:
>
> > > oeis.org/draft/A360447:
> > I believe people programming this can save some conditionals by noting
> > this: (...)
> > If the same new sum i'+j' = i+j appears later, when adding i' to the
> list,
> > i' > i., so the larger addend (i') in this new way of spelling the sum is
> > larger than the larger addend (i) in the way found before. In other
> words,
> > the new way can never "win" - the first way found of achieving a new sum
> is
> > the one that will eventually be used,
>
>
> Yes I think that's right, but in order to keep track of where that is, you
> have to update all positions of larger sums to the right whenever a new sum
> is inserted.
>
> I don't know whether this is possible in an efficient way, but when I tried
> very early a similar idea (keeping track of positions of sums and updating
> these positions)
> it was horribly inefficient.


Except the positions don't need to be tracked. As other posted code has
shown, it's sufficient to represent the list with an array mapping an
integer to its immediate successor. Rather than use piles of words, I'll
include short working Python code.

This doesn't bother keeping track of where "2" is. As in other code, if you
need that you can start with `first` and follow a chain of `succ[]` lookups
until you hit 2. Of course that takes time proportional to the number of
`succ[]` lookups needed.

As usual, when I start on a problem I couldn't care less about time or
memory efficiency, and using Python dictionaries (hash maps) instead of
arrays here requires much more memory than necessary. In return, they're
very flexible and nothing about "maximum values" needs to be committed to
in advance.

Even so, a(56) is reached in a few seconds. Using PyPy instead of the C
implementation of Python is faster and takes perhaps only half the memory,
but even then I run out of RAM (16 GB) before reaching a(59).

But the point here is to illustrate the _ideas_ as clearly as reasonably
possible.

def drive():
    # start with list [1, 2], which isn't explicitly built
    # succ[i] maps `i` to its immediate successor in the list
    succ = {1 : 2}
    # sum2L[S} maps a sum of adjacent terms to its left addend
    sum2L = {3 : 1}
    # `done` is a growing list of the stable values reached, which
    # are removed as keys from succ
    done = []
    # `first` is the first entry in the remaining list, and `last` the
    # last
    first, last = 1, 2
    i = 2

    def dump():
        print(f"{i=:_} {len(done)=:_} {len(succ)=:_} {len(sum2L)=:_}
{first=:_} {last=:_}")
        print("done", done)

    dump()

    while True:
        i += 1
        if L := sum2L.pop(i, 0):
            succ[i] = R = succ[L]
            assert L + R == i
            succ[L] = i
            if L + i not in sum2L:
                sum2L[L + i] = L
            if i + R not in sum2L:
                sum2L[i + R] = i
        else:
            succ[last] = i
            if last + i not in sum2L:
                sum2L[last + i] = last
            last = i
        finished = 0
        while ((S := first + succ[first]) <= i
               or sum2L[S] != first):
            finished += 1
            done.append(first)
            first = succ.pop(first)
        if finished:
            print()
            print("finished", finished)
        if finished or not i % 1_000_000:
            dump()

drive()