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