A385394 a(n) = (Sum_{k=0..n} (binomial(n, k) mod 8)) / 2^bitcount(n).

1, 1, 2, 2, 8, 4, 8, 4, 8, 8, 6, 6, 10, 8, 5, 4, 8, 8, 10, 8, 12, 6, 11, 6, 10, 10, 11, 7, 9, 7, 7, 4, 8, 8, 10, 8, 16, 12, 15, 10, 12, 12, 9, 9, 13, 11, 10, 6, 10, 10, 13, 11, 15, 11, 11, 7, 9, 9, 10, 7, 11, 7, 7, 4, 8, 8, 10, 8, 16, 12, 15, 10, 16, 16, 15, 13

Offset: 0

Author

Peter Luschny, Jun 27 2025

Keywords

• nonn

Links

• Peter Luschny, C Implementation.

Crossrefs

Cf. A000120, A001316, A385285, A385393.

Programs

Maple

a := n -> local j; add(modp(binomial(n, j), 8), j=0..n) / 2^add(convert(n, base, 2)): seq(a(n), n = 0..75);

Mathematica

Table[Sum[Mod[Binomial[n, k], 8], {k, 0, n}]/2^DigitCount[n, 2, 1], {n, 0, 80}]
(* Michael De Vlieger, Jun 27 2025 *)
pca[L_] := DigitCount[BitAnd @@ L, 2, 1]
A385394[n_] := Module[{s, n1, n2, n3, np, n1p, b100, b10, b110, b11, b1111, b101, b1100, m11, c},
If[n == 0, Return[1]];
n1 = BitShiftRight[n, 1]; n2 = BitShiftRight[n, 2]; n3 = BitShiftRight[n, 3];
np = BitNot[n]; n1p = BitNot[n1];
b1111 = pca[{n, n1, n2, n3}]; b11 = pca[{n, n1}]; b101 = pca[{n, n2, n1p}]; b100 = pca[{np, n2, n1p}]; b110 = pca[{n2, n1, np}]; b10 = pca[{n1, np}]; b1100 = pca[{n3, n2, n1p, np}];
s = "0" <> IntegerString[n, 2]; m11  = StringCount[s, "0110"];
c = BitShiftLeft[b100, 2] + b110 + BitShiftRight[b10 (b10 - 1), 1];
c += Switch[b11,
  0, b10 + BitShiftLeft[b100, 1],
  1, BitShiftLeft[b10 - b1100, 1] + b110,
  _, BitShiftLeft[b10, 1] ];
c += Which[
  b1111 == 0 && b11 == 0 && b101 == 0, 1,
  b1111 == 0 && b11 == 0 && b101 != 0, 3,
  StringEndsQ[s, "0111"], 4,
  b1111 == 0 && b101 == 0 && m11 == 0 && b11 != 0, 2,
  True, 4]; c]
Array[A385394, 76, 0]  (* After Chai Wah Wu, Peter Luschny, Jun 29 2025 *)

PARI

a(n) = sum(k=0, n, binomial(n, k) % 8) / 2^hammingweight(n); \\ Michel Marcus, Jun 28 2025

Python

def A385394(n):
    if n==0: return 1
    s = '0'+bin(n)[2:]
    n1 = n>>1
    n2 = n1>>1
    n3 = n2>>1
    np = ~n
    n1p = ~n1
    n1111 = (n3&n2&n1&n).bit_count()
    n11 = (n1&n).bit_count()
    n101 = (n2&n1p&n).bit_count()
    n100 = (n2&n1p&np).bit_count()
    n110 = (n2&n1&np).bit_count()
    n10 = (n1&np).bit_count()
    n1100 = (n3&n2&n1p&np).bit_count()
    m11 = s.count('0110')
    m111 = s.endswith('0111')
    c = (n100<<2)+n110+(n10*(n10-1)>>1)
    if n11==0:
        c += n10+(n100<<1)
    elif n11==1:
        c += (n10-n1100<<1)+n110
    else:
        c += n10<<1
    if not (n1111 or n11 or n101):
        c += 1
    elif not (n1111 or n11) and n101:
        c += 3
    elif m111:
        c += 4
    elif not (n1111 or n101 or m11) and n11:
        c += 2
    else:
        c += 4
    return c # Chai Wah Wu, Jun 28 2025

Formula

a(n) = A385285(n) / 2^A000120(n).

a(n) = A385285(n) / A001316(n).