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

 

Logo
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, 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
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.

License Agreements, Terms of Use, Privacy Policy. .

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