3 ms·

Kind of surprising, my intuitive idea of primes is that they become rarer much faster, while there's really a ton of them.

leric 1y ago
[dead]
susam 1y ago
They indeed do become rarer. Plotting all the primes in a single row makes this apparent, like so: https://susam.net/primegrid.html#1-1-1000000 https://susam.net/primegrid.html#1-1-1000000 In fact, according to the celebrated prime number theorem, the number of primes less than or equal to n is asymptotic to n/log n, which means the density of primes near n is asymptotic to 1/log n. I have a small section about this at https://susam.net/journey-to-prime-number-theorem.html#prime-number-theorem https://susam.net/journey-to-prime-number-theorem.html#prime... if you want to read more about this. See also: https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem
- eru 1y ago
  Yes. > In fact, according to the celebrated prime number theorem, the number of primes less than or equal to n is asymptotic to n/log n, which means the density of primes near n is asymptotic to 1/log n. When written down as a string of digits, log n is another way to say 'proportional to the number of digits'. The number of digits grows fairly slowly, thus also the 'probability' of a number being prime drops very slowly.
kristopolous 1y ago
This is a very well researched topic https://en.m.wikipedia.org/wiki/Prime_number_theorem https://en.m.wikipedia.org/wiki/Prime_number_theorem
Someone 1y ago
That’s what ‘everybody’ thinks. I think that’s from reading so much about them being hard to find. They aren’t hard to find, though, it’s (as far as we know) hard to recognize integers as being primes. There are more prime numbers than there are squares of integers.
- eru 1y ago
  > They aren’t hard to find, though, it’s (as far as we know) hard to recognize integers as being primes. Depends on what you mean by 'hard'. It's easy in the sense that we have algorithms to decide whether a number is prime or composite that take time polynomial in the space it takes to write down your number (ie polynomial in log n).
- throw310822 1y ago
  > I think that’s from reading so much about them being hard to find More from the fact that each prime number makes all its multiples non-prime, so you'd expect this would accumulate quickly in making primes an increasingly rare find. Which is the case, but slower than intuition suggests.
- knome 1y ago
  >There are more prime numbers than there are squares of integers. all integers have a square, while not all integers are prime. in any given span, you'll see more primes than squares, however. more dense?
  - madcaptenor 1y ago
    For example, the number of primes less than n is around n/log(n) while the number of squares less than n is around sqrt(n), which is much smaller.
  - SamBam 1y ago
    They must both have the same cardinality, ℵ0, because they are both infinite subsets of the natural numbers, and so can each be laid out in order and paired with every natural number.
  - Someone 1y ago
    > all integers have a square, while not all integers are prime. That’s true, but I don’t see how that’s an argument. “All integers have a prime ‘the nth prime’, while not all integers are squares” similarly is true, but not an argument as to which set is denser.

leric 1y ago

[dead]

susam 1y ago

They indeed do become rarer. Plotting all the primes in a single row makes this apparent, like so: https://susam.net/primegrid.html#1-1-1000000 https://susam.net/primegrid.html#1-1-1000000 In fact, according to the celebrated prime number theorem, the number of primes less than or equal to n is asymptotic to n/log n, which means the density of primes near n is asymptotic to 1/log n. I have a small section about this at https://susam.net/journey-to-prime-number-theorem.html#prime-number-theorem https://susam.net/journey-to-prime-number-theorem.html#prime... if you want to read more about this. See also: https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem

eru 1y ago
Yes. > In fact, according to the celebrated prime number theorem, the number of primes less than or equal to n is asymptotic to n/log n, which means the density of primes near n is asymptotic to 1/log n. When written down as a string of digits, log n is another way to say 'proportional to the number of digits'. The number of digits grows fairly slowly, thus also the 'probability' of a number being prime drops very slowly.

kristopolous 1y ago

This is a very well researched topic https://en.m.wikipedia.org/wiki/Prime_number_theorem https://en.m.wikipedia.org/wiki/Prime_number_theorem

Someone 1y ago

That’s what ‘everybody’ thinks. I think that’s from reading so much about them being hard to find. They aren’t hard to find, though, it’s (as far as we know) hard to recognize integers as being primes. There are more prime numbers than there are squares of integers.

eru 1y ago
> They aren’t hard to find, though, it’s (as far as we know) hard to recognize integers as being primes. Depends on what you mean by 'hard'. It's easy in the sense that we have algorithms to decide whether a number is prime or composite that take time polynomial in the space it takes to write down your number (ie polynomial in log n).
throw310822 1y ago
> I think that’s from reading so much about them being hard to find More from the fact that each prime number makes all its multiples non-prime, so you'd expect this would accumulate quickly in making primes an increasingly rare find. Which is the case, but slower than intuition suggests.
knome 1y ago
>There are more prime numbers than there are squares of integers. all integers have a square, while not all integers are prime. in any given span, you'll see more primes than squares, however. more dense?
- madcaptenor 1y ago
  For example, the number of primes less than n is around n/log(n) while the number of squares less than n is around sqrt(n), which is much smaller.
- SamBam 1y ago
  They must both have the same cardinality, ℵ0, because they are both infinite subsets of the natural numbers, and so can each be laid out in order and paired with every natural number.
- Someone 1y ago
  > all integers have a square, while not all integers are prime. That’s true, but I don’t see how that’s an argument. “All integers have a prime ‘the nth prime’, while not all integers are squares” similarly is true, but not an argument as to which set is denser.