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

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

Offset

1,3

Comments

Conjecture: a(n) > 0 for all n > 1.

See also the conjecture in A234388.

The conjecture is false. a(5962) = 0. - Jason Yuen, Nov 04 2024

Links

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

Example

a(7) = 2 since 2^1*(2^phi(6)-1) + 1 = 2*3 + 1 = 7 and 2^2*(2^phi(5)-1) + 1 = 4*15 + 1 = 61 are both prime.

Mathematica

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

Prog

(PARI) a(n) = sum(k=1, n-1, ispseudoprime(2^k*(2^eulerphi(n-k)-1)+1)) \\ Jason Yuen, Nov 04 2024

Crossrefs

Cf. A000010, A000040, A000079, A234309, A234310, A234337, A234344, A234346, A234347, A234359, A234360, A234361, A234388

Sequence in context: A308621 A308623 A115074 * A214749 A239330 A276273

Adjacent sequences: A234396 A234397 A234398 * A234400 A234401 A234402

Keyword

nonn

Author

Zhi-Wei Sun, Dec 25 2013

Status

approved