A039004 -id:A039004 - cp's OEIS frontend

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

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

A372433 Binary weight (number of ones in binary expansion) of the n-th squarefree number.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 5, 2, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 4, 4, 5, 4, 4, 5, 5, 5, 2, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 3, 4, 4, 4, 5, 4, 5, 5, 5, 6, 3, 4, 4, 5, 4, 4, 5, 5, 5, 6, 4, 4, 5, 5, 6, 5, 6, 7, 2, 2, 3, 3, 3, 3, 3, 4, 4

Offset: 1

Gus Wiseman, May 04 2024

Harvey P. Dale, Table of n, a(n) for n = 1..1000
MathOverflow, Are there primes of every Hamming weight?
Wikipedia, Hamming weight.

Restriction of A000120 to A005117.
For prime instead of squarefree we have A014499, zeros A035103.
Counting zeros instead of ones gives A372472, cf. A023416, A372473.
For binary length instead of weight we have A372475.
A003714 lists numbers with no successive binary indices.
A030190 gives binary expansion, reversed A030308.
A048793 lists positions of ones in reversed binary expansion, sum A029931.
A145037 counts ones minus zeros in binary expansion, cf. A031443, A031444, A031448, A097110.
A371571 lists positions of zeros in binary expansion, sum A359359.
A371572 lists positions of ones in binary expansion, sum A230877.
A372515 lists positions of zeros in reversed binary expansion, sum A359400.
A372516 counts ones minus zeros in binary expansion of primes, cf. A177718, A177796, A372538, A372539.
Cf. A039004, A049093, A049094, A059015, A069010, A070939, A073642, A211997, A368494, A372474.

