A060973 -id:A060973 - cp's OEIS frontend

A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).

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

Offset: 1

N. J. A. Sloane

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).
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
Hsien-Kuei Hwang, S Janson, TH Tsai (2016) show that A078881 is the same sequence, apart from the offset. - N. J. A. Sloane, Nov 26 2017

			From _Peter Bala_, Aug 01 2022: (Start)
1) The sequence {n - a(a(n)) : n >= 1} begins [0, 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 9, 10, 11, 12, 12, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, ...] has the repeated values 3 (twice), 6 (three times), 12 (five times), 24 (nine times), 48 (seventeen times) ..., conjecturally of the form 3*2^m
2) The sequence {n - a(a(a(n))) : n >= 1} begins [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 14, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 28, 28, 28, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, ...] has the repeated values 7 (twice), 14 (three times), 28 (five times), 56 (nine times) ..., conjecturally of the form 7*2^m. (End)

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.
Hsien-Kuei 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/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer 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).

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)
Jeffrey Shallit, Intertwining of Complementary Thue-Morse Factors, arXiv:2203.02917 [cs.FL], 2022.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to the Josephus Problem

Cf. A053644, A060973, A066997, A078881.

a := proc (n) option remember; if n = 1 then 1 else n - a(n - a(a(n-1))) end if end proc: seq(a(n), n = 1..100); # Peter Bala, Jul 31 2022

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 *)

