cp's OEIS Frontend

A003605 Unique monotonic sequence of nonnegative integers satisfying a(a(n)) = 3n.

%I A003605 M0747 #155 Feb 03 2025 19:01:09
%S A003605 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 A003605 48,51,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,
%U A003605 75,76,77,78,79,80,81,84,87,90,93,96,99,102,105,108,111,114,117,120
%N A003605 Unique monotonic sequence of nonnegative integers satisfying a(a(n)) = 3n.
%C A003605 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 A003605 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 A003605 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 A003605 Numbers whose base-3 representation starts with 2 or ends with 0. - _Franklin T. Adams-Watters_, Jan 17 2006
%C A003605 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 A003605 A. Gardiner, The Mathematical Olympiad Handbook: An Introduction to Problem Solving, Oxford University Press, 1997, reprinted 2011, pages 5 and 113-114 (1992).
%D A003605 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003605 Yifan Xie, <a href="/A003605/b003605.txt">Table of n, a(n) for n = 0..10000</a> (first 1000 terms from Vincenzo Librandi)
%H A003605 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 A003605 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 A003605 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 A003605 British Mathematical Olympiad 1992, <a href="https://bmos.ukmt.org.uk/home/bmo1-1992.pdf">Problem 5</a>
%H A003605 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 A003605 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 A003605 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 A003605 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 A003605 <a href="/index/Aa#aan">Index entries for sequences of the a(a(n)) = 2n family</a>
%H A003605 <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.
%F A003605 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 A003605 From _Michael Somos_, May 03 2000: (Start)
%F A003605 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 A003605 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 A003605 a(n) = n + A006166(n). - _Vladeta Jovovic_, Mar 01 2003
%F A003605 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 A003605 For any k >= 0, a(2*3^k + j) = 3^(k+1) + 3*j, 0 <= j <= 3^k. - _Bernard Schott_, Dec 25 2020
%e A003605 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 A003605 a(1992) = a(2*3^6+534) = 3^7+3*534 = 3789 (answer to B.M.O. problem).
%p A003605 filter:= n ->  (n mod 3 = 0) or (n >= 2*3^floor(log[3](n))):
%p A003605 select(filter, [$0..1000]); # _Robert Israel_, Oct 15 2014
%t A003605 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 A003605 (PARI) a(n)=if(n<3,n+(n>0),(3-(n%3))*a(n\3)+(n%3)*a(n\3+1))
%o A003605 (PARI) {A(n)=local(d,w,l3=log(3),l2=log(2),l3n);
%o A003605            l3n = log(n)/l3;
%o A003605            w   = floor(l3n);         \\ highest exponent w such that 3^w <= n
%o A003605            d   = frac(l3n)*l3/l2+1;  \\ first digit in base-3 repr. of n
%o A003605               if ( d<2 , d=1 , d=2 );\\   make d an integer either 1 or 2
%o A003605            if(d==1, n = n + 3^w , n = (n - 3^w)*3);
%o A003605            return(n);}
%o A003605 \\ _Gottfried Helms_, Jan 11 2012
%o A003605 (Python)
%o A003605 from sympy import integer_log
%o A003605 def A003605(n): return max(n+(m:=3**integer_log(n,3)[0]),3*(n-m)) if n else 0  # _Chai Wah Wu_, Feb 03 2025
%Y A003605 Cf. A079000, A007378, A080588, A079351.
%Y A003605 Unique monotonic sequence of positive integers satisfying a(a(n)) = k*(n-1) + 3: A080637 (k=2), this sequence (k=3), A353651 (k=4), A353652 (k=5), A353653 (k=6).
%K A003605 nonn,easy,nice
%O A003605 0,2
%A A003605 _James Propp_