

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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) = (n1)/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) = (n1)/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

Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,2,0,0,0,0,0,1).


FORMULA

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(n6)  a(n12); a(2*n+1) = 3*n + (n+1)*floor(mod(n+1,3)/2)  a(2*n1).
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

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(n6)Self(n12): n in [1..100]]; // Vincenzo Librandi, Sep 02 2015


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



