A034931 Triangle read by rows: Pascal's triangle (A007318) mod 4.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 0, 2, 0, 1, 1, 1, 2, 2, 1, 1, 1, 2, 3, 0, 3, 2, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 0, 0, 0, 2, 0, 0, 0, 1, 1, 1, 0, 0, 2, 2, 0, 0, 1, 1, 1, 2, 1, 0, 2, 0, 2, 0, 1, 2, 1, 1, 3, 3, 1, 2, 2, 2, 2, 1, 3, 3, 1, 1, 0, 2, 0, 3, 0, 0, 0, 3, 0, 2, 0, 1, 1, 1, 2, 2, 3, 3, 0, 0, 3, 3, 2, 2, 1, 1

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• tabl

Comments

The number of 3's in row n is given by 2^(A000120(n)-1) if A014081(n) is nonzero, else by 0 [Davis & Webb]. - R. J. Mathar, Jul 28 2017

Examples

			Triangle begins:
                 1
                1 1
               1 2 1
              1 3 3 1
             1 0 2 0 1
            1 1 2 2 1 1
           1 2 3 0 3 2 1
          1 3 1 3 3 1 3 1
         1 0 0 0 2 0 0 0 1
        1 1 0 0 2 2 0 0 1 1
       1 2 1 0 2 0 2 0 1 2 1
      1 3 3 1 2 2 2 2 1 3 3 1
  ...
		

Links

• Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
• Kenneth S. Davis and William A. Webb, Lucas' theorem for prime powers, European Journal of Combinatorics 11:3 (1990), pp. 229-233.
• Kenneth S. Davis and William A. Webb, Pascal's triangle modulo 4, Fib. Quart., 29 (1991), 79-83.
• Marc Evanstein, Hearing Pascal's Triangle Mod 4, YouTube video.
• Ilya Gutkovskiy, Illustrations (triangle formed by reading Pascal's triangle mod m),.
• James G. Huard, Blair K. Spearman, and Kenneth S. Williams, Pascal's triangle (mod 8), European Journal of Combinatorics 19:1 (1998), pp. 45-62.
• Ivan Korec, Definability of Pascal's Triangles Modulo 4 and 6 and Some Other Binary Operations from Their Associated Equivalence Relations, Acta Univ. M. Belii Ser. Math. 4 (1996), pp. 53-66.
• Index entries for triangles and arrays related to Pascal's triangle

Crossrefs

Cf. A007318, A047999, A083093, A034930, A008975, A034932, A163000 (# 2's), A270438 (# 1's), A249732 (# 0's).

Cf. A000120, A014081.

Sequences based on the triangles formed by reading Pascal's triangle mod m: A047999 (m = 2), A083093 (m = 3), (this sequence) (m = 4), A095140 (m = 5), A095141 (m = 6), A095142 (m = 7), A034930(m = 8), A095143 (m = 9), A008975 (m = 10), A095144 (m = 11), A095145 (m = 12), A275198 (m = 14), A034932 (m = 16).

Programs

Haskell

a034931 n k = a034931_tabl !! n !! k
a034931_row n = a034931_tabl !! n
a034931_tabl = iterate
   (\ws -> zipWith ((flip mod 4 .) . (+)) ([0] ++ ws) (ws ++ [0])) [1]
-- Reinhard Zumkeller, Mar 14 2015

Maple

A034931 := proc(n,k)
    modp(binomial(n,k),4) ;
end proc:
seq(seq(A034931(n,k),k=0..n),n=0..10); # R. J. Mathar, Jul 28 2017

Mathematica

Mod[ Flatten[ Table[ Binomial[n, k], {n, 0, 13}, {k, 0, n}]], 4] (* Robert G. Wilson v, May 26 2004 *)

PARI

C(n, k)=binomial(n, k)%4 \\ Charles R Greathouse IV, Aug 09 2016

PARI

f(n,k)=2*(bitand(n-k, k)==0);
T(n,j)=if(j==0,return(1)); my(k=logint(n,2),K=2^k,K1=K/2,L=n-K); if(LCharles R Greathouse IV, Aug 11 2016

Python

from math import isqrt, comb
def A034931(n):
    g = (m:=isqrt(f:=n+1<<1))-(f<=m*(m+1))
    k = n-comb(g+1,2)
    if k.bit_count()+(g-k).bit_count()-g.bit_count()>1: return 0
    s, c, d = bin(g)[2:], 1, 0
    w = (bin(k)[2:]).zfill(l:=len(s))
    for i in range(0,l-1):
        r, t = s[i:i+2], w[i:i+2]
        if (x:=int(r,2)) < (y:=int(t,2)):
            d += (t[0]>r[0])+(t[1]>r[1])
        else:
            c = c*comb(x,y)&3
    d -= sum(1 for i in range(1,l-1) if w[i]>s[i])
    return (c<Chai Wah Wu, Jul 19 2025

Formula

T(n+1,k) = (T(n,k) + T(n,k-1)) mod 4. - Reinhard Zumkeller, Mar 14 2015