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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).
(Formerly M0277)
7
1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

a(n+1) is the second-order survivor of the n-person Josephus problem where every second person is marked until only one remains, who is then eliminated; the process is repeated from the beginning until all but one is eliminated. a(n) is first a power of 2 when n is three times a power of 2. For example, the first appearances of 2, 4, 8 and 16 are at positions 3, 6, 12 and 24, or (3*1),(3*2),(3*4) and (3*8). Eugene McDonnell (eemcd(AT)aol.com), Jan 19 2002, reporting on work of Boyko Bantchev (Bulgaria).

a(n+1)=min(msb(n),1+n-msb(n)/2) for all n (msb = most significant bit, A053644). - Boyko Bantchev (bantchev(AT)math.bas.bg), May 17 2002

Appears to coincide with following sequence: Let n >= 1. Start with a bag B containing n 1's. At each step, replace the two least elements x and y in B with the single element x+y. Repeat until B contains 2 or fewer elements. Let a(n) be the largest element remaining in B at this point. - David W. Wilson, Jul 01 2003

REFERENCES

J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 85-94.

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 = 1..1024

J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

Dale Gerdemann, Second-Order Josephus Problem (video)

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

FORMULA

For n>=2, if a(n)>=A006257(n), i.e., if msb(n)>n-a(n)/2, then a(n+1)=a(n)+1, otherwise a(n+1)=a(n). - Henry Bottomley, Jan 21 2002

a(1)=1, a(n)=n-a(n-a(a(n-1))). - Benoit Cloitre, Nov 08 2002

For k>0, 0<=i<=2^k-1, a(2^k+i)=2^(k-1)+i; for 2^k-2^(k-2)<=x<=2^k a(x)=2^(k-1); (also a(m*2^k)=a(m)*2^k for m>=2). - Benoit Cloitre, Dec 16 2002

G.f. x * (1/(1+x) + 1/(1-x)^2 * sum(k>=0, t^2(1-t), t=x^2^k)). - Ralf Stephan, Sep 12 2003

a(n) = A005942(n+1)/2 - n = n - A060973(n) = 2n - A007378(n). - Ralf Stephan, Sep 13 2003

a(n) = A080776(n-1) + A060937(n). - Ralf Stephan

MATHEMATICA

t = {1, 1}; Do[If[OddQ[n], AppendTo[t, t[[Floor[n/2]]] + t[[Ceiling[n/2]]]], AppendTo[t, 2*t[[n/2]]]], {n, 3, 128}] (* T. D. Noe, May 25 2011 *)

CROSSREFS

Cf. A066997.

Sequence in context: A076502 A076897 A066997 * A078881 A131807 A104351

Adjacent sequences:  A006162 A006163 A006164 * A006166 A006167 A006168

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Larry Reeves (larryr(AT)acm.org), Jun 12 2002

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 20 00:42 EST 2017. Contains 294957 sequences.