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

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

Offset: 1

Author

Zhi-Wei Sun, Dec 12 2013

Keywords

• nonn

Comments

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

(ii) Any integer n > 7 can be written as k^2 + m with k > 0 and m > 0 such that phi(k)^2*phi(m) - 1 is prime.

(iii) If n > 1 is not equal to 36, then n can be written as k^2 + m with k > 0 and m > 0 such that sigma(k)^2*phi(m) + 1 is prime, where sigma(k) is the sum of all (positive) divisors of k.

We have verified part (i) of the conjecture for n up to 2*10^7.

Examples

			a(6) = 1 since 6 = 1^2 + 5 with phi(1^2)*phi(5) - 1 = 1*4 - 1 = 3 prime.
a(7) = 1 since 7 = 2^2 + 3 with phi(2^2)*phi(3) - 1 = 2*2 - 1 = 3 prime.
a(23) = 1 since 23 = 4^2 + 7 with phi(4^2)*phi(7) - 1 = 8*6 - 1 = 47 prime.
a(42) = 1 since 42 = 6^2 + 6 with phi(6^2)*phi(6) - 1 = 12*2 - 1 = 23 prime.
a(49) = 1 since 49 = 2^2 + 45 with phi(2^2)*phi(45) - 1 = 2*24 - 1 = 47 prime.
a(83) = 1 since 83 = 9^2 + 2 with phi(9^2)*phi(2) - 1 = 54*1 - 1 = 53 prime.
a(188) = 1 since 188 = 6^2 + 152 with phi(6^2)*phi(152) - 1 = 12*72 - 1 = 863 prime.
a(327) = 1 since 327 = 5^2 + 302 with phi(5^2)*phi(302) - 1 = 20*150 - 1 = 2999 prime.
a(557) = 1 since 557 = 12^2 + 413 with phi(12^2)*phi(413) - 1 = 48*348 - 1 = 16703 prime.
		

Links

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

Crossrefs

Cf. A000010, A000040, A000203, A233544, A233547, A233549.

Programs

Mathematica

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