A073941 a(n) = ceiling((Sum_{k=1..n-1} a(k)) / 2) for n >= 2 starting with a(1) = 1.

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

Offset: 1

Author

Reinhard Zumkeller, Nov 20 2002

Keywords

• nonn
• nice

Comments

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

From Petros Hadjicostas, Jul 20 2020: (Start)

We describe Schuh's counting-off game (pp. 373-375 and 377-379). Assume m people are standing on a circle and they are labeled 1 through m (say clockwise). We start with the person labeled 1 and every 3rd person drops out (in a variation of the famous Josephus problem). The process is repeated until only one person is left.

This sequence describes those numbers m for which either the person labeled 1 or the person labeled 2 is the last survivor.

From a(4) = 2 to a(53) = 775795914 (see T. D. Noe's b-file), the values agree with those in Schuh (1968, p. 374) and Burde (1987, p. 207). a(54) = 1163693871 while both Schuh and Burde have 1063693871 (a difference in the 2nd digit starting on the left). a(55) = 1745540806 while both Schuch and Burde have 1595540806.

Schuh (1968) obtains the numbers in the following way. Suppose we know a(n) and the corresponding number i(n) of the last survivor (i(n) = 1 or 2). We multiply a(n) by 3/2 (cf. Burde's use of fractional bases).

If the product is an integer, that is a(n+1) and the corresponding last survivor is the same.

If the product is not an integer, then a(n+1) = floor(a(n)*3/2) if the last survivor i(n) = 2 (and the new last survivor is i(n+1) = 1), and a(n+1) = ceiling(a(n)*3/2) if the last survivor is i(n) = 1 (and the new last survivor is i(n+1) = 2).

Note that a(53) = 775795914 and a(54) = (3/2)*a(53) = 1163693871 (not 1063693871), so it seems Schuh did a mistake and Burde copied it. Also (3/2)*1163693871 = 1745540806.5. Since a(53) = 775795914 corresponds to number 2, we round down, i.e., a(54) = 1745540806 (and move to number 1). If, however, we multiply the incorrect 1063693871 by 3/2 and round down, we get Schuh and Burde's incorrect value 1595540806 for a(54).

Numbers a(n) that correspond to last survivors being number 1 are tabulated in A081614 while numbers a(n) that correspond to last survivors being number 2 are tabulated in A081615. (End)

a(n) is the number of times (n-1) appears in A061420. - Chinmaya Dash, Aug 19 2020

References

• Fred Schuh, The Master Book of Mathematical Recreations, Dover, New York, 1968. [See Table 18, p. 374. Only the terms from a(6) = 4 forward are shown in the table. The table is definitely related to this sequence.]

Links

• T. D. Noe, Table of n, a(n) for n = 1..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. [The author deals with the representation of n in fractional bases k/(k-1) and its relation to counting-off games. Here k = 3. See the table on p. 207. See also the review in MathSciNet (MR0889384) by R. G. Stoneham.]
• B. Chen, R. Chen, J. Guo, S. Lee et al, On Base 3/2 and its sequences, arXiv:1808.04304 [math.NT], 2018.
• Tom Edgar, Hailey Olafson, and James Van Alstine, Approximating the Fibonacci Sequence, Integers 16 (2016), #A63.

Crossrefs

Same as log_2(A082125(n)), for n > 2. - Ralf Stephan, Apr 16 2002

Apart from initial term, same as A005428, which has further information.

a(n+4) = A079719(n)+2. Cf. A082416.

Partial sums for various start indices are in A006999, A061419, A061418. - Ralf Stephan, Apr 17 2003

Is this the same as A081848/3?

The constant c is (2/9)*K(3) (see A083286). - Ralf Stephan, May 29 2003

Cf. A081614, A081615.

Programs

Haskell

a073941 n = a073941_list !! (n-1)
a073941_list = 1 : f [1] where
   f xs = x' : f (x':xs) where x' = (1 + sum xs) `div` 2
-- Reinhard Zumkeller, Oct 26 2011

Mathematica

f[s_] := Append[s, Ceiling[Plus @@ s/2]]; Nest[f, {1}, 41] (* Robert G. Wilson v, Jul 07 2006 *)

PARI

v=vector(100);s=v[1]=1;for(i=2,#v,s+=(v[i]=(s+1)\2));v \\ Charles R Greathouse IV, Feb 11 2011

Python

from itertools import islice
def A073941_gen(): # generator of terms
    a, c = 1, 0
    yield 1
    while True:
        yield (a:=(c:=c+a)+1>>1)
A073941_list = list(islice(A073941_gen(),70)) # Chai Wah Wu, Sep 20 2022

Formula

a(n) = ceiling(c*(3/2)^n-1/2) where c = 0.3605045561966149591015446628665... - Benoit Cloitre, Nov 22 2002

If 2^m divides a(i) then 2^(m-1)*3^1 divides a(i+1) and so on... until finally, 3^m divides a(i+m). - Ralf Stephan, Apr 20 2003

a(n) = A081848(n)/3. - Tom Edgar, Jul 21 2014

a(n) = A005428(n-2). - Tanya Khovanova and PRIMES STEP Senior group, Jun 03 2018