|
%I M0572 #111 Sep 21 2022 12:25:20
%S 1,1,2,3,4,6,9,14,21,31,47,70,105,158,237,355,533,799,1199,1798,2697,
%T 4046,6069,9103,13655,20482,30723,46085,69127,103691,155536,233304,
%U 349956,524934,787401,1181102,1771653,2657479,3986219,5979328,8968992,13453488,20180232,30270348,45405522,68108283,102162425,153243637,229865456,344798184
%N a(n) = ceiling((1 + sum of preceding terms) / 2) starting with a(0) = 1.
%C 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.]
%C 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.
%C 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).
%C 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
%C 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
%C 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
%C 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
%D 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).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A005428/b005428.txt">Table of n, a(n) for n = 0..500</a>
%H K. Burde, <a href="http://dx.doi.org/10.1016/0022-314X(87)90078-3">Das Problem der Abzählreime und Zahlentwicklungen mit gebrochenen Basen [The problem of counting rhymes and number expansions with fractional bases]</a>, J. Number Theory 26(2) (1987), 192-209.
%H B. Chen, R. Chen, J. Guo, S. Lee et al., <a href="http://arxiv.org/abs/1808.04304">On Base 3/2 and its sequences</a>, arXiv:1808.04304 [math.NT], 2018.
%H L. Halbeisen and N. Hungerbuehler, <a href="http://www.numdam.org/item/JTNB_1997__9_2_303_0">The Josephus Problem</a>, J. Théor. Nombres Bordeaux 9(2) (1997), 303-318.
%H A. M. Odlyzko and H. S. Wilf, <a href="https://doi.org/10.1017/S0017089500008272">Functional iteration and the Josephus problem</a>, Glasgow Math. J. 33 (1991), 235-240.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/JosephusProblem.html">Josephus Problem</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Josephus_problem">Josephus problem</a>.
%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F a(0) = 1; a(n) = ceiling((1 + Sum_{k=0..n-1} a(k)) / 2). - _Don Reble_, Apr 23 2003
%F 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
%F a(n) = floor(1 + (sum of preceding terms)/2). - _M. F. Hasler_, Oct 14 2012
%e n........0...1...2...3...4...5...6...7...8...9..10..11..12..13..14.
%e state=1......1...........4...6...9..........31.....70..105.........
%e state=2..1.......2...3..............14..21......47.........158..237
%t f[s_] := Append[s, Ceiling[(1 + Plus @@ s)/2]]; Nest[f, {1}, 40] (* _Robert G. Wilson v_, Jul 07 2006 *)
%t 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 *)
%o (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
%o (PARI) s=0;vector(50,n,-s+s+=s\2+1) \\ _M. F. Hasler_, Oct 14 2012
%o (Haskell)
%o a005428 n = a005428_list !! n
%o a005428_list = (iterate j (1, 1)) where
%o j (a, s) = (a', (s + a') `mod` 2) where
%o a' = (3 * a + (1 - s) * a `mod` 2) `div` 2
%o -- _Reinhard Zumkeller_, May 10 2015 (fixed), Oct 26 2011
%o (Python)
%o from itertools import islice
%o def A005428_gen(): # generator of terms
%o a, c = 1, 0
%o yield 1
%o while True:
%o yield (a:=1+((c:=c+a)>>1))
%o A005428_list = list(islice(A005428_gen(),30)) # _Chai Wah Wu_, Sep 21 2022
%Y Cf. A005427, A073941, A082416. Union of A081614 and A081615.
%Y First differences of D_3(n) (A061419) in the terminology of Odlyzko and Wilf. - _Ralf Stephan_, Apr 23 2002
%Y Same as log_2(A082125(n+3)). - _Ralf Stephan_, Apr 16 2002
%Y Apart from initial terms, same as A073941, which has further information.
%Y a(n) is the number of positive even k for which A024629(k) has n+1 digits. - _Glen Whitney_, Jul 09 2017
%Y Partial sums are in A061419, A061418, A006999.
%Y Cf. A000079, A072493, A120160, A120170, A120178, A120186, A120194, A120202.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_ and _Simon Plouffe_
%E More terms from _Hans Havermann_, Apr 23 2003
%E Definition replaced with a simpler formula due to _Don Reble_, by _M. F. Hasler_, Oct 14 2012
|
