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