login
A233547
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.
15
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, 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, 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
OFFSET
1,7
COMMENTS
Conjecture: (i) a(n) > 0 for all n > 5.
(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.
(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.
Note that part (i) implies the twin prime conjecture. We have verified it for n up to 10^7.
EXAMPLE
a(6) = 1 since phi(1)*phi(5) = 1*4 = 4 with 4 - 1 and 4 + 1 twin primes.
a(8) = 1 since phi(1)*phi(7) = 1*6 = 6 with 6 - 1 and 6 + 1 twin primes.
a(16) = 1 since phi(2)*phi(14) = 1*6 = 6 with 6 - 1 and 6 + 1 twin primes.
a(17) = 1 since phi(3)*phi(14) = 2*6 = 12 with 12 - 1 and 12 + 1 twin primes.
a(19) = 1 since phi(1)*phi(18) = 1*6 = 6 with 6 - 1 and 6 + 1 twin primes.
a(23) = 1 since phi(2)*phi(21) = 1*12 = 12 with 12 - 1 and 12 + 1 twin primes.
a(25) = 1 since phi(11)*phi(14) = 10*6 = 60 with 60 - 1 and 60 + 1 twin primes.
a(26) = 1 since phi(7)*phi(19) = 6*18 = 108 with 108 - 1 and 108 + 1 twin primes.
a(42) = 1 since phi(14)*phi(28) = 6*12 = 72 with 72 - 1 and 72 +1 twin primes.
a(52) = 1 since phi(14)*phi(38) = 6*18 = 108 with 108 - 1 and 108 + 1 twin primes.
MATHEMATICA
TQ[n_]:=PrimeQ[n-1]&&PrimeQ[n+1]
a[n_]:=Sum[If[TQ[EulerPhi[k]*EulerPhi[n-k]], 1, 0], {k, 1, (n-1)/2}]
Table[a[n], {n, 1, 100}]
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Dec 12 2013
STATUS
approved