OFFSET
0,3
COMMENTS
Original definition: a(0) = 1, state(0) = 2; for n >= 1, if a(n-1) is even then a(n) = 3*a(n-1)/2 and state(n) = state(n-1); if a(n-1) is odd and state(n-1) = 1 then a(n) = ceiling( 3*a(n-1)/2) and state(n) = 3 - state(n-1) and if a(n-1) is odd and state(n-1) = 2 then a(n) = floor( 3*a(n-1)/2) and state(n) = 3 - state(n-1). [See formula by M. Alekseyev for a simpler equivalent. - Ed.]
Arises from a version of the Josephus problem: sequence gives set of n where, if you start with n people and every 3rd person drops out, either it is person #1 or #2 who is left at the end. A081614 and A081615 give the subsequences where it is person #1 (respectively #2) who is left.
The state changes just when a(n) is odd: it therefore indicates whether the sum of a(0) to a(n) is odd (1 means no, 2 means yes).
The sum a(0) to a(n) is never divisible by 3 (for n >= 0); it is 1 mod 3 precisely when the sum a(0) to a(n-1) is odd and thus indicates the state at the previous step. - Franklin T. Adams-Watters, May 14 2008
The number of nodes at level n of a planted binary tree with alternating branching and non-branching nodes. - Joseph P. Shoulak, Aug 26 2012
Take Sum_{k=1..n} a(k) objects, and partition them into 3 parts. It is always possible to generate those parts using addends once each from the initial n terms, and this is the fastest growing sequence with this property. For example, taking 1+1+2+3+4+6+9 = 26 objects, if we partition them [10,9,7], we can generate these sizes as 10 = 9+1, 9 = 6+3, 7 = 4+2+1. The corresponding sequence partitioning into 2 parts is the powers of 2, A000079. In general, to handle partitioning into k parts, replace the division by 2 in the definition with division by k-1. - Franklin T. Adams-Watters, Nov 07 2015
a(n) is the number of even integers that have n+1 digits when written in base 3/2. For example, there are 2 even integers that use three digits in base 3/2: 6 and 8: they are written as 210 and 212, respectively. - Tanya Khovanova and PRIMES STEP Senior group, Jun 03 2018
REFERENCES
LINKS
T. D. Noe, Table of n, a(n) for n = 0..500
K. Burde, Das Problem der Abzählreime und Zahlentwicklungen mit gebrochenen Basen [The problem of counting rhymes and number expansions with fractional bases], J. Number Theory 26(2) (1987), 192-209.
B. Chen, R. Chen, J. Guo, S. Lee et al., On Base 3/2 and its sequences, arXiv:1808.04304 [math.NT], 2018.
L. Halbeisen and N. Hungerbuehler, The Josephus Problem, J. Théor. Nombres Bordeaux 9(2) (1997), 303-318.
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235-240.
Eric Weisstein's World of Mathematics, Josephus Problem.
Wikipedia, Josephus problem.
FORMULA
a(0) = 1; a(n) = ceiling((1 + Sum_{k=0..n-1} a(k)) / 2). - Don Reble, Apr 23 2003
a(1) = 1, s(1) = 2, and for n > 1, a(n) = floor((3*a(n-1) + s(n-1) - 1) / 2), s(n) = (s(n-1) + a(n)) mod 3. - Max Alekseyev, Mar 28 2009
a(n) = floor(1 + (sum of preceding terms)/2). - M. F. Hasler, Oct 14 2012
EXAMPLE
n........0...1...2...3...4...5...6...7...8...9..10..11..12..13..14.
state=1......1...........4...6...9..........31.....70..105.........
state=2..1.......2...3..............14..21......47.........158..237
MATHEMATICA
f[s_] := Append[s, Ceiling[(1 + Plus @@ s)/2]]; Nest[f, {1}, 40] (* Robert G. Wilson v, Jul 07 2006 *)
nxt[{t_, a_}]:=Module[{c=Ceiling[(1+t)/2]}, {t+c, c}]; NestList[nxt, {1, 1}, 50][[All, 2]] (* Harvey P. Dale, Nov 05 2017 *)
PROG
(PARI) { a=1; s=2; for(k=1, 50, print1(a, ", "); a=(3*a+s-1)\2; s=(s+a)%3; ) } \\ Max Alekseyev, Mar 28 2009
(PARI) s=0; vector(50, n, -s+s+=s\2+1) \\ M. F. Hasler, Oct 14 2012
(Haskell)
a005428 n = a005428_list !! n
a005428_list = (iterate j (1, 1)) where
j (a, s) = (a', (s + a') `mod` 2) where
a' = (3 * a + (1 - s) * a `mod` 2) `div` 2
-- Reinhard Zumkeller, May 10 2015 (fixed), Oct 26 2011
(Python)
from itertools import islice
def A005428_gen(): # generator of terms
a, c = 1, 0
yield 1
while True:
yield (a:=1+((c:=c+a)>>1))
CROSSREFS
First differences of D_3(n) (A061419) in the terminology of Odlyzko and Wilf. - Ralf Stephan, Apr 23 2002
Same as log_2(A082125(n+3)). - Ralf Stephan, Apr 16 2002
Apart from initial terms, same as A073941, which has further information.
a(n) is the number of positive even k for which A024629(k) has n+1 digits. - Glen Whitney, Jul 09 2017
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Hans Havermann, Apr 23 2003
Definition replaced with a simpler formula due to Don Reble, by M. F. Hasler, Oct 14 2012
STATUS
approved