|
| |
|
|
A005428
|
|
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).
(Formerly M0572)
|
|
12
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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 (FrankTAW(AT)Netscape.net), May 14 2008
|
|
|
REFERENCES
| K. Burde, Das Problem der Abzaehlreime und Zahlentwicklungen mit gebrochenen Basen, J. Number Theory 26 (1987), no. 2, 192-209.
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
L. Halbeisen and N. Hungerbuehler, The Josephus Problem
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus problem
|
|
|
FORMULA
| a(0) = 1; a(n) = ceiling[(1 + sum{ a(0) to a(n-1) }) / 2]. - Don Reble (djr(AT)nk.ca), 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. [From Max Alekseyev (maxale(AT)gmail.com), Mar 28 2009]
|
|
|
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] (from Robert G. Wilson v (rgwv(at)rgwv.com), Jul 07 2006)
|
|
|
PROG
| (PARI) { a=1; s=2; for(k=1, 50, print1(a, ", "); a=(3*a+s-1)\2; s=(s+a)%3; ) } [From Max Alekseyev (maxale(AT)gmail.com), Mar 28 2009]
(Haskell)
a005428 n = a005428_list !! n
j (a, s) = (a', (s + a') `mod` 2) where
a' = (3 * a + (1 - s) * a `mod` 2) `div` 2
-- Reinhard Zumkeller, Oct 26 2011
|
|
|
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 (ralf(AT)ark.in-berlin.de), Apr 23 2002
Same as log2(A082125(n+3)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 16 2002
Apart from initial terms, same as A073941, which has further information.
Partial sums are in A061419, A061418, A006999.
Sequence in context: A039884 A078620 A073941 * A143951 A058355 A179041
Adjacent sequences: A005425 A005426 A005427 * A005429 A005430 A005431
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com) and Simon Plouffe (simon.plouffe(AT)gmail.com)
|
|
|
EXTENSIONS
| More terms from Hans Havermann (gladhobo(AT)teksavvy.com), Apr 23, 2003
|
| |
|
|
