A132385 Number of distinct primes among the cubes mod n.

0, 0, 1, 1, 2, 3, 0, 3, 0, 4, 4, 4, 1, 2, 6, 5, 6, 1, 2, 7, 2, 8, 8, 8, 8, 2, 2, 2, 9, 10, 3, 10, 11, 11, 3, 2, 4, 5, 3, 11, 12, 4, 3, 13, 3, 14, 14, 14, 4, 14, 15, 4, 15, 4, 16, 5, 5, 16, 16, 16, 6, 6, 0, 17, 5, 18, 5, 18, 19, 5

Offset: 1

Author

Jonathan Vos Post, Nov 07 2007

Keywords

• easy
• nonn
• look

Comments

This is to cubes A000578 as A132213 is to squares A000290.

It seems that the size of a(n) as compared to its surrounding elements is dependent on whether or not n is in A088232. If n is in A088232 the sequence assumes "big" values, otherwise the values will be "small". - Stefan Steinerberger, Nov 24 2007

If n is in A088232, a(n) = A000720(n-1) - A056170(n). - Robert Israel, Jun 28 2018

Examples

			a(10) = 4 because the cubes mod 10 repeat 0, 1, 8, 7, 4, 5, 6, 3, 2, 9, 0, 1, 8, 7, 4, 5, ... of which the 4 distinct primes are {2, 3, 5, 7}.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000040, A000578, A000720, A056170, A132213.

Programs

Maple

f:= proc(n)
  if numtheory:-phi(n) mod 3 = 0 then nops(select(isprime, {seq(i^3 mod n, i=0..n-1)}))
  else numtheory:-pi(n-1) - nops(select(t -> t[2]>1, ifactors(n)[2]))
  fi
end proc:
map(f, [$1..100]); # Robert Israel, Jun 28 2018

Mathematica

Table[Length[Select[Union[Table[Mod[i^3, n], {i, 0, n}], Table[Mod[i^3, n], {i, 0, n}]], PrimeQ[ # ] &]], {n, 1, 70}] (* Stefan Steinerberger, Nov 12 2007 *)

Formula

a(n) = Card{p = k^3 mod n, for primes p and for all integers k}.

Extensions

More terms from Stefan Steinerberger, Nov 12 2007

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010