A003605 Unique monotonic sequence of nonnegative integers satisfying a(a(n)) = 3n.
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, 48, 51, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120
Offset: 0
Examples
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. a(1992) = a(2*3^6+534) = 3^7+3*534 = 3789 (answer to B.M.O. problem).
References
- A. Gardiner, The Mathematical Olympiad Handbook: An Introduction to Problem Solving, Oxford University Press, 1997, reprinted 2011, pages 5 and 113-114 (1992).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Yifan Xie, Table of n, a(n) for n = 0..10000 (first 1000 terms from Vincenzo Librandi)
- J.-P. Allouche, N. Rampersad and J. Shallit, On integer sequences whose first iterates are linear, Aequationes Math. 69 (2005), 114-127.
- J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
- J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
- British Mathematical Olympiad 1992, Problem 5
- Benoit Cloitre, N. J. A. Sloane and Matthew J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2. (math.NT/0305308)
- Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016.
- Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47.
- J. Shallit, Number theory and formal languages, 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.
- Index entries for sequences of the a(a(n)) = 2n family
- Index to sequences related to Olympiads.
Crossrefs
Programs
-
Maple
filter:= n -> (n mod 3 = 0) or (n >= 2*3^floor(log[3](n))): select(filter, [$0..1000]); # Robert Israel, Oct 15 2014
-
Mathematica
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 *) -
PARI
a(n)=if(n<3,n+(n>0),(3-(n%3))*a(n\3)+(n%3)*a(n\3+1))
-
PARI
{A(n)=local(d,w,l3=log(3),l2=log(2),l3n); l3n = log(n)/l3; w = floor(l3n); \\ highest exponent w such that 3^w <= n d = frac(l3n)*l3/l2+1; \\ first digit in base-3 repr. of n if ( d<2 , d=1 , d=2 );\\ make d an integer either 1 or 2 if(d==1, n = n + 3^w , n = (n - 3^w)*3); return(n);} \\ Gottfried Helms, Jan 11 2012 -
Python
from sympy import integer_log 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
Formula
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.
From Michael Somos, May 03 2000: (Start)
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.
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)
a(n) = n + A006166(n). - Vladeta Jovovic, Mar 01 2003
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
For any k >= 0, a(2*3^k + j) = 3^(k+1) + 3*j, 0 <= j <= 3^k. - Bernard Schott, Dec 25 2020
Comments