login
Number of ordered ways to write n = k + m with 0 < k <= m such that the inverse of k mod prime(k) among 1, ..., prime(k) - 1 is prime and the inverse of m mod prime(m) among 1, ..., prime(m) - 1 is also prime.
6

%I #15 Jun 13 2014 17:35:26

%S 0,0,0,1,1,2,1,2,2,2,1,2,3,3,2,2,3,1,2,4,3,2,3,4,2,1,2,3,1,1,2,1,1,3,

%T 2,1,1,2,2,1,2,3,3,4,1,1,3,4,2,4,4,5,3,4,5,4,3,5,6,3,3,6,4,4,3,5,4,4,

%U 4,6,5,3,5,6,5,5,9,5,6,4

%N Number of ordered ways to write n = k + m with 0 < k <= m such that the inverse of k mod prime(k) among 1, ..., prime(k) - 1 is prime and the inverse of m mod prime(m) among 1, ..., prime(m) - 1 is also prime.

%C Conjecture: a(n) > 0 for all n > 3.

%C This implies that there are infinitely many positive integers k such that k*q == 1 (mod prime(k)) for some prime q < prime(k).

%H Zhi-Wei Sun, <a href="/A242753/b242753.txt">Table of n, a(n) for n = 1..10000</a>

%e a(11) = 1 since 11 = 4 + 7, 4*2 == 1 (mod prime(4)=7) with 2 prime, and 7*5 == 1 (mod Prime(7)=17) with 5 prime.

%e a(36) = 1 since 36 = 18 + 18, and 18*17 == 1 (mod 61) with 17 prime.

%e a(46) = 1 since 46 = 6 + 40, 6*11 == 1 (mod prime(6)= 13) with 11 prime, and 40*13 == 1 (mod prime(40)=173) with 13 prime.

%t p[n_]:=PrimeQ[PowerMod[n,-1,Prime[n]]]

%t Do[m=0;Do[If[p[k]&&p[n-k],m=m+1],{k,1,n/2}];Print[n," ",m];Continue,{n,1,80}]

%Y Cf. A000040, A000720, A242425, A242748, A242750, A242752, A242754, A242755.

%K nonn

%O 1,6

%A _Zhi-Wei Sun_, May 22 2014