A005428 a(n) = ceiling((1 + sum of preceding terms) / 2) starting with a(0) = 1.

1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799, 1199, 1798, 2697, 4046, 6069, 9103, 13655, 20482, 30723, 46085, 69127, 103691, 155536, 233304, 349956, 524934, 787401, 1181102, 1771653, 2657479, 3986219, 5979328, 8968992, 13453488, 20180232, 30270348, 45405522, 68108283, 102162425, 153243637, 229865456, 344798184

Offset: 0

Author

N. J. A. Sloane and Simon Plouffe

Keywords

• nonn
• easy
• nice

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

Examples

			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
		

References

• F. Schuh, The Master Book of Mathematical Recreations. Dover, NY, 1968, page, 374, Table 18, union of columns 1 and 2 (which are A081614 and A081615).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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.
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A005427, A073941, A082416. Union of A081614 and A081615.

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

Partial sums are in A061419, A061418, A006999.

Cf. A000079, A072493, A120160, A120170, A120178, A120186, A120194, A120202.

Programs

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

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

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

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))
A005428_list = list(islice(A005428_gen(),30)) # Chai Wah Wu, Sep 21 2022

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

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