login
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.
3
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,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
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
Sequence in context: A159962 A214871 A055173 * A367806 A291798 A212152
KEYWORD
nonn
AUTHOR
Vladimir Shevelev, Aug 30 2015
STATUS
approved