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

Author

Zhi-Wei Sun, Jan 28 2014

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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}]