

A350809


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



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,73,5    11     3
13: 2,73,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> pirem(n, p))(ithprime(i)), i=1..numtheory[pi](n))}):


PROG

(Java) // see link
(PARI)
nonempty(n, c)=my(p=factor(c)~[1, ]); sum(i=1, #p, cn<=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(pn%p for p in primerange(2, n+1))) # Chai Wah Wu, Mar 09 2022


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



