[seqfan] Re: Nice nontrivial integer sequence

[Tim Peters]

[M. F. Hasler <seqfan at hasler.fr>]

> Today I found a nice idea on reddit, which I propose as
> oeis.org/draft/A360447:
>
> The idea is to insert all integers n = 1, 2, 3, ... in a list, between the
> pair of consecutive elements whose sum equals n and whose absolute
> difference is the smallest possible,
> or at the end of the list of there's no such pair.
>

I believe people programming this can save some conditionals by noting
this: when "the next" int `i` is being added, one or two possibly new sums
pop into existence (one if `i` is appended, two if `i` is the sum of two
adjacent entries). A possibly new sum is i+j (for some `j`),. but j was
already in the list, so it must be that j < i, so that i is the larger of
the addends in i+j.

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, So no need to check "whose absolute
difference is the smallest possible" - the first way found yields the
smallest absolute difference, by construction.


> For n = 1 and n = 2, there is no pair in the sequence that sums to n, so
> both of these are appended to the list, which then is [1, 2].
> Now n = 3 is the sum of 1 & 2 so it is inserted between these two, the list
> becomes [1, 3, 2]
>

At which point two new sums pop into existence: 4 and 5. By the above, no
matter what happens next, we already know 4 will appear between 1 and 3,
and 5 between 3 and 2.


> Similarly, n = 4 is inserted between 1 & 3


Which created another possible way to spell 5 (as 1 + 4). But no need to
check that: we already know 2+3 has to win.

Now the list is

    [1, 4,. 3,  2]

and it's possible to form 7 as 4+3  Which must be the way it ends too.

and n = 5 is inserted between 3

& 2, to get [1, 4, 3, 5, 2].


As predicted above ;-)


> Now n = 6 isn't the sum of any two adjacent terms, so it is appended: [1,
> 4, 3, 5, 2, 6].
> Then n = 7 is the sum of 4+3 as well as 5+2, one has to compare the
> differences |4-3| and |5-2| to find that it must be inserted between 4 and
> 3. And so on.
>

But, as above, we already knew 4+3 would win.

A very simple Python program confirmed that this holds through a(58),
although I think the proof sketched is simple enough to be pretty
convincing on its own ;-)