On the Prime Number Divisibility by Deep Learning
share
Certain tasks such as determining whether a given integer can be divided by 2, 3, or other prime numbers may be trivial for human beings, but can be less straightforward for computers in the absence of pre-specified algorithms. In this paper, we tested multiple deep learning architectures and feature engineering approaches, and evaluated the scenario of determining divisibility of large finite integers (up to 2^32) by small prime numbers. It turns out that, regardless of the network frameworks or the complexity of the network structures (CNN, RNN, Transformer, etc.), the ability to predict the prime number divisibility critically depends on the feature space fed into the deep learning models. We also evaluated commercially available Automated Machine Learning (AutoML) pipelines from Amazon, Google and Microsoft, and demonstrated that they failed to address this issue unless appropriately engineered features were provided. We further proposed a closed form solution to the problem using the ordinary linear regression on Fourier series basis vectors, and showed its success. Finally, we evaluated prompt-based learning using ChatGPT and demonstrated its success on small primes and apparent failures on larger primes. We conclude that feature engineering remains an important task to improve the performance, increase the interpretability, and reduce the complexity of machine learning/deep learning models, even in the era of AutoML and large-language models (LLMs).
READ FULL TEXT