OFFSET
1,2
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=6k+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(6k+3) = 6k+4, a(6*k+5) = 3k+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).
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
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Shevelev, Aug 30 2015
STATUS
approved