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

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

Offset: 0

Author

Peter Luschny, Jun 27 2025

Keywords

• nonn

Comments

Apparently 2^bitcount(n) divides Sum_{k=0..n} (binomial(n, k) mod m) only if m is a power of 2.

Crossrefs

Cf. A000120, A001316, A384715, A385394.

Programs

Maple

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

Mathematica

Table[Sum[Mod[Binomial[n, k], 4], {k, 0, n}]/2^DigitCount[n, 2, 1], {n, 0, 105}] (* Michael De Vlieger, Jun 27 2025 *)
A385393[n_] := StringCount[#, "10"] + Boole[StringContainsQ[#, "11"]] + 1 & [IntegerString[n, 2]]; Array[A385393,100,0] (* Paolo Xausa, Jun 28 2025 *)

PARI

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

Python

def a(n: int) -> int:
    b = bin(n)[2:]
    return 1 + b.count("10") + int("11" in b)
print([a(n) for n in range(75)])

Python

def A385393(n): return (((m:=n>>1)&~n).bit_count()+bool(n&m)+1) # Chai Wah Wu, Jun 28 2025

Formula

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

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