cp's OEIS Frontend

A171884 Lexicographically earliest injective nonnegative sequence a(n) satisfying |a(n+1) - a(n)| = n for all n.

%I A171884 #57 Aug 16 2025 17:16:28
%S A171884 0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,64,40,
%T A171884 65,39,66,38,67,37,68,36,69,35,70,34,71,33,72,32,73,31,74,30,75,29,76,
%U A171884 28,77,27,78,26,79,133,188,132,189,131,190,130,191,129,192,128,193,127,194
%N A171884 Lexicographically earliest injective nonnegative sequence a(n) satisfying |a(n+1) - a(n)| = n for all n.
%C A171884 The map n -> a(n) is an injective map to the nonnegative integers, i.e., no two terms are identical.
%C A171884 Appears not to contain numbers from the following sets (grouped intentionally): {4, 5}, {14, 15, 16, 17, 18, 19}, {44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61}, etc. The numbers of terms in these groups appears to be A008776. - _Paul Raff_, Mar 15 2010 [This is correct: by the formula below, a(2*3^k+1...2*3^(k+1)) take all the values in the range [3^(k+1)-1, 5*3^k-2] U [7*3^k-1, 3^(k+2)-2], so the numbers not appearing are those in the range [5*3^k-1, 7*3^k-2] for some k. - _Jianing Song_, Oct 07 2022]
%C A171884 The first 23 terms are shared with Recamán's sequence A005132, but from then on they are different. - _Philippe Deléham_, Mar 01 2013, _Omar E. Pol_, Jul 01 2013
%C A171884 From _M. F. Hasler_, May 09 2013: (Start)
%C A171884 It appears that the starting points of the gaps (4, 14, 44, 134, 404, 1214, ...) are given by A181655(2n) = A198643(n-1), and thus the ending points (5, 19, 61, ...) by A181655(2n) + A048473(n-1).
%C A171884 The first differences have signs (grouped intentionally): +++, -, +++, -+-+-+-+- (5 times "-"), +++, -+...+- (17 times "-"), +++, ... where the number of minus signs is again given by A048473 = A008776-1. (End)
%C A171884 A correspondent, Dennis Reichard, conjectures that (i) a(n) <= 3.5*n for all n and (ii) the sequence covers 2/3 of all natural numbers. - _N. J. A. Sloane_, Jun 30 2018 [(i) is true: the indices of records for a(n)/n are n = 1, 2, 3, 4, 6, 7, and 2*3^k+2 for k >= 1, with record values 0, 1/2, 1, 1, 3/2, 7/6, 13/7, and (7*3^k-1)/(2*3^k+2) for k >= 1, so a(n) <= 3.5*n. (ii) needs further justification: the lower natural density is lim_{k->+oo} #{terms <= 7*3^k-2}/(7*3^k-2) = lim_{k->+oo} (4*3^k-1)/(7*3^k-2) = 4/7, and the upper natural density is lim_{k->+oo} #{terms <= 5*3^k-2}/(5*3^k-2) = lim_{k->+oo} (4*3^k-1)/(5*3^k-2) = 4/5. - _Jianing Song_, Oct 07 2022]
%H A171884 Jianing Song, <a href="/A171884/b171884.txt">Table of n, a(n) for n = 1..13122</a>
%H A171884 Robert Munafo, <a href="http://mrob.com/pub/math/seq-a171884.html">Lexicographically earliest injective and unbounded sequence A(n) satisfying |A(n+1)-A(n)|=n for all n</a>
%H A171884 Robert Munafo, <a href="http://mrob.com/pub/math/main-A171884.txt">main-A171884.c</a>(C source code to generate the sequence)
%F A171884 a(n+1) = a(n) +- n with - iff n is even but not n = 2 + 2*3^k. (Cf. comment from May 09 2013.) - _M. F. Hasler_, Apr 05 2019
%F A171884 a(2*3^k + 2*r - 1) = 5*3^k - 1 - r, a(2*3^k + 2*r) = 7*3^k - 2 + r, for k >= 0 and 1 <= r <= 2*3^k. - _Jianing Song_, Oct 07 2022
%e A171884 We begin with 0, 0+1=1, 1+2=3. 3-3=0 cannot be the next term because 0 is already in the sequence so we go to 3+3=6. The next could be 6-4=2 or 6+4=10 but we choose 2 because it is smaller.
%t A171884 A171884[{}, _, _] := {};
%t A171884 A171884[L_List, max_Integer, True] := If[Length[L] == max, L, With[{n = Length[L]},
%t A171884   If[Last[L] - n < 1 || MemberQ[L, Last[L] - n],
%t A171884     If[MemberQ[L, Last[L] + n],
%t A171884        A171884[Drop[L, -1], max, False],
%t A171884        A171884[Append[L, Last[L] + n], max, True]],
%t A171884     A171884[Append[L, Last[L] - n], max, True]]]]
%t A171884 A171884[L_List, max_Integer, False] := With[{n = Length[L]},
%t A171884   If[MemberQ[L, Last[L] + n],
%t A171884      A171884[Drop[L, -1], max, False],
%t A171884      A171884[Append[L, Last[L] + n], max, True]]]
%t A171884 A171884[{0}, 200, True] (* _Paul Raff_, Mar 15 2010 *)
%o A171884 (PARI) A171884_upto(N,a=0,t=2)=vector(N,k, a+=if(!bitand(k,1), k-1, t-=1, 1-k, t=k-1)) \\ or:
%o A171884 A171884_upto(N,a)=vector(N,k,a+=if(bitand(k,1)&&k\2!=3^valuation(k-(k>1),3),1-k,k-1)) \\ _M. F. Hasler_, Apr 05 2019
%o A171884 a(n) = if(n<=2, n-1, my(k=logint((n-1)\2, 3), r=n-2*3^k); if(r%2, 5*3^k-1-(r+1)/2, 7*3^k-2+r/2)) \\ _Jianing Song_, Oct 07 2022
%Y A171884 Cf. A005132, which allows duplicate values.
%Y A171884 Cf. also A118201, in which every value of a(n) and of |a(n+1)-a(n)| occurs exactly once, but does not ensure that the latter is strictly increasing.
%K A171884 nonn
%O A171884 1,3
%A A171884 _Robert Munafo_, Mar 11 2010
%E A171884 Definition edited by _M. F. Hasler_, Apr 01 2019