A234360 a(n) = |{0 < k < n: (k+1)^{phi(n-k)} + k is prime}|, where phi(.) is Euler's totient function.

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, 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, 8, 8, 5, 14, 6, 9, 4, 10, 2, 7, 7, 8, 2, 7, 9, 10, 7, 8, 5, 7

Offset: 1

Author

Zhi-Wei Sun, Dec 24 2013

Keywords

• nonn

Comments

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.

(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.

Examples

			a(74) = 2 since (2+1)^{phi(72)} + 2 = 3^{24} + 2 =
282429536483 and (14+1)^{phi(60)} + 14 = 15^{16} + 14 = 6568408355712890639 are both prime.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..2500

Crossrefs

Cf. A000010, A000040, A234309, A234310, A234337, A234344, A234346, A234347, A234359

Programs

Mathematica

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