A233547 - OEIS

%I #9 Dec 12 2013 10:00:11

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

%T 5,2,5,5,3,5,3,1,5,3,7,6,3,2,4,7,5,1,4,6,6,5,2,4,6,9,9,6,8,5,8,8,6,6,

%U 9,4,8,6,8,5,7,9,7,9,5,7,3,9,5,6,7,7,10,5,12,7,5,7,5,7,5,7,8,4,7,13

%N a(n) = |{0 < k < n/2: phi(k)*phi(n-k) - 1 and phi(k)*phi(n-k) + 1 are both prime}|, where phi(.) is Euler's totient function.

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

%C (ii) For any n > 3, sigma(k)*phi(n-k) - 1 and sigma(k)*phi(n-k) + 1 are both prime for some 0 < k < n, where sigma(k) is the sum of all (positive) divisors of k.

%C (iii) For any n > 5 not equal to 35, there is a positive integer k < n such that phi(k)*phi(n-k) - 1 is a Sophie Germain prime.

%C Note that part (i) implies the twin prime conjecture. We have verified it for n up to 10^7.

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

%e a(6) = 1 since phi(1)*phi(5) = 1*4 = 4 with 4 - 1 and 4 + 1 twin primes.

%e a(8) = 1 since phi(1)*phi(7) = 1*6 = 6 with 6 - 1 and 6 + 1 twin primes.

%e a(16) = 1 since phi(2)*phi(14) = 1*6 = 6 with 6 - 1 and 6 + 1 twin primes.

%e a(17) = 1 since phi(3)*phi(14) = 2*6 = 12 with 12 - 1 and 12 + 1 twin primes.

%e a(19) = 1 since phi(1)*phi(18) = 1*6 = 6 with 6 - 1 and 6 + 1 twin primes.

%e a(23) = 1 since phi(2)*phi(21) = 1*12 = 12 with 12 - 1 and 12 + 1 twin primes.

%e a(25) = 1 since phi(11)*phi(14) = 10*6 = 60 with 60 - 1 and 60 + 1 twin primes.

%e a(26) = 1 since phi(7)*phi(19) = 6*18 = 108 with 108 - 1 and 108 + 1 twin primes.

%e a(42) = 1 since phi(14)*phi(28) = 6*12 = 72 with 72 - 1 and 72 +1 twin primes.

%e a(52) = 1 since phi(14)*phi(38) = 6*18 = 108 with 108 - 1 and 108 + 1 twin primes.

%t TQ[n_]:=PrimeQ[n-1]&&PrimeQ[n+1]

%t a[n_]:=Sum[If[TQ[EulerPhi[k]*EulerPhi[n-k]],1,0],{k,1,(n-1)/2}]

%t Table[a[n],{n,1,100}]

%Y Cf. A000010, A000040, A001359, A005384, A006512, A014574, A232270, A233544.

%K nonn

%O 1,7

%A _Zhi-Wei Sun_, Dec 12 2013