A350809 - OEIS

%I #39 Mar 09 2022 16:33:24

%S 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,

%T 10,9,10,10,10,10,11,11,12,12,13,13,14,13,13,12,13,13,14,13,14,14,14,

%U 14,15,14,15,16,16,15,15,15,16,16,17,17,18,17,18,18

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

%C 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).

%H Luc Rousseau, <a href="/A350809/b350809.txt">Table of n, a(n) for n = 1..20000</a>

%H Luc Rousseau, <a href="/A350809/a350809_2.java.txt">Java program.</a>

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

%e 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.

%e 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:

%e   n\c  4 | 6 | 8 | 9 |10 |12 |14 |15 |16 |18 |20 |21 |22 |24 |25 |26 | ...   a(n)

%e    1:    |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |         0

%e    2:  2 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |         1

%e    3:  2 | 3 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |         2

%e    4:    |2,3|   |   |   |   |   |   |   |   |   |   |   |   |   |   |         1

%e    5:    |2,3|   |   | 5 |   |   |   |   |   |   |   |   |   |   |   |         2

%e    6:        | 2 | 3 | 5 |   |   |   |   |   |   |   |   |   |   |   |         3

%e    7:        | 2 | 3 | 5 |   | 7 |   |   |   |   |   |   |   |   |   |         4

%e    8:            | 3 |2,5|   | 7 |   |   |   |   |   |   |   |   |   |         3

%e    9:                |2,5| 3 | 7 |   |   |   |   |   |   |   |   |   |         3

%e   10:                    |2,3| 7 | 5 |   |   |   |   |   |   |   |   |         3

%e   11:                    |2,3| 7 | 5 |   |   |   |   |11 |   |   |   |         4

%e   12:                        |2,7|3,5|   |   |   |   |11 |   |   |   |         3

%e   13:                        |2,7|3,5|   |   |   |   |11 |   |   |13 |         4

%e   14:                            |3,5| 2 |   |   | 7 |11 |   |   |13 |         5

%e   15:                                | 2 | 3 | 5 | 7 |11 |   |   |13 |         6

%e   16:                                    |2,3| 5 | 7 |11 |   |   |13 |         5

%e 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.

%p a:= n-> nops({seq((p-> p-irem(n, p))(ithprime(i)), i=1..numtheory[pi](n))}):

%p seq(a(n), n=1..74);  # _Alois P. Heinz_, Jan 31 2022

%o (Java) // see link

%o (PARI)

%o nonempty(n,c)=my(p=factor(c)~[1,]);sum(i=1,#p,c-n<=p[i])!=0

%o a(n)=my(s=0);forcomposite(c=n+1,2*n,s+=nonempty(n,c));s

%o for(n=1,100,print1(a(n),", "))

%o (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

%o (Python)

%o from sympy import primerange

%o def A350809(n): return len(set(p-n%p for p in primerange(2,n+1))) # _Chai Wah Wu_, Mar 09 2022

%Y Cf. A000720.

%K nonn

%O 1,3

%A _Luc Rousseau_, Jan 17 2022