A236548 Number of ways to write n = k^2 + m with k > 0 and m > 0 such that phi(k^2) + prime(m) is prime, where phi(.) is Euler's totient function.

0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 3, 1, 0, 2, 2, 1, 2, 1, 0, 3, 0, 4, 1, 2, 1, 2, 2, 1, 2, 3, 3, 2, 1, 1, 2, 2, 2, 3, 4, 0, 2, 2, 4, 2, 1, 4, 3, 2, 2, 3, 3, 2, 1, 3, 2, 2, 5, 4, 3, 1, 0, 3, 4, 2, 1, 1, 3, 3, 2, 2, 2, 3, 3, 3, 5, 2, 3, 3, 2, 1, 4, 2, 4, 3, 4, 4, 3, 3, 3, 0

Offset

1,14

Comments

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

(ii) For any integer n > 4, there is a positive integer k < n with phi(k)^2 + prime(n-k)^2 prime.

Note that phi(k^2) (k = 1, 2, 3, ...) are pairwise distinct and this can be easily proved by induction.

Links

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

Example

a(16) = 1 since 16 = 3^2 + 7 with phi(3^2) + prime(7) = 6 + 17 = 23 prime.
a(611) = 1 since 611 = 22^2 + 127 with phi(22^2) + prime(127) = 220 + 709 = 929 prime.

Mathematica

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

Crossrefs

Cf. A000010, A000040, A233867, A233918, A234246, A236541.

Sequence in context: A161095 A276162 A118107 * A249949 A373246 A155798

Adjacent sequences: A236545 A236546 A236547 * A236549 A236550 A236551

Keyword

nonn

Author

Zhi-Wei Sun, Jan 28 2014

Status

approved