Answers.Body: <p>I'm an undergraduate researcher at Prairie View A&amp;M university. I just spent a few weeks tweaking an MLPRegressor model to predict the <span class="math-container">$n$</span>th prime number. It recently stumbled into a super low minimum, where the first <span class="math-container">$1000$</span> extrapolations outside of the training data produced error less than <span class="math-container">$.02$</span> percent. Even at <span class="math-container">$300000$</span> primes out, it was about <span class="math-container">$.5$</span> percent off. My model was simple: <span class="math-container">$10$</span> hidden layers, trained on a single processor for less than 2 hours.</p>
  <p>To me, it begs the question, &quot;Is there a reasonable function that produces the nth prime number?&quot; Right now, the algorithms become computationally very taxing for extreme <span class="math-container">$n$</span>. Check out the time gaps between the most recent largest primes discovered. Some of them are years apart. I know it's been proven that if such a function exists, it will not be polynomial.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T18:43:59.713Z
Answers.Text: Hi Cody, this wasn't long ago. But I would like to have a chat with you regarding the test you did. Would you be willing to live chat about what you did and what you perceived? I would like to see if there is a possibility to experiment further with this.
Answers.UserDisplayName: mjs
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-24T16:28:00.207Z
Answers.Text: Did you write this up? I'd love to read a summary if you have it.
Answers.UserDisplayName: cjm2671
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-22T22:04:59.370Z
Answers.Text: I suggest that you replicate the experiment on something else, for example, the divisible of 3 or other more complicated math predictions. Let see if something that we know has an equation can be predicted
Answers.UserDisplayName: Oren
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-28T21:23:52.587Z
Answers.LastActivityDate: 2020-11-14T13:53:36.487Z
Answers.LastEditDate: 2020-11-14T13:53:36.487Z
Answers.UserDisplayName: Cody K
Answers.Body: <p>In theory, a neural network can approximate <em>any</em> given function. This result is known as <a href="http://neuralnetworksanddeeplearning.com/chap4.html" rel="nofollow noreferrer">the universal approximation theorem</a>.</p>
  <p>However, if you train a network with the numbers <span class="math-container">$0$</span> to <span class="math-container">$N$</span>, you cannot guarantee that the network will classify numbers outside that range correctly (<span class="math-container">$n &gt; N$</span>).</p>
  <p>Such a network would be a regular feed-forward network (or <a href="https://en.wikipedia.org/wiki/Multilayer_perceptron" rel="nofollow noreferrer">MLP</a>) as recurrency does not add anything to the classification of the given input. The number of layers and nodes of that NN can only be found through trial and error.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-17T10:59:35.687Z
Answers.Text: Universal theorems applies to continuous functions on compact subsets. Prime/not prime is not such kind of function.
Answers.UserDisplayName: pasaba por aqui
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-27T09:00:33.610Z
Answers.Text: @pasabaporaqui: In this case the primeness function can be approximated well enough by a continuous function with peaks at the values of primes. So the NN might output 90% chance of being a prime for 6.93 - that is clearly nonsense, but if you discretised the inputs and outputs, you don't really care about what the NN would predict for non-integers. I think this answer is basically correct.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-05-26T17:33:08.773Z
Answers.LastActivityDate: 2020-11-14T13:23:19.610Z
Answers.LastEditDate: 2020-11-14T13:23:19.610Z
Answers.UserDisplayName: Thomas Wagenaar
Answers.Body: <p>From a purely theoretic standpoint, yes. Such a neural network(NN) can be manually constructed.</p>
  <p>A neuron is very similar to a logic gate. And it is definitely possible to use them as logic gate, replicate the structure of a CPU, and then perform any algorithm we already have. So in theory, YES. (Albeit obviously dumb to do so)</p>
  <p>The more complicated question is whether NN can &quot;learn&quot; to detect primes. Given that it is theoretically possible, and also that the human brain is literally NN, I am very inclined to guess that it is possible. But not with a feedforward network.</p>
  <p>Prime detection is not a very NN friendly task for two reasons:</p>
  <ol>
  <li>It is discrete maths, and NN are more fuzzy in nature.</li>
  <li>All currently known algorithm of prime detection requires some sort of loop / iteration, making them complexity &gt;= O(Bits). Where as feed forward NN is constant time complexity.</li>
  </ol>
  <p>The second difficulty will largely determine the shape of the final NN. Assuming there is no constant time detection algorithm of prime ever possible, the NN will not be feed forward. A recurrent network is required such that the NN can deal with loops.</p>
  <p>The first difficulty means that the NN will likely be rather complex and a lot of examples will be needed to overcome the inherent fuzziness. But that I guess is very much expected.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-29T07:44:04.740Z
