login
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).
11
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,8
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.
EXAMPLE
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.
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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Dec 12 2013
STATUS
approved