|
%I #11 Jan 03 2014 00:42:03
%S 0,0,0,0,1,3,1,3,3,1,3,1,2,2,3,2,1,2,1,1,1,2,2,4,3,3,1,2,5,1,2,2,4,1,
%T 2,2,3,3,3,3,3,3,7,5,1,4,4,2,3,2,3,2,1,5,1,3,4,2,2,1,2,2,4,4,4,3,5,4,
%U 3,2,6,3,6,5,1,6,2,4,3,5,3,4,5,3,4,4,3,6,3,2,6,2,3,6,1,9,3,4,7,3
%N a(n) = |{0 < k <= n/2: phi(k^2)*phi(n-k) - 1 is a Sophie Germain prime}|, where phi(.) is Euler's totient function.
%C Conjecture: (i) a(n) > 0 for all n > 4.
%C (ii) If n > 3, then phi(k^2)*phi(n-k) - 1 and phi(k^2)*phi(n-k) + 1 are both prime for some 0 < k < n, and also phi(j)^2*phi(n-j) - 1 and phi(j)^2*phi(n-j) + 1 are both prime for some 0 < j < n.
%C (iii) If n > 9 is not equal to 14, then |phi(k) - phi(n-k)|/2 is prime for some 0 < k < n, and also |phi(j) - phi(n-j)| - 1 and |phi(j) - phi(n-j)| + 1 are both prime for some 0 < j < n.
%C (iv) If n > 5, then sigma(k)*phi(n-k) + 1 is a square for some 0 < k < n, where sigma(k) is the sum of all positive divisors of k.
%C Note that part (i) of the conjecture implies that there are infinitely many Sophie Germain primes. We have verified part (i) for n up to 3*10^6.
%H Zhi-Wei Sun, <a href="/A234308/b234308.txt">Table of n, a(n) for n = 1..10000</a>
%e a(5) = 1 since phi(2^2)*phi(3) - 1 = 3 is a Sophie Germain prime.
%e a(10) = 1 since phi(1^2)*phi(9) - 1 = 5 is a Sophie Germain prime.
%e a(12) = 1 since phi(6^2)*phi(6) - 1 = 23 is a Sophie Germain prime.
%e a(30) = 1 since phi(2^2)*phi(28) - 1 = 23 is a Sophie Germain prime.
%e a(60) = 1 since phi(4^2)*phi(56) - 1 = 191 is a Sophie Germain prime.
%e a(75) = 1 since phi(14^2)*phi(61) - 1 = 5039 is a Sophie Germain prime.
%e a(95) = 1 since phi(30^2)*phi(65) - 1 = 11519 is a Sophie Germain prime.
%e a(106) = 1 since phi(22^2)*phi(84) - 1 = 5279 is a Sophie Germain prime.
%e a(110) = 1 since phi(9^2)*phi(101) - 1 = 5399 is a Sophie Germain prime.
%e a(156) = 1 since phi(27^2)*phi(129) - 1 = 40823 is a Sophie Germain prime.
%t SG[n_]:=PrimeQ[n]&&PrimeQ[2n+1]
%t a[n_]:=Sum[If[SG[EulerPhi[k^2]*EulerPhi[n-k]-1],1,0],{k,1,n/2}]
%t Table[a[n],{n,1,100}]
%Y Cf. A000010, A000040, A014574, A005384, A233542, A233547, A233566, A233867, A233918, A234200, A234246
%K nonn
%O 1,6
%A _Zhi-Wei Sun_, Dec 22 2013
|
