A261728 a(1)=1; a(2*n) = 3*n; for odd n>1, a(n) is the smallest number not already present which is entailed by the rules (i) k present => 3*k+1 present; (ii) 2*k present => k present.

1, 3, 4, 6, 2, 9, 7, 12, 10, 15, 5, 18, 13, 21, 16, 24, 8, 27, 19, 30, 22, 33, 11, 36, 25, 39, 28, 42, 14, 45, 31, 48, 34, 51, 17, 54, 37, 57, 40, 60, 20, 63, 43, 66, 46, 69, 23, 72, 49, 75, 52, 78, 26, 81, 55, 84, 58, 87, 29, 90, 61, 93, 64, 96, 32, 99, 67, 102, 70, 105, 35, 108, 73, 111, 76, 114, 38, 117, 79

Offset: 1

Author

Vladimir Shevelev, Aug 30 2015

Keywords

• nonn
• easy

Comments

Theorem. The only fixed points are 6*k+1, k>=0; if n==3 (mod 6), then a(n) = n+1; if n==5 (mod 6), then a(n) = (n-1)/2.

Proof. By definition, we every time consider the smallest c which has not already given the term 3*c+1.

Lemma. If c=2*k is even, then 3*c+1 appears in the position 6*k+1 and in this case 3*c+1=6*k+1, while if c=2*k+1 is odd, then 3*c+1 appears in the position 6*k+3 and in this case 3*c+1=6*k+4=(6*k+3)+1; finally, in the position 6*k+5 we have 3*k+2=((6*k+5)-1)/2.

Proof. We use induction. The induction hypothesis (IH) is that the lemma is true for every even c<=2*k and odd c<=2*k+1.

Using (IH), note that, by the condition, in the position 6*k+5 we have (6*k+4)/2=3*k+2, and even it is even, then 3*(k/2)+1 cannot occupy the position 6*k+7, since, by IH, 3*(k/2)+1 has already appeared. So the position 6*k+7=6*(k+1)+1 is occupied by 3*c+1, where c is the not yet used, i.e., c=2*k+2=2*(k+1). So the position 6*k+7 is occupied by 6*(k+1)+1=6*k+7. Further, the position 6*k+9=6*(k+1)+3 is occupied by 3*c+1, where c is the not yet used, i.e., c=2*k+3=2*(k+1)+1. Thus we have that the position 6*(k+1)+3 is occupied by the term 6*(k+1)+4=(6*(k+1)+3)+1. Finally, since in the position 6*k+9 we have an even term, then, by the condition, in the position 6*k+11=6*(k+1)+5 we have (6*(k+1)+4)/2=3*(k+1)+2=((6*(k+1)+5)-1)/2. This completes the induction.

Thus, by Lemma, we have a(6*k+1) = 6*k+1, a(6*k+3) = 6*k+4, a(6*k+5) = 3*k+2 and so, if n==3 (mod 6), then a(n) = n+1; if n==5 (mod 6), then a(n) = (n-1)/2. OED

Corollary. The sequence is a permutation of the positive integers.

On the other hand, the statement 'the sequence is a permutation of the positive integers' conjecturally is equivalent to the (3*n+1)-conjecture.

Links

• Peter J. C. Moses, Table of n, a(n) for n = 1..10000
• Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,2,0,0,0,0,0,-1).

Crossrefs

Cf. A109732, A261690.

Programs

Magma

I:=[1,3,4,6,2,9,7,12,10,15,5,18]; [n le 12 select I[n] else 2*Self(n-6)-Self(n-12): n in [1..100]]; // Vincenzo Librandi, Sep 02 2015

Mathematica

a[1] = 1; a[n_?EvenQ] := 3n/2; a[n_] := a[n] = Switch[Mod[n, 6], 1|5, (3/2)*(n-1), 3, 2n-1] - a[n-2]; Array[a, 100] (* Jean-François Alcover, Aug 31 2015, after Vladimir Shevelev *)
LinearRecurrence[{0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, -1}, {1, 3, 4, 6, 2, 9, 7, 12, 10, 15, 5, 18}, 100] (* Vincenzo Librandi, Sep 02 2015 *)

Formula

From Peter Bala, Aug 31 2015: (Start)

O.g.f.: ( 1 + 3*x + 4*x^2 + 6*x^3 + 2*x^4 + 9*x^5 + 5*x^6 + 6*x^7 + 2*x^8 + 3*x^9 + x^10 )/(1 - 2*x^6 + x^12).

Recurrence equations: a(n) = 2*a(n-6) - a(n-12); a(2*n+1) = 3*n + (n+1)*floor(mod(n+1,3)/2) - a(2*n-1).

The latter recurrence leads to the formula a(2*n+1) = 1/4*(6*n + 3 + (-1)^n) + (-1)^floor( mod(n,3)/2 ) * floor( (3*ceiling(n/3) + 1)/2 ). (End)

a(2*n) = 3*n and, for k>=0, a(6k+1)=6k+1; a(6k+3)=6k+4; a(6k+5)=3k+2. - Vladimir Shevelev, Aug 31 2015