DigitCount[Select[Range[100],SquareFreeQ],2,1]
Total[IntegerDigits[#,2]]&/@Select[Range[200],SquareFreeQ] (* Harvey P. Dale, Feb 14 2025 *)

from math import isqrt
from sympy import mobius
def A372433(n):
    def f(x): return n+x-sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return int(m).bit_count() # Chai Wah Wu, Aug 02 2024

a(n) = A000120(A005117(n)).

a(n) + A372472(n) = A372475(n) = A070939(A005117(n)).

A359359 Sum of positions of zeros in the binary expansion of n, where positions are read starting with 1 from the left (big-endian).

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jan 03 2023

			The binary expansion of 100 is (1,1,0,0,1,0,0), with zeros at positions {3,4,6,7}, so a(100) = 20.

The number of zeros is A023416, partial sums A059015.
For positions of 1's we have A230877, reversed A029931.
The reversed version is A359400.
A003714 lists numbers with no successive binary indices.
A030190 gives binary expansion.
A039004 lists the positions of zeros in A345927.
Cf. A000120, A048793, A065359, A069010, A070939, A073642, A083652, A328594, A328595, A359402, A359495.

Table[Total[Join@@Position[IntegerDigits[n,2],0]],{n,0,100}]

a(n>0) = binomial(A029837(n)+1,2) - A230877(n).

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

A359400 Sum of positions of zeros in the reversed binary expansion of n, where positions in a sequence are read starting with 1 from the left.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jan 05 2023

			The reversed binary expansion of 100 is (0,0,1,0,0,1,1), with zeros at positions {1,2,4,5}, so a(100) = 12.

The number of zeros is A023416, partial sums A059015.
Row sums of A368494.
For positions of 1's we have A029931, non-reversed A230877.
The non-reversed version is A359359.
A003714 lists numbers with no successive binary indices.
A030190 gives binary expansion, reverse A030308.
A039004 lists the positions of zeros in A345927.
Cf. A000120, A048793, A069010, A070939, A073642, A328594, A328595, A344618, A359402, A359495.

long A359400(long n) {
  long result = 0, counter = 1;
  do {
    if (n % 2 == 0)
      result += counter;
    counter++;
    n /= 2;
  } while (n > 0);
  return result; } // Frank Hollstein, Jan 06 2023

Table[Total[Join@@Position[Reverse[IntegerDigits[n,2]],0]],{n,0,100}]

def a(n): return sum(i for i, bi in enumerate(bin(n)[:1:-1], 1) if bi=='0')
print([a(n) for n in range(78)]) # Michael S. Branicky, Jan 09 2023

a(n) = binomial(A029837(n)+1, 2) - A029931(n), for n>0.

A139351 Let the binary expansion of n be n = Sum_{k} 2^{r_k}, let e(n) be the number of r_k's that are even, o(n) the number that are odd; sequence gives e(n).

Original entry on oeis.org

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

Offset: 0

Nadia Heninger and N. J. A. Sloane, Jun 07 2008

e(n)+o(n) = A000120(n), the binary weight of n.

a(n) is also number of 1's and 3's in 4-ary representation of n. - Frank Ruskey, May 02 2009

			For n = 43 = 2^0 + 2^1 + 2^3 + 2^5, e(43)=1, o(43)=3.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Franklin T. Adams-Watters and Frank Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009), Article 09.5.6.
N. J. A. Sloane, Fortran program for this and related sequences.

Cf. A000120, A030308, A059841, A139352, A139353, A139354, A139355, A039004, A139370, A139371, A139372, A139373.

Fortran
```
See Sloane link.
```

import Data.List (unfoldr)
a139351 = sum . map (`mod` 2) .
   unfoldr (\x -> if x == 0 then Nothing else Just (x, x `div` 4))
-- Reinhard Zumkeller, Apr 22 2011

A139351 := proc(n)
    local a,bdgs,r;
    a := 0 ;
    bdgs := convert(n,base,2) ;
    for r from 1 to nops(bdgs) by 2 do
        if op(r,bdgs) = 1 then
            a := a+1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, Jul 21 2016

terms = 99; s = (1/(1-z))*Sum[z^(4^m)/(1+z^(4^m)), {m, 0, Log[4, terms] // Ceiling}] + O[z]^terms; CoefficientList[s, z] (* Jean-François Alcover, Jul 21 2017 *)
a[0] = 0; a[n_] := a[n] = a[Floor[n/4]] + If[OddQ[Mod[n, 4]], 1, 0]; Array[a, 100, 0] (* Amiram Eldar, Jul 18 2023 *)

a(n)=if(n>3,a(n\4))+n%2 \\ Charles R Greathouse IV, Apr 21 2016

a(n) + A139352(n) = A000120(n).
G.f.: (1/(1-z))*Sum_{m>=0} (z^(4^m)/(1+z^(4^m))). - Frank Ruskey, May 03 2009
Recurrence relation: a(0)=0, a(4m) = a(4m+2) = a(m), a(4m+1) = a(4m+3) = 1+a(m). - Frank Ruskey, May 11 2009
a(n) = Sum_{k} A030308(n,k)*A059841(k). - Philippe Deléham, Oct 14 2011

Typo in example fixed by Reinhard Zumkeller, Apr 22 2011

A139352 Let the binary expansion of n be n = Sum_{k} 2^{r_k}, let e(n) be the number of r_k's that are even, o(n) the number that are odd; sequence gives o(n).

Original entry on oeis.org

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

Offset: 0

Nadia Heninger and N. J. A. Sloane, Jun 07 2008

e(n) + o(n) = A000120(n), the binary weight of n.

a(n) is also the number of 2's and 3's in the 4-ary representation of n. - Frank Ruskey, May 02 2009

			For n = 43 = 2^0 + 2^1 + 2^3 + 2^5, e(43)=1, o(43)=3. [Typo fixed by _Reinhard Zumkeller_, Apr 22 2011]

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Franklin T. Adams-Watters and Frank Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009), Article 09.5.6.

Cf. A000035, A000120, A030308, A039004, A139351, A139353, A139354, A139355, A139370, A139371, A139372, A139373.

Fortran
```
c See link in A139351
```

import Data.List (unfoldr)
a139352 = sum . map ((`div` 2) . (`mod` 4)) .
   unfoldr (\x -> if x == 0 then Nothing else Just (x, x `div` 4))
-- Reinhard Zumkeller, Apr 22 2011

A139352 := proc(n)
    local a,bdgs,r;
    a := 0 ;
    bdgs := convert(n,base,2) ;
    for r from 2 to nops(bdgs) by 2 do
        if op(r,bdgs) = 1 then
            a := a+1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, Jul 21 2016

a[n_] := Count[Position[Reverse@IntegerDigits[n, 2], 1]-1, {_?OddQ}];
Table[a[n], {n, 0, 99}] (* Jean-François Alcover, Mar 04 2023 *)
a[0] = 0; a[n_] := a[n] = a[Floor[n/4]] + If[Mod[n, 4] > 1, 1, 0]; Array[a, 100, 0] (* Amiram Eldar, Jul 18 2023 *)

a(n)=if(n>3,a(n\4))+n%4\2 \\ Charles R Greathouse IV, Apr 21 2016

G.f.: (1/(1-z))*Sum_{m>=0} (z^(2*4^m)/(1+(2*4^m))). - Frank Ruskey, May 03 2009
Recurrence relation: a(0)=0, a(4m) = a(4m+1) = a(m), a(4m+2) = a(4m+3) = 1+a(m). - Frank Ruskey, May 11 2009
a(n) = Sum_{k} A030308(n,k)*A000035(k). - Philippe Deléham, Oct 14 2011

A372473 Least k such that the k-th squarefree number has exactly n zeros in its binary expansion.

Original entry on oeis.org

1, 2, 7, 12, 21, 40, 79, 158, 315, 1247, 1246, 2492, 4983, 9963, 19921, 39845, 79689, 159361, 318726, 637462, 1274919, 2549835, 5099651, 10199302, 20398665, 40797328, 81594627, 163189198, 326378285, 652756723, 1305513584, 2611027095, 5222054082, 10444108052

Offset: 0

Gus Wiseman, May 09 2024

Note that the data is not strictly increasing.

			The squarefree numbers A005117(a(n)) together with their binary expansions and binary indices begin:
     1:              1 ~ {1}
     2:             10 ~ {2}
    10:           1010 ~ {2,4}
    17:          10001 ~ {1,5}
    33:         100001 ~ {1,6}
    65:        1000001 ~ {1,7}
   129:       10000001 ~ {1,8}
   257:      100000001 ~ {1,9}
   514:     1000000010 ~ {2,10}
  2051:   100000000011 ~ {1,2,12}
  2049:   100000000001 ~ {1,12}
  4097:  1000000000001 ~ {1,13}
  8193: 10000000000001 ~ {1,14}

Chai Wah Wu, Table of n, a(n) for n = 0..57

Positions of first appearances in A372472.
For prime instead of squarefree we have A372474, A035103, A372517, A014499.
Counting bits (length) gives A372540, firsts of A372475, runs A077643.
Counting 1's (weight) instead of 0's gives A372541, firsts of A372433.
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A005117 lists squarefree numbers.
A030190 gives binary expansion, reversed A030308.
A048793 lists positions of ones in reversed binary expansion, sum A029931.
A070939 gives length of binary expansion (number of bits).
A371571 lists positions of zeros in binary expansion, sum A359359.
A371572 lists positions of ones in binary expansion, sum A230877.
A372515 lists positions of zeros in reversed binary expansion, sum A359400.
Cf. A035100, A039004, A049093, A049094, A059015, A069010, A145037, A211997.

nn=10000;
spnm[y_]:=Max@@NestWhile[Most,y,Union[#]!=Range[0,Max@@#]&];
dcs=DigitCount[Select[Range[nn],SquareFreeQ],2,0];
Table[Position[dcs,i][[1,1]],{i,0,spnm[dcs]}]

from math import isqrt
from itertools import count
from sympy import factorint, mobius
from sympy.utilities.iterables import multiset_permutations
def A372473(n):
    if n==0: return 1
    for l in count(n):
        m = 1<Chai Wah Wu, May 10 2024

a(23)-a(33) from Chai Wah Wu, May 10 2024

A205783 Complement of A206074, a coding of reducible polynomials over Q (with coefficients 0 or 1).

Original entry on oeis.org

1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 70, 72, 74, 75, 76, 78, 80, 82, 84, 85, 86, 88, 90, 92, 93, 94, 95, 96, 98, 99, 100

Offset: 1

Clark Kimberling, Feb 03 2012

nonn

Reducibility here refers to the field of rational numbers.

Except for its initial 3, is A039004 a subsequence of A205783?

			The reducible polynomials matching the first four terms:
1 = 1(base 2) matches 1
4 = 100(base 2) matches x^2
6 = 110(base 2) matches x^2 + x
8 = 1000(base 2) matches x^3
9 = 1001(base 2) matches x^3 + 1

Antti Karttunen, Table of n, a(n) for n = 1..21951

Cf. A206074 (complement), A255573 (left inverse).
After 1 a subsequence of A091212 (69 is the first term missing from here).
Cf. also permutations A260421 - A260426.

t = Table[IntegerDigits[n, 2], {n, 1, 850}];
b[n_] := Reverse[Table[x^k, {k, 0, n}]]
p[n_, x_] := t[[n]].b[-1 + Length[t[[n]]]]
Table[p[n, x], {n, 1, 15}]
u = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],
AppendTo[u, n]], {n, 300}];
u                          (* A206074 *)
Complement[Range[200], u]  (* A205783 *)
b[n_] := FromDigits[IntegerDigits[u, 2][[n]]]
Table[b[n], {n, 1, 40}]    (* A206073 *)

isA205783(n) = ((n > 0) && !polisirreducible(Pol(binary(n))));
n = 0; i = 0; while(n < 32768, n++; if(isA205783(n), i++; write("b205783.txt", i, " ", n)));
\\ Antti Karttunen, Jul 28 2015 after Joerg Arndt's code for A206074.

Other identities and observations. For all n >= 1:

A255573(a(n)) = n.

A372472 Number of zeros in the binary expansion of the n-th squarefree number.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, May 09 2024

			The 12th squarefree number is 17, with binary expansion (1,0,0,0,1), so a(12) = 3.

Positions of first appearances are A372473.
Restriction of A023416 to A005117.
For prime instead of squarefree we have A035103, ones A014499, bits A035100.
Counting 1's instead of 0's (so restrict A000120 to A005117) gives A372433.
For binary length we have A372475, run-lengths A077643.
A030190 gives binary expansion, reversed A030308.
A048793 lists positions of ones in reversed binary expansion, sum A029931.
A371571 lists positions of zeros in binary expansion, sum A359359.
A371572 lists positions of ones in binary expansion, sum A230877.
A372515 lists positions of zeros in reversed binary expansion, sum A359400.
Cf. A003714, A039004, A049093, A049094, A059015, A069010, A070939, A073642, A145037, A211997, A368494, A372474, A372516.

A372583 := proc(n)
    A023416(A005117(n)) ;
end proc:
seq(A372583(n),n=1..200) ; # R. J. Mathar, May 20 2024

DigitCount[Select[Range[100],SquareFreeQ],2,0]

a(n) = A023416(A005117(n)).

a(n) + A372433(n) = A070939(A005117(n)) = A372475(n).

cp's OEIS Frontend

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

A372433 Binary weight (number of ones in binary expansion) of the n-th squarefree number.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

A359359 Sum of positions of zeros in the binary expansion of n, where positions are read starting with 1 from the left (big-endian).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

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

A359400 Sum of positions of zeros in the reversed binary expansion of n, where positions in a sequence are read starting with 1 from the left.

Views

Author

Keywords

Examples

Crossrefs

Programs

C

Mathematica

Python

Formula

A139351 Let the binary expansion of n be n = Sum_{k} 2^{r_k}, let e(n) be the number of r_k's that are even, o(n) the number that are odd; sequence gives e(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Fortran

Haskell

Maple

Mathematica