A079944 -id:A079944 - cp's OEIS frontend

A001196 Double-bitters: only even length runs in binary expansion.

0, 3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255, 768, 771, 780, 783, 816, 819, 828, 831, 960, 963, 972, 975, 1008, 1011, 1020, 1023, 3072, 3075, 3084, 3087, 3120, 3123, 3132, 3135, 3264, 3267, 3276, 3279, 3312, 3315, 3324, 3327, 3840, 3843

Offset: 0

N. J. A. Sloane, based on an email from Bart la Bastide (bart(AT)xs4all.nl)

Numbers whose set of base 4 digits is {0,3}. - Ray Chandler, Aug 03 2004
n such that there exists a permutation p_1, ..., p_n of 1, ..., n such that i + p_i is a power of 4 for every i. - Ray Chandler, Aug 03 2004
The first 2^n terms of the sequence could be obtained using the Cantor-like process for the segment [0, 4^n-1]. E.g., for n=1 we have [0, {1, 2}, 3] such that numbers outside of braces are the first 2 terms of the sequence; for n=2 we have [0, {1, 2}, 3, {4, 5, 6, 7, 8, 9, 10, 11}, 12, {13, 14}, 15] such that the numbers outside of braces are the first 4 terms of the sequence, etc. - Vladimir Shevelev, Dec 17 2012
From Emeric Deutsch, Jan 26 2018: (Start)
Also, the indices of the compositions having only even parts. For the definition of the index of a composition, see A298644. For example, 195 is in the sequence since its binary form is 11000011 and the composition [2,4,2] has only even parts. 132 is not in the sequence since its binary form is 10000100 and the composition [1,4,1,2] also has odd parts.
The command c(n) from the Maple program yields the composition having index n. (End)
After the k-th step of generating the Koch snowflake curve, label the edges of the curve consecutively 0..3*4^k-1 starting from a vertex of the originating triangle. a(0), a(1), ... a(2^k-1) are the labels of the edges contained in one edge of the originating triangle. Add 4^k to each label to get the labels for the next edge of the triangle. Compare with A191108 in respect of the Sierpinski arrowhead curve. - Peter Munn, Aug 18 2019

Sean A. Irvine, Table of n, a(n) for n = 0..10000
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
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]
Eric Weisstein's World of Mathematics, Koch Snowflake.
Wikipedia, Koch snowflake.
Index entries for sequences related to binary expansion of n

3 times the Moser-de Bruijn sequence A000695.
Two digits in other bases: A005823, A097252-A097262.
Digit duplication in other bases: A338086, A338754.
Main diagonal of A054238.
Cf. A191108.

int a_next(int a_n) { int t = a_n << 1; return a_n ^ t ^ (t + 3); } /* Falk Hüffner, Jan 24 2022 */

