A079944 -id:A079944 - cp's OEIS frontend

A053985 Replace 2^k with (-2)^k in binary expansion of n.

0, 1, -2, -1, 4, 5, 2, 3, -8, -7, -10, -9, -4, -3, -6, -5, 16, 17, 14, 15, 20, 21, 18, 19, 8, 9, 6, 7, 12, 13, 10, 11, -32, -31, -34, -33, -28, -27, -30, -29, -40, -39, -42, -41, -36, -35, -38, -37, -16, -15, -18, -17, -12, -11, -14, -13, -24, -23, -26, -25, -20, -19

Offset: 0

Henry Bottomley, Apr 03 2000

Base 2 representation for n (in lexicographic order) converted from base -2 to base 10.
Maps natural numbers uniquely onto integers; within each group of positive values, maximum is in A002450; a(n)=n iff n can be written only with 1's and 0's in base 4 (A000695).
a(n) = A004514(n) - n. - Reinhard Zumkeller, Dec 27 2003
Schroeppel gives formula n = (a(n) + b) XOR b where b = binary ...101010, and notes this formula is reversible.  The reverse a(n) = (n XOR b) - b is a bit twiddle to transform 1 bits to -1.  Odd position 0 or 1 in n is flipped by "XOR b" to 1 or 0, then "- b" gives 0 or -1.  Only odd position 1's are changed, so b can be any length sure to cover those. - Kevin Ryde, Jun 26 2020

			a(9)=-7 because 9 is written 1001 base 2 and (-2)^3 + (-2)^0 = -8 + 1 = -7.
Or by Schroeppel's formula, b = binary 1010 then a(9) = (1001 XOR 1010) - 1010 = decimal -7. - _Kevin Ryde_, Jun 26 2020

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Michael Beeler, R. William Gosper, and Richard Schroeppel, HAKMEM, MIT Artificial Intelligence Laboratory report AIM-239, February 1972, item 128 by Schroeppel, page 62. Also HTML transcription. Figure 7 path drawn 0, 1, -2, -1, 4, ... is the present sequence.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 45, 49.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625 [math.CO], 2020-2021.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Inverse of A005351. Cf. A039724, A007088, A065369, A073791, A073792, A073793, A073794, A073795, A073796 and A073835.

