login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005428 a(n) = ceiling((1 + sum of preceding terms) / 2).
(Formerly M0572)
22
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 (list; graph; refs; listen; history; text; internal format)
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

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, J. Number Theory 26 (1987), no. 2, 192-209.

B. Chen, R. Chen, J. Guo, S. Lee et al, On Base 3/2 and its sequences, arXiv:1808.04304

L. Halbeisen and N. Hungerbuehler, The Josephus Problem, J. Théor. Nombres Bordeaux 9 (1997), no. 2, 303-318.

A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33, 235-240, 1991.

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

(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

(PARI) s=0; vector(50, n, -s+s+=s\2+1)  \\ M. F. Hasler, Oct 14 2012

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.

Sequence in context: A302016 A078620 A073941 * A143951 A292800 A214041

Adjacent sequences:  A005425 A005426 A005427 * A005429 A005430 A005431

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane and Simon Plouffe

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

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 October 14 14:20 EDT 2019. Contains 328017 sequences. (Running on oeis4.)