

A360447


Result of inserting the integers n = 0, 1, 2, ... in this order into an initially empty list, where n is inserted between the pair of consecutive elements with sum equal to n and minimal absolute difference, or at the end of the list if no such pair exists.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Is this a permutation of the nonnegative integers, i.e., will any n eventually reach a stable position in the sequence? This is the case when n is no longer preceded by a pair of consecutive terms with a sum larger than the current length of the sequence.


LINKS



EXAMPLE

For n = 0, 1, and 2, there is no pair in the sequence that sums to n, so each of these is appended to the initially empty list, which then is [0, 1, 2].
Now n = 3 is the sum of 1 and 2 so it is inserted between these two, so the list becomes [0, 1, 3, 2].
Similarly, n = 4 is inserted between 1 and 3 to get [0, 1, 4, 3, 2].
Then n = 5 could be inserted between 1 and 4 or 3 and 2; we have to compare the differences 14 and 32 to find that it must be inserted between 3 and 2 to get [0, 1, 4, 3, 5, 2].
Now n = 6 isn't the sum of any two adjacent terms, so it is appended: [0, 1, 4, 3, 5, 2, 6].
Then n = 7 is the sum of 4+3 as well as 5+2; as for 5 we compare the differences to find that it must be inserted between 4 and 3.
And so on.
The number 2 (which, from step 13 on, is a member of the group (10, 3, 8, 13, 5, 2, 6), later extended by (..., 15, 24, 9, 21)) gets pushed further and further while the initial terms are computed:
In order to get a(13) = 2213 for certain, we use the integers up to 3185, and 2 is then at position 106.
To get a(14) = 10093, we insert all integers up to 12306, and 2 is then at position 176.
To get a(15) = 17973, we use all integers up to 28066, and 2 is then at position 234. The number 7 is by then at position 119, the number 12 at position 351, and 14 at position 431 (followed by 16, 19, 20, 22 and 23 within the next 2030 indices).
To get a(96) = 1345208697, one has to use all integers up to 1708015633, and 2 is then at position 4091. [Result from Brendan McKay]
a(107) = 25782714218. 2 is at position 8714 after 6*10^10 terms.  Chai Wah Wu, Mar 18 2023


PROG

(PARI) upto(N)={my(A=List([1, 2]), bad=2, n=#A, f); until(bad>N, n++; listinsert(A, n, if(#f=[k  k<[2..#A], n==A[k1]+A[k]], vecsort(f, k>abs(A[k]A[k1]))[1], n)); while(A[bad1]+A[bad]<n, bad++)); A[1..N]} \\ returns the vector a(1..N) without the initial a(0)=0
(Python)
while len(A)len(S) <= n:
L = len(A); K = [k for k, s in enumerate(S, Llen(S)) if s == L]
if not K: S += [L + A[1]]; A += [L]
else:
m = min(K, key = lambda k: abs(A[k]A[k1])); k = mL+len(S)
S[k] = L + A[m]; S.insert(k, L + A[m1]); A.insert(m, L)
while S and S[0] <= L: S.pop(0)
return A[n]


CROSSREFS

Cf. A306835 (uses a different choice for the pair which sums to n if there is a choice).


KEYWORD

nonn,hard,nice


AUTHOR



EXTENSIONS



STATUS

approved



