A242748 Number of ordered ways to write n = k + m with 0 < k <= m such that k is a primitive root modulo prime(k) and m is a primitive root modulo prime(m).

0, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 3, 3, 3, 1, 3, 3, 2, 2, 3, 3, 2, 1, 2, 3, 3, 2, 3, 3, 3, 3, 1, 2, 3, 3, 3, 2, 1, 4, 2, 3, 3, 3, 3, 2, 5, 3, 4, 2, 4, 6, 6, 1, 5, 4, 6, 7, 4, 6, 4, 6, 3, 6, 3, 7, 5, 5, 6, 7, 4, 6, 8, 5, 6, 4, 6, 4, 8, 3, 7

Offset: 1

Author

Zhi-Wei Sun, May 21 2014

Keywords

• nonn

Comments

Conjecture: a(n) > 0 for all n > 1.

This implies that there are infinitely many positive integers k which is a primitive root modulo prime(k).

Examples

			a(6) = 1 since 6 = 3 + 3 with 3 a primitive root modulo prime(3) = 5.
a(7) = 1 since 7 = 1 + 6 with 1 a primitive root modulo prime(1) = 2 and 6 a primitive root modulo prime(6) = 13.
a(15) = 1 since 15 = 2 + 13 with 2 a primitive root modulo prime(2) = 3 and 13 a primitive root modulo prime(13) = 41.
a(38) = 1 since 38 = 10 + 28 with 10 a primitive root modulo prime(10) = 29 and 28 a primitive root modulo prime(28) = 107.
a(53) = 1 since 53 = 3 + 50 with 3 a primitive root modulo prime(3) = 5 and 50 a primitive root modulo prime(50) = 229.
		

Links

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

Crossrefs

Cf. A000040, A000720, A242750, A242752.

Programs

Mathematica

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