5
$\begingroup$

As there are no patterns to prime numbers. Is there any way in which ML could predict it?

Improve this question
$\endgroup$
2
  • $\begingroup$ Well the gaps between the primes do tend to increase for larger numbers--put differently, primes appear with lower probability for increasingly large numbers--so there is some sort of weak pattern. $\endgroup$
    – Jake Westfall
    Commented May 29, 2018 at 4:33
  • 2
    $\begingroup$ There are plenty of patterns in the prime numbers. No prime number is even except 2. In any triple of odd numbers (n, n+2, n+4) at least one is divisible by three. Etc. $\endgroup$
    – Matthew Drury
    Commented May 29, 2018 at 4:47

2 Answers 2

Reset to default
3
$\begingroup$

Search for mathematical formulae (in a restricted alphabet) which satisfies the data. Basically, the hypothesis space is the set of all valid formulae.

For example, $\min \{z \in \mathbb{N}\ |\ (z > x) \wedge (\not \exists y: (1 < y < z) \wedge (y | z)) \}$ predicts the next prime after $x$.

Given that I've used 9 unique symbols here -- and a total of 19 symbols, this seems not too intractable a search space -- and there may be an even more compact solution.

The simplest algorithm would be a brute force search in ascending length, although you could get clever about it and try some sort of genetic algorithm. The search concludes when you find a formula which satisfies all of your test cases, at which point you should've learned a perfect predictor -- given that you use sufficiently many test cases, I doubt there is a shorter incorrect formula than the correct one.

Improve this answer
$\endgroup$
2
$\begingroup$

With which accuracy ? And with which (algorithmic) complexity ?

One can extract "features" from an integer (with a constant time) :

  • Does it end by 2 ?
  • Does it end by 5 ?
  • Does it end by ... ?
  • Is the sum of its number a multiple of 3 ?
  • Is the sum of its number a multiple of 11 ?

And train any model on these features (random forest...), the label being "is my number prime".

I guess with this you would be much better than a random classifier.

Now you can add more complex features (but they may be longer to evaluate than simply check from being prime)

  • Is it a square of an integer ?
  • Is it a Mersenne number ?
  • Does it have the form $3k+1$ ? (or any other form)
  • ...
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.