a001196 n = if n == 0 then 0 else 4 * a001196 n' + 3 * b
            where (n',b) = divMod n 2
-- Reinhard Zumkeller, Feb 21 2014

Runs := proc (L) local j, r, i, k: j := 1: r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: A := {}: for n to 3350 do if type(product(1+c(n)[j], j = 1 .. nops(c(n))), odd) = true then A := `union`(A, {n}) else  end if end do: A; # most of the Maple  program is due to W. Edwin Clark. - Emeric Deutsch, Jan 26 2018
# second Maple program:
a:= proc(n) option remember;
     `if`(n<2, 3*n, 4*a(iquo(n, 2, 'r'))+3*r)
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Jan 24 2022

fQ[n_] := Union@ Mod[Length@# & /@ Split@ IntegerDigits[n, 2], 2] == {0}; Select[ Range@ 10000, fQ] (* Or *)
fQ[n_] := Union@ Join[IntegerDigits[n, 4], {0, 3}] == {0, 3}; Select[ Range@ 10000, fQ] (* Robert G. Wilson v, Dec 24 2012 *)

a(n) = 3*fromdigits(binary(n),4); \\ Kevin Ryde, Nov 07 2020

def inA001196(n):
    while n != 0:
        if n%4 == 1 or n%4 == 2:
            return 0
        n = n//4
    return 1
n, a = 0, 0
while n < 20:
    if inA001196(a):
        print(n,a)
        n = n+1
    a = a+1 # A.H.M. Smeets, Aug 19 2019

from itertools import groupby
def ok2lb(n):
  if n == 0: return True  # by convention
  return all(len(list(g))%2 == 0 for k, g in groupby(bin(n)[2:]))
print([i for i in range(3313) if ok2lb(i)]) # Michael S. Branicky, Jan 04 2021

def A001196(n): return 3*int(bin(n)[2:],4) # Chai Wah Wu, Aug 21 2023

a(2n) = 4*a(n), a(2n+1) = 4*a(n) + 3.
a(n) = 3 * A000695(n).
Sum_{n>=1} 1/a(n) = 0.628725478158702414849086504025451177643560169366348272891020450593453403709... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

A037861 (Number of 0's) - (number of 1's) in the base-2 representation of n.

Original entry on oeis.org

1, -1, 0, -2, 1, -1, -1, -3, 2, 0, 0, -2, 0, -2, -2, -4, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3, -3, -5, 4, 2, 2, 0, 2, 0, 0, -2, 2, 0, 0, -2, 0, -2, -2, -4, 2, 0, 0, -2, 0, -2, -2, -4, 0, -2, -2, -4, -2, -4, -4, -6, 5, 3, 3, 1, 3, 1, 1, -1, 3

Offset: 0

Clark Kimberling

-Sum_{n>=1} a(n)/((2*n)*(2*n+1)) = the "alternating Euler constant" log(4/Pi) = 0.24156... - (see A094640 and Sondow 2005, 2010).

a(A072600(n)) < 0; a(A072601(n)) <= 0; a(A031443(n)) = 0; a(A072602(n)) >= 0; a(A072603(n)) > 0; a(A031444(n)) = 1; a(A031448(n)) = -1; abs(a(A089648(n))) <= 1. - Reinhard Zumkeller, Feb 07 2015

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Jonathan Sondow, Double integrals for Euler's constant and ln(4/Pi) and an analog of Hadjicostas's formula, arXiv:math/0211148 [math.CA], 2002-2004; Amer. Math. Monthly 112 (2005), 61-65.
Jonathan Sondow, New Vacca-Type Rational Series for Euler's Constant and Its "Alternating" Analog ln(4/Pi), arXiv:math/0508042 [math.NT], 2005; Additive Number Theory, Festschrift In Honor of the Sixtieth Birthday of Melvyn B. Nathanson (D. Chudnovsky and G. Chudnovsky, eds.), Springer, 2010, pp. 331-340.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
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).
Index entries for sequences related to binary expansion of n

Cf. A031443 for n when a(n)=0, A053738 for n when a(n) odd, A053754 for n when a(n) even, A030300 for a(n+1) mod 2.
Cf. A066879, A094640, A110625, A145037.
Cf. A072600, A072601, A072602, A072603, A031444, A031448, A089648.
See A268289 for a recurrence based on this sequence.

a037861 n = a023416 n - a000120 n  -- Reinhard Zumkeller, Aug 01 2013

A037861:= proc(n) local L;
     L:= convert(n,base,2);
     numboccur(0,L) - numboccur(1,L)
end proc:
map(A037861, [$0..100]); # Robert Israel, Mar 08 2016

Table[Count[ IntegerDigits[n, 2], 0] - Count[IntegerDigits[n, 2], 1], {n, 0, 75}]

a(n) = if (n==0, 1, 1 + logint(n, 2) - 2*hammingweight(n)); \\ Michel Marcus, May 15 2020 and Jun 16 2020

def A037861(n):
    return 2*format(n,'b').count('0')-len(format(n,'b')) # Chai Wah Wu, Mar 07 2016

From Henry Bottomley, Oct 27 2000: (Start)
a(n) = A023416(n) - A000120(n) = A029837(n) - 2*A000120(n) = 2*A023416(n) - A029837(n).
a(2*n) = a(n) + 1; a(2*n + 1) = a(2*n) - 2 = a(n) - 1. (End)
G.f. satisfies A(x) = (1 + x)*A(x^2) - x*(2 + x)/(1 + x). - Franklin T. Adams-Watters, Dec 26 2006
a(n) = b(n) for n > 0 with b(0) = 0 and b(n) = b(floor(n/2)) + (-1)^(n mod 2). - Reinhard Zumkeller, Dec 31 2007
G.f.: 1 + (1/(1 - x))*Sum_{k>=0} x^(2^k)*(x^(2^k) - 1)/(1 + x^(2^k)). - Ilya Gutkovskiy, Apr 07 2018

A065359 Alternating bit sum for n: replace 2^k with (-1)^k in binary expansion of n.

Original entry on oeis.org

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

Offset: 0

Marc LeBrun, Oct 31 2001

Notation: (2)[n](-1)
From David W. Wilson and Ralf Stephan, Jan 09 2007: (Start)
a(n) is even iff n in A001969; a(n) is odd iff n in A000069.
a(n) == 0 (mod 3) iff n == 0 (mod 3).
a(n) == 0 (mod 6) iff (n == 0 (mod 3) and n/3 not in A036556).
a(n) == 3 (mod 6) iff (n == 0 (mod 3) and n/3 in A036556). (End)
a(n) = A030300(n) - A083905(n). - Ralf Stephan, Jul 12 2003
From Robert G. Wilson v, Feb 15 2011: (Start)
First occurrence of k and -k: 0, 1, 2, 5, 10, 21, 42, 85, ..., (A000975); i.e., first 0 occurs for 0, first 1 occurs for 1, first -1 occurs at 2, first 2 occurs for 5, etc.;
  a(n)=-3 only if n mod 3 = 0,
  a(n)=-2 only if n mod 3 = 1,
  a(n)=-1 only if n mod 3 = 2,
  a(n)= 0 only if n mod 3 = 0,
  a(n)= 1 only if n mod 3 = 1,
  a(n)= 2 only if n mod 3 = 2,
  a(n)= 3 only if n mod 3 = 0, ..., . (End)
a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. - Philippe Deléham, Oct 20 2011
In the Koch curve, number the segments starting with n=0 for the first segment. The net direction (i.e., the sum of the preceding turns) of segment n is a(n)*60 degrees. This is since in the curve each base-4 digit 0,1,2,3 of n is a sub-curve directed respectively 0, +60, -60, 0 degrees, which is the net 0,+1,-1,0 of two bits in the sum here. - Kevin Ryde, Jan 24 2020

			Alternating bit sum for 11 = 1011 in binary is 1 - 1 + 0 - 1 = -1, so a(11) = -1.

Antti Karttunen, Table of n, a(n) for n = 0..65535 (terms 0..1000 from Harry J. Smith)
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197. [Preprint.]
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
H.-K. 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.
H.-K. 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.
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, p. 45.
Helge von Koch, Une Méthode Géométrique Élémentaire pour l'Étude de Certaines Questions de la Théorie des Courbes Planes, Acta Arithmetica, volume 30, 1906, pages 145-174.
William Paulsen, wpaulsen(AT)csm.astate.edu, Partitioning the [prime] maze
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A005536 (partial sums), A056832 (abs first differences), A010060 (mod 2), A039004 (indices of 0's).
Cf. A000120, A065360, A065081, A019565, A195017.
Cf. also A004718.
Cf. analogous sequences for bases 3-10: A065368, A346688, A346689, A346690, A346691, A346731, A346732, A055017 and also A373605 (for primorial base).

a065359 0 = 0
a065359 n = - a065359 n' + m where (n', m) = divMod n 2
-- Reinhard Zumkeller, Mar 20 2015

A065359 := proc(n) local dgs ; dgs := convert(n,base,2) ; add( -op(i,dgs)*(-1)^i,i=1..nops(dgs)) ; end proc: # R. J. Mathar, Feb 04 2011

f[0]=0; f[n_] := Plus @@ (-(-1)^Range[ Floor[ Log2@ n + 1]] Reverse@ IntegerDigits[n, 2]); Array[ f, 107, 0]

a(n) = my(s=0, u=1); for(k=0,#binary(n)-1,s+=bittest(n,k)*u;u=-u);s /* Washington Bomfim, Jan 18 2011 */

a(n) = my(b=binary(n)); b*[(-1)^k|k<-[-#b+1..0]]~; \\ Ruud H.G. van Tol, Oct 16 2023

a(n) = if(n==0, 0, 2*hammingweight(bitand(n, ((4<<(2*logint(n,4)))-1)/3)) - hammingweight(n)) \\ Andrew Howroyd, Dec 14 2024

def a(n):
    return sum((-1)**k for k, bi in enumerate(bin(n)[2:][::-1]) if bi=='1')
print([a(n) for n in range(107)]) # Michael S. Branicky, Jul 13 2021

from sympy.ntheory import digits
def A065359(n): return sum((0,1,-1,0)[i] for i in digits(n,4)[1:]) # Chai Wah Wu, Jul 19 2024

G.f.: (1/(1-x)) * Sum_{k>=0} (-1)^k*x^2^k/(1+x^2^k). - Ralf Stephan, Mar 07 2003
a(0) = 0, a(2n) = -a(n), a(2n+1) = 1-a(n). - Ralf Stephan, Mar 07 2003
a(n) = Sum_{k>=0} A030308(n,k)*(-1)^k. - Philippe Deléham, Oct 20 2011
a(n) = -a(floor(n/2)) + n mod 2. - Reinhard Zumkeller, Mar 20 2015
a(n) = A139351(n) - A139352(n). - Kevin Ryde, Jan 24 2020
G.f. A(x) satisfies: A(x) = x / (1 - x^2) - (1 + x) * A(x^2). - Ilya Gutkovskiy, Jul 28 2021
a(n) = A195017(A019565(n)). - Antti Karttunen, Jun 19 2024

More terms from Ralf Stephan, Jul 12 2003

A014081 a(n) is the number of occurrences of '11' in the binary expansion of n.

Original entry on oeis.org

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

Offset: 0

Simon Plouffe

a(n) takes the value k for the first time at n = 2^(k+1)-1. Cf. A000225. - Robert G. Wilson v, Apr 02 2009

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

			The binary expansion of 15 is 1111, which contains three occurrences of 11, so a(15)=3.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
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.
John Brillhart and L. Carlitz, Note on the Shapiro Polynomials, Proceedings of the American Mathematical Society, volume 25, number 1, May 1970, pages 114-118 (see A001782 for a scanned copy), with a(n) = exponent in theorem 4.
Helmut Prodinger, Generalizing the sum of digits function, SIAM J. Algebraic Discrete Methods, Vol. 3, No. 1 (1982), pp. 35-42. MR0644955 (83f:10009). [See B_2(11,n) on p. 35. - _N. J. A. Sloane_, Apr 06 2014]
Michel Rigo and Manon Stipulanti, Revisiting regular sequences in light of rational base numeration systems, arXiv:2103.16966 [cs.FL], 2021. Mentions this sequence.
Bartosz Sobolewski and Lukas Spiegelhofer, Block occurrences in the binary expansion, arXiv:2309.00142 [math.NT], 2023.
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.
Eric Weisstein's World of Mathematics, Rudin-Shapiro Sequence.
Index entries for sequences related to binary expansion of n

Cf. A014082, A033264, A037800, A056973, A000225, A213629, A000120, A069010, A100046.
First differences give A245194.
A245195 gives 2^a(n).

import Data.Bits ((.&.))
a014081 n = a000120 (n .&. div n 2)  -- Reinhard Zumkeller, Jan 23 2012

# To count occurrences of 11..1 (k times) in binary expansion of v:
cn := proc(v, k) local n, s, nn, i, j, som, kk;
som := 0;
kk := convert(cat(seq(1, j = 1 .. k)),string);
n := convert(v, binary);
s := convert(n, string);
nn := length(s);
for i to nn - k + 1 do
if substring(s, i .. i + k - 1) = kk then som := som + 1 fi od;
som; end; # This program no longer worked. Corrected by N. J. A. Sloane, Apr 06 2014.
[seq(cn(n,2),n=0..300)];
# Alternative:
A014081 := proc(n) option remember;
  if n mod 4 <= 1 then procname(floor(n/4))
elif n mod 4 = 2 then procname(n/2)
else 1 + procname((n-1)/2)
fi
end proc:
A014081(0):= 0:
map(A014081, [$0..1000]); # Robert Israel, Sep 04 2015

f[n_] := Count[ Partition[ IntegerDigits[n, 2], 2, 1], {1, 1}]; Table[ f@n, {n, 0, 104}] (* Robert G. Wilson v, Apr 02 2009 *)
Table[SequenceCount[IntegerDigits[n,2],{1,1},Overlaps->True],{n,0,120}] (* Harvey P. Dale, Jun 06 2022 *)

A014081(n)=sum(i=0,#binary(n)-2,bitand(n>>i,3)==3)  \\ M. F. Hasler, Jun 06 2012

a(n) = hammingweight(bitand(n, n>>1)) ;
vector(105, i, a(i-1))  \\ Gheorghe Coserea, Aug 30 2015

def a(n): return sum([((n>>i)&3==3) for i in range(len(bin(n)[2:]) - 1)]) # Indranil Ghosh, Jun 03 2017

from re import split
def A014081(n): return sum(len(d)-1 for d in split('0+', bin(n)[2:]) if d != '') # Chai Wah Wu, Feb 04 2022

a(4n) = a(4n+1) = a(n), a(4n+2) = a(2n+1), a(4n+3) = a(2n+1) + 1. - Ralf Stephan, Aug 21 2003
G.f.: (1/(1-x)) * Sum_{k>=0} t^3/((1+t)*(1+t^2)), where t = x^(2^k). - Ralf Stephan, Sep 10 2003
a(n) = A000120(n) - A069010(n). - Ralf Stephan, Sep 10 2003
Sum_{n>=1} A014081(n)/(n*(n+1)) = A100046 (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

A038554 Derivative of n: write n in binary, replace each pair of adjacent bits with their mod 2 sum (a(0)=a(1)=0 by convention). Also n XOR (n shift 1).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

From Antti Karttunen: this is also a version of A003188: a(n) = A003188(n) - 2^floor(log_2(A003188(n))), that is, the corresponding Gray code expansion, but with highest 1-bit turned off. Also a(n) = A003188(n) - 2^floor(log_2(n)).
From John W. Layman: {a(n)} is a self-similar sequence under Kimberling's "upper-trimming" operation.
a(A000225(n)) = 0; a(A062289(n)) > 0; a(A038558(n)) = n. - Reinhard Zumkeller, Mar 06 2013

			If n = 18 = 10010_2, derivative is (1+0)(0+0)(0+1)(1+0) = 1011_2, so a(18)=11.

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

T. D. Noe, Table of n, a(n) for n = 0..4096
Clark Kimberling, Fractal sequences.
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.
J. W. Layman, View the fractal-like graph of a(n) vs. n.
Ralf Stephan, Some divide-and-conquer sequences ....
Ralf Stephan, Table of generating functions.

Cf. A038570, A038571. See A003415 for another definition of the derivative of a number.
Cf. A038556 (rotates n instead of shifting).
Cf. A000035.
Cf. A030308.

import Data.Bits (xor)
a038554 n = foldr (\d v -> v * 2 + d) 0 $ zipWith xor bs $ tail bs
   where bs = a030308_row n
-- Reinhard Zumkeller, May 26 2013, Mar 06 2013

A038554 := proc(n) local i,b,ans; ans := 0; b := convert(n,base,2); for i to nops(b)-1 do ans := ans+((b[ i ]+b[ i+1 ]) mod 2)*2^(i-1); od; RETURN(ans); end; [ seq(A038554(i),i=0..100) ];

a[0] = a[1] = 0; a[n_ /; Mod[n, 4] == 0] := a[n] = 2*a[n/2]; a[n_ /; Mod[n, 4] == 1] := a[n] =  2*a[(n-1)/2] + 1; a[n_ /; Mod[n, 4] == 2] := a[n] = 2*a[n/2] + 1; a[n_ /; Mod[n, 4] == 3] := a[n] = 2*a[(n-1)/2]; Table[a[n], {n, 0, 81}] (* Jean-François Alcover, Jul 13 2012, after Ralf Stephan *)
Table[FromDigits[Mod[Total[#],2]&/@Partition[IntegerDigits[n,2],2,1],2],{n,0,90}] (* Harvey P. Dale, Oct 27 2015 *)

a003188(n)=bitxor(n, n>>1);
a(n)=if(n<2, 0, a003188(n) - 2^logint(a003188(n), 2)); \\ Indranil Ghosh, Apr 26 2017

import math
def a003188(n): return n^(n>>1)
def a(n): return 0 if n<2 else a003188(n) - 2**int(math.floor(math.log(a003188(n), 2))) # Indranil Ghosh, Apr 26 2017

If 2*2^k <= n < 3*2^k then a(n) = 2^k + a(2^(k+2)-n-1); if 3*2^k <= n < 4*2^k then a(n) = a(n-2^(k+1)). - Henry Bottomley, May 11 2000
G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*(t^4-t^3+t^2)/(1+t^2), t=x^2^k. - Ralf Stephan, Sep 10 2003
a(0)=0, a(2n) = 2*a(n) + [n odd], a(2n+1) = 2*a(n) + [n>0 even]. - Ralf Stephan, Oct 20 2003
a(0) = a(1) = 0, a(4n) = 2*a(2n), a(4n+2) = 2*a(2n+1)+1, a(4n+1) = 2*a(2n)+1, a(4n+3) = 2*a(2n+1). Proof by Nikolaus Meyberg following a conjecture by Ralf Stephan.

More terms from Erich Friedman

A004754 Numbers n whose binary expansion starts 10.

Original entry on oeis.org

2, 4, 5, 8, 9, 10, 11, 16, 17, 18, 19, 20, 21, 22, 23, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 128, 129, 130, 131

Offset: 1

N. J. A. Sloane

A000120(a(n)) = A000120(n); A023416(a(n-1)) = A008687(n) for n > 1. - Reinhard Zumkeller, Dec 04 2015

			10 in binary is 1010, so 10 is in sequence.

T. D. Noe, Table of n, a(n) for n = 1..1023
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to binary expansion of n

Cf. A123001 (binary version), A004755 (11), A004756 (100), A004757 (101), A004758 (110), A004759 (111).
Cf. A004760, A053644, A062050, A076877.
Apart from initial terms, same as A004761.
Cf. A000120, A023416, A008687.

import Data.List (transpose)
a004754 n = a004754_list !! (n-1)
a004754_list = 2 : concat (transpose [zs, map (+ 1) zs])
                   where zs = map (* 2) a004754_list
-- Reinhard Zumkeller, Dec 04 2015

w = {1, 0}; Select[Range[2, 131], If[# < 2^(Length@ w - 1), True, Take[IntegerDigits[#, 2], Length@ w] == w] &] (* Michael De Vlieger, Aug 08 2016 *)

PARI
```
a(n)=n+2^floor(log(n)/log(2))
```

is(n)=n>1 && !binary(n)[2] \\ Charles R Greathouse IV, Sep 23 2012

def A004754(n): return n+(1<Chai Wah Wu, Jul 13 2022

a(2n) = 2a(n), a(2n+1) = 2a(n) + 1 + [n==0].
a(n) = n + 2^floor(log_2(n)) = n + A053644(n).
a(2^m+k) = 2^(m+1) + k, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 08 2016

Edited by Ralf Stephan, Oct 12 2003

A057300 Binary counter with odd/even bit positions swapped; base-4 counter with 1's replaced by 2's and vice versa.

Original entry on oeis.org

0, 2, 1, 3, 8, 10, 9, 11, 4, 6, 5, 7, 12, 14, 13, 15, 32, 34, 33, 35, 40, 42, 41, 43, 36, 38, 37, 39, 44, 46, 45, 47, 16, 18, 17, 19, 24, 26, 25, 27, 20, 22, 21, 23, 28, 30, 29, 31, 48, 50, 49, 51, 56, 58, 57, 59, 52, 54, 53, 55, 60, 62, 61, 63, 128, 130, 129, 131, 136, 138

Offset: 0

Marc LeBrun, Aug 24 2000

A self-inverse permutation of the integers.
a(n) = n if and only if n can be written as 3*Sum_{k>=0} d_i*4^k, where d_i is either 0 or 1. - Jon Perry, Oct 06 2012
From Veselin Jungic, Mar 03 2015: (Start)
In 1988 A. F. Sidorenko, see the Sidorenko reference, used this sequence as an example of a permutation of the set of positive integers with the property that if positive integers i, j, and k form a 3-term arithmetic progression then the corresponding terms a(i), a(j), and a(k) do not form an arithmetic progression.
In the terminology introduced in the Brown, Jungic, and Poelstra reference, the sequence does not contain "double 3-term arithmetic progressions".
It is not difficult to check that this sequence is with unbounded gaps, i.e., for any positive number m there is a natural number n such that a(n+1) - a(n) > m.
It is an open question if every sequence of integers with bounded gaps must contain a double 3-term arithmetic progression. This problem is equivalent to the well known additive square problem in infinite words: Is it true that any infinite word with a finite set of integers as its alphabet contains two consecutive blocks of the same length and the same sum? For more details about the additive square problem in infinite words see the following references: Ardal, et al.; Brown and Freedman; Freedman; Grytczuk; Halbeisen and Hungerbuhler, and Pirillo and Varricchio.
The sequence was attributed to Sidorenko in P. Hegarty's paper "Permutations avoiding arithmetic patterns". In his paper Hegarty characterized the countably infinite abelian groups for which there exists a bijection mapping arithmetic progressions to non-arithmetic progressions. This was further generalized by Jungic and Sahasrabudhe. (End)

			a(31) = a(4*7+3) = 4*a(7) + a(3) = 4*11 + 3 = 47.

Paul Tek, Table of n, a(n) for n = 0..16383
H. Ardal, T. Brown, V. Jungic, and J. Sahasrabudhe, On Additive and Abelian Complexity in Infinite Words, INTEGERS: Elect. J. Combin. Number Theory, 12 (2012), A21.
T. C. Brown and A. R. Freedman, Arithmetic progressions in lacunary sets, Rocky Mountain J. Math., 17 Number 3 (1987), 587-596. doi:10.1216/RMJ-1987-17-3-587
T. Brown, V. Jungic, and A. Poelstra, On 3-term double arithmetic progressions, INTEGERS: Elect. J. Combin. Number Theory, 14 (2014), A43.
A. R. Freedman, Sequences on sets of four numbers, INTEGERS: Elect. J. Combin. Number Theory, 16 (2016), A33.
J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
L. Halbeisen and N. Hungerbuhler, An application of van der Waerden's theorem in additive number theory, INTEGERS: Elect. J. Combin. Number Theory, 0 (2000), A7.
Peter Hegarty, Permutations avoiding arithmetic patterns, The Electronic Journal of Combinatorics, 11 (2004), #R39.
V. Jungic and J. Sahasrabudhe, Permutations destroying arithmetic structure, The Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.5.
G. Pirillo and S. Varricchio, On uniformly repetitive semigroups, Semigroup Forum, 49 (1994), 125-129.
A. F. Sidorenko, An infinite permutation without arithmetic progressions, Discrete Math., 69 (1988), 211.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers

Sequences used in definitions of this sequence: A000695, A059905, A059906.
Sequences with similar definitions: A057301, A126006, A126007, A126008, A163241, A163327.
A003986, A003987, A004198, A053985, A054240 are used to express relationships between sequence terms.

#include 
uint32_t a(uint32_t n) { return ((n & 0x55555555) << 1) | ((n & 0xaaaaaaaa) >> 1); } /* Falk Hüffner, Jan 23 2022 */

a:= proc(n) option remember; `if`(n=0, 0,
      a(iquo(n, 4, 'r'))*4+[0, 2, 1, 3][r+1])
    end:
seq(a(n), n=0..69);  # Alois P. Heinz, Jan 25 2022

Table[FromDigits[IntegerDigits[n,4]/.{1->2,2->1},4],{n,0,70}] (* Harvey P. Dale, Aug 24 2017 *)

A057300(n) = { my(t=1,s=0); while(n>0, if(1==(n%4),n++,if(2==(n%4),n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); }; \\ Antti Karttunen, Apr 14 2018

Conjecture: a(2*n) = -2*a(n) + 5*n, a(2*n+1) = -2*a(n) + 5*n + 2. - Ralf Stephan, Oct 11 2003
a(4n+k) = 4a(n) + a(k), 0 <= k <= 3. - Jon Perry, Oct 06 2012
a(n) = A000695(A059906(n)) + 2*A000695(A059905(n)). - Antti Karttunen, Apr 14 2018
From Peter Munn, Dec 10 2019: (Start)
a(a(n)) = n.
a(A000695(m) + 2*A000695(n)) = 2*A000695(m) + A000695(n).
a(n OR k) = a(n) OR a(k), where OR is bitwise-or (A003986).
a(n XOR k) = a(n) XOR a(k), where XOR is bitwise exclusive-or (A003987).
a(n AND k) = a(n) AND a(k), where AND is bitwise-and (A004198).
a(A054240(n,k)) = A054240(a(n), a(k)). (End)
a(n) = 5*n/4 - 3*A053985(2*n)/8. - Alan Michael Gómez Calderón, May 20 2025

A003817 a(0) = 0, a(n) = a(n-1) OR n.

Original entry on oeis.org

0, 1, 3, 3, 7, 7, 7, 7, 15, 15, 15, 15, 15, 15, 15, 15, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63

Offset: 0

Marc LeBrun

Also, 0+1+2+...+n in lunar arithmetic in base 2 written in base 10. - N. J. A. Sloane, Oct 02 2010

For n>0: replace all 0's with 1's in binary representation of n. - Reinhard Zumkeller, Jul 14 2003

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 [From _Reinhard Zumkeller_, Nov 14 2009]
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2011. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
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.
Reinhard Zumkeller, Logical Convolutions
Index entries for sequences related to dismal (or lunar) arithmetic

This is Guy Steele's sequence GS(6, 6) (see A135416).
Cf. A000004, A142149, A086099, A142150, A142151, A001477, A062383.
Cf. A167832, A167878. - Reinhard Zumkeller, Nov 14 2009
Cf. A179526; subsequence of A007448. - Reinhard Zumkeller, Jul 18 2010
Cf. A265705.

import Data.Bits ((.|.))
a003817 n = if n == 0 then 0 else 2 * a053644 n - 1
a003817_list = scanl (.|.) 0 [1..] :: [Integer]
-- Reinhard Zumkeller, Dec 08 2012, Jan 15 2012

A003817 := n -> n + Bits:-Nand(n, n):
seq(A003817(n), n=0..61); # Peter Luschny, Sep 23 2019

a[0] = 0; a[n_] := a[n] = BitOr[ a[n-1], n]; Table[a[n], {n, 0, 61}] (* Jean-François Alcover, Dec 19 2011 *)
nxt[{n_,a_}]:={n+1,BitOr[a,n+1]}; Transpose[NestList[nxt,{0,0},70]] [[2]] (* Harvey P. Dale, May 06 2016 *)
2^BitLength[Range[0,100]]-1 (* Paolo Xausa, Feb 08 2024 *)

a(n)=1<<(log(2*n+1)\log(2))-1 \\ Charles R Greathouse IV, Dec 08 2011

def a(n): return 0 if n==0 else 1 + 2*a(int(n/2)) # Indranil Ghosh, Apr 28 2017

def A003817(n): return (1<Chai Wah Wu, Jul 17 2024

a(n) = a(n-1) + n*(1-floor(a(n-1)/n)). If 2^(k-1) <= n < 2^k, a(n) = 2^k - 1. - Benoit Cloitre, Aug 25 2002
a(n) = 1 + 2*a(floor(n/2)) for n > 0. - Benoit Cloitre, Apr 04 2003
G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*x^2^k. - Ralf Stephan, Apr 18 2003
a(n) = 2*A053644(n)-1 = A092323(n) + A053644(n). - Reinhard Zumkeller, Feb 15 2004; corrected by Anthony Browne, Jun 26 2016
a(n) = OR{k OR (n-k): 0<=k<=n}. - Reinhard Zumkeller, Jul 15 2008
For n>0: a(n+1) = A035327(n) + n = A035327(n) XOR n. - Reinhard Zumkeller, Nov 14 2009
A092323(n+1) = floor(a(n)/2). - Reinhard Zumkeller, Jul 18 2010
a(n) = A265705(n,0) = A265705(n,n). - Reinhard Zumkeller, Dec 15 2015
a(n) = A062383(n) - 1.
G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 - x). - Ilya Gutkovskiy, Aug 31 2019
a(n) >= A175039(n) - Austin Shapiro, Dec 29 2022

A001855 Sorting numbers: maximal number of comparisons for sorting n elements by binary insertion.

Original entry on oeis.org

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, 45, 49, 54, 59, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 135, 141, 147, 153, 159, 165, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255, 261, 267, 273, 279, 285

Offset: 1

N. J. A. Sloane

Equals n-1 times the expected number of probes for a successful binary search in a size n-1 list.
Piecewise linear: breakpoints at powers of 2 with values given by A000337.
a(n) is the number of digits in the binary representation of all the numbers 1 to n-1. - Hieronymus Fischer, Dec 05 2006
It is also coincidentally the maximum number of comparisons for merge sort. - Li-yao Xia, Nov 18 2015

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.3.1, Eq. (3); Sect. 6.2.1 (4).
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 48.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989.

Paolo Xausa, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, Universal layered permutations, arXiv:1710.04240 [math.CO], (2017).
Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, Universal Layered Permutations, Electronic Journal of Combinatorics. Volume 25(3), 2018, #P3.23.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
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.
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, p. 36.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
D. Knuth, Letter to N. J. A. Sloane, date unknown
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 5.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Sorting.
Index entries for sequences related to sorting

Partial sums of A029837.

Cf. A003071, A000337, A030190, A030308, A061168, A123753, A373709.

import Data.List (transpose)
a001855 n = a001855_list !! n
a001855_list = 0 : zipWith (+) [1..] (zipWith (+) hs $ tail hs) where
   hs = concat $ transpose [a001855_list, a001855_list]
-- Reinhard Zumkeller, Jun 03 2013

a := proc(n) local k; k := ilog2(n) + 1; 1 + n*k - 2^k end; # N. J. A. Sloane, Dec 01 2007 [edited by Peter Luschny, Nov 30 2017]

a[n_?EvenQ] := a[n] = n + 2a[n/2] - 1; a[n_?OddQ] := a[n] = n + a[(n+1)/2] + a[(n-1)/2] - 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 1, 58}] (* Jean-François Alcover, Nov 23 2011, after Pari *)
a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2] + 1;
Table[a[n], {n, 1, 58}] (* Peter Luschny, Dec 02 2017 *)
Accumulate[BitLength[Range[0, 100]]] (* Paolo Xausa, Sep 30 2024 *)

PARI
```
a(n)=if(n<2,0,n-1+a(n\2)+a((n+1)\2))
```

a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+1)

def A001855(n):
    s, i, z = 0, n-1, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A001855(n) for n in range(1, 59)]) # Peter Luschny, Nov 30 2017

def A001855(n): return n*(m:=(n-1).bit_length())-(1<Chai Wah Wu, Mar 29 2023

Let n = 2^(k-1) + g, 0 <= g <= 2^(k-1); then a(n) = 1 + n*k - 2^k. - N. J. A. Sloane, Dec 01 2007
a(n) = Sum_{k=1..n}ceiling(log_2 k) = n*ceiling(log_2 n) - 2^ceiling(log_2(n)) + 1.
a(n) = a(floor(n/2)) + a(ceiling(n/2)) + n - 1.
G.f.: x/(1-x)^2 * Sum_{k>=0} x^2^k. - Ralf Stephan, Apr 13 2002
a(1)=0, for n>1, a(n) = ceiling(n*a(n-1)/(n-1)+1). - Benoit Cloitre, Apr 26 2003
a(n) = n-1 + min { a(k)+a(n-k) : 1 <= k <= n-1 }, cf. A003314. - Vladeta Jovovic, Aug 15 2004
a(n) = A061168(n-1) + n - 1 for n>1. - Hieronymus Fischer, Dec 05 2006
a(n) = A123753(n-1) - n. - Peter Luschny, Nov 30 2017

Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu)

A004755 Binary expansion starts 11.

Original entry on oeis.org

3, 6, 7, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122

Offset: 1

N. J. A. Sloane

a(n) is the smallest value > a(n-1) (or > 1 for n=1) for which A001511(a(n)) = A001511(n). - Franklin T. Adams-Watters, Oct 23 2006

			12 in binary is 1100, so 12 is in the sequence.

Kenny Lau, Table of n, a(n) for n = 1..16383 (first 1023 terms from T. D. Noe)
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Equals union of A079946 and A080565.
Cf. A004754 (10), A004756 (100), A004757 (101), A004758 (110), A004759 (111).
Cf. A004760, A053644, A062050, A076877.

import Data.List (transpose)
a004755 n = a004755_list !! (n-1)
a004755_list = 3 : concat (transpose [zs, map (+ 1) zs])
                   where zs = map (* 2) a004755_list
-- Reinhard Zumkeller, Dec 04 2015

a:= proc(n) n+2*2^floor(log(n)/log(2)) end: seq(a(n),n=1..60); # Muniru A Asiru, Oct 16 2018

Flatten[Table[FromDigits[#,2]&/@(Join[{1,1},#]&/@Tuples[{0,1},n]),{n,0,5}]] (* Harvey P. Dale, Feb 05 2015 *)

PARI
```
a(n)=n+2*2^floor(log(n)/log(2))
```

is(n)=n>2 && binary(n)[2] \\ Charles R Greathouse IV, Sep 23 2012

f = open('b004755.txt', 'w')
lo = 3
hi = 4
i = 1
while i<16384:
    for x in range(lo,hi):
        f.write(str(i)+" "+str(x)+"\n")
        i += 1
    lo <<= 1
    hi <<= 1
# Kenny Lau, Jul 05 2016

def A004755(n): return n+(1<Chai Wah Wu, Jul 13 2022

a(2n) = 2*a(n), a(2n+1) = 2*a(n) + 1 + 2*[n==0].
a(n) = n + 2 * 2^floor(log_2(n)) = A004754(n) + A053644(n).
a(n) = 2n + A080079(n). - Benoit Cloitre, Feb 22 2003
G.f.: (1/(1+x)) * (1 + Sum_{k>=0, t=x^2^k} 2^k*(2t+t^2)/(1+t)).
a(n) = n + 2^(floor(log_2(n)) + 1) = n + A062383(n). - Franklin T. Adams-Watters, Oct 23 2006
a(2^m+k) = 2^(m+1) + 2^m + k, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 08 2016

Edited by Ralf Stephan, Oct 12 2003

cp's OEIS Frontend

A001196 Double-bitters: only even length runs in binary expansion.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

Python

Python

Python

Formula

A037861 (Number of 0's) - (number of 1's) in the base-2 representation of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A065359 Alternating bit sum for n: replace 2^k with (-1)^k in binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

Extensions

A014081 a(n) is the number of occurrences of '11' in the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A038554 Derivative of n: write n in binary, replace each pair of adjacent bits with their mod 2 sum (a(0)=a(1)=0 by convention). Also n XOR (n shift 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple