cp's OEIS Frontend

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

%I A034931 #56 Jul 23 2025 01:03:27
%S A034931 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,
%T A034931 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,
%U A034931 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
%N A034931 Triangle read by rows: Pascal's triangle (A007318) mod 4.
%C A034931 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
%H A034931 Reinhard Zumkeller, <a href="/A034931/b034931.txt">Rows n = 0..120 of triangle, flattened</a>
%H A034931 Kenneth S. Davis and William A. Webb, <a href="https://doi.org/10.1016/S0195-6698(13)80122-9">Lucas' theorem for prime powers</a>, European Journal of Combinatorics 11:3 (1990), pp. 229-233.
%H A034931 Kenneth S. Davis and William A. Webb, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/29-1/davis.pdf">Pascal's triangle modulo 4</a>, Fib. Quart., 29 (1991), 79-83.
%H A034931 Marc Evanstein, <a href="https://www.youtube.com/watch?v=85rCF9XpIlM">Hearing Pascal's Triangle Mod 4</a>, YouTube video.
%H A034931 Ilya Gutkovskiy, <a href="/A275198/a275198.pdf">Illustrations (triangle formed by reading Pascal's triangle mod m)</a>,.
%H A034931 James G. Huard, Blair K. Spearman, and Kenneth S. Williams, <a href="https://doi.org/10.1006/eujc.1997.0146">Pascal's triangle (mod 8)</a>, European Journal of Combinatorics 19:1 (1998), pp. 45-62.
%H A034931 Ivan Korec, <a href="http://actamath.savbb.sk/acta0405.shtml">Definability of Pascal's Triangles Modulo 4 and 6 and Some Other Binary Operations from Their Associated Equivalence Relations</a>, Acta Univ. M. Belii Ser. Math. 4 (1996), pp. 53-66.
%H A034931 <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>
%F A034931 T(n+1,k) = (T(n,k) + T(n,k-1)) mod 4. - _Reinhard Zumkeller_, Mar 14 2015
%e A034931 Triangle begins:
%e A034931                  1
%e A034931                 1 1
%e A034931                1 2 1
%e A034931               1 3 3 1
%e A034931              1 0 2 0 1
%e A034931             1 1 2 2 1 1
%e A034931            1 2 3 0 3 2 1
%e A034931           1 3 1 3 3 1 3 1
%e A034931          1 0 0 0 2 0 0 0 1
%e A034931         1 1 0 0 2 2 0 0 1 1
%e A034931        1 2 1 0 2 0 2 0 1 2 1
%e A034931       1 3 3 1 2 2 2 2 1 3 3 1
%e A034931   ...
%p A034931 A034931 := proc(n,k)
%p A034931     modp(binomial(n,k),4) ;
%p A034931 end proc:
%p A034931 seq(seq(A034931(n,k),k=0..n),n=0..10); # _R. J. Mathar_, Jul 28 2017
%t A034931 Mod[ Flatten[ Table[ Binomial[n, k], {n, 0, 13}, {k, 0, n}]], 4] (* _Robert G. Wilson v_, May 26 2004 *)
%o A034931 (Haskell)
%o A034931 a034931 n k = a034931_tabl !! n !! k
%o A034931 a034931_row n = a034931_tabl !! n
%o A034931 a034931_tabl = iterate
%o A034931    (\ws -> zipWith ((flip mod 4 .) . (+)) ([0] ++ ws) (ws ++ [0])) [1]
%o A034931 -- _Reinhard Zumkeller_, Mar 14 2015
%o A034931 (PARI) C(n, k)=binomial(n, k)%4 \\ _Charles R Greathouse IV_, Aug 09 2016
%o A034931 (PARI) f(n,k)=2*(bitand(n-k, k)==0);
%o A034931 T(n,j)=if(j==0,return(1)); my(k=logint(n,2),K=2^k,K1=K/2,L=n-K); if(L<K1, if(j<=L, T(L,j), j<K1, 0, j<=K1+L, f(L,j-K1), j<K, 0, T(L,j-K)), if(j<K1, T(L,j), j<=L, bitxor(T(L,j), f(L,j-K1)), j<K, f(L,j-K1), j<=L+K, bitxor(T(L,j-K), f(L,j-K1)), T(L,j-K))); \\ See Davis & Webb 1991. - _Charles R Greathouse IV_, Aug 11 2016
%o A034931 (Python)
%o A034931 from math import isqrt, comb
%o A034931 def A034931(n):
%o A034931     g = (m:=isqrt(f:=n+1<<1))-(f<=m*(m+1))
%o A034931     k = n-comb(g+1,2)
%o A034931     if k.bit_count()+(g-k).bit_count()-g.bit_count()>1: return 0
%o A034931     s, c, d = bin(g)[2:], 1, 0
%o A034931     w = (bin(k)[2:]).zfill(l:=len(s))
%o A034931     for i in range(0,l-1):
%o A034931         r, t = s[i:i+2], w[i:i+2]
%o A034931         if (x:=int(r,2)) < (y:=int(t,2)):
%o A034931             d += (t[0]>r[0])+(t[1]>r[1])
%o A034931         else:
%o A034931             c = c*comb(x,y)&3
%o A034931     d -= sum(1 for i in range(1,l-1) if w[i]>s[i])
%o A034931     return (c<<d)&3 # _Chai Wah Wu_, Jul 19 2025
%Y A034931 Cf. A007318, A047999, A083093, A034930, A008975, A034932, A163000 (# 2's), A270438 (# 1's), A249732 (# 0's).
%Y A034931 Cf. A000120, A014081.
%Y A034931 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).
%K A034931 nonn,tabl
%O A034931 0,5
%A A034931 _N. J. A. Sloane_