The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 16 09:52 EDT 2024. Contains 371698 sequences. (Running on oeis4.)