4 ms·

How to Build a Big Prime Number

40 points by rolph 3y ago

deleted 3y ago
[deleted]
yanslookup 3y ago
> You could use randomness and find one by guessing, but the method is inconsistent — you run the risk of generating a different prime every time. I'm having a hard time reading this sentence. Obviously generating a different prime would be awesome and not a risk if finding primes is your goal. What are they trying to say here?
- danbruc 3y ago
  A relaxed version of find me the next prime after X, find me some prime a bit larger than X. And just as the next prime after X will always yield the same answer, they want some prime a bit larger than X to also always yield the same answer.
danbruc 3y ago
It's not really clear to me what they invented. You basically have two computational options, both with drawbacks. You could use randomness and find one by guessing, but the method is inconsistent — you run the risk of generating a different prime every time. Or you could use a more reliable, deterministic algorithm, but at a heavy computational cost. If you use a pseudorandom number generator and fix the seed, then you get a deterministic result. But I guess we can not prove that replacing random numbers with pseudorandom ones does not alter the behavior of the algorithm. So they came up with something clever where they use true random numbers to find a primes and are able to proof this while at the same time mostly canceling out the effect of the random numbers used so that the prime number they get pack is the same every time with high probability. Or am I misunderstanding the article?
- jksk61 3y ago
  I guess that algorithm used to get the prime number they want to generate, involves sampling from some kind of distribution such that by Law of large numbers it converges in probability to the same thing (but of course much more advanced than that).
- eklitzke 3y ago
  According to the article, the original motivating problem posed by Terence Tao is to develop an algorithm that deterministically generates an N-digit prime in polynomial time. The article says of the new algorithm: >The algorithm works for infinitely many input lengths, but it doesn’t cover all lengths of digits. There may still be some values of n out there for which the algorithm doesn’t deterministically produce a prime. So the advancement here is that they've "nearly solved" the problem posed by Tao, and maybe (hopefully) someone else will be able to build on their solution to fully solve the problem.
deleted 3y ago
[deleted]
m3047 3y ago
Haven't automated this yet but I've noticed, playing around with primes, that e.g. 1/17 is a repeating decimal (that means base 10) of length n-1 or 16. Others such as 7, 11, 13, 31 are shorter and I have a working theory (not a proof) for this, that's how I backed into the first observation. Haven't automated it (yet), I've been toying with it one step more modern than pencil and paper. Not really related to the article except that it is apparent to me at this point that generating the sequences can be automated. It started as a hobby to see if e.g. telephone numbers could be represented as fractions yielding repeating decimals.
- o11c 3y ago
  You might want to look into "repunits" (though we really do want the 9s, actually) and the Cunningham Project. Mersenne primes, the largest known, are the base-2 case of these (in which case there is no "9"s distinction).
- pretzellogician 3y ago
  Yes! This comes from the multiplicative order of 10 modulo the number: https://mathworld.wolfram.com/DecimalPeriod.html https://mathworld.wolfram.com/DecimalPeriod.html IIRC, Gauss was the first to formalize this.
  - m3047 3y ago
    Thank you! I have a weird story about Gauss. I was working on my motorcycle late at night with too little sleep and Gauss appeared in my head and was asking questions. Also gave me an answer to solve a "field repair" fab problem (damn, it worked!) and told me it was related to chain mail somehow, but I didn't understand.
- Someone 3y ago
  > Others such as 7, 11, 13, 31 are shorter ⅐ has maximum possible length of n-1 (142857) > to see if e.g. telephone numbers could be represented as fractions yielding repeating decimals. Every number can. For example, phone number 15224787 would yield n = 0.1522478715224787[15224787] ⇒ n × 10⁸ = 15224787.1522478715224787[15224787] = 15224787 + n ⇒ n × (10⁸ - 1) = 15224787 ⇒ n = 15224787 / 99999999 = 1691643 / 11111111 (I didn’t check whether further simplifications are possible)
deleted 3y ago
[deleted]
neoneye2 3y ago
A while ago I made a nice plot of how the prime numbers are distributed. Starting out somewhat wobbly, but getting more evenly spaced for bigger N's. Using irrational numbers and it would often yield amazing patterns. https://oeis.org/A342730/a342730.png https://oeis.org/A342730/a342730.png However my thing is no solution for finding primes, but maybe it can narrow down the search space.
- 8n4vidtmkvmk 3y ago
  What are the axes?
  - neoneye2 3y ago
    From left to right is the `N` value. From bottom to top is the `a(n)` value. A342730 a(n) = floor((frac(en) + 1) prime(n+1)). https://oeis.org/A342730 https://oeis.org/A342730 Knowing the N value and the previous nearby prime points, I guess it's possible to narrow down the search range for the next prime value.
