A236483 a(n) = |{0 < k < n-2: p(k) + 2^(phi(n-k)/2) is prime}|, where p(.) is the partition function (A000041) and phi(.) is Euler's totient function.

0, 0, 0, 1, 1, 2, 3, 2, 3, 5, 4, 3, 6, 1, 6, 5, 7, 7, 5, 6, 4, 6, 5, 4, 7, 4, 6, 5, 5, 6, 9, 6, 13, 6, 10, 5, 6, 7, 4, 10, 9, 12, 6, 12, 3, 8, 8, 9, 11, 8, 11, 7, 11, 7, 8, 8, 9, 8, 10, 10, 9, 9, 14, 8, 15, 8, 11, 13, 12, 12, 15, 13, 12, 8, 11, 12, 10, 11, 12, 12, 13, 8, 12, 14, 8, 13, 10, 8, 8, 12, 8, 15, 11, 10, 11, 11, 13, 14, 10, 8

Offset: 1

Author

Zhi-Wei Sun, Jan 27 2014

Keywords

• nonn

Comments

Conjecture: (i) a(n) > 0 for all n > 3.

(ii) For any integer n > 1, there is a positive integer k < n such that p(k)*2^(phi(n-k)) + 1 is prime.

(iii) For any integer n > 1 not among 6, 23, 42, there is a positive integer k < n such that 2*p(k) + p(n-k) is prime.

Clearly, part (i) of the conjecture implies that there are infinitely many primes of the form p(k) + 2^m, where k and m are positive integers.

Examples

			a(14) = 1 since p(7) + 2^(phi(7)/2) = 15 + 2^3 = 23 is prime.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
• Z.-W. Sun, Problems on combinatorial properties of primes, arXiv:1402.6641, 2014

Crossrefs

Cf. A000010, A000040, A000041, A000079, A234337.

Programs

Mathematica

a[n_]:=Sum[If[PrimeQ[PartitionsP[k]+2^(EulerPhi[n-k]/2)],1,0],{k,1,n-3}]
Table[a[n],{n,1,100}]