A233542 - OEIS

%I #25 Dec 13 2013 03:15:37

%S 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,

%T 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,

%U 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

%N 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).

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

%C (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.

%C (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.

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

%H Zhi-Wei Sun, <a href="/A233542/b233542.txt">Table of n, a(n) for n = 1..10000</a>

%e a(6) = 1 since 6 = 1^2 + 5 with phi(1^2)*phi(5) - 1 = 1*4 - 1 = 3 prime.

%e a(7) = 1 since 7 = 2^2 + 3 with phi(2^2)*phi(3) - 1 = 2*2 - 1 = 3 prime.

%e a(23) = 1 since 23 = 4^2 + 7 with phi(4^2)*phi(7) - 1 = 8*6 - 1 = 47 prime.

%e a(42) = 1 since 42 = 6^2 + 6 with phi(6^2)*phi(6) - 1 = 12*2 - 1 = 23 prime.

%e a(49) = 1 since 49 = 2^2 + 45 with phi(2^2)*phi(45) - 1 = 2*24 - 1 = 47 prime.

%e a(83) = 1 since 83 = 9^2 + 2 with phi(9^2)*phi(2) - 1 = 54*1 - 1 = 53 prime.

%e a(188) = 1 since 188 = 6^2 + 152 with phi(6^2)*phi(152) - 1 = 12*72 - 1 = 863 prime.

%e a(327) = 1 since 327 = 5^2 + 302 with phi(5^2)*phi(302) - 1 = 20*150 - 1 = 2999 prime.

%e a(557) = 1 since 557 = 12^2 + 413 with phi(12^2)*phi(413) - 1 = 48*348 - 1 = 16703 prime.

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

%t Table[a[n],{n,1,100}]

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

%K nonn

%O 1,8

%A _Zhi-Wei Sun_, Dec 12 2013