A384715 a(n) = Sum_{k=0..n} (binomial(n, k) mod 4).

1, 2, 4, 8, 4, 8, 12, 16, 4, 8, 12, 24, 12, 24, 24, 32, 4, 8, 12, 24, 12, 24, 32, 48, 12, 24, 32, 48, 24, 48, 48, 64, 4, 8, 12, 24, 12, 24, 32, 48, 12, 24, 32, 64, 32, 64, 64, 96, 12, 24, 32, 48, 32, 64, 64, 96, 24, 48, 64, 96, 48, 96, 96, 128, 4, 8, 12, 24

Offset: 0

Author

David Radcliffe, Jun 23 2025

Keywords

• nonn
• easy

Comments

This is a 2-automatic sequence.

Examples

			Let b(n) be the binary expansion of n. Then a(n) = (1 + p10 + p11) * 2^c, where c is the number of set bits in b(n), p10 is the number of '10' patterns in b(n), and p11 is 1 or 0 depending on whether the pattern '11' is occurring in b(n) or not. This formula is used by _Chai Wah Wu_ in the Python function below. For instance:
  n = 25 -> b(n) = 11001 -> a(n) = (1+1+1) * 2^3 = 24.
  n = 26 -> b(n) = 11010 -> a(n) = (1+2+1) * 2^3 = 32.
  n = 27 -> b(n) = 11011 -> a(n) = (1+1+1) * 2^4 = 48.
- _Peter Luschny_, Jun 25 2025
		

Links

• David Radcliffe, Table of n, a(n) for n = 0..10000
• Kenneth S. Davis and William A. Webb, Pascal's triangle modulo 4, Fib. Quart., 29 (1991), 79-83.

Crossrefs

Cf. A001316, A014081, A033264, A051638 (mod 3 analog), A085357. Row sums of triangle A034931.

Programs

Mathematica

A384715[n_] := 2^DigitSum[n, 2]*(StringCount[IntegerString[n, 2], "10"] - Boole[BitAnd[n,2*n] == 0] + 2);
Array[A384715, 100, 0] (* Paolo Xausa, Jun 26 2025 *)

PARI

a(n) = sum(k=0, n, binomial(n,k)%4); \\ Michel Marcus, Jun 25 2025

Python

def A001316(n): return (1 + (n % 2)) * A001316(n // 2) if n else 1
def A033264(n): return (n % 4 == 2) + A033264(n // 2) if n else 0
def A085357(n): return int(n & (n<<1) == 0)
def A384715(n): return A001316(n) * (A033264(n) - A085357(n) + 2)

Python

def A384715(n): return (((n>>1)&~n).bit_count()+bool(n&(n<<1))+1)<Chai Wah Wu, Jun 25 2025

Python

def a(n: int) -> int:  # after Chai Wah Wu
    b = bin(n)[2:]; p = b.count("10"); q = b.count("11")
    return (p + (2 if q else 1)) * 2**n.bit_count()  # Peter Luschny, Jun 25 2025

Formula

a(n) = A001316(n) * (A033264(n) - A085357(n) + 2) for n > 0.

Recurrences:

a(4n) = a(2n),

a(4n+1) = 2a(2n),

a(8n+2) = a(4n+2) + 2a(2n) - a(2n+1),

a(8n+3) = a(4n+3) + 4a(2n) - 4a(n),

a(8n+6) = a(4n+3) + 2a(4n+2) - 2a(2n+1),

a(8n+7) = 2a(4n+3).