A237121 Number of primes p < prime(n)/2 such that P(p) is a primitive root modulo prime(n), where P(.) is the partition function given by A000041.

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

Offset: 1

Author

Zhi-Wei Sun, Apr 22 2014

Keywords

• nonn

Comments

Conjecture: a(n) > 0 for all n > 2. In other words, for any prime p > 3, there is a prime q < p/2 with P(q) = A000041(q) a primitive root modulo p.

Examples

			a(14) = 1 since 3 is a prime smaller than prime(14)/2 = 43/2 and P(3) = 3 is a primitive root modulo prime(14) = 43.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A000040, A000041, A236308, A236966, A237112.

Programs

Mathematica

f[k_]:=PartitionsP[Prime[k]]
dv[n_]:=Divisors[n]
Do[m=0;Do[If[Mod[f[k],Prime[n]]==0,Goto[aa],Do[If[Mod[f[k]^(Part[dv[Prime[n]-1],i]),Prime[n]]==1,Goto[aa]],{i,1,Length[dv[Prime[n]-1]]-1}]];m=m+1;Label[aa];Continue,{k,1,PrimePi[(Prime[n]-1)/2]}];Print[n," ",m];Continue,{n,1,70}]