A073642 -id:A073642 - cp's OEIS frontend

A087136 Smallest positive number m such that A073642(m)=n.

1, 2, 4, 6, 10, 12, 14, 22, 26, 28, 30, 46, 54, 58, 60, 62, 94, 110, 118, 122, 124, 126, 190, 222, 238, 246, 250, 252, 254, 382, 446, 478, 494, 502, 506, 508, 510, 766, 894, 958, 990, 1006, 1014, 1018, 1020, 1022, 1534, 1790, 1918, 1982, 2014, 2030, 2038

Offset: 0

Reinhard Zumkeller, Aug 17 2003

nonn

A073642(a(n))=n and A073642(k)

A073642(A000051(n))=n and A073642(k)>n for k>A000051(n).

Cf. A087135.

i = 1; Table[While[Total[Flatten[Position[Rest[Reverse[IntegerDigits[i, 2]]], 1]]] != k, i++]; i, {k, 0, 52}] (* Jayanta Basu, Aug 12 2013 *)

"Positive" added to definition by N. J. A. Sloane, Aug 25 2019

A060960 Duplicate of A073642.

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 4, 4, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 10, 10, 5, 5, 6

Offset: 1

dead

A029931 If 2n = Sum 2^e_i, a(n) = Sum e_i.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Write n in base 2, n = sum b(i)*2^(i-1), then a(n) = sum b(i)*i. - Benoit Cloitre, Jun 09 2002
May be regarded as a triangular array read by rows, giving weighted sum of compositions in standard order. The standard order of compositions is given by A066099. - Franklin T. Adams-Watters, Nov 06 2006
Sum of all positive integer roots m_i of polynomial {m,k} - see link [Shevelev]; see also A264613. - Vladimir Shevelev, Dec 13 2015
Also the sum of binary indices of n, where a binary index of n (A048793) is any position of a 1 in its reversed binary expansion. For example, the binary indices of 11 are {1,2,4}, so a(11) = 7. - Gus Wiseman, May 22 2024

			14 = 8+4+2 so a(7) = 3+2+1 = 6.
Composition number 11 is 2,1,1; 1*2+2*1+3*1 = 7, so a(11) = 7.
The triangle starts:
  0
  1
  2 3
  3 4 5 6
The reversed binary expansion of 18 is (0,1,0,0,1) with 1's at positions {2,5}, so a(18) = 2 + 5 = 7. - _Gus Wiseman_, Jul 22 2019

T. D. Noe, Table of n, a(n) for n = 0..1023
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 10. See also DOI.
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. (See Section 3, Theorem 21 and Section 8, Theorem 50)

Other sequences that are built by replacing 2^k in the binary representation with other numbers: A022290 (Fibonacci), A059590 (factorials), A073642, A089625 (primes), A116549, A326031.
Cf. A001793 (row sums), A011782 (row lengths), A059867, A066099, A124757.
Row sums of A048793 and A272020.
Cf. A035327, A056239, A291166, A295235, A326669, A326674, A326675, A326699/A326700.
Contains exactly A000009(n) copies of n.
For length instead of sum we have A000120, complement A023416.
For minimum instead of sum we have A001511, opposite A000012.
For maximum instead of sum we have A029837 or A070939, opposite A070940.
For product instead of sum we have A096111.
The reverse version is A230877, row sums of A371572.
The reverse complement is A359359, row sums of A371571.
The complement is A359400, row sums of A368494.
Numbers k such that a(k) is prime are A372689.
A014499 lists binary indices of prime numbers.
A019565 gives Heinz number of binary indices, inverse A048675.
A372471 lists binary indices of primes, row-sums A372429.
Cf. A000009, A030101, A359401, A359402.

a029931 = sum . zipWith (*) [1..] . a030308_row
-- Reinhard Zumkeller, Feb 28 2014

HammingWeight := n -> add(i, i = convert(n, base, 2)):
a := proc(n) option remember; `if`(n = 0, 0,
ifelse(n::even, a(n/2) + HammingWeight(n/2), a(n-1) + 1)) end:
seq(a(n), n = 0..78); # Peter Luschny, Oct 30 2021

a[n_] := (b = IntegerDigits[n, 2]).Reverse @ Range[Length @ b]; Array[a,78,0] (* Jean-François Alcover, Apr 28 2011, after B. Cloitre *)

for(n=0,100,l=length(binary(n)); print1(sum(i=1,l, component(binary(n),i)*(l-i+1)),","))

