login
Number of ways to write n = k + m with k > 0 and m > 2 such that p(k + phi(m)/2) is prime, where p(.) is the partition function (A000041) and phi(.) is Euler's totient function.
17

%I #15 Apr 05 2014 22:29:05

%S 0,0,0,1,2,3,4,5,5,4,4,4,2,2,3,5,4,2,4,2,3,2,3,2,3,1,0,3,1,1,2,1,2,0,

%T 1,2,1,1,4,2,1,4,2,1,2,3,3,3,1,0,4,2,4,1,1,2,2,3,2,2,0,2,2,1,2,2,1,1,

%U 2,2,4,2,1,0,1,3,1,0,2,4,3,1,6,2,2,1,2,4,3,1,2,6,2,3,2,2,2,2,3,3

%N Number of ways to write n = k + m with k > 0 and m > 2 such that p(k + phi(m)/2) is prime, where p(.) is the partition function (A000041) and phi(.) is Euler's totient function.

%C Conjecture: a(n) > 0 if n > 3 is not among 27, 34, 50, 61, 74, 78, 115, 120, 123, 127.

%C This implies that there are infinitely many primes in the range of the partition function p(n).

%H Zhi-Wei Sun, <a href="/A234470/b234470.txt">Table of n, a(n) for n = 1..6500</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(26) = 1 since 26 = 2 + 24 with p(2 + phi(24)/2) = p(6) = 11 prime.

%e a(54) = 1 since 54 = 27 + 27 with p(27 + phi(27)/2) = p(36) = 17977 prime.

%e a(73) = 1 since 73 = 1 + 72 with p(1 + phi(72)/2) = p(36) = 17977 prime.

%e a(110) = 1 since 110 = 65 + 45 with p(65 + phi(45)/2) = p(77) = 10619863 prime.

%e a(150) = 1 since 150 = 123 + 27 with p(123 + phi(27)/2) = p(132) = 6620830889 prime.

%e a(170) = 1 since 170 = 167 + 3 with p(167 + phi(3)/2) = p(168) = 228204732751 prime.

%t f[n_,k_]:=PartitionsP[k+EulerPhi[n-k]/2]

%t a[n_]:=Sum[If[PrimeQ[f[n,k]],1,0],{k,1,n-3}]

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

%Y Cf. A000010, A000040, A000041, A049575, A232504, A233307, A233346, A233918, A234200, A234246, A234309, A234337, A234344, A234347, A234359, A234360, A234451, A234475

%K nonn

%O 1,5

%A _Zhi-Wei Sun_, Dec 26 2013