login
a(n) = (1/4^n) * Sum_{k=0..n^2} ( (binomial(n^2, k) * 3^k) (mod 4^n) ).
6

%I #21 Oct 12 2024 09:06:07

%S 1,2,4,6,13,14,26,31,39,50,57,73,86,104,110,129,142,165,186,201,218,

%T 239,257,301,315,326,355,385,434,457,476,522,557,577,592,646,686,707,

%U 766,800,832,879,928,961,1011,1070,1107,1161,1178,1227,1306,1379,1404,1450,1526,1562,1625,1682

%N a(n) = (1/4^n) * Sum_{k=0..n^2} ( (binomial(n^2, k) * 3^k) (mod 4^n) ).

%H Chai Wah Wu, <a href="/A376533/b376533.txt">Table of n, a(n) for n = 1..300</a> (terms 1..200 from Paul D. Hanna)

%H J. B. Roberts, <a href="https://doi.org/10.4153/CJM-1957-043-6">On Binomial Coefficient Residues</a>, Canadian Journal of Mathematics, Volume 9 1957, pp. 363 - 370.

%e The table of residues of coefficients of x^k in (1 + 3*x)^(n^2) modulo 4^n begins:

%e (1+3*x) (mod 4): [1, 3];

%e (1+3*x)^4 (mod 4^2): [1, 12, 6, 12, 1];

%e (1+3*x)^9 (mod 4^3): [1, 27, 4, 28, 30, 26, 52, 12, 41, 35];

%e (1+3*x)^16 (mod 4^4): [1, 48, 56, 16, 220, 48, 8, 144, 6, 16, 136, 176, 92, 144, 184, 176, 65];

%e (1+3*x)^25 (mod 4^5): [1, 75, 652, 660, 650, 1022, 1004, 276, 71, 61, 88, 360, 748, 196, 504, 904, 287, 757, 668, 900, 810, 286, 156, 996, 505, 675];

%e (1+3*x)^36 (mod 4^6): [1, 108, 1574, 268, 3561, 2016, 528, 352, 2292, 912, 424, 400, 1476, 928, 3696, 2336, 1262, 840, 612, 3464, 3918, 3104, 1136, 1184, 2436, 3344, 936, 1040, 3636, 608, 16, 2784, 153, 428, 3366, 460, 1745];

%e (1+3*x)^49 (mod 4^7): [1, 147, 10584, 5928, 7908, 524, 11528, 13496, 3666, 950, 11400, 8056, 10996, 8188, 11672, 16168, 8863, 6317, 6384, 14864, 1352, 920, 10960, 9392, 14140, 9652, 7824, 9072, 13192, 3800, 7600, 7632, 6735, 14877, 16184, 4424, 16084, 8540, 1192, 14872, 15250, 14838, 13160, 6808, 13956, 4652, 6200, 3976, 2545, 8515];

%e ...

%e where a(n) equals the sum of row n divided by 4^n:

%e a(1) = (1 + 3)/4 = 1;

%e a(2) = (1 + 12 + 6 + 12 + 1)/4^2 = 2;

%e a(3) = (1 + 27 + 4 + 28 + 30 + 26 + 52 + 12 + 41 + 35)/4^3 = 4;

%e a(4) = (1 + 48 + 56 + 16 + 220 + 48 + 8 + 144 + 6 + 16 + 136 + 176 + 92 + 144 + 184 + 176 + 65)/4^4 = 6;

%e a(5) = (1 + 75 + 652 + 660 + 650 + 1022 + 1004 + 276 + 71 + 61 + 88 + 360 + 748 + 196 + 504 + 904 + 287 + 757 + 668 + 900 + 810 + 286 + 156 + 996 + 505 + 675)/4^5 = 13;

%e a(6) = (1 + 108 + 1574 + 268 + 3561 + 2016 + 528 + 352 + 2292 + 912 + 424 + 400 + 1476 + 928 + 3696 + 2336 + 1262 + 840 + 612 + 3464 + 3918 + 3104 + 1136 + 1184 + 2436 + 3344 + 936 + 1040 + 3636 + 608 + 16 + 2784 + 153 + 428 + 3366 + 460 + 1745)/4^6 = 14;

%e ...

%o (PARI) {a(n) = sum(k=0,n^2, ( binomial(n^2,k) * 3^k ) % (4^n) )/4^n}

%o for(n=1,60,print1(a(n),", "))

%o (Python)

%o def A376533(n):

%o m, r, c, a, b, d = (1<<(n<<1))-1, n**2, 1, 3, n**2, 1

%o for k in range(1,r+1):

%o c += b//d*a&m

%o a = a*3&m

%o b *= r-k

%o d *= k+1

%o return c>>(n<<1) # _Chai Wah Wu_, Oct 09 2024

%Y Cf. A376531, A376532, A376534, A376535, A376536.

%K nonn

%O 1,2

%A _Paul D. Hanna_, Oct 06 2024