

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 secondorder survivor of the nperson 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+nmsb(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
HsienKuei Hwang, S Janson, TH Tsai (2016) show that A078881 is the same sequence, apart from the offset.  N. J. A. Sloane, Nov 26 2017


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), 8594.
HsienKuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wpcontent/files/2016/12/aathhrr1.pdf. Also Exact and Asymptotic Solutions of a DivideandConquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
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 kregular Sequences, II
J.P. Allouche and J. Shallit, The ring of kregular sequences, II, Theoret. Computer Sci., 307 (2003), 329.
Dale Gerdemann, SecondOrder Josephus Problem (video)
R. Stephan, Some divideandconquer sequences ...
R. Stephan, Table of generating functions


FORMULA

For n>=2, if a(n)>=A006257(n), i.e., if msb(n)>na(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)=na(na(a(n1))).  Benoit Cloitre, Nov 08 2002
For k>0, 0<=i<=2^k1, a(2^k+i)=2^(k1)+i; for 2^k2^(k2)<=x<=2^k a(x)=2^(k1); (also a(m*2^k)=a(m)*2^k for m>=2).  Benoit Cloitre, Dec 16 2002
G.f. x * (1/(1+x) + 1/(1x)^2 * sum(k>=0, t^2(1t), 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(n1) + 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, A078881.
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



