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.

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

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

Tim Peters, Table of n, a(n) for n = 0..110 (first 107 terms from Brendan McKay)

M. F. Hasler, Logarithmic plot of a(1 .. 96), Mar 05 2023.

Adrian P. Morgan, Sequence built by iterative insertion of integers, Posting to Reddit/CasualMath, Mar 01, 2023.

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 |1-4| and |3-2| 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 20-30 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[k-1]+A[k]], vecsort(f, k->abs(A[k]-A[k-1]))[1], n)); while(A[bad-1]+A[bad]<n, bad++)); A[1..N]} \\ returns the vector a(1..N) without the initial a(0)=0
(Python)
def A360447(n, A=[0], S=[]):
    while len(A)-len(S) <= n:
        L = len(A); K = [k for k, s in enumerate(S, L-len(S)) if s == L]
        if not K: S += [L + A[-1]]; A += [L]
        else:
            m = min(K, key = lambda k: abs(A[k]-A[k-1])); k = m-L+len(S)
            S[k] = L + A[m]; S.insert(k, L + A[m-1]); 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).

Sequence in context: A290890 A152689 A217918 * A000604 A153876 A036881

Adjacent sequences: A360444 A360445 A360446 * A360448 A360449 A360450

Keyword

nonn,hard,nice

Author

M. F. Hasler, Mar 01 2023

Extensions

a(16)-a(55) from Arthur O'Dwyer, Mar 01 2023

Status

approved