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

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, 65, 39, 66, 38, 67, 37, 68, 36, 69, 35, 70, 34, 71, 33, 72, 32, 73, 31, 74, 30, 75, 29, 76, 28, 77, 27, 78, 26, 79, 133, 188, 132, 189, 131, 190, 130, 191, 129, 192, 128, 193, 127, 194

Offset: 1

Author

Robert Munafo, Mar 11 2010

Keywords

• nonn

Comments

The map n -> a(n) is an injective map to the nonnegative integers, i.e., no two terms are identical.

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]

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

From M. F. Hasler, May 09 2013: (Start)

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

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)

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]

Examples

			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.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..13122
• Robert Munafo, Lexicographically earliest injective and unbounded sequence A(n) satisfying |A(n+1)-A(n)|=n for all n
• Robert Munafo, main-A171884.c(C source code to generate the sequence)

Crossrefs

Cf. A005132, which allows duplicate values.

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.

Programs

Mathematica

A171884[{}, , ] := {};
A171884[L_List, max_Integer, True] := If[Length[L] == max, L, With[{n = Length[L]},
  If[Last[L] - n < 1 || MemberQ[L, Last[L] - n],
    If[MemberQ[L, Last[L] + n],
       A171884[Drop[L, -1], max, False],
       A171884[Append[L, Last[L] + n], max, True]],
    A171884[Append[L, Last[L] - n], max, True]]]]
A171884[L_List, max_Integer, False] := With[{n = Length[L]},
  If[MemberQ[L, Last[L] + n],
     A171884[Drop[L, -1], max, False],
     A171884[Append[L, Last[L] + n], max, True]]]
A171884[{0}, 200, True] (* Paul Raff, Mar 15 2010 *)

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

Formula

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

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

Extensions

Definition edited by M. F. Hasler, Apr 01 2019