%I #73 Sep 08 2022 08:46:13

%S 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,

%T 28,42,14,45,31,48,34,51,17,54,37,57,40,60,20,63,43,66,46,69,23,72,49,

%U 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

%N 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.

%C 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.

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

%C 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.

%C 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.

%C 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.

%C Thus, by Lemma, we have a(6*k+1) = 6*k+1,

%C 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

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

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

%H Peter J. C. Moses, <a href="/A261728/b261728.txt">Table of n, a(n) for n = 1..10000</a>

%H <a href="/index/Rec#order_12">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,0,2,0,0,0,0,0,-1).

%F From _Peter Bala_, Aug 31 2015: (Start)

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

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

%F 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)

%F 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

%t 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_ *)

%t 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 *)

%o (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

%Y Cf. A109732, A261690.

%K nonn

%O 1,2

%A _Vladimir Shevelev_, Aug 30 2015