login
Number of distinct primes among the cubes mod n.
1

%I #13 Jun 28 2018 02:44:35

%S 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,

%T 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,

%U 6,6,0,17,5,18,5,18,19,5

%N Number of distinct primes among the cubes mod n.

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

%C 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

%C If n is in A088232, a(n) = A000720(n-1) - A056170(n). - _Robert Israel_, Jun 28 2018

%H Robert Israel, <a href="/A132385/b132385.txt">Table of n, a(n) for n = 1..10000</a>

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

%e 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}.

%p f:= proc(n)

%p if numtheory:-phi(n) mod 3 = 0 then nops(select(isprime, {seq(i^3 mod n, i=0..n-1)}))

%p else numtheory:-pi(n-1) - nops(select(t -> t[2]>1, ifactors(n)[2]))

%p fi

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Jun 28 2018

%t 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 *)

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

%K easy,nonn,look

%O 1,5

%A _Jonathan Vos Post_, Nov 07 2007

%E More terms from _Stefan Steinerberger_, Nov 12 2007

%E Spelling/notation corrections by _Charles R Greathouse IV_, Mar 18 2010