A067587 -id:A067587 - cp's OEIS frontend

A066884 Square array read by upward antidiagonals where the n-th row contains the positive integers with n binary 1's.

1, 3, 2, 7, 5, 4, 15, 11, 6, 8, 31, 23, 13, 9, 16, 63, 47, 27, 14, 10, 32, 127, 95, 55, 29, 19, 12, 64, 255, 191, 111, 59, 30, 21, 17, 128, 511, 383, 223, 119, 61, 39, 22, 18, 256, 1023, 767, 447, 239, 123, 62, 43, 25, 20, 512, 2047, 1535, 895, 479, 247, 125, 79, 45, 26, 24, 1024

Offset: 1

Jared Benjamin Ricks (jaredricks(AT)yahoo.com), Jan 21 2002

This is a permutation of the positive integers; the inverse permutation is A067587.

			Column: 1   2   3   4   5   6
-----------------------------
Row 1:| 1   2   4   8  16  32
Row 2:| 3   5   6   9  10  12
Row 3:| 7  11  13  14  19  21
Row 4:|15  23  27  29  30  39
Row 5:|31  47  55  59  61  62
Row 6:|63  95 111 119 123 125

Ivan Neretin, Table of n, a(n) for n = 1..8001 (126 antidiagonals)
Vladimir Dobric, M. Skyers, and L. J. Stanley, Polynomial Time Computable Triangular Arrays For Almost Sure Convergence, arXiv preprint arXiv:1603.04896 [math.PR], 2016. [Shows that this sequence is in P-TIME]
Index entries for sequences that are permutations of the natural numbers

Cf. A000120, A067587.
Selected rows: A000079 (1), A018900 (2), A014311 (3), A014312 (4), A014313 (5), A023688 (6), A023689 (7), A023690 (8), A023691 (9), A038461 (10), A038462 (11), A038463 (12). For decimal analogs, see A011557 and A038444-A038452.
Selected columns: A000225 (1), A055010 (2).
Selected diagonals: A036563 (main), A000918 (1st upper), A153894 (2nd upper). [Franklin T. Adams-Watters, Apr 22 2009]
Cf. A067576 (the same array read by downward antidiagonals).
Antidiagonal sums give A361074.

a = {}; Do[ a = Append[a, Last[ Take[ Take[ Select[ Range[2^12], Count[ IntegerDigits[ #, 2], 1] == j - i + 1 & ], j], i]]], {j, 1, 11}, {i, 1, j}]; a

Corrected and extended by Henry Bottomley, Jan 27 2002

A068076 Number of positive integers < n with the same number of 1's in their binary expansions as n.

Original entry on oeis.org

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

Offset: 1

Dean Hickerson, Feb 16 2002

From Rémy Sigrist, Dec 23 2018: (Start)
This sequence is related to the combinatorial number system:
- if n = Sum_{k=1..h} 2^c_k with 0 <= c_1 < c_2 < ... < c_h,
- then a(n) = Sum_{k=1..h} binomial(c_k, k) (with binomial(n, r) = 0 if n < r).
(End)

			The binary expansion of 22 (10110) has 3 1's, as do those of the 6 smaller numbers 7, 11, 13, 14, 19 and 21, so a(22)=6.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Wikipedia, Combinatorial number system

One less than A263017.

Cf. A067587, also A000120 for numerous references.

w[n_] := Plus@@IntegerDigits[n, 2]; a[n_] := Plus@@MapThread[Binomial, {Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]]-1, Range[w[n]]}]

a(n)=my(k=hammingweight(n));sum(i=1,n-1,hammingweight(i)==k) \\ Charles R Greathouse IV, Sep 24 2012

a(n) = my (v=0, k=0); for (c=0, oo, if (n==0, return (v), n%2, k++; if (c>=k, v+=c!/k!/(c-k)!)); n\=2) \\ Rémy Sigrist, Dec 23 2018

def a(n):
    x=bin(n)[2:].count("1")
    return sum(1 for i in range(n) if bin(i)[2:].count("1")==x) # Indranil Ghosh, May 24 2017

from math import comb
def A068076(n):
    c, k = 0, 1
    for i,j in enumerate(bin(n)[-1:1:-1]):
        if j == '1':
            c += comb(i,k)
            k += 1
    return c # Chai Wah Wu, Mar 01 2023

a(n) = A263017(n) - 1. - Antti Karttunen, May 22 2017

Edited by John W. Layman, Feb 20 2002

A356419 Inverse of A067576 considered as a permutation of the positive integers.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 6, 7, 12, 17, 9, 23, 13, 18, 10, 11, 30, 38, 24, 47, 31, 39, 14, 57, 48, 58, 19, 69, 25, 32, 15, 16, 68, 80, 81, 93, 94, 108, 40, 107, 123, 139, 49, 156, 59, 70, 20, 122, 174, 193, 82, 213, 95, 109, 26, 234, 124, 140, 33, 157, 41, 50, 21, 22, 138, 155, 256

Offset: 1

Jianing Song, Aug 06 2022

			A067576(12) = 9, so a(9) = 12.

Cf. A067576, A000120, A068076, A263017, A067587.

a(n)=my(w=hammingweight(n), p=sum(i=1, n-1, hammingweight(i)==w)); binomial(w+p+1, 2) - p

from math import comb
def A356419(n):
    c, k = 0, 0
    for i,j in enumerate(bin(n)[-1:1:-1]):
        if j == '1':
            k += 1
            c += comb(i,k)
    return comb(n.bit_count()+c+1,2)-c # Chai Wah Wu, Mar 02 2023

Let w(n) = A000120(n) be the Hamming weight of n, p(n) = A068076(n), then a(n) = binomial(w(n)+p(n)+1, 2) - p(n).

cp's OEIS Frontend

A066884 Square array read by upward antidiagonals where the n-th row contains the positive integers with n binary 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A068076 Number of positive integers < n with the same number of 1's in their binary expansions as n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A356419 Inverse of A067576 considered as a permutation of the positive integers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Formula