f[n_Integer, b_Integer] := Block[{l = IntegerDigits[n]}, Sum[l[[ -i]]*(-b)^(i - 1), {i, 1, Length[l]}]]; a = Table[ FromDigits[ IntegerDigits[n, 2]], {n, 0, 80}]; b = {}; Do[b = Append[b, f[a[[n]], 2]], {n, 1, 80}]; b
(* Second program: *)
Array[FromDigits[IntegerDigits[#, 2], -2] &, 62, 0] (* Michael De Vlieger, Jun 27 2020 *)

a(n) = fromdigits(binary(n), -2) \\ Rémy Sigrist, Sep 01 2018

def A053985(n): return  -(b:=int('10'*(n.bit_length()+1>>1),2)) + (n^b) if n else 0 # Chai Wah Wu, Nov 18 2022

From Ralf Stephan, Jun 13 2003: (Start)
G.f.: (1/(1-x)) * Sum_{k>=0} (-2)^k*x^2^k/(1+x^2^k).
a(0) = 0, a(2*n) = -2*a(n), a(2*n+1) = -2*a(n)+1. (End)
a(n) = Sum_{k>=0} A030308(n,k)*A122803(k). - Philippe Deléham, Oct 15 2011
a(n) = (n XOR b) - b where b = binary ..101010 [Schroeppel].  Any b of this form (A020988) with bitlength(b) >= bitlength(n) suits. - Kevin Ryde, Jun 26 2020

A080277 Partial sums of A038712.

Original entry on oeis.org

1, 4, 5, 12, 13, 16, 17, 32, 33, 36, 37, 44, 45, 48, 49, 80, 81, 84, 85, 92, 93, 96, 97, 112, 113, 116, 117, 124, 125, 128, 129, 192, 193, 196, 197, 204, 205, 208, 209, 224, 225, 228, 229, 236, 237, 240, 241, 272, 273, 276, 277, 284, 285, 288, 289, 304, 305, 308

Offset: 1

N. J. A. Sloane, Mar 19 2003

nonn

			From _Omar E. Pol_, Sep 10 2019: (Start)
Illustration of initial terms:
a(n) is also the total area (or the total number of cells) in first n regions of an infinite diagram of compositions (ordered partitions) of the positive integers, where the length of the n-th horizontal line segment is equal to A001511(n), the length of the n-th vertical line segment is equal to A006519(n), and area of the n-th region is equal to A038712(n), as shown below (first eight regions):
-----------------------------------
n  A038712(n)  a(n)       Diagram
-----------------------------------
.                         _ _ _ _
1      1         1       |_| | | |
2      3         4       |_ _| | |
3      1         5       |_|   | |
4      7        12       |_ _ _| |
5      1        13       |_| |   |
6      3        16       |_ _|   |
7      1        17       |_|     |
8     15        32       |_ _ _ _|
.
The above diagram represents the eight compositions of 4: [1,1,1,1],[2,1,1],[1,2,1],[3,1],[1,1,2],[2,2],[1,3],[4].
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..16383
M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, 21st Int. Symp. Graph Drawing, 2013, arXiv:1308.0403 [cs.CG], 2013-2014.
M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, Journal of Graph Algorithms and Applications 18(2) (2014), 177-209.
Klaus Brockhaus, Illustration of A038712 and A080277.
B. Dearden, J. Iiams, and J. Metzger, A Function Related to the Rumor Sequence Conjecture, J. Int. Seq. 14 (2011), #11.2.3.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions. [ps file]
Ralf Stephan, Table of generating functions. [pdf file]

Cf. A001787, A038712, A050292, A080333, A120385.

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 16, 17, 17, 18, 19, 20, 20, 21, 21, 22, 22, 23, 24, 25, 25, 26, 26, 27, 27, 28, 29, 30, 30, 31, 32, 33, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 40, 41, 41, 42, 43, 44, 44, 45, 46, 47, 47, 48, 48, 49, 49, 50, 51, 52, 52, 53, 54

Offset: 0

Eric W. Weisstein

Note that the first equation implies a(0)=0, so there is no need to specify an initial value.
Maximal cardinality of a double-free subset of {1, 2, ..., n}, or in other words, maximal size of a subset S of {1, 2, ..., n} with the property that if x is in S then 2x is not. a(0)=0 by convention.
Least k such that a(k)=n is equal to A003159(n).
To construct the sequence: let [a, b, c, a, a, a, b, c, a, b, c, ...] be the fixed point of the morphism a -> abc, b ->a, c -> a, starting from a(1) = a, then write the indices of a, b, c, that of a being written twice; see A092606. - Philippe Deléham, Apr 13 2004
Number of integers from {1,...,n} for which the subtraction of 1 changes the parity of the number of 1's in their binary expansion. - Vladimir Shevelev, Apr 15 2010
Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. - Vladimir Shevelev, Apr 16 2010
a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. Each number n appears A026465(n+1) times. - Philippe Deléham, Oct 19 2011
Another way of stating the last two comments from Philippe Deléham: the sequence can be obtained by replacing each term of the Thue-Morse sequence A010060 by the run number that term is in. - N. J. A. Sloane, Dec 31 2013

			Examples for n = 1 through 8: {1}, {1}, {1,3}, {1,3,4}, {1,3,4,5}, {1,3,4,5}, {1,3,4,5,7}, {1,3,4,5,7}.
Binary expansion of 5 is 101, so Sum{i>=0} b_i*(-1)^i = 2. Therefore a(5) = 10/3 + 2/3 = 4. - _Vladimir Shevelev_, Apr 15 2010

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.
Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Double-Free Set.

Bisection of A123087.

Cf. A001045, A050291-A050296, A050321, A035263, A121701, A030308, A080277, A120385, A197911.

a050292 n = a050292_list !! (n-1)
a050292_list = scanl (+) 0 a035263_list
-- Reinhard Zumkeller, Jan 21 2013

A050292:=n->add((-1)^k*floor(n/2^k), k=0..n); seq(A050292(n), n=0..100); # Wesley Ivan Hurt, Feb 14 2014

a[n_] := a[n] = If[n < 2, 1, n - a[Floor[n/2]]]; Table[ a[n], {n, 1, 75}]
Join[{0},Accumulate[Nest[Flatten[#/.{0->{1,1},1->{1,0}}]&,{0},7]]] (* Harvey P. Dale, Apr 29 2018 *)

PARI
```
a(n)=if(n<2,1,n-a(floor(n/2)))
```

from sympy.ntheory import digits
def A050292(n): return ((n<<1)+sum((0,1,-1,0)[i] for i in digits(n,4)[1:]))//3 # Chai Wah Wu, Jan 30 2025

Partial sums of A035263. Close to (2/3)*n.
a(n) = A123087(2*n) = n - A123087(n). - Max Alekseyev, Mar 05 2023
From Benoit Cloitre, Nov 24 2002: (Start)
a(1)=1, a(n) = n - a(floor(n/2));
a(n) = (2/3)*n + (1/3)*A065359(n);
more generally, for m>=0, a(2^m*n) - 2^m*a(n) = A001045(m)*A065359(n) where A001045(m) = (2^m - (-1)^m)/3 is the Jacobsthal sequence;
a(A039004(n)) = (2/3)*A039004(n);
a(2*A039004(n)) = 2*a(A039004(n));
a(A003159(n)) = n;
a(A003159(n)-1) = n-1;
a(n) mod 2 = A010060(n) the Thue-Morse sequence;
a(n+1) - a(n) = A035263(n+1);
a(n+2) - a(n) = abs(A029884(n)).
(End)
G.f.: (1/(x-1)) * Sum_{i>=0} (-1)^i*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*floor(n/2^k). - Benoit Cloitre, Jun 03 2003
a(A091785(n)) = 2n; a(A091855(n)) = 2n-1. - Philippe Deléham, Mar 26 2004
a(2^n) = (2^(n+1) + (-1)^n)/3. - Vladimir Shevelev, Apr 15 2010
If n = Sum_{i>=0} b_i*2^i is the binary expansion of n, then a(n) = 2n/3 + (1/3)Sum_{i>=0} b_i*(-1)^i. Thus a(n) = 2n/3 + O(log(n)). - Vladimir Shevelev, Apr 15 2010
Moreover, the equation a(3m)=2m has infinitely many solutions, e.g., a(3*2^k)=2*2^k; on the other hand, a((4^k-1)/3)=(2*(4^k-1))/9+k/3, i.e., limsup |a(n)-2n/3| = infinity. - Vladimir Shevelev, Feb 23 2011
a(n) = Sum_{k>=0} A030308(n,k)*A001045(k+1). - Philippe Deléham, Oct 19 2011
From Peter Bala, Feb 02 2013: (Start)
Product_{n >= 1} (1 + x^((2^n - (-1)^n)/3 )) = (1 + x)^2(1 + x^3)(1 + x^5)(1 + x^11)(1 + x^21)... = 1 + sum {n >= 1} x^a(n) = 1 + 2x + x^2 + x^3 + 2x^4 + 2x^5 + .... Hence this sequence lists the numbers representable as a sum of distinct Jacobsthal numbers A001045 = [1, 1', 3, 5, 11, 21, ...], where we distinguish between the two occurrences of 1 by writing them as 1 and 1'. For example, 9 occurs twice in the present sequence because 9 = 5 + 3 + 1 and 9 = 5 + 3 + 1'. Cf. A197911 and A080277. See also A120385.
(End)

Extended with formula by Christian G. Bower, Sep 15 1999
Corrected and extended by Reinhard Zumkeller, Aug 16 2006
Extended with formula by Philippe Deléham, Oct 19 2011
Entry revised to give a simpler definition by N. J. A. Sloane, Jan 03 2014

A033264 Number of blocks of {1,0} in the binary expansion of n.

Original entry on oeis.org

0, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2, 2

Offset: 1

Clark Kimberling

Number of i such that d(i) < d(i-1), where Sum_{d(i)*2^i: i=0,1,....,m} is base 2 representation of n.

This is the base-2 down-variation sequence; see A297330. - Clark Kimberling, Jan 18 2017

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche and Jeffrey Shallit, Sums of digits and the Hurwitz zeta function, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Eric Weisstein's World of Mathematics, Digit Block.
Index entries for sequences related to binary expansion of n

Cf. A014081, A014082, A037800, A056974, A056975, A056976, A056977, A056978, A056979, A056980, A196521.
a(n) = A005811(n) - ceiling(A005811(n)/2) = A005811(n) - A069010(n).
Equals (A072219(n+1)-1)/2.
Cf. also A175047, A030308.
Essentially the same as A087116.

a033264 = f 0 . a030308_row where
   f c [] = c
   f c (0 : 1 : bs) = f (c + 1) bs
   f c (_ : bs) = f c bs
-- Reinhard Zumkeller, Feb 20 2014, Jun 17 2012

f:= proc(n) option remember; local k;
k:= n mod 4;
if k = 2 then procname((n-2)/4) + 1
elif k = 3 then procname((n-3)/4)
else procname((n-k)/2)
fi
end proc:
f(1):= 0: f(0):= q:
seq(f(i),i=1..100); # Robert Israel, Aug 31 2015

Table[Count[Partition[IntegerDigits[n, 2], 2, 1], {1, 0}], {n, 102}] (* Michael De Vlieger, Aug 31 2015, after Robert G. Wilson v at A014081 *)
Table[SequenceCount[IntegerDigits[n,2],{1,0}],{n,110}] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Jan 26 2017 *)

a(n) = { hammingweight(bitand(n>>1, bitneg(n))) }; \\ Gheorghe Coserea, Aug 30 2015

def A033264(n): return ((n>>1)&~n).bit_count() # Chai Wah Wu, Jun 25 2025

G.f.: 1/(1-x) * Sum_(k>=0, t^2/(1+t)/(1+t^2), t=x^2^k). - Ralf Stephan, Sep 10 2003
a(n) = A069010(n) - (n mod 2). - Ralf Stephan, Sep 10 2003
a(4n) = a(4n+1) = a(2n), a(4n+2) = a(n)+1, a(4n+3) = a(n). - Ralf Stephan, Aug 20 2003
a(n) = A087116(n) for n > 0, since strings of 0's alternate with strings of 1's, which end in (1,0). - Jonathan Sondow, Jan 17 2016
Sum_{n>=1} a(n)/(n*(n+1)) = Pi/4 - log(2)/2 (A196521) (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

A062050 n-th chunk consists of the numbers 1, ..., 2^n.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 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, 26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17

Offset: 1

Marc LeBrun, Jun 30 2001

a(k) is the distance between k and the largest power of 2 not exceeding k, where k = n + 1. [Consider the sequence of even numbers <= k; after sending the first term to the last position delete all odd-indexed terms; the final term that remains after iterating the process is the a(k)-th even number.] - Lekraj Beedassy, May 26 2005

Triangle read by rows in which row n lists the first 2^(n-1) positive integers, n >= 1; see the example. - Omar E. Pol, Sep 10 2013

			From _Omar E. Pol_, Aug 31 2013: (Start)
Written as irregular triangle with row lengths A000079:
  1;
  1, 2;
  1, 2, 3, 4;
  1, 2, 3, 4, 5, 6, 7, 8;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16;
  ...
Row sums give A007582.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions. [ps file]
Ralf Stephan, Table of generating functions. [pdf file]

Cf. A053644, A053645.

Cf. A092754.

a062050 n = if n < 2 then n else 2 * a062050 n' + m - 1
            where (n',m) = divMod n 2
-- Reinhard Zumkeller, May 07 2012

A062050 := proc(n) option remember; if n < 4 then return [1, 1, 2][n] fi;
2*A062050(floor(n/2)) + irem(n,2) - 1 end:
seq(A062050(n), n=1..89); # Peter Luschny, Apr 27 2020

Flatten[Table[Range[2^n],{n,0,6}]] (* Harvey P. Dale, Oct 12 2015 *)

PARI
```
a(n)=floor(n+1-2^logint(n,2))
```

a(n)= n - 1<Ruud H.G. van Tol, Dec 13 2024

def A062050(n): return n-(1<Chai Wah Wu, Jan 22 2023

a(n) = A053645(n) + 1.
a(n) = n - msb(n) + 1 (where msb(n) = A053644(n)).
a(n) = 1 + n - 2^floor(log(n)/log(2)). - Benoit Cloitre, Feb 06 2003; corrected by Joseph Biberstine (jrbibers(AT)indiana.edu), Nov 25 2008
G.f.: 1/(1-x) * ((1-x+x^2)/(1-x) - Sum_{k>=1} 2^(k-1)*x^(2^k)). - Ralf Stephan, Apr 18 2003
a(1) = 1, a(2*n) = 2*a(n) - 1, a(2*n+1) = 2*a(n). - Ralf Stephan, Oct 06 2003
A005836(a(n+1)) = A107681(n). - Reinhard Zumkeller, May 20 2005
a(n) = if n < 2 then n else 2*a(floor(n/2)) - 1 + n mod 2. - Reinhard Zumkeller, May 07 2012
Without the constant 1, Ralf Stephan's g.f. becomes A(x) = x/(1-x)^2 - (1/(1-x)) * Sum_{k>=1} 2^(k-1)*x^(2^k) and satisfies the functional equation A(x) - 2*(1+x)*A(x^2) = x*(1 - x - x^2)/(1 - x^2). - Petros Hadjicostas, Apr 27 2020
For n > 0: a(n) = (A006257(n) + 1) / 2. - Frank Hollstein, Oct 25 2021

A002516 Earliest sequence with a(a(n)) = 2n.

Original entry on oeis.org

0, 3, 6, 2, 12, 7, 4, 10, 24, 11, 14, 18, 8, 15, 20, 26, 48, 19, 22, 34, 28, 23, 36, 42, 16, 27, 30, 50, 40, 31, 52, 58, 96, 35, 38, 66, 44, 39, 68, 74, 56, 43, 46, 82, 72, 47, 84, 90, 32, 51, 54, 98, 60, 55, 100, 106, 80, 59, 62, 114, 104, 63, 116, 122, 192, 67, 70, 130

Offset: 0

Colin Mallows

T. D. Noe, Table of n, a(n) for n = 0..1000
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. A002517, A004767, A007379, A017089, A091067.

import Data.List (transpose)
a002516 n = a002516_list !! n
a002516_list = 0 : concat (transpose
[a004767_list, f a002516_list, a017089_list, g $ drop 2 a002516_list])
where f [z] = []; f (_:z:zs) = 2 * z : f zs
g [z] = [z]; g (z:_:zs) = 2 * z : g zs
-- Reinhard Zumkeller, Jun 08 2015

a[0] = 0; a[n_ /; Mod[n, 2] == 0] := a[n] = 2*a[n/2]; a[n_ /; Mod[n, 4] == 1] := n+2; a[n_ /; Mod[n, 4] == 3] := 2(n-2); Table[a[n], {n, 0, 67}] (* Jean-François Alcover, Feb 06 2012, after Henry Bottomley *)

v2(n)=valuation(n,2)
a(n)=2^v2(n)*(-1+3/2*n/2^v2(n)-(-3+1/2*n/2^v2(n))*(-1)^((n/2^v2(n)-1)/2))

a(n)=local(t); if(n<1,0,if(n%2==0,2*a(n/2),t=(n-1)/2; 3*t+1/2-(t-5/2)*(-1)^t)) \\ Ralf Stephan, Feb 22 2004

a(4n) = 2*(a(2n)), a(4n+1) = 4n+3, a(4n+2) = 2*(a(2n+1)), a(4n+3) = 8n+2. - Henry Bottomley, Apr 27 2000
From Ralf Stephan, Feb 22 2004: (Start)
a(n) = n + 2*A006519(n) if odd part of n is of form 4k+1, or 2n - 4*A006519(n) otherwise.
a(2n) = 2*a(n), a(2n+1) = 2n + 3 + (2n - 5)*[n mod 2].
G.f.: Sum_{k>=0} 2^k*t(6t^6 + t^4 + 2t^2 + 3)/(1 - t^4)^2, t = x^2^k. (End)

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

Original entry on oeis.org

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

A037800 Number of occurrences of 01 in the binary expansion of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 0, 1, 1, 1, 1, 2, 1

Offset: 0

Clark Kimberling

Number of i such that d(i)>d(i-1), where Sum{d(i)*2^i: i=0,1,...,m} is base 2 representation of n.

This is the base-2 up-variation sequence; see A297330. - Clark Kimberling, Jan 18 2017

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche and Jeffrey Shallit, Sums of digits and the Hurwitz zeta function, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Eric Weisstein's World of Mathematics, Digit Block.
Index entries for sequences related to binary expansion of n

Cf. A014081, A014082, A033264, A056974, A056975, A056976, A056977, A056978, A056979, A056980.

Cf. A030308, A231902.

a037800 = f 0 . a030308_row where
   f c [_]          = c
   f c (1 : 0 : bs) = f (c + 1) bs
   f c (_ : bs)     = f c bs
-- Reinhard Zumkeller, Feb 20 2014

Table[SequenceCount[IntegerDigits[n,2],{0,1}],{n,0,120}] (* Harvey P. Dale, Aug 10 2023 *)

a(n) = { if(n == 0, 0, -1 + hammingweight(bitnegimply(n, n>>1))) };  \\ Gheorghe Coserea, Aug 31 2015

a(2n) = a(n), a(2n+1) = a(n) + [n is even]. - Ralf Stephan, Aug 21 2003
G.f.: 1/(1-x) * Sum_{k>=0} t^5/(1+t)/(1+t^2) where t=x^2^k. - Ralf Stephan, Sep 10 2003
a(n) = A069010(n) - 1, n>0. - Ralf Stephan, Sep 10 2003
Sum_{n>=1} a(n)/(n*(n+1)) = log(2)/2 + Pi/4 - 1 = A231902 - 1 (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

A014082 Number of occurrences of '111' in binary expansion of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 1, 0

Offset: 0

Simon Plouffe

a(n) = A213629(n,7) for n > 6. - Reinhard Zumkeller, Jun 17 2012

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Digit Block
Index entries for sequences related to binary expansion of n

Cf. A014081, A033264, A056974, A056975, A056976, A056977, A056978, A056979, A056980, A213629, A239906, A239907.

import Data.List (tails, isPrefixOf)
a014082 = sum . map (fromEnum . ([1,1,1] `isPrefixOf`)) .
                    tails . a030308_row
-- Reinhard Zumkeller, Jun 17 2012

See A014081.
f:= proc(n) option remember;
  if n::even then procname(n/2)
  elif n mod 8 = 7 then 1 + procname((n-1)/2)
  else procname((n-1)/2)
fi
end proc:
f(0):= 0:
map(f, [$0..1000]); # Robert Israel, Sep 11 2015

f[n_] := Count[ Partition[ IntegerDigits[n, 2], 3, 1], {1, 1, 1}]; Table[f@n, {n, 0, 104}] (* Robert G. Wilson v, Apr 02 2009 *)
a[0] = a[1] = 0; a[n_] := a[n] = If[EvenQ[n], a[n/2], a[(n - 1)/2] + Boole[Mod[(n - 1)/2, 4] == 3]]; Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Oct 22 2012, after Ralf Stephan *)
Table[SequenceCount[IntegerDigits[n,2],{1,1,1},Overlaps->True],{n,0,110}] (* Harvey P. Dale, Mar 05 2023 *)

a(n) = hammingweight(bitand(n, bitand(n>>1, n>>2))); \\ Gheorghe Coserea, Aug 30 2015

a(2n) = a(n), a(2n+1) = a(n) + [n congruent to 3 mod 4]. - Ralf Stephan, Aug 21 2003

G.f.: 1/(1-x) * Sum_{k>=0} t^7(1-t)/(1-t^8), where t=x^2^k. - Ralf Stephan, Sep 08 2003

A030300 Runs have lengths 2^n, n >= 0.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Jean-Paul Delahaye

An example of a sequence with property that the fraction of 1's in the first n terms does not converge to a limit. - N. J. A. Sloane, Sep 24 2007
Image, under the coding sending a,d,e -> 1 and b,c -> 0, of the fixed point, starting with a, of the morphism a -> ab, b -> cd, c -> ee, d -> eb, e -> cc. - Jeffrey Shallit, May 14 2016
This sequence taken as digits of a base-b fraction is g(1/b) = Sum_{n>=1} a(n)/b^n = b/(b-1) * Sum_{k>=0} (-1)^k/b^(2^k) per the generating function below.  With initial 0, it is binary expansion .01001111 = A275975.  With initial 0 and digits 2*a(n), it is ternary expansion .02002222 = A160386.  These and in general g(1/b) for any integer b>=2 are among forms which Kempner showed are transcendental. - Kevin Ryde, Sep 07 2019

Antti Karttunen, Table of n, a(n) for n = 1..65537
Aubrey J. Kempner, On Transcendental Numbers, Transactions of the American Mathematical Society, volume 17, number 4, October 1916, pages 476-482.
Kevin Ryde, Plot of A079947(n)/n, illustrating proportion of 1s in the first n terms here does not converge (but oscillates with rises and falls by hyperbolas)
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index entries for sequences related to binary expansion of n
Index entries for characteristic functions

Cf. A030301. Partial sums give A079947.
Cf. A065359, A083905.
Characteristic function of A053738.

f0 := n->[seq(0,i=1..2^n)]; f1 := n->[seq(1,i=1..2^n)]; s := []; for i from 0 to 4 do s := [op(s), op(f1(2*i)), op(f0(2*i+1))]; od: A030300 := s;

nMax = 6; Table[1 - Mod[n, 2], {n, 0, nMax}, {2^n}] // Flatten (* Jean-François Alcover, Oct 20 2016 *)

a(n) = if(n, !(logint(n,2)%2)); /* Kevin Ryde, Aug 02 2019 */

def A030300(n): return n.bit_length()&1 # Chai Wah Wu, Jan 30 2023

a(n) = A065359(n) + A083905(n).
a(n) = (1/2)*(1+(-1)^floor(log_2(n))). - Benoit Cloitre, Feb 22 2003
G.f.: 1/(1-x) * Sum_{k>=0} (-1)^k*x^2^k. - Ralf Stephan, Jul 12 2003
a(n) = 1 - a(floor(n/2)). - Vladeta Jovovic, Aug 04 2003
a(n) = A115253(2n, n) mod 2. - Paul Barry, Jan 18 2006
a(n) = 1 - A030301(n). - Antti Karttunen, Oct 10 2017

cp's OEIS Frontend

A053985 Replace 2^k with (-2)^k in binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A080277 Partial sums of A038712.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A033264 Number of blocks of {1,0} in the binary expansion of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A062050 n-th chunk consists of the numbers 1, ..., 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A002516 Earliest sequence with a(a(n)) = 2n.

Views

Author

Keywords

Links

Crossrefs

Programs