a(n) = my(b=binary(n)); b*-[-#b..-1]~; \\ Ruud H.G. van Tol, Oct 17 2023

def A029931(n): return sum(i if j == '1' else 0 for i, j in enumerate(bin(n)[:1:-1],1)) # Chai Wah Wu, Dec 20 2022
(C#)
ulong A029931(ulong n) {
    ulong result = 0, counter = 1;
    while(n > 0) {
        if (n % 2 == 1)
          result += counter;
        counter++;
        n /= 2;
    }
    return result;
} // Frank Hollstein, Jan 07 2023

a(n) = a(n - 2^L(n)) + L(n) + 1 [where L(n) = floor(log_2(n)) = A000523(n)] = sum of digits of A048794 [at least for n < 512]. - Henry Bottomley, Mar 09 2001
a(0) = 0, a(2n) = a(n) + e1(n), a(2n+1) = a(2n) + 1, where e1(n) = A000120(n). a(n) = log_2(A029930(n)). - Ralf Stephan, Jun 19 2003
G.f.: (1/(1-x)) * Sum_{k>=0} (k+1)*x^2^k/(1+x^2^k). - Ralf Stephan, Jun 23 2003
a(n) = Sum_{k>=0} A030308(n,k)*A000027(k+1). - Philippe Deléham, Oct 15 2011
a(n) = sum of n-th row of the triangle in A213629. - Reinhard Zumkeller, Jun 17 2012
From Reinhard Zumkeller, Feb 28 2014: (Start)
a(A089633(n)) = n and a(m) != n for m < A089633(n).
a(n) = Sum_{k=1..A070939(n)} k*A030308(n,k-1). (End)
a(n) = A073642(n) + A000120(n). - Peter Kagey, Apr 04 2016

More terms from Erich Friedman

A133457 Irregular triangle read by rows: row n gives exponents in expression for n as a sum of powers of 2.

Original entry on oeis.org

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

Offset: 1

Masahiko Shin, Nov 27 2007

This sequence contains every increasing finite sequence. For example, the finite sequence {0,2,3,5} arises from n = 45.
Essentially A030308(n,k)*k, then entries removed where A030308(n,k)=0. - R. J. Mathar, Nov 30 2007
In the corresponding irregular triangle {a(n)+1}, the m-th row gives all positive integer roots m_i of polynomial {m,k}. - see link [Shevelev]; see also A264613. - Vladimir Shevelev, Dec 13 2015

			1 = 2^0.
2 = 2^1.
3 = 2^0 + 2^1.
4 = 2^2.
5 = 2^0 + 2^2.
etc. and reading the exponents gives the rows of the triangle.

Reinhard Zumkeller, Rows n = 1..1024 of triangle, flattened
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. (See Section 3, Theorem 21 and Section 8, Theorem 50)

Cf. A003071, A030308, A048793, A067255, A264613.

Cf. A073642 (row sums), A272011 (rows reversed).

a133457 n k = a133457_tabf !! (n-1) !! n
a133457_row n = a133457_tabf !! (n-1)
a133457_tabf = map (fst . unzip . filter ((> 0) . snd) . zip [0..]) $
                   tail a030308_tabf
-- Reinhard Zumkeller, Oct 28 2013, Feb 06 2013

A133457 := proc(n) local a,bdigs,i ; a := [] ; bdigs := convert(n,base,2) ; for i from 1 to nops(bdigs) do if op(i,bdigs) <> 0 then a := [op(a),i-1] ; fi ; od: a ; end: seq(op(A133457(n)),n=1..80) ; # R. J. Mathar, Nov 30 2007

Array[Join @@ Position[#, 1] - 1 &@ Reverse@ IntegerDigits[#, 2] &, 41] // Flatten (* Michael De Vlieger, Oct 08 2017 *)

a(n) = A048793(n) - 1.

More terms from R. J. Mathar, Nov 30 2007

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

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.

A372475 Length of binary expansion (or number of bits) of the n-th squarefree number.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, May 09 2024

			The 10th squarefree number is 14, with binary expansion (1,1,1,0), so a(10) = 4.

For prime instead of squarefree we have A035100, 1's A014499, 0's A035103.
Restriction of A070939 to A005117.
Run-lengths are A077643.
For weight instead of length we have A372433 (restrict A000120 to A005117).
For zeros instead of length we have A372472, firsts A372473.
Positions of first appearances are A372540.
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, A023416, A049093, A049094, A059015, A069010, A073642, A145037, A211997, A368494, A372474, A372516.

IntegerLength[Select[Range[1000],SquareFreeQ],2]

from math import isqrt
from sympy import mobius
def A372475(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_length() # Chai Wah Wu, Aug 02 2024

a(n) = A070939(A005117(n)).

a(n) = A372472(n) + A372433(n).

A124757 Zero-based weighted sum of compositions in standard order.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 3, 4, 5, 6, 0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14, 15, 0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

Sum of all positions of 1's except the last in the reversed binary expansion of n. For example, the reversed binary expansion of 14 is (0,1,1,1), so a(14) = 2 + 3 = 5. Keeping the last position gives A029931. - Gus Wiseman, Jan 17 2023

			Composition number 11 is 2,1,1; 0*2+1*1+2*1 = 3, so a(11) = 3.
The table starts:
  0
  0
  0 1
  0 1 2 3

Alois P. Heinz, Rows n = 0..14, flattened

Cf. A066099, A070939, A029931, A011782 (row lengths), A001788 (row sums).
Row sums of A048793 if we delete the last part of every row.
For prime indices instead of standard comps we have A359674, rev A359677.
Positions of first appearances are A359756.
A003714 lists numbers with no successive binary indices.
A030190 gives binary expansion, reverse A030308.
A230877 adds up positions of 1's in binary expansion, length A000120.
A359359 adds up positions of 0's in binary expansion, length A023416.
Cf. A059015, A065359, A069010, A073642, A083652, A359400, A359402, A359678.

Table[Total[Most[Join@@Position[Reverse[IntegerDigits[n,2]],1]]],{n,30}]

For a composition b(1),...,b(k), a(n) = Sum_{i=1..k} (i-1)*b(i).

For n>0, a(n) = A029931(n) - A070939(n).

Showing 1-10 of 22 results. Next

For n > 0, number of partitions of n into distinct nonnegative integers; for all n, number of nonempty partitions of n into distinct nonnegative integers. - Franklin T. Adams-Watters, Dec 28 2006

For n >= 1, a(n-1) is the number of partitions of n where all parts except possibly the two smallest are distinct, see example. - Joerg Arndt, May 23 2013

cp's OEIS Frontend

A087135 Number of positive numbers m such that A073642(m) = n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A087136 Smallest positive number m such that A073642(m)=n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A060960 Duplicate of A073642.

Views

Author

Keywords

A029931 If 2n = Sum 2^e_i, a(n) = Sum e_i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A133457 Irregular triangle read by rows: row n gives exponents in expression for n as a sum of powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

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

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