login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003605 Unique monotonic sequence of nonnegative integers satisfying a(a(n)) = 3n.
(Formerly M0747)
11
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

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

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

Numbers whose base 3 representation starts with 2 or ends with 0. - Franklin T. Adams-Watters, Jan 17 2006

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

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

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

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

B. Cloitre, N. J. A. Sloane and M. 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, 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, 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.

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

EXAMPLE

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

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

PROG

(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

CROSSREFS

Cf. A079000, A007378, A080588, A079351.

Sequence in context: A161824 A102806 A275884 * A132188 A326027 A255527

Adjacent sequences:  A003602 A003603 A003604 * A003606 A003607 A003608

KEYWORD

nonn,nice

AUTHOR

James Propp

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 04:44 EST 2021. Contains 340214 sequences. (Running on oeis4.)