%I #12 Jan 01 2024 19:27:14
%S 0,0,0,1,2,1,1,3,2,2,3,2,4,2,4,4,2,4,3,5,1,3,2,3,0,1,1,1,0,1,0,0,1,1,
%T 0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,2,0,0,0,1,1,1,1,0,1,0,1,2,0,1,2,1,
%U 1,2,1,2,3,2,8,2,1,2,2,3,3,1,2,7,0,2,3,3,4,5,7,3,4,1,9,1,4,3,1,2
%N Number of ways to write n = k + m with k > 0 and m > 0 such that p = phi(k) + phi(m)/2 + 1 and P(p-1) are both prime, where phi(.) is Euler's totient function and P(.) is the partition function (A000041).
%C Conjecture: (i) a(n) > 0 for all n > 727.
%C (ii) For the strict partition function q(.) (cf. A000009), any n > 93 can be written as k + m with k > 0 and m > 0 such that p = phi(k) + phi(m)/2 + 1 and q(p-1) - 1 are both prime.
%C (iii) If n > 75 is not equal to 391, then n can be written as k + m with k > 0 and m > 0 such that f(k,m) - 1, f(k,m) + 1 and q(f(k,m)) + 1 are all prime, where f(k,m) = phi(k) + phi(m)/2.
%C Part (i) of the conjecture implies that there are infinitely many primes p with P(p-1) prime.
%H Zhi-Wei Sun, <a href="/A234567/b234567.txt">Table of n, a(n) for n = 1..10000</a>
%H Z.-W. Sun, <a href="http://arxiv.org/abs/1402.6641">Problems on combinatorial properties of primes</a>, arXiv:1402.6641, 2014
%e a(21) = 1 since 21 = 6 + 15 with phi(6) + phi(15)/2 + 1 = 7 and P(6) = 11 both prime.
%e a(700) = 1 since 700 = 247 + 453 with phi(247) + phi(453)/2 + 1 = 367 and P(366) = 790738119649411319 both prime.
%e a(945) = 1 since 945 = 687 + 258 with phi(687) + phi(258)/2 + 1 = 499 and P(498) = 2058791472042884901563 both prime.
%t f[n_,k_]:=EulerPhi[k]+EulerPhi[n-k]/2
%t q[n_,k_]:=PrimeQ[f[n,k]+1]&&PrimeQ[PartitionsP[f[n,k]]]
%t a[n_]:=Sum[If[q[n,k],1,0],{k,1,n-1}]
%t Table[a[n],{n,1,100}]
%Y Cf. A000009, A000010, A000040, A000041, A234470, A234475, A234514, A234530.
%K nonn
%O 1,5
%A _Zhi-Wei Sun_, Dec 28 2013