

A234309


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


15



0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 6, 5, 6, 5, 7, 7, 6, 7, 7, 8, 7, 7, 6, 6, 7, 9, 9, 6, 9, 12, 8, 6, 9, 9, 9, 8, 10, 8, 9, 6, 9, 8, 8, 10, 6, 8, 11, 8, 11, 8, 7, 10, 8, 7, 8, 7, 9, 9, 11, 11, 8, 8, 9, 10, 12, 7, 12, 10, 8, 5, 7, 9, 14, 9, 9, 9, 8, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,8


COMMENTS

Conjecture: (i) a(n) > 0 for all n > 5.
(ii) For any integer n > 1, 2^k +2^{phi(nk)}  1 is prime for some 0 < k < n, and 2^{sigma(j)} + 2^{phi(nj)}  1 is prime for some 0 < j < n, where sigma(j) is the sum of all positive divisors of j.
As phi(k) is even for any k > 2, part (i) of the conjecture implies that there are infinitely many primes of the form 4^a + 4^b  1 with a and b positive integers (cf. A234310). Note that any Mersenne prime greater than 3 has the form 2^{2a+1}  1 = 4^a + 4^a  1.


LINKS

ZhiWei Sun, Table of n, a(n) for n = 1..8000


EXAMPLE

a(6) = 1 since 2^{phi(3)} + 2^{phi(3)}  1 = 2^2 + 2^2  1 = 7 is prime.
a(7) = 1 since 2^{phi(3)} + 2^{phi(4)}  1 = 2^2 + 2^2  1 = 7 is prime.
a(8) = 2 since 2^{phi(3)} + 2^{phi(5)}  1 = 2^2 + 2^4  1 = 19 and 2^{phi(4)} + 2^{phi(4)}  1 = 2^2 + 2^2  1 = 7 are both prime.


MATHEMATICA

a[n_]:=Sum[If[PrimeQ[2^(EulerPhi[k])+2^(EulerPhi[nk])1], 1, 0], {k, 3, n/2}]
Table[a[n], {n, 1, 100}]


CROSSREFS

Cf. A000010, A000040, A000079, A000668, A233307, A233390, A233542, A233544, A233547, A233566, A233867, A233918, A234200, A234246, A234308, A234310, A234337, A234344, A234346, A234347, A234359, A234360, A234361
Sequence in context: A285879 A117695 A074794 * A306921 A048686 A278959
Adjacent sequences: A234306 A234307 A234308 * A234310 A234311 A234312


KEYWORD

nonn


AUTHOR

ZhiWei Sun, Dec 23 2013


STATUS

approved



