A236548 - OEIS

%I #9 Jan 28 2014 15:25:51

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

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

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

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

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

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

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

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

%e a(16) = 1 since 16 = 3^2 + 7 with phi(3^2) + prime(7) = 6 + 17 = 23 prime.

%e a(611) = 1 since 611 = 22^2 + 127 with phi(22^2) + prime(127) = 220 + 709 = 929 prime.

%t p[n_,k_]:=PrimeQ[EulerPhi[k^2]+Prime[n-k^2]]

%t a[n_]:=Sum[If[p[n,k],1,0],{k,1,Sqrt[n-1]}]

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

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

%K nonn

%O 1,14

%A _Zhi-Wei Sun_, Jan 28 2014