binary digit sum mod 3


October 21, 2012
Problem: For length n bit strings, x ∈{0, 1}n = x0x1⋅⋅⋅xn-1, define digitsum(x) = ∑ ixi as the number of 1s in x. We want to know the number of bit strings that have digitsum(x) ≡ 0( mod3).

For 0 ≤ k ≤ n, the number of bit strings with digitsum(x) = k is given by the binomial co-efficient ( ) k n. Thus the count we want is given by

∑ ∑ (k ) 1 = n digitsum (x)≡0( mod3 ) k≡0 ( mod3)

Consider the primitive cube root of 1, ω = -1 2 + √ - --3 2i. Since ω2 = -1 2 -√- -3- 2i and ω3 = 1, we have the real part ℜ(ωk) = 1 if k ≡ 0( mod3) and -1 2 otherwise. We can scale this to get a function of k which is 1 for k divisible by 3 and 0 otherwise, i.e. with f(k) = 2 3ℜ(ωk) + 1 3, we have

{ 1 ifk ≡ 0( mod3 ) f (k) = 0 ifk ⁄≡ 0( mod3 )

Thus, the count is

∑ ( ) ∑n ( ) k = k f (k) n n k≡0( mod3) k=0 ∑n ( ) ( ) k 2- k 1- = n 3ℜ (ω ) + 3 k=0 ( ) ∑ n ( ) ∑ n ( ) 2- k k 1- k = 3 ℜ n ω + 3 n k=0 k=0 2 2n = --ℜ (1 + ω )n + --- 3 3
Now, 1 + ω = 1 2 + √- -3- 2 is the primitive sixth root of 1, and we have ℜ(1 + ω)n = 1,1 2,-1 2,-1,-1 2,1 2 respectively, based on n( mod3) ≡ 0, 1, 2, 3, 4, 5. Substituting in the above equation, our count = 2n 3 ± 1 3 or 2 3. The counts for digitsum(x) ≡ 1 or 2( mod3) is similar except that we use ωk+2 or ωk+1 in the equation. This gives us the final table:

n mod3 0 1 2 3 4 5
count(digitsum(x) ≡ 0( mod3)) = n 2-- 3+ 2- 3 1- 3 -1- 3-2- 3-1- 3 1- 3
count(digitsum(x) ≡ 1( mod3)) = n 2-- 3+-1- 3 1- 3 2- 3 1- 3 -1- 3-2- 3
count(digitsum(x) ≡ 2( mod3)) = 2n --- 3+-1- 3-2- 3-1- 3 1- 3 2- 3 1- 3

Anil Das