Answers.LastActivityDate: 2022-09-29T07:55:34.467Z
Answers.LastEditDate: 2022-09-29T07:55:34.467Z
Answers.UserDisplayName: Shi Kin Ma
Answers.Body: <p>yes it is feasible, but consider that integer factorization problem is an <a href="https://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity" rel="nofollow noreferrer">NP-something problem</a> and <a href="https://en.wikipedia.org/wiki/BQP" rel="nofollow noreferrer">BQP problem</a>.</p>
  
  <p>because of this, it is impossible that a neural network purely based on classical computing finds prime number with 100% accuracy, unless P=NP.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-17T10:52:41.950Z
Answers.Text: As the question explains, check if a number is prime is not a NP problem.
Answers.UserDisplayName: pasaba por aqui
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-08T01:15:58.567Z
Answers.LastActivityDate: 2017-06-08T01:15:58.567Z
Answers.UserDisplayName: ncomputers
Answers.Body: <p>Early success on prime number testing via artificial networks is presented in <a href="https://cloudfront.escholarship.org/dist/prd/content/qt5sg7n4ww/qt5sg7n4ww.pdf" rel="nofollow noreferrer"><em>A Compositional Neural-network Solution to Prime-number Testing</em>, László Egri, Thomas R. Shultz, 2006</a>.</p>
  <p>The knowledge-based cascade-correlation (KBCC) network approach showed the most promise, although the practicality of this approach is eclipsed by other prime detection algorithms that usually begin by checking the least significant bit, immediately reducing the search by half, and then searching based other theorems and heuristics up to <span class="math-container">$floor(\sqrt{x})$</span>.  However the work was continued with <a href="http://www.psych.mcgill.ca/perpg/fac/shultz/personal/Recent_Publications_files/kbcc06.pdf" rel="nofollow noreferrer"><em>Knowledge Based Learning with KBCC</em>, Shultz et. al. 2006</a></p>
  <p>There are actually multiple sub-questions in this question.  First, let's write a more formal version of the question: &quot;Can an artificial network of some type converge during training to a behavior that will accurately test whether the input ranging from <span class="math-container">$0$</span> to <span class="math-container">$2^n-1$</span>, where <span class="math-container">$n$</span> is the number of bits in the integer representation, represents a prime number?&quot;</p>
  <ol>
  <li>Can it by simply memorizing the primes over the range of integers?</li>
  <li>Can it by learning to factor and apply the definition of a prime?</li>
  <li>Can it by learning a known algorithm?</li>
  <li>Can it by developing a novel algorithm of its own during training?</li>
  </ol>
  <p>The direct answer is yes, and it has already been done according to 1. above, but it was done by over-fitting, not learning a prime number detection method.  We know the human brain contains a neural network that can accomplish 2., 3., and 4., so if artificial networks are developed to the degree most think they can be, then the answer is yes for those.  There exists no counter-proof to exclude any of them from the range of possibilities as of this answer's writing.</p>
  <p>It is not surprising that work has been done to train artificial networks on prime number testing because of the importance of primes in discrete mathematics, its application to cryptography, and, more specifically, to cryptanalysis.  We can identify the importance of digital network detection of prime numbers in the research and development of intelligent digital security in works like <a href="https://www.researchgate.net/profile/Michael_Vrahatis/publication/228790268_A_first_study_of_the_neural_network_approach_to_the_RSA_cryptosystem/links/0fcfd50e4b1dad4c70000000.pdf" rel="nofollow noreferrer"><em>A First Study of the Neural Network Approach in the RSA Cryptosystem</em>, G.c. Meletius et. al., 2002</a>.  The tie of cryptography to the security of our respective nations is also the reason why not all of the current research in this area will be public.  Those of us that may have the clearance and exposure can only speak of what is not classified.</p>
  <p>On the civilian end, ongoing work in what is called novelty detection is an important direction of research.  Those like Markos Markou and Sameer Singh are <a href="https://www.sciencedirect.com/science/article/pii/S0165168403002020" rel="nofollow noreferrer">approaching novelty detection from the signal processing side</a>, and it is obvious to those that understand that artificial networks are essentially digital signal processors that have multi-point self tuning capabilities can see how their work applies directly to this question.  Markou and Singh write, &quot;There are a multitude of applications where novelty detection is extremely important including signal processing, computer vision, pattern recognition, data mining, and robotics.&quot;</p>
  <p>On the cognitive mathematics side, the development of a mathematics of surprise, such as <a href="https://infoscience.epfl.ch/record/223460/files/EPFL_TH7418.pdf" rel="nofollow noreferrer"><em>Learning with Surprise: Theory and Applications</em> (thesis), Mohammadjavad Faraji, 2016</a> may further what Ergi and Shultz began.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T10:21:10.127Z
