Why can machine learning not recognise prime numbers? [closed]

Question

EDIT : I'm moving this to cstheory.stackexchange.com

I want a binary decision on an input sequence of integers. For a given n in the sequence output whether it is prime or not. Don't use AKS, don't use Miller Rabin, don't use trial division, don't even hard code in that the last digit must be 1,3,7,9 and that it must be congruent to 1 or 5 modulo 6.

Only use machine learning.

I don't know for certain, but I assess that the "general consensus" is/would be that machine learning techniques (neural networks, SVM, binary classifiers, clustering, Bayesian inference, etc) will be unable to crunch this problem?

What do people think?

Okay and secondly, what if we have some vector representation of the integers that carries some useful information, (unknown), are there any major in principle objections to machine learning being able to classify n as prime or composite, given we could "select the right features" so-to-speak?

Let's ignore the trivial case where the vector contains, say, the factorization of n.

Answer 1

Machine learning is not the answer of everything. Machine learning, as the name says, learns from data. The problem is that to learn something, we need a pattern in the data that we can teach the algorithm to learn.

By definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

The basic difficulty here is that the sequence of primes

2, 3, 5, 7, 11, 13, 17, 19, 23, . . .

behaves “unpredictably” or “randomly”, we do not have a (useful) exact formula for the nth prime number !

Even if you try to train an algorithm you will have something that will approximate a solution. You can't choose features good enough to predict the solution.

Let's say, the hard way is to train your model with these features:

• Any number ending with an even number (except 2) is not a prime number.
• Any number which all digits added equals 3, 6, 9 or its divisors is not a prime number.
• Any number ending with a 5 is not a prime number. (except 5)
• Any number with the same digits is not prime number. (unless ends with 1)

You end up with all prime numbers end with 1, 3, 7 or 9 but not all are prime numbers.

So there is no need to find an algorithm that will approximate something when we want an exact solution and when there is already an exact way to compute it.