How to Build a Big Prime Number
quantamagazine.org
quantamagazine.org
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?
>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.
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.
IIRC, Gauss was the first to formalize this.
⅐ 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)3 is trivial because 9 is 3^2. 7 is a trick question because it happens to coincidentally be a factor of 999999.
At my current rate of progress with this hobby, I might have something interesting to report in another decade or so.
Mersenne primes, the largest known, are the base-2 case of these (in which case there is no "9"s distinction).
From bottom to top is the `a(n)` value.
A342730 a(n) = floor((frac(en) + 1) prime(n+1)).
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.
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?