|
%I #92 Apr 12 2023 09:23:18
%S 0,1,4,11,29,47,18,61,165,434,703,1675,972,2213,10093,17973,25853,
%T 59586,33733,7880,21427,56401,204177,147776,91375,217724,126349,
%U 414021,287672,161323,34974,48521,13547,5667,9121,12575,28604,16029,3454,1241,269,1180,3271,2091,911,2464,11409,20354
%N 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.
%C 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.
%H Tim Peters, <a href="/A360447/b360447.txt">Table of n, a(n) for n = 0..110</a> (first 107 terms from Brendan McKay)
%H M. F. Hasler, <a href="/A360447/a360447.gif">Logarithmic plot of a(1 .. 96)</a>, Mar 05 2023.
%H Adrian P. Morgan, <a href="https://www.reddit.com/r/CasualMath/comments/11ep7ml">Sequence built by iterative insertion of integers</a>, Posting to Reddit/CasualMath, Mar 01, 2023.
%e 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].
%e 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].
%e Similarly, n = 4 is inserted between 1 and 3 to get [0, 1, 4, 3, 2].
%e 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].
%e Now n = 6 isn't the sum of any two adjacent terms, so it is appended: [0, 1, 4, 3, 5, 2, 6].
%e 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.
%e And so on.
%e 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:
%e In order to get a(13) = 2213 for certain, we use the integers up to 3185, and 2 is then at position 106.
%e To get a(14) = 10093, we insert all integers up to 12306, and 2 is then at position 176.
%e 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).
%e 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_]
%e a(107) = 25782714218. 2 is at position 8714 after 6*10^10 terms. - _Chai Wah Wu_, Mar 18 2023
%o (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
%o (Python)
%o def A360447(n, A=[0], S=[]):
%o while len(A)-len(S) <= n:
%o L = len(A); K = [k for k,s in enumerate(S, L-len(S)) if s == L]
%o if not K: S += [L + A[-1]]; A += [L]
%o else:
%o m = min(K, key = lambda k: abs(A[k]-A[k-1])); k = m-L+len(S)
%o S[k] = L + A[m]; S.insert(k, L + A[m-1]); A.insert(m, L)
%o while S and S[0] <= L: S.pop(0)
%o return A[n]
%Y Cf. A306835 (uses a different choice for the pair which sums to n if there is a choice).
%K nonn,hard,nice
%O 0,3
%A _M. F. Hasler_, Mar 01 2023
%E a(16)-a(55) from _Arthur O'Dwyer_, Mar 01 2023
|
