login
A376533
a(n) = (1/4^n) * Sum_{k=0..n^2} ( (binomial(n^2, k) * 3^k) (mod 4^n) ).
6
1, 2, 4, 6, 13, 14, 26, 31, 39, 50, 57, 73, 86, 104, 110, 129, 142, 165, 186, 201, 218, 239, 257, 301, 315, 326, 355, 385, 434, 457, 476, 522, 557, 577, 592, 646, 686, 707, 766, 800, 832, 879, 928, 961, 1011, 1070, 1107, 1161, 1178, 1227, 1306, 1379, 1404, 1450, 1526, 1562, 1625, 1682
OFFSET
1,2
LINKS
Chai Wah Wu, Table of n, a(n) for n = 1..300 (terms 1..200 from Paul D. Hanna)
J. B. Roberts, On Binomial Coefficient Residues, Canadian Journal of Mathematics, Volume 9 1957, pp. 363 - 370.
EXAMPLE
The table of residues of coefficients of x^k in (1 + 3*x)^(n^2) modulo 4^n begins:
(1+3*x) (mod 4): [1, 3];
(1+3*x)^4 (mod 4^2): [1, 12, 6, 12, 1];
(1+3*x)^9 (mod 4^3): [1, 27, 4, 28, 30, 26, 52, 12, 41, 35];
(1+3*x)^16 (mod 4^4): [1, 48, 56, 16, 220, 48, 8, 144, 6, 16, 136, 176, 92, 144, 184, 176, 65];
(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];
(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];
(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];
...
where a(n) equals the sum of row n divided by 4^n:
a(1) = (1 + 3)/4 = 1;
a(2) = (1 + 12 + 6 + 12 + 1)/4^2 = 2;
a(3) = (1 + 27 + 4 + 28 + 30 + 26 + 52 + 12 + 41 + 35)/4^3 = 4;
a(4) = (1 + 48 + 56 + 16 + 220 + 48 + 8 + 144 + 6 + 16 + 136 + 176 + 92 + 144 + 184 + 176 + 65)/4^4 = 6;
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;
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;
...
PROG
(PARI) {a(n) = sum(k=0, n^2, ( binomial(n^2, k) * 3^k ) % (4^n) )/4^n}
for(n=1, 60, print1(a(n), ", "))
(Python)
def A376533(n):
m, r, c, a, b, d = (1<<(n<<1))-1, n**2, 1, 3, n**2, 1
for k in range(1, r+1):
c += b//d*a&m
a = a*3&m
b *= r-k
d *= k+1
return c>>(n<<1) # Chai Wah Wu, Oct 09 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Oct 06 2024
STATUS
approved