nubinetwork 3y ago
[flagged]

40 points by rolph 3y ago

deleted 3y ago

[deleted]

> You could use randomness and find one by guessing, but the method is inconsistent — you run the risk of generating a different prime every time. I'm having a hard time reading this sentence. Obviously generating a different prime would be awesome and not a risk if finding primes is your goal. What are they trying to say here?

danbruc 3y ago
A relaxed version of find me the next prime after X, find me some prime a bit larger than X. And just as the next prime after X will always yield the same answer, they want some prime a bit larger than X to also always yield the same answer.

danbruc 3y ago

It's not really clear to me what they invented. You basically have two computational options, both with drawbacks. You could use randomness and find one by guessing, but the method is inconsistent — you run the risk of generating a different prime every time. Or you could use a more reliable, deterministic algorithm, but at a heavy computational cost. If you use a pseudorandom number generator and fix the seed, then you get a deterministic result. But I guess we can not prove that replacing random numbers with pseudorandom ones does not alter the behavior of the algorithm. So they came up with something clever where they use true random numbers to find a primes and are able to proof this while at the same time mostly canceling out the effect of the random numbers used so that the prime number they get pack is the same every time with high probability. Or am I misunderstanding the article?

jksk61 3y ago
I guess that algorithm used to get the prime number they want to generate, involves sampling from some kind of distribution such that by Law of large numbers it converges in probability to the same thing (but of course much more advanced than that).
eklitzke 3y ago
According to the article, the original motivating problem posed by Terence Tao is to develop an algorithm that deterministically generates an N-digit prime in polynomial time. The article says of the new algorithm: >The algorithm works for infinitely many input lengths, but it doesn’t cover all lengths of digits. There may still be some values of n out there for which the algorithm doesn’t deterministically produce a prime. So the advancement here is that they've "nearly solved" the problem posed by Tao, and maybe (hopefully) someone else will be able to build on their solution to fully solve the problem.

deleted 3y ago

[deleted]

m3047 3y ago

Haven't automated this yet but I've noticed, playing around with primes, that e.g. 1/17 is a repeating decimal (that means base 10) of length n-1 or 16. Others such as 7, 11, 13, 31 are shorter and I have a working theory (not a proof) for this, that's how I backed into the first observation. Haven't automated it (yet), I've been toying with it one step more modern than pencil and paper. Not really related to the article except that it is apparent to me at this point that generating the sequences can be automated. It started as a hobby to see if e.g. telephone numbers could be represented as fractions yielding repeating decimals.

o11c 3y ago
You might want to look into "repunits" (though we really do want the 9s, actually) and the Cunningham Project. Mersenne primes, the largest known, are the base-2 case of these (in which case there is no "9"s distinction).
pretzellogician 3y ago
Yes! This comes from the multiplicative order of 10 modulo the number: https://mathworld.wolfram.com/DecimalPeriod.html https://mathworld.wolfram.com/DecimalPeriod.html IIRC, Gauss was the first to formalize this.
- m3047 3y ago
  Thank you! I have a weird story about Gauss. I was working on my motorcycle late at night with too little sleep and Gauss appeared in my head and was asking questions. Also gave me an answer to solve a "field repair" fab problem (damn, it worked!) and told me it was related to chain mail somehow, but I didn't understand.
Someone 3y ago
> Others such as 7, 11, 13, 31 are shorter ⅐ has maximum possible length of n-1 (142857) > to see if e.g. telephone numbers could be represented as fractions yielding repeating decimals. Every number can. For example, phone number 15224787 would yield n = 0.1522478715224787[15224787] ⇒ n × 10⁸ = 15224787.1522478715224787[15224787] = 15224787 + n ⇒ n × (10⁸ - 1) = 15224787 ⇒ n = 15224787 / 99999999 = 1691643 / 11111111 (I didn’t check whether further simplifications are possible)

deleted 3y ago

[deleted]

neoneye2 3y ago

A while ago I made a nice plot of how the prime numbers are distributed. Starting out somewhat wobbly, but getting more evenly spaced for bigger N's. Using irrational numbers and it would often yield amazing patterns. https://oeis.org/A342730/a342730.png https://oeis.org/A342730/a342730.png However my thing is no solution for finding primes, but maybe it can narrow down the search space.

8n4vidtmkvmk 3y ago
What are the axes?
- neoneye2 3y ago
  From left to right is the `N` value. From bottom to top is the `a(n)` value. A342730 a(n) = floor((frac(en) + 1) prime(n+1)). https://oeis.org/A342730 https://oeis.org/A342730 Knowing the N value and the previous nearby prime points, I guess it's possible to narrow down the search range for the next prime value.

nubinetwork 3y ago

[flagged]