[seqfan] Re: Nice nontrivial integer sequence

[Arthur O'Dwyer]

Hi Tim et al.,
In off-list discussion, cc'ing MF Hasler and with help from Christian
Sievers, I've made a C++ program that uses only 5*MAX bytes of RAM to
compute the permutation of the first MAX integers (of which we already know
how to extract the "stable" prefix).
https://quuxplusone.github.io/blog/code/2023-03-05-oeis-a360447-revised.cpp
Brendan McKay ran this program for two hours on a machine with 500GB RAM
and produced the following (quoted) elements of OEIS A360447: a(0) through
a(106).
If anyone else wants to give it a shot, please, be our guest. :)

(Brendan asks if there's any way to parallelize the computation to use more
than one CPU core. I don't think there is, since
- inserting x between 2 and (x-2) can affect the future placement of (x+2)
- inserting x between (2x-y) and (y-x) can affect the future placement of
y, and inserting (x+1) between (2x+2-y) and (y-x-1) can also affect the
future placement of y
So I think one-at-a-time insertion is probably unavoidable.)

Arthur

On Wed, Mar 8, 2023 at 1:40 AM Brendan McKay <brendan.mckay at anu.edu.au>
wrote:

> [...]
> 0, 1, 4, 11, 29, 47, 18, 61, 165, 434, 703, 1675, 972, 2213, 10093, 17973,
> 25853, 59586, 33733, 7880,
> 21427, 56401, 204177, 147776, 91375, 217724, 126349, 414021, 287672,
> 161323, 34974, 48521, 13547,
> 5667, 9121, 12575, 28604, 16029, 3454, 1241, 269, 1180, 3271, 2091, 911,
> 2464, 11409, 20354, 90361,
> 250729, 160368, 551111, 1492965, 941854, 390743, 1011861, 621118, 2714847,
> 15667964, 44289045,
> 161488216, 278687387, 117199171, 72910126, 174441333, 450413873,
> 275972540, 101531207, 28621081,
> 12953117, 36144504, 23191387, 33429657, 10238270, 7523423, 19855422,
> 52042843, 32187421, 44519420,
> 12331999, 4808576, 21328033, 59175523, 156198536, 253221549, 350244562,
> 97023013, 231893516,
> 134870503, 37847490, 16519457, 61269252, 167288299, 273307346, 106019047,
> 362806936, 1345208697,
> 3672819155, 6000429613, 2327610458, 982401761, 1601996586, 5425584583,
> 14674757163, 9249172580,
> 3823587997, 9868767405,   (i=25782714218, next update at i=35651481623,
> elapsed=5744s)
>
> You can see that the next update is a big jump away. It didn't manage to
> get there before 7200 seconds was up.
>
>
>> On 8/3/2023 9:55 am, Arthur O'Dwyer wrote:
>>
>> On Tue, Mar 7, 2023 at 5:30 PM Arthur O'Dwyer <arthur.j.odwyer at gmail.com> <arthur.j.odwyer at gmail.com> wrote:
>>
>> Well, that turned out to be quite straightforward!  Updated the code link:https://quuxplusone.github.io/blog/code/2023-03-05-oeis-a360447-revised.cpp
>>
>> Sorry for the rapid update: My for-loop had been one iteration short,
>> which was annoying. Updated.
>> The current code, on my laptop, produces this output in a little over 4 minutes:
>>
>> 0, 1, 4, 11, 29, 47, 18, 61, 165, 434, 703, 1675, 972, 2213, 10093,
>> 17973, 25853, 59586, 33733, 7880, 21427, 56401, 204177, 147776, 91375,
>> 217724, 126349, 414021, 287672, 161323, 34974, 48521, 13547, 5667,
>> 9121, 12575, 28604, 16029, 3454, 1241, 269, 1180, 3271, 2091, 911,
>> 2464, 11409, 20354, 90361, 250729, 160368, 551111, 1492965, 941854,
>> 390743, 1011861, 621118, 2714847, 15667964, 44289045, 161488216,
>> 278687387, 117199171, 72910126, 174441333, 450413873, 275972540,
>> 101531207, 28621081, 12953117, 36144504, 23191387, 33429657, 10238270,
>> 7523423, 19855422, 52042843, 32187421, 44519420, 12331999, 4808576,
>> 21328033, 59175523, 156198536, 253221549, 350244562, 97023013,
>> 231893516, 134870503, 37847490, 16519457, 61269252, 167288299,
>> 273307346, 106019047, 362806936, 1345208697,   (i=2584398347, next
>> update at i=3672819155, elapsed=244s)
>>
>>
>
On Wed, Mar 8, 2023 at 2:04 AM Tim Peters <tim.peters at gmail.com> wrote:

> 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()
>