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

0, 0, 1, 1, 1, 1, 2, 0, 2, 1, 3, 3, 1, 1, 2, 1, 2, 7, 4, 2, 1, 1, 1, 4, 3, 4, 2, 4, 3, 3, 4, 7, 3, 3, 5, 5, 5, 5, 4, 3, 6, 7, 5, 5, 5, 3, 7, 7, 5, 2, 7, 6, 4, 5, 5, 7, 10, 9, 8, 8, 4, 7, 5, 11, 14, 7, 12, 11, 9, 6

Offset: 1

Author

Zhi-Wei Sun, Aug 27 2015

Keywords

• nonn

Comments

Conjecture: (i) a(n) > 0 except for n = 1, 2, 8.

(ii) Any positive rational number r not equal to 1 can be written as m/n, where m and n are positive integers such that prime(m) is a primitive root modulo prime(n) and also prime(n) is a primitive root modulo prime(m).

Examples

			a(7) = 2 since 7 = 1+6 = 3+4, prime(1) = 2 is a primitive root modulo prime(6) = 13 and 13 is a primitive root modulo 2, also prime(3) = 5 is a primitive root modulo prime(4) = 7 and 7 is a primitive root modulo 5.
a(22) = 1 since 22 = 4+18, prime(4)= 7 is a primitive root modulo prime(18) = 61 and 61 is a primitive root modulo 7.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..3000
• Zhi-Wei Sun, Checking part (ii) of the conjecture for r = a/b with 1 <= a < b <= 100
• Zhi-Wei Sun, New observations on primitive roots modulo primes, arXiv:1405.0290 [math.NT], 2014.

Crossrefs

Cf. A000040, A242748, A259492.

Programs

Mathematica

f[n_]:=Prime[n]
Dv[n_]:=Divisors[n]
LL[n_]:=Length[Dv[n]]
Do[r=0;Do[Do[If[Mod[f[k]^(Part[Dv[f[n-k]-1],i])-1,f[n-k]]==0,Goto[bb]],{i,1,LL[f[n-k]-1]-1}];Do[If[Mod[f[n-k]^(Part[Dv[f[k]-1],i])-1,f[k]]==0,Goto[bb]],{i,1,LL[f[k]-1]-1}];
r=r+1;Label[bb];Continue,{k,1,(n-1)/2}];Print[n," ",r];Continue,{n,1,70}]