Answers.LastActivityDate: 2020-11-16T22:26:02.337Z
Answers.LastEditDate: 2020-11-16T22:26:02.337Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>I am not looking for an efficient way to find primes (which of course is a <a href="https://en.wikipedia.org/wiki/AKS_primality_test" rel="noreferrer">solved problem</a>). This is more of a &quot;what if&quot; question.</p>
  <p>So, in theory, could you train a neural network to predict whether or not a given number <span class="math-container">$n$</span> is composite or prime? How would such a network be laid out?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-05T07:31:56.757Z
Comments.Text: If the primes follow a pattern and someone just happens to train a neural network with enough hidden nodes in order to define the classification boundary, I suppose it would work. However, we don't know if that classification exists and even if it did, we would have to prove what the boundary is in order to prove that the neural network did indeed find the correct pattern.
Comments.UserDisplayName: quintumnia
Tags: <neural-networks><prediction><primality-test>
Title: Could a neural network detect primes?
UserDisplayName: Fullk33
ThreadText: # Could a neural network detect primes?
  
  (Asked by: username_0 on 2017-05-26)
  
  I am not looking for an efficient way to find primes (which of course is a [solved problem](https://en.wikipedia.org/wiki/AKS_primality_test)). This is more of a "what if" question.
  
  So, in theory, could you train a neural network to predict whether or not a given number $n$ is composite or prime? How would such a network be laid out?
  
  **Tags:** neural-networks, prediction, primality-test
  > **Comments:**
  > **username_1**: If the primes follow a pattern and someone just happens to train a neural network with enough hidden nodes in order to define the classification boundary, I suppose it would work. However, we don't know if that classification exists and even if it did, we would have to prove what the boundary is in order to prove that the neural network did indeed find the correct pattern.  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_11 on 2018-08-16. Score: 19 | Accepted answer
  
  Early success on prime number testing via artificial networks is presented in [*A Compositional Neural-network Solution to Prime-number Testing*, László Egri, Thomas R. Shultz, 2006](https://cloudfront.escholarship.org/dist/prd/content/qt5sg7n4ww/qt5sg7n4ww.pdf).
  
  The knowledge-based cascade-correlation (KBCC) network approach showed the most promise, although the practicality of this approach is eclipsed by other prime detection algorithms that usually begin by checking the least significant bit, immediately reducing the search by half, and then searching based other theorems and heuristics up to $floor(\sqrt{x})$. However the work was continued with [*Knowledge Based Learning with KBCC*, Shultz et. al. 2006](http://www.psych.mcgill.ca/perpg/fac/shultz/personal/Recent_Publications_files/kbcc06.pdf)
  
  There are actually multiple sub-questions in this question. First, let's write a more formal version of the question: "Can an artificial network of some type converge during training to a behavior that will accurately test whether the input ranging from $0$ to $2^n-1$, where $n$ is the number of bits in the integer representation, represents a prime number?"
  
  1. Can it by simply memorizing the primes over the range of integers?
  2. Can it by learning to factor and apply the definition of a prime?
  3. Can it by learning a known algorithm?
  4. Can it by developing a novel algorithm of its own during training?
  
  The direct answer is yes, and it has already been done according to 1. above, but it was done by over-fitting, not learning a prime number detection method. We know the human brain contains a neural network that can accomplish 2., 3., and 4., so if artificial networks are developed to the degree most think they can be, then the answer is yes for those. There exists no counter-proof to exclude any of them from the range of possibilities as of this answer's writing.
  
  It is not surprising that work has been done to train artificial networks on prime number testing because of the importance of primes in discrete mathematics, its application to cryptography, and, more specifically, to cryptanalysis. We can identify the importance of digital network detection of prime numbers in the research and development of intelligent digital security in works like [*A First Study of the Neural Network Approach in the RSA Cryptosystem*, G.c. Meletius et. al., 2002](https://www.researchgate.net/profile/Michael_Vrahatis/publication/228790268_A_first_study_of_the_neural_network_approach_to_the_RSA_cryptosystem/links/0fcfd50e4b1dad4c70000000.pdf). The tie of cryptography to the security of our respective nations is also the reason why not all of the current research in this area will be public. Those of us that may have the clearance and exposure can only speak of what is not classified.
  
  On the civilian end, ongoing work in what is called novelty detection is an important direction of research. Those like Markos Markou and Sameer Singh are [approaching novelty detection from the signal processing side](https://www.sciencedirect.com/science/article/pii/S0165168403002020), and it is obvious to those that understand that artificial networks are essentially digital signal processors that have multi-point self tuning capabilities can see how their work applies directly to this question. Markou and Singh write, "There are a multitude of applications where novelty detection is extremely important including signal processing, computer vision, pattern recognition, data mining, and robotics."
  
  On the cognitive mathematics side, the development of a mathematics of surprise, such as [*Learning with Surprise: Theory and Applications* (thesis), Mohammadjavad Faraji, 2016](https://infoscience.epfl.ch/record/223460/files/EPFL_TH7418.pdf) may further what Ergi and Shultz began.
  
  
  ---
  
  ### Answer by username_2 on 2019-03-28. Score: 4
  
  I'm an undergraduate researcher at Prairie View A&M university. I just spent a few weeks tweaking an MLPRegressor model to predict the $n$th prime number. It recently stumbled into a super low minimum, where the first $1000$ extrapolations outside of the training data produced error less than $.02$ percent. Even at $300000$ primes out, it was about $.5$ percent off. My model was simple: $10$ hidden layers, trained on a single processor for less than 2 hours.
  
  To me, it begs the question, "Is there a reasonable function that produces the nth prime number?" Right now, the algorithms become computationally very taxing for extreme $n$. Check out the time gaps between the most recent largest primes discovered. Some of them are years apart. I know it's been proven that if such a function exists, it will not be polynomial.
  
  > **Comments:**
  > **username_3**: Hi Cody, this wasn't long ago. But I would like to have a chat with you regarding the test you did. Would you be willing to live chat about what you did and what you perceived? I would like to see if there is a possibility to experiment further with this.  
  > **username_4**: Did you write this up? I'd love to read a summary if you have it.  
  > **username_5**: I suggest that you replicate the experiment on something else, for example, the divisible of 3 or other more complicated math predictions. Let see if something that we know has an equation can be predicted  
  
  ---
  
  ### Answer by username_6 on 2017-05-26. Score: 3
  
  In theory, a neural network can approximate *any* given function. This result is known as [the universal approximation theorem](http://neuralnetworksanddeeplearning.com/chap4.html).
  
  However, if you train a network with the numbers $0$ to $N$, you cannot guarantee that the network will classify numbers outside that range correctly ($n > N$).
  
  Such a network would be a regular feed-forward network (or [MLP](https://en.wikipedia.org/wiki/Multilayer_perceptron)) as recurrency does not add anything to the classification of the given input. The number of layers and nodes of that NN can only be found through trial and error.
  
  > **Comments:**
  > **username_7**: Universal theorems applies to continuous functions on compact subsets. Prime/not prime is not such kind of function.  
  > **username_8**: @pasabaporaqui: In this case the primeness function can be approximated well enough by a continuous function with peaks at the values of primes. So the NN might output 90% chance of being a prime for 6.93 - that is clearly nonsense, but if you discretised the inputs and outputs, you don't really care about what the NN would predict for non-integers. I think this answer is basically correct.  
  
  ---
  
  ### Answer by username_9 on 2022-09-29. Score: 0
  
  From a purely theoretic standpoint, yes. Such a neural network(NN) can be manually constructed.
  
  A neuron is very similar to a logic gate. And it is definitely possible to use them as logic gate, replicate the structure of a CPU, and then perform any algorithm we already have. So in theory, YES. (Albeit obviously dumb to do so)
  
  The more complicated question is whether NN can "learn" to detect primes. Given that it is theoretically possible, and also that the human brain is literally NN, I am very inclined to guess that it is possible. But not with a feedforward network.
  
  Prime detection is not a very NN friendly task for two reasons:
  
  1. It is discrete maths, and NN are more fuzzy in nature.
  2. All currently known algorithm of prime detection requires some sort of loop / iteration, making them complexity >= O(Bits). Where as feed forward NN is constant time complexity.
  
  The second difficulty will largely determine the shape of the final NN. Assuming there is no constant time detection algorithm of prime ever possible, the NN will not be feed forward. A recurrent network is required such that the NN can deal with loops.
  
  The first difficulty means that the NN will likely be rather complex and a lot of examples will be needed to overcome the inherent fuzziness. But that I guess is very much expected.
  
  
  ---
  
  ### Answer by username_10 on 2017-06-08. Score: -3
  
  yes it is feasible, but consider that integer factorization problem is an [NP-something problem](https://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity) and [BQP problem](https://en.wikipedia.org/wiki/BQP).
  
  because of this, it is impossible that a neural network purely based on classical computing finds prime number with 100% accuracy, unless P=NP.
  
  > **Comments:**
  > **username_7**: As the question explains, check if a number is prime is not a NP problem.  
  
  ---
  
  