

A234308


a(n) = {0 < k <= n/2: phi(k^2)*phi(nk)  1 is a Sophie Germain prime}, where phi(.) is Euler's totient function.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


COMMENTS

Conjecture: (i) a(n) > 0 for all n > 4.
(ii) If n > 3, then phi(k^2)*phi(nk)  1 and phi(k^2)*phi(nk) + 1 are both prime for some 0 < k < n, and also phi(j)^2*phi(nj)  1 and phi(j)^2*phi(nj) + 1 are both prime for some 0 < j < n.
(iii) If n > 9 is not equal to 14, then phi(k)  phi(nk)/2 is prime for some 0 < k < n, and also phi(j)  phi(nj)  1 and phi(j)  phi(nj) + 1 are both prime for some 0 < j < n.
(iv) If n > 5, then sigma(k)*phi(nk) + 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

ZhiWei 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[nk]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: A279340 A089607 A216637 * A050141 A274773 A132752
Adjacent sequences: A234305 A234306 A234307 * A234309 A234310 A234311


KEYWORD

nonn


AUTHOR

ZhiWei Sun, Dec 22 2013


STATUS

approved



