|
| |
|
|
A003605
|
|
Unique monotonic sequence of nonnegative integers satisfying a(a(n)) = 3n.
(Formerly M0747)
|
|
16
|
|
|
|
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).
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
|
British Mathematical Olympiad 1992, Problem 5
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.
|
|
|
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.
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)
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))):
|
|
|
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); }
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
