A234308 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.

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, 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, 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

Offset

1,6

Comments

Conjecture: (i) a(n) > 0 for all n > 4.

(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.

(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.

(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.

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.

Links

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Example

a(5) = 1 since phi(2^2)*phi(3) - 1 = 3 is a Sophie Germain prime.
a(10) = 1 since phi(1^2)*phi(9) - 1 = 5 is a Sophie Germain prime.
a(12) = 1 since phi(6^2)*phi(6) - 1 = 23 is a Sophie Germain prime.
a(30) = 1 since phi(2^2)*phi(28) - 1 = 23 is a Sophie Germain prime.
a(60) = 1 since phi(4^2)*phi(56) - 1 = 191 is a Sophie Germain prime.
a(75) = 1 since phi(14^2)*phi(61) - 1 = 5039 is a Sophie Germain prime.
a(95) = 1 since phi(30^2)*phi(65) - 1 = 11519 is a Sophie Germain prime.
a(106) = 1 since phi(22^2)*phi(84) - 1 = 5279 is a Sophie Germain prime.
a(110) = 1 since phi(9^2)*phi(101) - 1 = 5399 is a Sophie Germain prime.
a(156) = 1 since phi(27^2)*phi(129) - 1 = 40823 is a Sophie Germain prime.

Mathematica

SG[n_]:=PrimeQ[n]&&PrimeQ[2n+1]
a[n_]:=Sum[If[SG[EulerPhi[k^2]*EulerPhi[n-k]-1], 1, 0], {k, 1, n/2}]
Table[a[n], {n, 1, 100}]

Crossrefs

Cf. A000010, A000040, A014574, A005384, A233542, A233547, A233566, A233867, A233918, A234200, A234246

Sequence in context: A089607 A216637 A358643 * A050141 A274773 A132752

Adjacent sequences: A234305 A234306 A234307 * A234309 A234310 A234311

Keyword

nonn

Author

Zhi-Wei Sun, Dec 22 2013

Status

approved