login
Number of polynomial functions from Z to Z/nZ.
3

%I #48 Jun 06 2021 02:56:28

%S 1,1,4,27,64,3125,108,823543,1024,19683,12500,285311670611,1728,

%T 302875106592253,3294172,84375,65536,827240261886336764177,78732,

%U 1978419655660313589123979,200000,22235661,1141246682444,20880467999847912034355032910567

%N Number of polynomial functions from Z to Z/nZ.

%C The first formula for a(n) is due to Kempner (1921). - _Jonathan Sondow_, Nov 05 2017

%H Amiram Eldar, <a href="/A058067/b058067.txt">Table of n, a(n) for n = 0..388</a>

%H Manjul Bhargava, <a href="http://dx.doi.org/10.2307/2695734">The factorial function and generalizations</a>, Amer. Math. Monthly, Vol. 107, No. 9 (Nov. 2000), pp. 783-799; <a href="https://www.jstor.org/stable/2695734">alternative link</a>,

%H Aubrey J. Kempner, <a href="https://doi.org/10.1090/S0002-9947-1921-1501173-4">Polynomials and their residue systems</a>, <a href="https://doi.org/10.1090/S0002-9947-1921-1501174-6">continued</a>, Amer. Math. Soc. Trans., Vol. 22 (1921), pp. 240-288.

%H David Singmaster, <a href="https://doi.org/10.1016/0022-314X(74)90031-6">On polynomial functions (mod m)</a>, Journal of Number Theory, Volume 6, Issue 5, October 1974, pp. 345-352.

%F a(n) = Product_{k=0..n-1} n/gcd(n, k!).

%F Multiplicative with a(p^e) = p^t_p(e). - _David W. Wilson_, Aug 14 2005 [t_p(e) = Sum_{k>=0: e > A090622(k, p)} (e - A090622(k, p)) = p * Sum_{k = 1..e} max(0, k - A090622(e-k, p)). In particular, t_p(e) = p*e*(e+1)/2 for e <= p. - _Andrey Zabolotskiy_, Nov 09 2017 and Sep 29 2020]

%F a(prime(n)) = A051674(n). - _R. J. Mathar_, Apr 01 2014 [Edited by _Andrey Zabolotskiy_, Nov 08 2017]

%F a(n) = n^n / A240098(n). - _Jonathan Sondow_, Nov 10 2017

%p A058067 := n->mul(n/gcd(n,k!),k=0..n-1);

%t a[0] = 1; a[n_] := Product[n/GCD[n, k!], {k, 0, n - 1}]; Array[a, 24, 0] (* _Amiram Eldar_, Sep 29 2020 *)

%o (PARI) a(n) = prod(k=0, n-1, n/gcd(n, k!)); \\ _Michel Marcus_, Nov 06 2017

%Y Cf. A051674, A090622, A240098.

%K nonn,mult,easy

%O 0,3

%A _N. J. A. Sloane_, Nov 24 2000