A368415 Array read by ascending antidiagonals. A(n, k) = floor((n^k + 3)*(n/(2*n + 2))).

1, 1, 1, 2, 2, 1, 2, 4, 3, 1, 3, 7, 11, 6, 1, 3, 11, 26, 31, 11, 1, 4, 16, 53, 103, 92, 22, 1, 4, 22, 93, 261, 410, 274, 43, 1, 5, 29, 151, 556, 1303, 1639, 821, 86, 1, 5, 37, 228, 1051, 3333, 6511, 6554, 2461, 171, 1, 6, 46, 329, 1821, 7354, 19996, 32553, 26215, 7382, 342, 1, 6, 56, 455, 2953

Offset: 1

Author

Thomas Scheuerle, Dec 23 2023

Keywords

• nonn
• tabl

Comments

Let p be an odd prime number, then A(p, k) is the number of distinct quadratic residues mod p^k. Let m = p1^k1^*p2^k2*..*pz^kz with p1..pz odd primes, then A(p1, k1)*A(p2, k2)*..*A(pz, kz) is the number of distinct quadratic residues mod m. For 2^t*m is floor((2^t+10)*(1/6))*A(p1, k1)*A(p2, k2)*..*A(pz, kz) the number of distinct quadratic residues mod 2^t*m.

Examples

			The array A(n, k) begins:
1,  1,   1,    1,     1,      1,       1,        1,         1,          1
1,  2,   3,    6,    11,     22,      43,       86,       171,        342
2,  4,  11,   31,    92,    274,     821,     2461,      7382,      22144
2,  7,  26,  103,   410,   1639,    6554,    26215,    104858,     419431
3, 11,  53,  261,  1303,   6511,   32553,   162761,    813803,    4069011
3, 16,  93,  556,  3333,  19996,  119973,   719836,   4319013,   25914076
4, 22, 151, 1051,  7354,  51472,  360301,  2522101,  17654704,  123582922
4, 29, 228, 1821, 14564, 116509,  932068,  7456541,  59652324,  477218589
5, 37, 323, 2953, 26573, 239149, 2152337, 19371025, 174339221, 1569052981
5, 46, 455, 4546, 45455, 454546, 4545455, 45454546, 454545455, 4545454546
		

Crossrefs

Cf. A000124, A005578, A039300, A039302, A039304, A172241, A363773.

Programs

PARI

A(n, k) = (n^(k+1)+n*3)\(2*n+2)

Formula

A(n, k) = n*A(n, k-1) + A(n, k-2) - n*A(n, k-3), for k > 2 and A(n, 0) = 1.

A(1, k) = 1.

A(2, k) = A005578(k).

A(3, k) = A039300(k).

A(4, k) = A363773(k).

A(5, k) = A039302(k).

A(7, k) = A039304(k).

A(8, k) = A172241(k+1)+1.

A(n, 2) = A000124(n-1), for n > 0.