A233867 a(n) = |{0 < m < 2*n: m is a square with 2*n - 1 - phi(m) prime}|, where phi(.) is Euler's totient function (A000010).

0, 1, 1, 1, 2, 1, 2, 1, 1, 3, 2, 1, 4, 2, 1, 3, 2, 1, 3, 3, 1, 4, 2, 1, 6, 2, 3, 4, 1, 3, 4, 2, 3, 3, 3, 2, 6, 3, 1, 6, 3, 3, 6, 2, 2, 6, 2, 4, 2, 3, 4, 5, 3, 3, 6, 4, 5, 7, 2, 3, 7, 3, 3, 3, 5, 1, 6, 2, 3, 6, 4, 5, 5, 4, 4, 7, 3, 4, 6, 4, 3, 5, 2, 2, 8, 5, 3, 5, 3, 6, 6, 4, 5, 5, 4, 4, 7, 2, 5, 9

Offset

1,5

Comments

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

(ii) For any odd number 2*n - 1 > 4, there is a positive integer k < 2*n such that 2*n - 1 - phi(k) and 2*n - 1 + phi(k) are both prime.

By Goldbach's conjecture, 2*n > 2 could be written as p + q with p and q both prime, and hence 2*n - 1 = p + (q - 1) = p + phi(q).

By induction, phi(k^2) (k = 1,2,3,...) are pairwise distinct.

Links

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

Example

a(29) = 1 since 2*29 - 1 = 37 + phi(5^2) with 37 prime.
a(39) = 1 since 2*39 - 1 = 71 + phi(3^2) with 71 prime.
a(66) = 1 since 2*66 - 1 = 89 + phi(7^2) with 89 prime.
a(128) = 1 since 2*128 - 1 = 223 + phi(8^2) with 223 prime.
a(182) = 1 since 2*182 - 1 = 331 + phi(8^2) with 331 prime.
a(413) = 1 since 2*413 - 1 = 823 + phi(2^2) with 823 prime.
a(171) = 3 since 2*171 - 1 = 233 + phi(18^2) = 257 + phi(14^2) = 293 + phi(12^2) with 233, 257, 293 all prime.

Mathematica

a[n_]:=Sum[If[PrimeQ[2n-1-EulerPhi[k^2]], 1, 0], {k, 1, Sqrt[2n-1]}]
Table[a[n], {n, 1, 100}]

Crossrefs

Cf. A000010, A000040, A002372, A002375, A233542, A233544, A233547, A233654, A233793, A233864.

Sequence in context: A135840 A228570 A173305 * A319814 A220272 A298917

Adjacent sequences: A233864 A233865 A233866 * A233868 A233869 A233870

Keyword

nonn

Author

Zhi-Wei Sun, Dec 17 2013

Status

approved