Fórmula para o enésimo bit_count (ou contagem de população) de tamanho M

Eu não conheço Python, então este é Ruby. O algoritmo deve ser fácil de traduzir. A ideia é, para cada bit definido (indo do menor para o maior), contar todos os números que são iguais à esquerda daquele bit, ter o mesmo número de bits definidos naquele bit e à sua direita, mas não tem esse pouco definido.

• Percorra os bits da sua entrada do menor para o maior.
• Acompanhe os bits definidos vistos e o total de bits vistos.
• Conte todos os números com o mesmo número de bits definidos vistos, mas um bit definido máximo menor (do que o índice atual) cada vez que encontrar um bit definido.
• Por exemplo, ao atingir o 1 menor em 10100, adicionamos 2 à contagem porque existem 2 números com 1 bit definido e um bit definido máximo menor: 10 e 01.

Código:

def g(k)
  set_bits_seen = 0
  all_bits_seen = 0
  
  total = 0
  
  while k > 0
    all_bits_seen += 1
    
    if k % 2 == 1 # cur bit is set
      set_bits_seen += 1
      if all_bits_seen > set_bits_seen
        total += n_choose_k(all_bits_seen - 1, set_bits_seen)
      end
    end
    k /= 2
  end
  return total
end

def n_choose_k(n, k)
  return 1 if k == 0 or k == n
  (k + 1 .. n).reduce(:*) / (1 .. n - k).reduce(:*)
end

Resultados:

1.upto(20) do |i|
  puts "#{i.to_s(2)}  --  #{g(i)}"
end

1  --  0
10  --  1
11  --  0
100  --  2
101  --  1
110  --  2
111  --  0
1000  --  3
1001  --  3
1010  --  4
1011  --  1
1100  --  5
1101  --  2
1110  --  3
1111  --  0
10000  --  4
10001  --  6
10010  --  7
10011  --  4
10100  --  8

E para o seu grande exemplo:

> g(123456789123456789123456789)
=> 3594960708495168399327022

A solução trivial:

def count_same0(k: int) -> int:
    s = 0
    m = k.bit_count()
    for n in range(k):
        if n.bit_count() == m:
            s += n
    return s

No entanto, você pode tentar gerar apenas todos os números < kcom uma contagem de bits específica e contá-los.

Aqui está uma tentativa simples de fazer exatamente isso:

def count_same1(k: int) -> int:
    from itertools import permutations
    from math import log2, floor

    m = k.bit_count()
    positions = floor(log2(k)) + 1  # the total number of bit positions 

    s = 0
    # start generating unique permutations of positions #bits
    ps = set()
    for p in permutations([0] * (positions-m) + [1] * m):
        if p not in ps:
            ps.add(p)
            n = 0
            for b in p:
                n = (n << 1) | b
            # stop when we first exceed k
            if n >= k:
                break
            s += n

    return s 

Isso funciona, mas é muito ineficiente, pois ainda precisa gerar todas as permutações que não são únicas. E no final, gerar uma permutação é muito mais lento do que apenas contar os bits.

Em vez disso, talvez seja melhor gerar combinações únicas de posições para zeros para números que possuem um certo número de unidades e depois calcular esses números:

def gen_int_n_ones(n: int) -> Generator[int, None, None]:
    from itertools import combinations

    z = 0
    while True:
        bits_cs = list(combinations(range(1, n), z))
        yield from (sum(0 if i in bits else 2**(n-(i+1)) for i in range(n)) for bits in bits_cs)
        z += 1
        n += 1


def count_same2(k: int) -> int:
    s = 0
    for n in gen_int_n_ones(k.bit_count()):
        if n >= k:
            break
        s += n

    return s

No entanto, a solução ingénua utiliza operações que são tão eficientes que é mais eficiente apenas testar todos os números, em vez de descobrir quais devem ser evitados.

Tente executar isto:

def main():
    from timeit import timeit

    for x in range(1, 100):
        print(x, count_same0(x), count_same1(x), count_same2(x))
        print(
            timeit(lambda: count_same0(x), number=10000), 
            timeit(lambda: count_same1(x), number=10000), 
            timeit(lambda: count_same2(x), number=10000)
        )

Você descobrirá que count_same0é facilmente o mais rápido (na verdade, simplesmente rápido) e que count_same2é melhor que count_same1, mas não chega perto de count_same0.

Então acho que a resposta simples é realmente:

def n_for_k(k: int) -> int:
    b = k.bit_count()
    return sum(1 for i in range(k) if i.bit_count() == b)

No entanto, para o seu valor de exemplo de 123456789123456789123456789, isso levará muito tempo para ser concluído. Duvido que exista uma solução mais simples conhecida, visto que (depois de resolvê-la conforme descrito acima) também encontrei a sequência no OEIS: https://oeis.org/A079071 e basicamente define a mesma coisa. (e olhando o gráfico, não melhora muito: https://oeis.org/A079071/graph )

Quem ou o que lhe encarregou de resolvê-lo por esse valor?

Expressando o número como uma combinação de bits e calculando o índice de combinação:

from more_itertools import combination_index
from math import comb

K = 123456789123456789123456789

M = K.bit_length()
c = [i for i, b in enumerate(f'{K:b}') if b == '1']
N = comb(M, len(c)) - 1 - combination_index(c, range(M))

print(N)

Saída (igual à de Dave):

3594960708495168399327022

Ah, droga, acabei de perceber que você está atrás de "uma fórmula simples". Ah bem. Talvez isso ainda seja útil para quem vem aqui em busca de código simples.