A350809 a(n) = Card({ p - (n mod p) ; p prime, p <= n }).

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

Offset

1,3

Comments

Number of entries in the map that stores the computations state at step n in a variant of the Sieve of Eratosthenes. Upper bound: a(n) <= pi(n) = A000720(n).

Links

Luc Rousseau, Table of n, a(n) for n = 1..20000

Luc Rousseau, Java program.

Formula

a(n) = Card({ Min_{k integer, k*p > n} k*p ; p prime, p <= n }).

Example

When n=4, the primes <= n are p1=2 and p2=3; their least multiples > n are 6=3*p1 and 6=2*p2, but since they are equal, they only account for one, so a(4)=1.
In an array with rows numbered n and columns numbered c (the composite numbers), let us put in the (n,c)-cell the set of primes p <= n such that c is the least multiple of p > n:
  n\c  4 | 6 | 8 | 9 |10 |12 |14 |15 |16 |18 |20 |21 |22 |24 |25 |26 | ...   a(n)
   1:    |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |         0
   2:  2 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |         1
   3:  2 | 3 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |         2
   4:    |2,3|   |   |   |   |   |   |   |   |   |   |   |   |   |   |         1
   5:    |2,3|   |   | 5 |   |   |   |   |   |   |   |   |   |   |   |         2
   6:        | 2 | 3 | 5 |   |   |   |   |   |   |   |   |   |   |   |         3
   7:        | 2 | 3 | 5 |   | 7 |   |   |   |   |   |   |   |   |   |         4
   8:            | 3 |2,5|   | 7 |   |   |   |   |   |   |   |   |   |         3
   9:                |2,5| 3 | 7 |   |   |   |   |   |   |   |   |   |         3
  10:                    |2,3| 7 | 5 |   |   |   |   |   |   |   |   |         3
  11:                    |2,3| 7 | 5 |   |   |   |   |11 |   |   |   |         4
  12:                        |2,7|3,5|   |   |   |   |11 |   |   |   |         3
  13:                        |2,7|3,5|   |   |   |   |11 |   |   |13 |         4
  14:                            |3,5| 2 |   |   | 7 |11 |   |   |13 |         5
  15:                                | 2 | 3 | 5 | 7 |11 |   |   |13 |         6
  16:                                    |2,3| 5 | 7 |11 |   |   |13 |         5
Then in that array, pi(n) is the number of numbers in row n and a(n) is the number of nonempty cells in row n.

Maple

a:= n-> nops({seq((p-> p-irem(n, p))(ithprime(i)), i=1..numtheory[pi](n))}):
seq(a(n), n=1..74);  # Alois P. Heinz, Jan 31 2022

Prog

(Java) // see link
(PARI)
nonempty(n, c)=my(p=factor(c)~[1, ]); sum(i=1, #p, c-n<=p[i])!=0
a(n)=my(s=0); forcomposite(c=n+1, 2*n, s+=nonempty(n, c)); s
for(n=1, 100, print1(a(n), ", "))
(PARI) a2(n) = my(list = List()); forprime(p=2, n, k = n\p+1; listput(list, k*p)); #Set(list); \\ Michel Marcus, Jan 31 2022
(Python)
from sympy import primerange
def A350809(n): return len(set(p-n%p for p in primerange(2, n+1))) # Chai Wah Wu, Mar 09 2022

Crossrefs

Cf. A000720.

Sequence in context: A357564 A169809 A214962 * A366525 A360737 A076258

Adjacent sequences: A350806 A350807 A350808 * A350810 A350811 A350812

Keyword

nonn

Author

Luc Rousseau, Jan 17 2022

Status

approved