A237053 Smallest number k such that some subset of n+1..n+k can be summed and added to n to produce a prime.

2, 1, 0, 0, 3, 0, 1, 0, 1, 1, 3, 0, 3, 0, 1, 1, 3, 0, 1, 0, 1, 1, 3, 0, 4, 3, 1, 5, 3, 0, 1, 0, 3, 1, 3, 1, 1, 0, 3, 1, 3, 0, 3, 0, 1, 3, 4, 0, 1, 3, 1, 1, 3, 0, 1, 3, 1, 5, 3, 0, 5, 0, 3, 1, 3, 1, 4, 0, 1, 1, 6, 0, 4, 0, 1, 1, 3, 3, 1, 0, 3, 1, 3, 0, 3, 3, 1, 5, 3, 0, 1, 3, 3, 3, 3, 1, 1

Offset: 0

Author

Franklin T. Adams-Watters, Feb 03 2014

Keywords

• nonn
• changed

Comments

a(n) = 0 iff n is prime.

a(n) = 2 only for n=0; the only possible sums for k=2 are n+(n+2) = 2n+2, divisible by 2, and n+(n+1)+(n+2) = 3n+3, divisible by 3.

There are infinitely many 1's in the sequence; if p > 5 is a prime == 1 (mod 4), a((p-1)/2) = 1.

Conjecture: every nonnegative integer except 2 occurs infinitely often in the sequence.

Examples

			If n is prime, sum({n}) is prime, so we can take k = 0, whence n+1..n+0 is empty, so a(n) = 0.
6 is not prime, but 6+7 = 13 is prime, so a(6) = 1.
4 is not prime, and 4+5 is not prime, but 4+7 = 11 and 4+6+7 = 17 are prime; either of these suffices to make a(4) = 3.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..100000

Crossrefs

Cf. A000040, A005097, A104636, A077654, A089306.

Programs

Maple

b:= (n, i, t)-> isprime(n) or t>0 and
    (b(n, i+1, t-1) or b(n+i, i+1, t-1)):
a:= proc(n) local k;
      for k from 0 while not b(n, n+1, k) do od; k
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 07 2014

Mathematica

b[n_, i_, t_] := PrimeQ[n] || t > 0 && (b[n, i+1, t-1] || b[n+i, i+1, t-1]);
a[n_] := Module[{k}, For[k = 0, !b[n, n+1, k], k++]; k];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 04 2025, after Alois P. Heinz *)