A323703 Number of values of (X^3 + X) mod prime(n).

1, 3, 3, 5, 7, 9, 11, 13, 15, 19, 21, 25, 27, 29, 31, 35, 39, 41, 45, 47, 49, 53, 55, 59, 65, 67, 69, 71, 73, 75, 85, 87, 91, 93, 99, 101, 105, 109, 111, 115, 119, 121, 127, 129, 131, 133, 141, 149, 151, 153, 155, 159, 161, 167, 171, 175, 179, 181, 185, 187, 189, 195

Offset: 1

Author

Florian Severin, Jan 24 2019

Keywords

• nonn

Comments

a(n) is also the number of values of any other polynomial of degree 3, except X^3.

a(n) appears to approach (2/3)*prime(n) as n increases.

Examples

			a(1) = 1 since the only value X^3 + X takes mod 2 is 0.
		

References

• R. Daublebsky von Sterneck, Über die Anzahl inkongruenter Werte, die eine ganze Funktion dritten Grades annimmt, Sitzungsber. Akad. Wiss. Wien (2A) 114 (1908), 711-717.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• Thomas Brazelton, Joshua Harrington, Matthew Litman, and Tony W. H. Wong, Distinct residues of Lucas polynomials over Fp, arXiv:2103.09119 [math.NT], 2021. See p. 1.
• Zhi-Hong Sun, On the theory of cubic residues and nonresidues, Acta Arithmetica 84.4 (1998): 291-335.
• Zhi-Hong Sun, On the number of incongruent residues of x^4 +ax^2 +bx modulo p, Journal of Number Theory 119 (2006), 210-241. See p. 211.

Crossrefs

Cf. A323704 (the number of values of X^3), A130291 (the number of values of X^2, which is also the number of values of any other polynomial of degree 2).

Programs

Mathematica

Array[Length@ Union@ Mod[Array[#^3 + # &, #], #] &@ Prime@ # &, 62] (* Michael De Vlieger, Jan 27 2019 *)

PARI

a(n) = #Set(vector(prime(n), k, Mod(k^3+k, prime(n)))); \\ Michel Marcus, Jan 25 2019

Formula

a(n) = prime(n) - 2*floor(prime(n)/6 + 1/2), for n >= 3. - Ridouane Oudra, Jun 13 2020

for n>=3, a(n) = (2*p + (p/3))/3 with p=prime(n) and where (p/3) is the Legendre symbol. See von Sterneck, Sun, and Brazelton et al. articles. - Michel Marcus, Mar 17 2021