|
%I M0747 #149 Jul 20 2022 22:38:33
%S 0,2,3,6,7,8,9,12,15,18,19,20,21,22,23,24,25,26,27,30,33,36,39,42,45,
%T 48,51,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,
%U 75,76,77,78,79,80,81,84,87,90,93,96,99,102,105,108,111,114,117,120
%N Unique monotonic sequence of nonnegative integers satisfying a(a(n)) = 3n.
%C Another definition: a(0) = 0, a(1) = 2; for n > 1, a(n) is taken to be the smallest positive integer greater than a(n-1) which is consistent with the condition "n is a member of the sequence if and only if a(n) is a multiple of 3". - _Benoit Cloitre_, Feb 14 2003
%C Yet another definition: a(0) = 0, a(1)=2; for n > 1, a(n) is the smallest integer > a(n-1) satisfying "if n is in the sequence, a(n)==0 (mod 3)" ("only if" omitted).
%C This sequence is the case m = 2 of the following family: a(1, m) = m, a(n, m) is the smallest integer > a(n-1, m) satisfying "if n is in the sequence, a(n, m) == 0 (mod (2m-1))". The general formula is: for any k >= 0, for j = -m*(2m-1)^k, ..., -1, 0, 1, ..., m*(2m-1)^k, a((m-1)*(2*m-1)^k+j) = (2*m-1)^(k+1)+m*j+(m-1)*abs(j).
%C Numbers whose base-3 representation starts with 2 or ends with 0. - _Franklin T. Adams-Watters_, Jan 17 2006
%C This sequence was the subject of the 5th problem of the 27th British Mathematical Olympiad in 1992 (see link British Mathematical Olympiad, reference Gardiner's book and second example for the answer to the BMO question). - _Bernard Schott_, Dec 25 2020
%D A. Gardiner, The Mathematical Olympiad Handbook: An Introduction to Problem Solving, Oxford University Press, 1997, reprinted 2011, pages 5 and 113-114 (1992).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Yifan Xie, <a href="/A003605/b003605.txt">Table of n, a(n) for n = 0..10000</a> (first 1000 terms from Vincenzo Librandi)
%H J.-P. Allouche, N. Rampersad and J. Shallit, <a href="http://dx.doi.org/10.1007/s00010-004-2750-x">On integer sequences whose first iterates are linear</a>, Aequationes Math. 69 (2005), 114-127.
%H J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>
%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.
%H British Mathematical Olympiad 1992, <a href="https://bmos.ukmt.org.uk/home/bmo1-1992.pdf">Problem 5</a>
%H Benoit Cloitre, N. J. A. Sloane and Matthew J. Vandermast, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Cloitre/cloitre2.html">Numerical analogues of Aronson's sequence</a>, J. Integer Seqs., Vol. 6 (2003), #03.2.2. <a href="http://arXiv.org/abs/math.NT/0305308">(math.NT/0305308)</a>
%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint, 2016.
%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47.
%H J. Shallit, <a href="http://www.math.uwaterloo.ca/~shallit/Papers/ntfl.ps">Number theory and formal languages</a>, in D. A. Hejhal, J. Friedman, M. C. Gutzwiller and A. M. Odlyzko, eds., Emerging Applications of Number Theory, IMA Volumes in Mathematics and Its Applications, V. 109, Springer-Verlag, 1999, pp. 547-570.
%H <a href="/index/Aa#aan">Index entries for sequences of the a(a(n)) = 2n family</a>
%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.
%F For any k>=0, a(3^k - j) = 2*3^k - 3j, 0 <= j <= 3^(k-1); a(3^k + j) = 2*3^k + j, 0 <= j <= 3^k.
%F From _Michael Somos_, May 03 2000: (Start)
%F a(3*n) = 3*a(n), a(3*n+1) = 2*a(n) + a(n+1), a(3*n+2) = a(n) + 2a(n+1), n > 0.
%F a(n+1) - 2*a(n) + a(n-1) = {2 if n=3^k, -2 if n=2*3^k, otherwise 0}, n > 1. (End)
%F a(n) = n + A006166(n). - _Vladeta Jovovic_, Mar 01 2003
%F a(n) = abs(2*3^floor(log_3(n)) - n) + 2n - 3^floor(log_3(n)) for n>=1. - _Theodore Lamort de Gail_, Sep 12 2017
%F For any k >= 0, a(2*3^k + j) = 3^(k+1) + 3*j, 0 <= j <= 3^k. - _Bernard Schott_, Dec 25 2020
%e 9 is in the sequence and the smallest multiple of 3 greater than a(9-1)=a(8)=15 is 18. Hence a(9)=18.
%e a(1992) = a(2*3^6+534) = 3^7+3*534 = 3789 (answer to B.M.O. problem).
%p filter:= n -> (n mod 3 = 0) or (n >= 2*3^floor(log[3](n))):
%p select(filter, [$0..1000]); # _Robert Israel_, Oct 15 2014
%t a[n_] := a[n] = Which[ Mod[n, 3] == 0, 3 a[n/3], Mod[n, 3] == 1, 2*a[(n-1)/3] + a[(n-1)/3 + 1], True, a[(n-2)/3] + 2*a[(n-2)/3 + 1]]; a[0]=0; a[1]=2; a[2]=3; Table[a[n], {n, 0, 67}] (* _Jean-François Alcover_, Jul 18 2012, after _Michael Somos_ *)
%o (PARI) a(n)=if(n<3,n+(n>0),(3-(n%3))*a(n\3)+(n%3)*a(n\3+1))
%o (PARI) {A(n)=local(d,w,l3=log(3),l2=log(2),l3n);
%o l3n = log(n)/l3;
%o w = floor(l3n); \\ highest exponent w such that 3^w <= n
%o d = frac(l3n)*l3/l2+1; \\ first digit in base-3 repr. of n
%o if ( d<2 , d=1 , d=2 );\\ make d an integer either 1 or 2
%o if(d==1, n = n + 3^w , n = (n - 3^w)*3);
%o return(n);}
%o \\ _Gottfried Helms_, Jan 11 2012
%Y Cf. A079000, A007378, A080588, A079351.
%Y Cf. A080637, A353651, A353652.
%K nonn,easy,nice
%O 0,2
%A _James Propp_
|
