5 ms·

I was pondering a few weeks back about the prospects of using ML/AI to find new ways to factor primes and if their is any sequence in primes and how to calculat

by Zenst 7y ago

I was pondering a few weeks back about the prospects of using ML/AI to find new ways to factor primes and if their is any sequence in primes and how to calculate them in a way that you input N and it will produce the Nth prime. That would be something.

m3kw9 7y ago
Can primes be estimated?
- drinfinity 7y ago
  Through my genius I've come to the conclusion that primes are related to entropy. There is no hope.
- OscarCunningham 7y ago
  The nth prime is about nlog(n).
klipt 7y ago
We can already do this approximately (asymptotically): https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem "The prime number theorem is equivalent to the statement that the nth prime number p_n satisfies p_n ~ nlog(n) the asymptotic notation meaning, again, that the relative error of this approximation approaches 0 as n increases without bound. For example, the 2^1017th prime number is 8512677386048191063, and (2^1017)log(2^1017) rounds to 7967418752291744388, a relative error of about 6.4%."
- eesmith 7y ago
  https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-prime/ https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-... is a recent blog posted titled "Bounds on the nth prime". It lists tighter upper and lower bounds: from math import log def f(n, k): ln = log(n); lln = log(log(n)) return ln + lln - 1 + (lln-2)/ln - ((lln**2) - 6*lln+k)/(2*ln*ln) With that in place, and once I realized that 2^1017 mean 2E17 not 2 to the power of 1017: >>> n = 2E17 >>> lo = n * f(n, 11.847) >>> hi = n * f(n, 10.273) >>> lo 8.512627944213742e+18 >>> hi 8.512727125430618e+18 >>> exact = 8512677386048191063 >>> (exact - lo)/exact 5.80802398678381e-06 >>> (exact - hi)/exact -5.842977499434444e-06
sweezyjeezy 7y ago
This is not really ML for what it's worth, it's gradient descent which is just basic optimisation, there is no training data or anything like that. re: using AI to learn to factor integers / find primes - probably not doable yet. There are neural networks that could model an algorithm that does it (memory networks, neural turing machine etc.). But any target algorithm would surely be too complicated for the neural net to converge towards it simply based on binary signals and gradient descent.
carapace 7y ago
There's something called "Deep Algebra" (no links handy sorry) where they are trying to parse LaTeX source of math papers to extract equations and figure out new stuff using ML.
fzort 7y ago
> you input N and it will produce the Nth prime Look for Willans' formula (there's a nice explanation in the book "Hacker's Delight").

by Zenst 7y ago

m3kw9 7y ago

Can primes be estimated?

drinfinity 7y ago
Through my genius I've come to the conclusion that primes are related to entropy. There is no hope.
OscarCunningham 7y ago
The nth prime is about nlog(n).

klipt 7y ago

We can already do this approximately (asymptotically): https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem "The prime number theorem is equivalent to the statement that the nth prime number p_n satisfies p_n ~ nlog(n) the asymptotic notation meaning, again, that the relative error of this approximation approaches 0 as n increases without bound. For example, the 2^1017th prime number is 8512677386048191063, and (2^1017)log(2^1017) rounds to 7967418752291744388, a relative error of about 6.4%."

eesmith 7y ago
https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-prime/ https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-... is a recent blog posted titled "Bounds on the nth prime". It lists tighter upper and lower bounds: from math import log def f(n, k): ln = log(n); lln = log(log(n)) return ln + lln - 1 + (lln-2)/ln - ((lln**2) - 6*lln+k)/(2*ln*ln) With that in place, and once I realized that 2^1017 mean 2E17 not 2 to the power of 1017: >>> n = 2E17 >>> lo = n * f(n, 11.847) >>> hi = n * f(n, 10.273) >>> lo 8.512627944213742e+18 >>> hi 8.512727125430618e+18 >>> exact = 8512677386048191063 >>> (exact - lo)/exact 5.80802398678381e-06 >>> (exact - hi)/exact -5.842977499434444e-06

sweezyjeezy 7y ago

This is not really ML for what it's worth, it's gradient descent which is just basic optimisation, there is no training data or anything like that. re: using AI to learn to factor integers / find primes - probably not doable yet. There are neural networks that could model an algorithm that does it (memory networks, neural turing machine etc.). But any target algorithm would surely be too complicated for the neural net to converge towards it simply based on binary signals and gradient descent.

carapace 7y ago

There's something called "Deep Algebra" (no links handy sorry) where they are trying to parse LaTeX source of math papers to extract equations and figure out new stuff using ML.

fzort 7y ago

> you input N and it will produce the Nth prime Look for Willans' formula (there's a nice explanation in the book "Hacker's Delight").