%I #11 Jan 24 2014 10:23:10
%S 0,1,2,3,3,4,6,4,4,7,6,5,9,5,5,9,8,9,6,5,9,7,8,9,6,8,7,4,7,8,12,8,6,7,
%T 8,7,11,5,6,11,7,10,5,9,4,10,9,7,8,9,8,8,8,9,7,7,5,10,7,3,12,5,7,7,9,
%U 8,8,5,14,6,9,4,10,2,7,7,8,2,7,9,10,7,8,5,7
%N a(n) = |{0 < k < n: (k+1)^{phi(n-k)} + k is prime}|, where phi(.) is Euler's totient function.
%C Conjecture: (i) a(n) > 0 for all n > 1. Also, for any n > 5 there is a positive integer k < n with (k+1)^{phi(n-k)/2} - k prime.
%C (ii) If n > 1, then k*(k+1)^{phi(n-k)} + 1 is prime for some 0 < k < n. If n > 3, then k*(k+1)^{phi(n-k)/2} - 1 is prime for some 0 < k < n.
%H Zhi-Wei Sun, <a href="/A234360/b234360.txt">Table of n, a(n) for n = 1..2500</a>
%e a(74) = 2 since (2+1)^{phi(72)} + 2 = 3^{24} + 2 =
%e 282429536483 and (14+1)^{phi(60)} + 14 = 15^{16} + 14 = 6568408355712890639 are both prime.
%t f[n_,k_]:=f[n,k]=(k+1)^(EulerPhi[n-k])+k
%t a[n_]:=Sum[If[PrimeQ[f[n,k]],1,0],{k,1,n-1}]
%t Table[a[n],{n,1,100}]
%Y Cf. A000010, A000040, A234309, A234310, A234337, A234344, A234346, A234347, A234359
%K nonn
%O 1,3
%A _Zhi-Wei Sun_, Dec 24 2013