A033138 a(n) = floor(2^(n+2)/7).

1, 2, 4, 9, 18, 36, 73, 146, 292, 585, 1170, 2340, 4681, 9362, 18724, 37449, 74898, 149796, 299593, 599186, 1198372, 2396745, 4793490, 9586980, 19173961, 38347922, 76695844, 153391689, 306783378, 613566756, 1227133513, 2454267026

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

Previous name was: "Base 2 digits are, in order, the first n terms of the periodic sequence with initial period 1,0,0".

Here we let p = 3 to produce the above sequence, but p can be an arbitrary natural number. By letting p = 2, 4, 6, 7 we produce A000975, A083593, A195904 and A117302. We denote by U[p,n,m] the number of cases in which the first player in a game of Russian roulette gets killed when p players use a gun with n chambers and m bullets. They never rotate the cylinder after the game starts.

The chambers can be represented by the list {1,2,...,n}. We are going to calculate the following (0), (1),...(t) separately. (0) The first player gets killed when one bullet is in the first chamber and the remaining (m-1)- bullets are in {2,3,...,n}. We have binomial(n-1,m-1) cases for this. (1) The first gets killed when one bullet is in the (p+1)st chamber and the rest of the bullets are in {p+2,..,n}. We have binomial(n-p-1,m-1) cases for this. We continue to calculate and the last is (t), where t = floor((n-m)/p). (t) The first gets killed when one bullet is in the (pt+1)st chamber and the remaining bullets are in {pt+2,...,n}. We have binomial(n-pt-1,m-1) cases for this.

Therefore U[p,n,m] = Sum_{z=0..t} binomial(n-pz-1,m-1), where t = floor((n-m)/p). Let A[p,n] be the number of the cases in which the first player gets killed when p players use a gun with n chambers and the number of bullets can be from 1 to n. Then A[p,n] = Sum_{m=1..n} U[p,n,m]. - Ryohei Miyadera, Tomohide Hashiba, Yuta Nakagawa, Hiroshi Matsui, Jun 04 2006

Partial sums of A077947. - Mircea Merca, Dec 28 2010

a(n+1) is the number of partitions of n into two kinds of part 1 and one kind of part 2. - Joerg Arndt, Mar 10 2015

A078010(n) = b(n+1) - 2*b(n) + b(n-1) where b=A078010. - Michael Somos, Nov 18 2020

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 926
• S. Klavzar, Structure of Fibonacci cubes: a survey, Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia; Preprint series Vol. 49 (2011), 1150 ISSN 2232-2094.
• Index entries for linear recurrences with constant coefficients, signature (2,0,1,-2).

Crossrefs

Cf. A000975, A078010, A083593, A195904, A117302, A023001, A111662, A077947.

Programs

Magma

[Round((4*2^n-2)/7): n in [1..40]]; // Vincenzo Librandi, Jun 25 2011

Maple

seq(iquo(2^n,7),n=3..34); # Zerinvary Lajos, Apr 20 2008

Mathematica

U[p_, n_, m_, v_]:=Block[{t}, t=Floor[(1+p-m+n-v)/p];Sum[Binomial[n-v-p*z,m-1],{z,0,t-1}]]; A[p_,n_,v_]:=Sum[U[p,n,k,v],{k,1,n}]; (* Here we let p = 3 to produce the above sequence, but this code can produce A000975, A083593, A195904, A117302 for p = 2,4,6,7. *) Table[A[3,n,1], {n,1,20}] (* Ryohei Miyadera, Tomohide Hashiba, Yuta Nakagawa, Hiroshi Matsui, Jun 04 2006 *)

PARI

a(n)=2^(n+2)\7 \\ Charles R Greathouse IV, Oct 07 2015

Formula

a(n) = 2*a(n-1) + a(n-3) - 2*a(n-4). -John W. Layman

G.f.: 1/((1-x^3)*(1-2*x)); a(n) = sum{k=0..floor(n/3), 2^(n-3*k)}; a(n) = Sum_{k=0..n} 2^k*( cos(2*Pi*(n-k)/3 + Pi/3)/3 + sqrt(3)*sin(2*Pi*(n-k)/3 + Pi/3)/3 + 1/3 ). - Paul Barry, Apr 16 2005

a(n) = floor(2^(n+2)/7). - Gary Detlefs, Sep 06 2010

a(n) = floor((4*2^n - 1)/7) = ceiling((4*2^n - 4)/7) = round((4*2^n - 2)/7) = round((8*2^n - 5)/14); a(n) = a(n-3) + 2^(n-1), n>3. - Mircea Merca, Dec 28 2010

a(n) = 4/7*2^n - 5/21*cos(2/3*Pi*n) + 1/21*3^(1/2)*sin(2/3*Pi*n)-1/3. - Leonid Bedratyuk, May 13 2012

Extensions

Edited by Jeremy Gardiner, Oct 08 2011

New name (using formula form Gary Detlefs) from Joerg Arndt, Mar 10 2015