a(n) = my(i=logint(n,2)-1); if(bittest(n,i), 2<Kevin Ryde, Aug 06 2022

a(n)=if(n<2,1,n-a(n-a(n\2))); \\ Benoit Cloitre, May 12 2024

from functools import lru_cache
@lru_cache(maxsize=None)
def A006165(n): return 1 if n <= 2 else A006165(n//2) + A006165((n+1)//2) # Chai Wah Wu, Mar 08 2022

def A006165(n): return min(n-(m:=1<1 else 1 # Chai Wah Wu, Oct 22 2024

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(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
a(1)=1, a(n) = n - a(n - a(a(n-1))). - Benoit Cloitre, Nov 08 2002
a(1)=1, a(n) = n - a(n - a(floor(n/2))). - Benoit Cloitre, May 12 2024
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)) where 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
From Peter Bala, Jul 31 2022: (Start)
For k a positive integer, define the k-th iterated sequence a^(k) of a by a^(1)(n) = a(n) and setting a^(k)(n) = a^(k-1)(a(n)) for k >= 2. For example, a^(2)(n) = a(a(n)) and a^(3)(n) = a(a(a(n))).
Conjectures: for n >= 2 there holds
(i) a(n) + a(n - a(n - a(n - a(n - a(n))))) = n;
(ii) a(n - a(n - a(n - a(n)))) = a(n - a(n - a(n - a(n - a(n - a(n))))));
(iii) a^2(n) = a(n - a(n - a(n - a(n))));
(iv) n - a(n) = a(n - a^(2)(n));
(v) a(n - a(n)) = a^(2)(n - a^(2)(n - a^(2)(n - a^(2)(n))));
(vi) for k >= 2, a^(k)(n - a^(k)(n)) = a^(k)(n - a^(k)(n - a^(k)(n - a^(k)(n)))).
(vii) for k >= 1, the sequence {n - a^(k)(n) : n >= 1} has first differences either 0 or 1. We conjecture that the repeated values of the sequence are of the form (2^k - 1)*2^m. The number of repeated values appears to always be 2, 3, 5, 9, 17, 35, ..., independent of k, conjecturally A000051. Two examples are given below.
A similar property may hold for the sequences {n - A060973^(k)(n) : n >= 2^(k-1)}, k = 1,2,3,.... (End)

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

A053646 Distance to nearest power of 2.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Offset: 1

Henry Bottomley, Mar 22 2000

Sum_{j=1..2^(k+1)} a(j) = A002450(k) = (4^k - 1)/3. - Klaus Brockhaus, Mar 17 2003

			a(10)=2 since 8 is closest power of 2 to 10 and |8-10| = 2.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Klaus Brockhaus, Illustration for A053646, A081252, A081253 and A081254
Hsien-Kuei Hwang, S. Janson, and T.-H. 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.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Index entries for sequences related to distance to nearest element of some set

Cf. A006165, A053188, A060973, A081134, A002450, A081252, A081253, A081254.

a:= n-> (h-> min(n-h, 2*h-n))(2^ilog2(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Mar 28 2021

np2[n_]:=Module[{min=Floor[Log[2,n]],max},max=min+1;If[2^max-nHarvey P. Dale, Feb 21 2012 *)

a(n)=vecmin(vector(n,i,abs(n-2^(i-1))))

for(n=1,89,p=2^floor(0.1^25+log(n)/log(2)); print1(min(n-p,2*p-n),","))

a(n) = my (p=#binary(n)); return (min(n-2^(p-1), 2^p-n)) \\ Rémy Sigrist, Mar 24 2018

def A053646(n): return min(n-(m := 2**(len(bin(n))-3)),2*m-n) # Chai Wah Wu, Mar 08 2022

a(2^k+i) = i for 1 <= i <= 2^(k-1); a(3*2^k+i) = 2^k-i for 1 <= i <= 2^k; (Sum_{k=1..n} a(k))/n^2 is bounded. - Benoit Cloitre, Aug 17 2002
a(n) = min(n-2^floor(log(n)/log(2)), 2*2^floor(log(n)/log(2))-n). - Klaus Brockhaus, Mar 08 2003
From Peter Bala, Aug 04 2022: (Start)
a(n) = a( 1 + floor((n-1)/2) ) + a( ceiling((n-1)/2) ).
a(2*n) = 2*a(n); a(2*n+1) = a(n) + a(n+1) for n >= 2. Cf. A006165. (End)
a(n) = 2*A006165(n) - n for n >= 2. - Peter Bala, Sep 25 2022

A007378 a(n), for n >= 2, is smallest positive integer which is consistent with sequence being monotonically increasing and satisfying a(a(n)) = 2n.

Original entry on oeis.org

3, 4, 6, 7, 8, 10, 12, 13, 14, 15, 16, 18, 20, 22, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 36, 38, 40, 42, 44, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 97, 98, 99, 100, 101, 102, 103

Offset: 2

Colin Mallows

This is the unique monotonic sequence {a(n)}, n>=2, satisfying a(a(n)) = 2n.
May also be defined by: a(n), n=2,3,4,..., is smallest positive integer greater than a(n-1) which is consistent with the condition "n is a member of the sequence if and only if a(n) is an even number >= 4". - N. J. A. Sloane, Feb 23 2003
A monotone sequence satisfying a^(k+1)(n) = mn is unique if m=2, k >= 0 or if (k,m) = (1,3). See A088720. - Colin Mallows, Oct 16 2003
Numbers (greater than 2) whose binary representation starts with "11" or ends with "0". - Franklin T. Adams-Watters, Jan 17 2006
Lower density 2/3, upper density 3/4. - Charles R Greathouse IV, Dec 14 2022

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 2..10000
J.-P. Allouche, N. Rampersad and J. Shallit, On integer sequences whose first iterates are linear, Aequationes Math. 69 (2005), 114-127.
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.
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.
Hsien-Kuei Hwang, S. Janson, and T.-H. 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.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47.
Jeffrey Shallit, k-regular Sequences
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences of the a(a(n)) = 2n family

Cf. A003605. Equals A080653 + 2.
This sequence, A079905, A080637 and A080653 are all essentially the same.
Cf. A088720, A042965.

a := proc(n) option remember; if n < 4 then n+1 else a(iquo(n,2)) + a(iquo(n+1,2)) fi end:
seq(a(n), n = 2..70); # Peter Bala, Aug 03 2022

max = 70; f[x_] := -x/(1-x) + x/(1-x)^2*(2 + Sum[ x^(2^k + 2^(k+1)) - x^2^(k+1) , {k, 0, Ceiling[Log[2, max]]}]); Drop[ CoefficientList[ Series[f[x], {x, 0, max + 1}], x], 2](* Jean-François Alcover, May 16 2012, from g.f. *)
a[2]=3; a[3]=4; a[n_?OddQ] := a[n] = a[(n-1)/2+1] + a[(n-1)/2]; a[n_?EvenQ] := a[n] = 2a[n/2]; Table[a[n], {n, 2, 71}] (* Jean-François Alcover, Jun 26 2012, after Vladeta Jovovic *)

a(n) = my(s=logint(n,2)-1); if(bittest(n,s), n<<1 - 2<Kevin Ryde, Aug 08 2022

from functools import cache
@cache
def a(n): return n+1 if n < 4 else a(n//2) + a((n+1)//2)
print([a(n) for n in range(2, 72)]) # Michael S. Branicky, Aug 04 2022

a(2^i + j) = 3*2^(i-1) + j, 0<=j<2^(i-1); a(3*2^(i-1) + j) = 2^(i+1) + 2*j, 0<=j<2^(i-1).
a(3*2^k + j) = 4*2^k + 3j/2 + |j|/2, k>=0, -2^k <= j < 2^k. - N. J. A. Sloane, Feb 23 2003
a(2*n+1) = a(n+1)+a(n), a(2*n) = 2*a(n). a(n) = n+A060973(n). - Vladeta Jovovic, Mar 01 2003
G.f.: -x/(1-x) + x/(1-x)^2 * (2 + sum(k>=0, t^2(t-1), t=x^2^k)). - Ralf Stephan, Sep 12 2003

More terms from Matthew Vandermast and Vladeta Jovovic, Mar 01 2003

A352228 Number of length-n blocks in the Thue-Morse sequence with intertwining pattern ABBA ABBA ABBA... .

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 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

Offset: 1

Jeffrey Shallit, Mar 08 2022

nonn

Essentially a duplicate of A060973. This is 0 together with A060973.

The intertwining pattern is the list of consecutive occurrences of a block x and its binary complement x' in the Thue-Morse sequence A010060, where A codes an occurrence of x and B codes an occurrence of x'.

			For n = 4, the only block with intertwining sequence ABBA ABBA ... is 0011.

Jeffrey Shallit, Intertwining of Complementary Thue-Morse Factors, arxiv preprint arXiv:2203.02917 [cs.FL], March 6 2022.

Cf. A010060, A060973. Related to A352227.

a[n_] := a[n] = Switch[n, 1|2, 0, 3, 1, n, If[Mod[n, 2] == 1, 2*a[(n+1)/2//Floor], a[n/2//Floor] + a[1+n/2//Floor]]];
Table[a[n], {n, 1, 78}] (* Jean-François Alcover, Mar 25 2023 *)

# Recurrence from Henry Bottomley in A060973.
from functools import cache
@cache
def a(n):
    match n:
        case 1 | 2: return 0
        case 3: return 1
        case n  if n % 2 == 1: return 2*a((n+1)//2)
        case _: return a(n//2) + a(1+n//2)
print([a(n) for n in range(1, 73)])  # Peter Luschny, Mar 08 2022

a(n) = A060973(n-1) for n >= 1.

cp's OEIS Frontend

A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A053646 Distance to nearest power of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A007378 a(n), for n >= 2, is smallest positive integer which is consistent with sequence being monotonically increasing and satisfying a(a(n)) = 2n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A352228 Number of length-n blocks in the Thue-Morse sequence with intertwining pattern ABBA ABBA ABBA... .

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula