# On the Prime Number Divisibility by Deep Learning

Da Wu, Jingye Yang
Department of Mathematics
University of Pennsylvania
Philadelphia, PA 19104, USA
<EMAIL_ADDRESS>
&Mian Umair Ahsan, Kai Wang
Department of Pathology
Children’s Hospital of Philadelpha
University of Pennsylvania
Philadelphia, PA 19104, USA
<EMAIL_ADDRESS>

###### Abstract

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).

_K_ eywords Feature engineering $\cdot$ Prime number divisibility $\cdot$
Machine learning $\cdot$ Deep learning $\cdot$ ChatGPT

##  1 Introduction

Whether a given integer (such as $74$ or $243589$) can be divided by a
specific prime number (such as $2$ or $3$) remains an interesting practical
problem. In its simpliest form, determining whether an integer is odd or even
is trivial for human; one only needs to look at the unit digit: it is even if
the unit digit belongs to $\\{0,2,4,6,8\\}$ and it is odd otherwise. Similar
rule works when checking the divisibility of an integer by $5$: one only needs
to check if the unit digit is $5$ or $0$.

Classifying integers based on their residues when divided by $3$ is slightly
more difficult. Given an integer $x=\overline{CBA}$ whose digits are $A$, $B$,
$C$ from the smallest to the largest, i.e., $x=A+B*10+C*100$, we have
$x\equiv(99*C+9*B+C+B+A)\equiv(C+B+A)\mod 3$. By the exact same argument, an
integer is divisible by $3$ if and only if the sum of its numerical digits is
divisible by $3$. For instance, $123$ is divisible by $3$ since $1+2+3=6$ is
divisible by $3$, and $59$ is not divisible by $3$ since $5+9=14$ is not
divisible by $3$. The same rule applies when checking if an integer is
divisible by $9$. Based on this rule, one can quickly develop a simple
algorithm for human to classify integers mod $3$.

However, for each of the two cases above (divisibility by $2$ and $3$), we as
human beings injected intellectual contribution to design the appropriate
algorithms to make the call. Whether there is a systematic way for turing
machines to automatically discover features (from training data) and then
address this prime number divisibility problem appears to be an interesting
topic that is generally overlooked. This is the central problem that our study
set out to address. Additionally, while ultrafast probabilistic algorithms
exist for pseudoprimality test, they are not scalable in classical computers;
a noise-tolerant machine learning approach that gives approximate solutions
could be favorable under certain circumstances over Shorś algorithm in quantum
computers. We will not elaborate these topics here but they could be an
additional motivation to study pseudoprimality by machine learning.

##  2 Prime number divisibility via modern machine learning and deep learning
techniques

###  2.1 Problem Setups

We consider a very simple set of supervised learning problems, which is to
classify integers based on their residues when divided by some fixed prime $p$
for $p\geq 2$.

For instance, when $p=2$, our parameter space $\mathcal{X}_{2}=\mathbb{Z}$ and
our label space $\mathcal{Y}_{2}=\\{0,1\\}$. Given a set of training data
$S_{2}=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n}),y_{i}\equiv x_{i}\mod
2\\}\in(\mathcal{X}_{2}\times\mathcal{Y}_{2})^{n}$, we want to train a
classifier $h_{S_{2}}:\mathcal{X}_{2}\mapsto\mathcal{Y}_{2}$ to predict
whether an “unseen” integer is odd or even. In this case, we have a binary
classification problem. For the case of general $m$, the parameter space
$\mathcal{X}_{p}=\mathbb{Z}$ and the label space
$\mathcal{Y}_{p}=\\{0,1,\ldots,p-1\\}$. The training set
$S_{p}=\\{(x_{1},y_{1})\ldots,(x_{n},y_{n}):y_{i}\equiv x_{i}\mod p\\}$ is
sampled from $(\mathcal{X}_{p}\times\mathcal{Y}_{p})^{n}$ and we hope to build
a effective classifier $h_{S_{p}}:\mathcal{X}_{p}\mapsto\mathcal{Y}_{p}$ to
classify integers based on their residues when divided by $p$. In this case,
we have a multi-class classification problem.

In this section, we primarily focus on the cases when $p=2$ and $3$ but we
also extend some of the analysis to other small prime numbers, e.g. $p=7$ in
Section 3.

As discussed in the Section 1, determining whether an integer is odd or even
is trivial for human; one only needs to look at the unit digit: it is even if
the last digit belongs to $\\{0,2,4,6,8\\}$ and it is odd otherwise. Similar
rule works when checking the divisibility of an integer by $5$: one only needs
to check if the last digit is $5$ or $0$.

It is an integer is divisible by $3$ if and only if the sum of its numerical
digits is divisible by $3$. In addition, it can be easily shown that the same
rule applies when checking if an integer is divisible by $9$. Based on this
rule, one can quickly develop a simple algorithm for human to classify
integers mod $3$. Given an arbitrary integer $n$, one can first check whether
it is divisible by $3$. If yes, then we are done. If not, then we try $n+1$ or
$n-1$. If it is divisible by $3$, then stop. If not, then try $n+2$ or $n-2$.
We must stop at this point given that there are only three possibilities. Same
algorithm works for the case of $9$ except one might need to check all the way
up to $n\pm 9$.

Nonetheless, the case of training computers to learn to perform this set of
tasks from large training sets, i.e., without pre-specified algorithms, is
less clear and we do not know if the widely-used machine learning and deep
learning algorithms nowadays can perform well. Moreover, if the algorithms
perform poorly, are there any ways to improve it? In conclusions, the feature
engineering processes are the decisive factors to the performance of our final
deep learning models. For “decisive”, we mean without feature engineering, it
is impossible to increase the performance by increasing the complexity of
algorithms and the size of training datasets. Of course, with feature
engineering, it is not always possible to increase the performance by fitting
a more complex networks and feeding more training data, or even switching to
“more advanced” algorithms.

In the following sections, we will discuss the methodologies and findings of
our empirical experiments in details.

###  2.2 Prime number divisibility via Deep Neural Networks

####  2.2.1 Preparation of datasets

The set of raw training data is pretty simple to obtain: we sample $50,000$
integers uniformly at random within the range of $[0,2^{32}]$. In order to
make our final results more robust, we sample our training set three times,
i.e., we have three sets of non-negative integers, each of size $50,000$, and
repeat each experiment three times on each training set. In the case of mod
$2$, the training labels are in $\\{0,1\\}$, where $0$ means even and $1$
means odd. In the case of mod $3$, the training labels are in $\\{0,1,2\\}$,
where the each training label represents the residue after being divided by
$3$.

In addition, we also consider the following feature engineering processes on
non-negative integers:

  1. 1.

Binary representation: For instance, $4$ is equal to $[0,\ldots,0,1,0,0]$, $2$
is equal to $[0,\ldots,0,0,1,0]$ and $5$ is equal to $[0,\ldots,0,1,0,1]$.

  2. 2.

Base-three representation: It is in the exact same spirit with binary
representation. For example, $3$ is equal to $[0,\ldots,0,1,0]$ and $6$ is
equal to $[0,\ldots,0,2,0]$.

  3. 3.

One-gram encoding: We simply separate the integer into a vector of numerical
digits. For instance, $123$ will become $[0,\ldots,0,1,2,3]$

  4. 4.

Two-gram encoding: We group two consecutive numerical digits together (with
overlap) to form our feature vector. For instance, $1234$ will become
$[[0,0],\ldots,[0,0],[0,1],[1,2],[2,3],[3,4]]$.

  5. 5.

Three-gram encoding: We group three consecutive numerical digits together
(with overlap). For instance, under Three-gram encoding, $1234$ will become
$[[0,0,0],\ldots,[0,0,0],[0,0,1],[0,1,2],[1,2,3],[2,3,4]]$.

  6. 6.

One-gram & Two-gram encoding combined: For any integer, we take the union of
One-gram and Two-gram encoding.

  7. 7.

One-gram & Two-gram & Three gram encoding combined: For any integer, we take
the union of One-gram, Two-gram, and Three-gram encoding.

All the above feature engineering processes will be tested on both mod $2$ and
mod $3$ problems. In addition to these, given the problem nature of mod $3$,
we also try the following two feature engineering processes:

  * •

One-gram encoding$+$its sum: In addition to the One-gram encoding, we also add
the sum of all of its numerical digits. For instance, $1234$ will become
$[0,\ldots,0,1,2,3,4,10]$.

  * •

One-gram encoding$+$(its sum $\%3$): In this case, the $1234$ will become
$[0,\ldots,0,1,2,3,4,10\%3]=[0,\ldots,0,1,2,3,4,1]$.

Here, since we run experiments in Python, we adopt the conventions of Python:
$[\ldots]$ means list and $[[\ldots],\ldots,[\ldots]]$ means nested list
(a.k.a. matrix). We also pad additional $0$’s or zero lists $[0,\ldots,0]$ on
the left to make sure each feature vector has the same dimension. By doing
this, we can covert list-like objects into tensor forms so that we can put
them into tensorflow neural networks.

Note that we do not sample additional test sets. Instead, we use $10\%$ of the
total training data for testing and remaining $90\%$ for parameter training,
i.e. “validation$\\_$split $=0.1$” in model training.

At the first glace, we do not expect the modern deep learning algorithms can
learn well from the raw training sets, i.e., without any feature engineering,
since the feature vector is only one-dimensional and it varies wildly due to
the long range of sampling domain. We also expect binary representation and
base-three representation should perform “extremely well” on mod $2$ and mod
$3$ cases respectively since we are essentially doing the mod $2$ and mod $3$
operations on integers before training, i.e., we have used pre-specified
algorithms to transform the data and only let the computers to find the
“pattern” from the feature vector. For the remaining gram-like feature
engineering processes, we do expect the performance to be good given large set
of training data. But in terms of how much better compared to raw data and are
there any significant differences between one, two, three grams, and their
combined versions, we cannot form a very well-educated guess at this stage.

Notice that we also designed two additional feature engineering processes for
the mod $3$ case. It is easy to see that these two are motivated from the
problem nature of mod $3$. At this point, we are not sure if the current deep
neutral networks can learn well from these two. It is plausible to believe
that the “One-gram + (its sum $\%3$) should perform extremely well since
basically we are telling computer everything about the mod $3$ algorithms.
This can be viewed as an “indirect” way of “cheating” compared to Base-three
representation. The more interesting case is the “One-gram $+$ its sum” case,
where we are not sure if the deep learning, or any other classical machine
learning algorithms, can detect the “recursive nature” (the most difficult
part) of this problem.

####  2.2.2 Network architectures

For the purpose of illustration and not consuming too much computing power, we
first consider the classical Artificial Neural Network (ANN). The ANNs are
heavily inspired by the way human biological nervous systems operate and are
mainly comprised of a high number of interconnected computational nodes
(a.k.a. neurons). The neurons work collectively to learn from the input in
order to optimize the final output. See for instance [1, 2] and the references
therein for a comprehensive review on the ANNs. In this paper, the ANN
considered has $64$ neurons in the first layer and $32$ neurons in the second
layer. The dimension of input layer of course depends what feature engineering
process are we using. The output layer has dimension $2$ when doing mod $2$
and has dimension $3$ when doing mod $3$. The activation functions are the
classical ReLU functions except for the output layer we use the Sigmoid
function. Notice that this is the only ANN that we will consider in this paper
and we will not list the results of other ANNs with different architectures.
This consideration is due to the facts that 1) the above neural network is
sufficient for us to demonstrate the importance of the feature engineering,
and 2) the more complex networks will be tested on the commonly used AutoML
platforms (as will be discussed in the later sections).

Besides the classical Artificial Neural Networks, we also consider the
Convolutional Neural Network (CNN) and Recurrent Neural Network (RNN). The CNN
is a well-known deep learning algorithm inspired by the natural vision
perception mechanisms of the living creatures. The modern framework of the CNN
was established by LeCun et al. in [3] and later improved in [4]. For recent
advances in CNN and its applications, see e.g. [5] and the references therein.
The RNN architecture was mainly designed to overcome the issue of “limited
context memory” in [6]: only a fixed number of previous words can be taken
into account to predict the next word. In RNN, the context length was extended
to indefinite size, which can handle arbitrary context lengths. See [7] for
the review on the RNN model and its applications on the statistical language
modeling. The CNN considered in this paper has two $1$D convolution layers,
two max pooling layers, and two dense layers with ReLU activation functions.
The RNN here has a single LSTM layer and a dense layer with sigmoid activation
functions.

Finally, we also test on the Bidirectional Encoder Representations from
Transformers (BERT), which is a family of masked language models introduced by
Google in $2018$ [8]. The BERT model is based on the transformer architecture
(specifically, composed of Transformer encoder layers). The BERT model was
pre-trained simultaneously on two tasks: masked language modeling and next
sentence prediction. After pre-training, the BERT model can be fine-tuned on
smaller datasets to optimize its performance on specific tasks, including text
classifications, language inference etc. See also [9, 10, 11, 12] for more
discussions on the BERT model and the Transformer architecture. In this paper,
we test the BERT model on the cases of mod $2$ and $3$ by using
“BertForSequenceClassification” package in Python.

The ANN, CNN and RNN architectures considered in Section 2.2 are illustrated
in Figure 1, Figure 2 and Figure 3 respectively.

Figure 1: The Artificial Neural Network (ANN) that we used for training raw
data. Figure 2: The Convolutional Neural Network (CNN) that we used for
training data after One-gram encoding. Figure 3: The Recurrent Neural Network
(RNN) that we used for training data after One-gram encoding.

####  2.2.3 Results and findings

Next, we summarize the experimental results tested on the neural networks
described in Section 2.2.2 with different feature engineering processes listed
in Section 2.2.1. The Table 1 records the mean and the standard deviation of
accuracy after running the experiments on mod $2$ three times. The network
architectures with different feature engineering processes are listed in the
left-most column. The same thing applies to Table 2, which records the results
of experiments on mod $3$.

In the mod $2$ case, as listed in Table 1, the ANN on raw data can only give
accuracy around $0.5$, which is essentially a fair coin flip. Therefore, it is
not a effective classifier at all. Also, as discussed in Section 2.2.1, it is
not surprising to see that after converting to binary representations, the
results can suddenly achieve $1.000$. In this case, we are feeding too much
information to the training algorithms and it can be considered as “cheating”.
However, it does give us a strong signal that the feature engineering matters.
How about the gram-like feature engineering? The one, two and three gram
transformations (or their combined versions) do give “reasonable” hints to the
algorithms and they significantly improve the accuracy to $\sim 0.8$. Here we
do want to emphasize that in the cases of gram-like feature engineering,
increasing the size of training sets and complexity of neural networks will
help increase the performance at the end. This can be seen when compared with
the AutoML results, since these platforms will fit the model with much larger
networks, try not only deep neural networks but also other algorithms, and
have “more” training data due to the integrated bootstrap aggregations. In
fact, as we will see in Section 2.3.4, after the gram-like feature
engineering, it is possible to achieve accuracy $1.000$. The authors also
tested these two phenomena on our simple neural networks and verified that it
is indeed true, although we will not list any more comparisons here in this
section. The BERT model in the end can also achieve accuracy $1.000$, which
again verifies that gram-like feature engineering processes are effective in
the mod $2$ case. Due to the large pre-training process (contain more
information) and the Transformer architecture, the BERT model is expected to
outperform all the algorithms above with the current size of training data.

Classification on divisibility by $2$ via Deep Learning
---
Algorithm Statistics of Accuracy Accuracy | Mean | Standard Deviation
Artificial Neutral Network (ANN) | $0.501$ | $0.003$
ANN (Binary representation) | $1.000$ | $0.000$
ANN (Base-three representation) | $0.537$ | $0.002$
ANN (One-gram) | $0.864$ | $0.024$
ANN (Two-gram) | $0.778$ | $0.048$
ANN (Three-gram) | $0.799$ | $0.002$
ANN (One $\&$ Two-gram combined) | $0.786$ | $0.028$
ANN (One $\&$ Two $\&$ Three-gram combined) | $0.781$ | $0.023$
Convolutional Neural Network (One-gram) | $0.921$ | $0.042$
Recurrent Neural Network (One-gram) | $0.740$ | $0.206$
Bidirectional Encoder Representations from Transformers (BERT) (One-gram) | $1.000$ | $0.000$
Table 1: Summarizations of results on mod $2$. Mean and standard deviation are
calculated with three randomly-sampled, equal-size training sets.
Classification on divisibility by $3$ via Deep Learning
---
Algorithm Statistics of Accuracy Accuracy | Mean | Standard Deviation
Artificial Neutral Network (ANN) | $0.334$ | $0.002$
ANN (Binary representation) | $0.396$ | $0.002$
ANN (Base-three representation) | $1.000$ | $0.000$
ANN (One-gram) | $0.343$ | $0.003$
ANN (One-gram+its sum) | $0.335$ | $0.002$
ANN (One-gram+(its sum$\%3$)) | $1.000$ | $0.000$
ANN (Two-gram) | $0.334$ | $0.002$
ANN (Three-gram) | $0.333$ | $0.001$
ANN (One $\&$ Two-gram combined) | $0.332$ | $0.004$
ANN (One $\&$ Two $\&$ Three-gram combined) | $0.334$ | $0.007$
Convolutional Neural Network (CNN) (One-gram) | $0.340$ | $0.002$
CNN (One-gram+its sum) | $0.330$ | $0.002$
CNN (One-gram+(its sum$\%3$)) | $0.936$ | $0.001$
Recurrent Neural Network (RNN) (One-gram) | $0.330$ | $0.003$
RNN (One-gram+its sum) | $0.333$ | $0.001$
RNN (One-gram+(its sum$\%3$)) | $0.934$ | $0.001$
Bidirectional Encoder Representations from Transformers (BERT) (One-gram) | $0.336$ | $0.005$
BERT (One-gram + its sum) | $1.000$ | $0.000$
BERT (One-gram + (its sum $\%3$)) | $1.000$ | $0.000$
Table 2: Summarizations of results on mod $3$. Mean and standard deviation are
calculated with three randomly-sampled, equal-size training sets.

In the case of mod $3$, as shown in Table 2, the results are a bit more
disappointing. Again, like the mod $2$ case, base-three representations feed
too much information to the algorithms and it is expected to achieve accuracy
$1.000$ even under very simple neural network architectures. Another
“extremely useful” feature engineering is the “One-gram + (its sum $\%3$)”,
which can achieve $>0.9$ in all networks tested. We also believe that by using
sufficient complex architectures, $1.000$ accuracy can be achieved for all
types of deep neural networks. Like mentioned in Section 2.2.1, the “One-gram
+ (its sum $\%3$)” essentially told the algorithms everything about the mod
$3$ divisibility rule. In other words, we used too much human knowledge and
this should be considered as “cheating” as well. Notice that in the CNN and
RNN cases of Table 2, although no more comparisons will be listed here, we
believe that $1.000$ accuracy can be achieved by increasing the complexity of
networks and/or increasing the size of the training set and/or switching to
classical ML algorithms.

It is also very interesting to see that BERT can achieve $1.000$ accuracy from
the “One-gram+its sum” encoding whereas it can only have $\sim 0.33$ accuracy
from the “One-gram” encoding. In other words, the hint of “summing up digits”
works well with BERT but poorly with other types of deep neural networks. The
BERT model is the only algorithm in this section that can achieve $1.000$
accuracy with “One-gram + its sum” encoding in the mod $3$ case. The key
difference between BERT and other neural networks is that in BERT, all the
possible sums of the digits ($99$ potential choices of sums assuming there are
$10$ digits maximum) are embedded into algorithms with length $768$ each, and
therefore we have $768*99$ more features in BERT instead of having only one
additional feature (sum of digits) in other neural networks. Due to the large
pre-training data, these $768*99$ additional features have already been “seen
and learned” by BERT and this helps detect the recursive nature of the mod $3$
problem. On the contrary, in other neural networks, the sum of digits could be
large and therefore completely new during the training, which causes
inaccuracy.

Besides those mentioned above, all the remaining cases have results $\sim
0.33$, which are essentially uniformly choosing a label at random. At this
stage, increasing the training size and/or the complexity of neural network
architectures and/or trying classical ML algorithms (e.g. regressions, tree-
based algorithms, etc.) will not help.

We can also compare the results between One, Two, Three-gram, and their
combined versions. Their results are almost identical. This is also expected
since the Two and Three-gram encoding (or their combined versions) contain the
repeated information generated from One-gram encoding. In other words, as long
as we have done One-gram encoding, higher-order gram encoding can be obtained
solely from One-gram encoding. In the language of measure theory in
Mathematics, the sigma algebra generated by One-gram encoding contains (is
equal to, strictly speaking) all the other higher-order gram encoding (without
summing up digits) considered in this paper. In the cases of other scientific
domains (e.g. Biology-related fields), this may not be the case but this
finding alerts us that not only we should try the useful feature engineering
to increase the performance, but also we need to do the most effective feature
engineering to reduce computing time and save computing power.

###  2.3 Prime number divisibility via Automated Machine Learning (AutoML)

####  2.3.1 Overview of AutoML

Nowadays, the modern Deep Learning (DL) techniques have achieved remarkable
results on a variety of tasks, spanning over image recognition [13, 14],
language modeling [15], and object detection [16] . Given the challenge and
complication of different tasks, the depth and complexity of neural networks
keep increasing. For instance, in Natural Language Processing (NLP), the Large
Language Models (LLMs) typically contain over $100$ million parameters and are
trained using advanced algorithms on a large corpus. The first version of GPT
launched in $2018$ developed by OpenAI has $117$ million parameters. The GPT-2
followed in $2019$ has $1.5$ billion parameters and the GPT-3 introduced in
$2020$ has $175$ billion parameters.

Since developing such huge models requires extremely high development costs
(traditionally, the high cost of test-and-error processes by human capital),
the novel idea of automating entire machine learning pipeline has emerged
since then. The Automated Machine Learning (AutoML hereafter) is designed to
reduce the large demand of data scientists and create a user-friendly platform
for industry domain experts to automatically build effective machine learning
models without too much computer science and statistics knowledge. In other
words, the AutoML is designed and built to involve an automated construction
of Machine Learning pipeline with limited computation budgets.

A complete AutoML pipeline involves everything from upstream to downstream
data analysis, covering data preparation, feature engineering, model testing
and selection, and model evaluation in the end. It is a very comprehensive
data analysis process and given its large computing power, relatively cheap
computing budget, and user-friendly interface, it is a hot product in both
academia and industry. We refer to [17] and the references therein for readers
who are interested in more details of AutoML.

In this paper, to make our results more robust and comprehensive, we also test
prime divisibility problems on commonly-used AutoML platforms developed by
leading tech companies, including Google, Microsoft and Amazon. For readers
who are also interested in running the experiments yourself, the tasks we run
are completely free without consuming all of your free credits. One can
generate datasets on the Google Colab for instance and upload to AutoML
systems after converting to the CSV file. We will discuss the experiments in
detail in the following sections.

####  2.3.2 Preparation of Datasets

In the case of AutoML training, to reduce the computing time and save
computing power, we sample $30,000$ non-negative integers from $[0,2^{32}]$.
The sample size is smaller compared to that of our training on simple deep
learning models described in Section 2.2.1, but is sufficiently large to fit
our purpose. In addition, we also consider the Binary representation, Base-
three representation, and all the gram-like feature engineering processes
listed in Section 2.2.1. We also test two additional feature engineering
processes designed specifically for the mod $3$ case.

####  2.3.3 Platforms for training

In this paper, we consider the three commonly-used AutoML platforms, including
Microsoft Azure ML Studio, Google Cloud Vertex AI, and Amazon AWS Sagemaker.
All of them are easily accessible online with (limited) free credits. It is
also very easy for academic researchers or industry professionals with little
machine learning expertise to train models for each individual purposes. One
can upload the data in the “.csv” format and pre-specify the target value,
type of tasks (classification, regression, NLP, etc.), metric of evaluation,
etc.

####  2.3.4 Results and Findings

As can be seen in both Table 3 and Table 4, suppose we just throw in the raw
data without any pre-specified feature engineering, the feature engineering
algorithms installed in the AutoML pipelines are not effective at all to deal
with the prime number divisibility problems. This raises an alert to all the
academic researchers and industry Machine Learning practitioners that blindly
throw in the data without any feature engineering has certain level (sometimes
very high) of risks. Although these AutoML products are extremely powerful,
carefully designed, fit into a large variety of needs and updated constantly
by ML experts, they cannot guarantee to deliver the best possible model. It is
crucial to apply the domain knowledge by human experts to better transform the
data so that algorithms are easier to learn. Especially, this can be seen in
the case of mod $2$. Like discussed before, if we break down digits for the
computer, then it is much easier to detect patterns and with the state-of-the-
art machine learning models, it is possible to reach $1.000$ accuracy.

It is also worth noting that certain feature engineering process is not
effective in helping train the model and in the reverse direction, it will
also increase the dimension of feature vectors and even “confuse” the
computer. For instance, we can look at the Base-three representation in the
mod $2$ case, it is easy to see that Base-three representations will only help
the mod $3$ case whereas in the mod $2$ case, it will not do any more good
than the raw data. Therefore, not surprisingly, the results of AutoML stay at
$\sim 0.5$.

In the case of mod $3$, given the subtilty of the problem nature, breaking
down and/or combining digits without summing up them will not effectively help
the model training (no matter how complex the model is or fitting in other
types of models, even with BERT). However, as presented in Table 4, suppose we
sum up all the digits in addition to One-gram encoding, then all the AutoML
platforms can deliver classifiers with accuracy $1.000$, just as the BERT
model. Although here we do want to remark that the results of AutoML are
reported for the best-possible model under multi-angle considerations (e.g.,
complexity, interpretations, etc.) and in case of “One-gram+its sum”, the best
possible model does not fall into the class of deep neural networks considered
in Section 2.2.2. For instance, in Microsoft Azure AI, the best algorithm is
“LightGBMClassifier” in “sklearn” after “MaxAbsScaler” and in Amazon
Sagemaker, it is “XGBoost” under L1-regularization. This is also an
interesting phenomenon since in this case, the tree-based algorithms
outperforms deep neural networks by a large margin. In general, tree-based
algorithms work better on heterogeneous data due to the nature of splitting
data based on “one particular feature”. On the other hand, deep neural
networks work better with homogeneous data, such as image recognition tasks
(pixels) and language models (word vectors). In our case, our input vectors
are certainly heterogeneous since all the single digits are between $0$ and
$9$ and sum of digits could be potentially very large, and therefore, it is
expected that tree-based algorithms will perform better.

To summarize, with our experiments, “One-gram+sum of its digits” seems like
the best feature engineering so far to tackle mod $3$ problem, whereas in the
case of mod $2$, we should favour the “One-gram encoding”.

Classification on divisibility by $2$ via AutoML
---
FE Platform Accuracy | Microsoft Azure ML | Google Cloud Vertex AI | Amazon Sagemaker
No feature engineering | $0.504$ | $0.495$ | $0.508$
Binary representation | $1.000$ | $1.000$ | $1.000$
Base-three representation | $0.508$ | $0.506$ | $0.514$
One-gram | $1.000$ | $1.000$ | $1.000$
Two-gram | $1.000$ | $1.000$ | $1.000$
Three-gram | $1.000$ | $1.000$ | $1.000$
One $\&$ Two-gram combined | $1.000$ | $1.000$ | $1.000$
One $\&$ Two $\&$ Three-gram combined | $1.000$ | $1.000$ | $1.000$
Table 3: Results are reported for the best model tested on each AutoML
platform for each task. FE:Feature Engineering Classification on divisibility
by $3$ via AutoML
---
FE Platform Accuracy | Microsoft Azure ML | Google Cloud Vertex AI | Amazon Sagemaker
No feature engineering | $0.357$ | $0.352$ | $0.345$
Binary representation | $0.361$ | $0.342$ | $0.345$
Base-three representation | $1.000$ | $1.000$ | $1.000$
One-gram | $0.352$ | $0.352$ | $0.348$
One-gram+its sum | $1.000$ | $1.000$ | $1.000$
One-gram+(its sum$\%3$) | $1.000$ | $1.000$ | $1.000$
Two-gram | $0.359$ | $0.353$ | $0.348$
Three-gram | $0.346$ | $0.349$ | $0.351$
One $\&$ Two-gram combined | $0.348$ | $0.351$ | $0.349$
One $\&$ Two $\&$ Three-gram combined | $0.346$ | $0.341$ | $0.345$
Table 4: Results are reported for the best model tested on each AutoML
platform for each task. FE: Feature Engineering.

###  2.4 Conclusions

To conclude, in Section 2, we discussed the methodologies and findings of the
main component of this paper, which is to use modern deep learning and machine
learning techniques to classify integers based on prime number divisibility.
The experiments can be separated into two parts: the first is using deep
neural networks, including ANN, CNN, RNN and BERT and the second is using the
commonly-used, well-developed AutoML platforms. Each are combined with
multiple feature engineering processes.

Overall, even with the most advanced set of learning algorithms, feature
engineering processes coming from pre-specified human knowledge are extremely
crucial in helping deliver the best possible model. It can be seen that, in
some cases, the advanced automated ML pipelines nowadays are not very good at
detecting the most useful relationships between features in helping train the
best model. Given the diversity of applications of AI and ML, it is a
extremely challenging task to create a platform so that it can solve all kinds
of problems (with high standards) automatically. Therefore, before throwing
the data into models, one should certainly pause a bit and put into some
thoughts on how to do useful and effective feature engineering on the raw
data, as this part is largely overlooked by a lot of industry professionals as
well as academic researchers due to overconfidence on current machine learning
tools.

Sometimes, finding a useful and effective feature engineering procedure
directly is not that straightforward (or intuitive) due to the complication of
practical situations. It also requires long trial-and-error processes. Besides
direct feature engineering on training samples, there are other places where
we can inject our domain expertise into so that high-quality classifiers can
be obtained. In the next few sections, we propose a method using Fourier
series regressions to pick up the periodic nature of the prime number
divisibility problem. As a by-product of Fourier series regressions, we also
obtain some feature engineering procedure that cannot be easily found
directly. This approach is essentially linear regression (ordinary least
square), and therefore can be easily programmed and has high model
interpretabilities. It also works well for arbitrarily positive integer $p\geq
2$ (not just prime) in the sense that accuracy $1.000$ can be achieved with
small time complexity.

##  3 Prime number divisibility via Fourier series regressions

###  3.1 Motivations

It is not hard to see that the heart of the prime divisibility problem is to
make computer learn the “mod $p$” function, which is a discrete periodic
function with period $p$. The linear interpolation of the mod $p$ function
takes the form of

$f(x;p)=\begin{cases}x&\qquad{\text{when $0\leq x\leq p-1$},}\\\
(1-p)x+(p-1)p&\qquad{\text{when $p-1<x<p$},}\end{cases}$ (1)

with $f(x+p;p)=f(x;p)$. Therefore, for any $x\geq p$, we can use the shift
relation to shift $x$ back to $[0,p)$, of which the value $f(x;p)$ is
explicit. See Figure LABEL:fig:f(x;7) for the case when $p=7$. We also want to
emphasize the fact that (1) is just one form of the continuous counterpart of
discrete mod $p$ function and there are indeed infinitely many of possible
choices.

Figure 4: Plot of function $f(x;p)$ (1) when $p=7$ and $0\leq x\leq 7$: it is
the linear interpolation of the discrete mod $7$ function with one entire
period.

In order to learn or approximate the discrete periodic function mod $p$ or its
linearly continuous counterpart (1), it is natural for us to consider the
trigonometric functions such as sine or cosine. However, before diving deeper,
let us first pause a bit and think about the question that is it enough to use
only one single sine or cosine function? If yes, then we can, for instance,
replace the classical activation function Sigmoid in the output layer of the
ANN by $\sin$ or $\cos$ to pick up the periodic structure. In the mod $3$
case, the authors tested by replacing the Sigmoid activation function in the
output layer of ANN architecture 1 by the customized activation function
$\sigma(x)=\frac{1}{2}+\frac{1}{2}\sin(x)\in[0,1]$. The accuracy is still
$\sim 0.33$ with raw data, therefore not effective at all. To simplify the
problem, we consider the problem of whether a given integer is divisible by
$3$ or not? In this case, we have a binary classification problem: $0$ being
divisible by $3$ and $1$ otherwise. Again, we tested by replacing the
activation function of the output layer by
$\sigma(x)=\frac{1}{2}+\frac{1}{2}\sin(x)$, and the accuracy is $\sim 0.5$. We
also tried more complex architectures in both cases and unfortunately, not
visible improvements were discovered. Hence, it is probably not enough to use
sine or cosine alone, even with the binary classification problem.

If we think from the “linear algebra” point of view, this is indeed the case.
The discrete mod $3$ function has three possible outputs: $0$, $1$ and $2$ and
it should be viewed as having “dimension $3$”. The simpler version of “whether
a given integer is divisible by $3$” has two possible outputs: $0$ and $1$,
and therefore having “dimension $2$”. Strictly speaking, we are not allowed to
talk about “the dimension” of a particular function since it is not a vector
space but it should help us understand why single sine or cosine function is
not enough. In the continuous case, the function (1) has infinitely many
possible outputs, therefore potentially infinitely many sine and cosine are
needed.

Moreover, given that there are infinitely many continuous counterparts of mod
$p$, i.e., not just in the form of (1), there should have infinitely many
estimates of the coefficients before sine and cosine functions qualified for
approximations of the discrete mod $p$ function. As we will see later in
Figure 5 and Figure 6, the continuous estimates of mod $3$ and mod $7$ from
training data are not linear and can only provide good approximations at
integer points.

To conclude, although sine and cosine are natural good candidates to pick up
the periodic natural of the problem, it is not enough to use only one single
sine or cosine to do the estimate given the “dimensionality issue”. To
overcome this difficulty, we need the theory of Fourier series.

###  3.2 Fourier series and its statistical applications

####  3.2.1 Definition of Fourier series and pointwise convergence

Fourier series is a well-studied subject in the fields of partial differential
equations (PDE), harmonic analysis, etc. in Mathematics and it is now covered
in many undergraduate textbooks (see e.g. [18, Chapter 11]). In short, a
Fourier series is an expansion of a periodic function into a sum of
trigonometric functions, which consists of a collection of $\sin$ and $\cos$
functions with increasing frequencies. Precisely, suppose we have a piecewise
continuous function $\phi(x)$ defined symmetric interval $(-\ell/2,\ell/2)$,
then the full Fourier series of function $\phi(x)$ is defined by

$\frac{1}{2}a_{0}+\sum_{n=1}^{\infty}\left[a_{n}\cos\left(\frac{2\pi
nx}{\ell}\right)+b_{n}\sin\left(\frac{2\pi nx}{\ell}\right)\right],$ (2)

where

$a_{n}=\frac{2}{\ell}\int_{-\ell/2}^{\ell/2}\phi(x)\cos\left(\frac{2\pi
nx}{\ell}\right)dx,\qquad n=0,1,2,\ldots$ (3)

and

$b_{n}=\frac{2}{\ell}\int_{-\ell/2}^{\ell/2}\phi(x)\sin\left(\frac{2\pi
nx}{\ell}\right)dx,\qquad n=1,2,3,\ldots$ (4)

Note that while the function $\phi(x)$ is defined on $(-\ell/2,\ell/2)$, the
full Fourier series (2) is defined for any $x\in\mathbb{R}$. Since it is
comprised entirely of periodic functions with periodic $\ell$, the full
Fourier series (2) is periodic with periodic $\ell$. If we define the partial
sum of full Fourier series (2) by

$S_{N}(x):=\sum_{n=1}^{\infty}\frac{1}{2}a_{0}+\sum_{n=1}^{N}\left[a_{n}\cos\left(\frac{2\pi
nx}{\ell}\right)+b_{n}\sin\left(\frac{2\pi nx}{\ell}\right)\right]$ (5)

and it can be proved that $S_{N}(x)\to\phi(x)$ as $N\to\infty$ pointwise under
certain regularity conditions on $\phi(x)$. The details are not relevant to
our presentation here so we refer to [18, Theorem 11.6] for readers interested
in more details of the theory. Notice that the piecewise continuous function
$\phi(x)$ has infinitely many possible outputs, therefore having “dimension
infinity” and consequently, infinitely many sine & cosine pairs are needed for
approximation. The pointwise convergence of Fourier series is extremely
crucial and provides the theoretical backup that sine and cosine pairs would
do a good job of estimating periodic functions.

####  3.2.2 Applications in time series analysis

To put it short, in Statistics, we use elements in full Fourier series (2) to
pick up the periodic nature of the target that we want to estimate. In most
cases, the estimates are computed via simple linear regression. In classical
time series analysis literature, they are sometimes called “sine and cosine
seasonal dummies”. Note that the sine and cosine always come in pairs as in
(2) since they appear together from the expansion of the most general form of
the cosine function: $f(t)=R\cos(\lambda t+\alpha)=A\cos\lambda t+B\sin\lambda
t$, where $A=R\cos\alpha$ and $B=-R\sin\alpha$. In practice, for instance, if
the data are observed monthly and we have an annual seasonal component, then
we use

$\cos\left(\frac{2\pi j}{12}t\right),\sin\left(\frac{2\pi
j}{12}t\right),j=1\ldots,5;\qquad\cos\left(\frac{2\pi 6}{12}\right)=(-1)^{t}$

as dummy variables for regression. We call $1/12$ the fundamental frequency
and the overtone frequencies are $j/12,j=2,\ldots,6.$ If the data are observed
quarterly and the seasonal component is annual, then we use

$\cos\left(\frac{2\pi}{4}t\right),\sin\left(\frac{2\pi}{4}t\right);\qquad\cos\left(\frac{2\pi
2}{4}t\right)=(-1)^{t}$

as dummies to pick up the periodic structure. Similarly, if the data are
observed daily, to model a weekly periodic component we use

$\cos\left(\frac{2\pi j}{7}t\right),\sin\left(\frac{2\pi
j}{7}t\right),j=1,2,3.$

In the case of mod $p$ for general $p\geq 2$, it is not hard to see that
$\sim[p/2]$ pairs of sine and cosine functions are needed in order to carry
out the estimation. Before describing our methods in detail, let us first talk
about the datasets.

###  3.3 Preparation of datasets

Our preparation of datasets is again very simple: we uniformly sample $30,000$
non-negative integers from $[0,2^{32}]$. For the purpose of demonstrating the
powerfulness of this technique, we use mod $3$ and mod $7$ as illustrations in
this section. Therefore, we have two columns of labels: one is mod $3$,
another one is mod $7$.

Within these $30,000$ samples, we use the first $25,000$ of them to run the
regression and the remaining $5,000$ ones as testing sets to compute the
accuracy, which is the same evaluation metric we used in the previous section.

###  3.4 Fourier series regressions

In this section, we first describe our methodologies for general mod $p$ case,
where $p\geq 2$ is an integer and not necessarily prime. Fix integer $p\geq
2$. Suppose $X=[x_{1},\ldots,x_{n}]^{T}$ is our training set and let
$Y_{p}=[y_{1},\ldots,y_{n}]^{T}$ be the vector of training labels, i.e.,
$y_{i}\equiv x_{i}\mod p$ where $y_{i}\in\\{0,1\ldots,p-1\\}$. For each non-
negative integer $x_{i}$ in $X$, consider the following Fourier series basis:

$\left\\{\sin\left(\frac{2\pi j}{p}\cdot x_{i}\right),\cos\left(\frac{2\pi
j}{p}\cdot x_{i}\right),\ \text{where}\ j=\begin{cases}1,\ldots,[(p-1)/2]&\
\text{if $p$ is odd}\\\ 1,\ldots,[(p-1)/2]+1&\ \text{if $p$ is
even}\end{cases}\right\\}.$ (6)

Note that the Fourier series basis (6) can also be viewed as a feature vector
for each integer $x_{i}$. For each $j$, let

$\sin\left(\frac{2\pi j}{p}X\right)=\left[\sin\left(\frac{2\pi j}{p}\cdot
x_{1}\right),\ldots,\sin\left(\frac{2\pi j}{p}\cdot x_{n}\right)\right]^{T}$

and

$\cos\left(\frac{2\pi j}{p}X\right)=\left[\sin\left(\frac{2\pi j}{p}\cdot
x_{1}\right),\ldots,\sin\left(\frac{2\pi j}{p}\cdot x_{n}\right)\right]^{T}$

be the vectors of Fourier series basis.

Next, we consider the following linear regression equation:

$Y_{p}=\begin{cases}\gamma+\sum_{j=1}^{[(p-1)/2]}\left(\alpha_{j}\sin\left(\frac{2\pi
j}{p}X\right)+\beta_{j}\cos\left(\frac{2\pi
j}{p}X\right)\right)+\varepsilon,&\qquad\text{if $p$ is odd},\\\
\gamma+\sum_{j=1}^{[(p-1)/2]+1}\left(\alpha_{j}\sin\left(\frac{2\pi
j}{p}X\right)+\beta_{j}\cos\left(\frac{2\pi
j}{p}X\right)\right)+\varepsilon,&\qquad\text{if $p$ is even},\end{cases}$ (7)

where $\varepsilon$ denote the (vector of) standard Gaussian noise in linear
regression. All the coefficients in (7) are estimated by the classical
ordinary least square (OLS) method.

Generally speaking, linear regression model is not a good candidate for
classification problems due to a number of reasons, one of them being the
output values are continuous instead of categorical. As we will see later, in
our case, due to large numbers of training samples, the predicted values on
the testing set are very close to integers so that we can round them to the
nearest integer if their distance is within certain the error, e.g. up to
$10^{-5}$. In other words, the Fourier series regression (7) gives a almost
perfect approximation for the mod $p$ function at integer points.

###  3.5 Regression estimates of mod $3$ and mod $7$

As mentioned before, for the purpose of demonstration, we run experiments on
the cases of mod $3$ and mod $7$. In both cases, the Fourier series regression
(7) can achieve accuracy $1.000$. We believe this is the case for all $p$
given large number of training samples (sample size $\gg p$). Like described
in Section 3.3, we use $25,000$ samples to estimate the regression
coefficients and the remaining $5,000$ ones for testing purposes.

####  3.5.1 Regression results of mod $3$

By using the “LinearRegression” package in the “sklearn” of Python, we have
the following regression coefficients estimate:

$\displaystyle\widehat{Y_{3}}(X)=0.9999999987106293$
$\displaystyle+(-0.57735)\cdot\sin\left(\frac{2\pi}{3}X\right)+(-1.00000)\cdot\cos\left(\frac{2\pi}{3}X\right)$
(8)

with $R^{2}$-value being $1$ and all coefficients being statistically
significant. Here the $R^{2}$ value is computed under train-validation splits
with size $0.1$. The estimated regression function in the mod $3$ case is
plotted in Figure 5 and the its values at integer points, spanning over three
periods, are listed in Table 5. For each integer $z_{i}$ from the testing set,
we first compute $\widehat{y}_{i}=\widehat{Y_{3}}(z_{i})$. Each
$\widehat{y_{i}}$ is of float value and may not be an exact integer. In fact,
they are really close to integers and we can round them to the nearest integer
if the absolute value of their distance is less than $10^{-5}$. By doing this,
we can compare the predicted label with the correct label and further compute
the accuracy, which is the ratio of number of correct predictions over total
number of testing samples. In the mod $3$ case, the accuracy is equal to
$1.000$, which yields an extremely useful classifier. We also want to mention
that the joint presence of both sine and cosine functions is needed and if we,
for instance, remove all the cosines and only keep the sines in (7), the
$R^{2}$-value only has $0.2546$ and the final accuracy is $0.3406$ with the
same datasets, which is essentially equal to “random guess”. On the contrary,
we can also add more pairs of sine and cosine, e.g. $j=1,\ldots p-1$ in
Fourier series basis (6). This will also give us a satisfying linear
regression estimate (accuracy $1.000$) with “less overshoot and undershoot”
compared to (7). However, the regression table will give the potential warning
of multicollinearity, indicating that too many features were added. This will
cause instability of regression coefficients estimates in some cases,
especially when $p$ is large, so our linear regression model (7) is optimal.

Figure 5: Plot of regression function $\widehat{Y_{3}}(X)$: it provides a almost perfect continuous approximation of mod $3$ function. Its values at integer points, covering three periods, are listed in Table 5. $X$ | $\widehat{Y_{3}}(X)$ | $X\mod 3$
---|---|---
$0$ | $-1.2893707213024186\cdot 10^{-9}$ | $0$
$1$ | $1.0000002318356833$ | $1$
$2$ | $1.9999997655855752$ | $2$
$3$ | $-1.2893706102801161\cdot 10^{-9}$ | $0$
$4$ | $1.0000002318356827$ | $1$
$5$ | $1.9999997655855757$ | $2$
$6$ | $-1.2893703882355112\cdot 10^{-9}$ | $0$
$7$ | $1.0000002318356822$ | $1$
$8$ | $1.999999765585576$ | $2$
$9$ | $-1.2893702772132087\cdot 10^{-9}$ | $0$
Table 5: Predicted values of $\\{0,1,\ldots,8,9\\}$ by regression function (8)
and their comparisons with true labels.

####  3.5.2 Regression results of mod $7$

In the case of mod $7$, we have the following regression estimates:

$\displaystyle\begin{split}\widehat{Y_{7}}(X)=3.000000002749488&+(-2.076521)\cdot\sin\left(\frac{2\pi}{7}X\right)+(-1.000000)\cdot\cos\left(\frac{2\pi}{7}X\right)\\\
&+(-0.797473)\cdot\sin\left(\frac{4\pi}{7}X\right)+(-1.000000)\cdot\cos\left(\frac{4\pi}{7}X\right)\\\
&+(-0.228243)\cdot\sin\left(\frac{6\pi}{7}X\right)+(-1.000000)\cdot\cos\left(\frac{6\pi}{7}X\right),\end{split}$
(9)

with $R^{2}$-value being $1$ and all coefficients being statistically
significant. In this case, again, the accuracy is $1$ with our testing set.
The estimated regression function is plotted in Figure 6 and its values at
integer points, covering two periods, are recorded in Table 6.

Figure 6: Plot of regression function $\widehat{Y_{7}}(X)$: it provides a almost perfect continuous approximation of mod $7$ function. Its values at integer points, covering two periods, are listed in Table 6. $X$ | $\widehat{Y_{7}}(X)$ | $X\mod 7$
---|---|---
$0$ | $2.749488192677063\cdot 10^{-9}$ | $0$
$1$ | $1.000000897764708$ | $1$
$2$ | $1.9999998497560223$ | $2$
$3$ | $3.0000003332714678$ | $3$
$4$ | $3.9999996722275086$ | $4$
$5$ | $5.000000155742953$ | $5$
$6$ | $5.9999991077342685$ | $6$
$7$ | $2.7494893029000878\cdot 10^{-9}$ | $0$
$8$ | $1.0000008977647075$ | $1$
$9$ | $1.9999998497560227$ | $2$
$10$ | $3.0000003332714673$ | $3$
$11$ | $3.999999672227508$ | $4$
$12$ | $5.000000155742954$ | $5$
$13$ | $5.99999910773427$ | $6$
$14$ | $2.7494904131231124\cdot 10^{-9}$ | $0$
$15$ | $1.0000008977647064$ | $1$
$16$ | $1.999999849756023$ | $2$
Table 6: Predicted values of $\\{0,1,\ldots,15,16\\}$ by regression function
(9) and their comparisons with true labels.

###  3.6 Conclusions

To conclude, in this section, we used the basis vectors of the full Fourier
series (2) to construct a simple linear regression estimate for the discrete
mod $p$ function for any integer $p\geq 2$ (not just prime). This approach is
motivated by the “periodic nature” of the mod $p$ function, the theory of
Fourier series, and the seasonal dummies in time series analysis. This linear
regression model is extremely useful in the sense that accuracy $1$ can be
achieved on “unseen integers” for all the mod $p$ problems. As a by-product,
this method also provides a clean and effective way of doing feature
engineering, which is to encode integers with a ($p$ or $p-1$)-dimensional
Fourier series basis vector (6), even the integer itself could be potentially
very large and has many digits. Comparing with our previous deep neural
network approach in Section 2, the Fourier series regression outperforms in
almost all aspects, including model complexity, model interpretation,
prediction power, reliability, and ability to deal with general case. Next, we
investigate the recent popular large language model ChatGPT’s ability to
tackle the prime number divisibility problem.

##  4 Prime number divisibility via ChatGPT

Given the extensive media coverage surrounding ChatGPT since late $2022$, it
would be remiss of us not to assess its efficacy in addressing the current
scientific problem of interests.

###  4.1 ChatGPT on prime number divisibility problems

In this section, we first assess ChatGPT’s knowledge on the prime number
divisibility problem. The detailed response from ChatGPT (March $2023$
version) are given in Table 7 and Table 8. We also checked the correctness of
the response from ChatGPT, labeled as “[Correct]” or “[Wrong]”, by comparing
with the Wikipedia page on “Divisibility rule” [19].

Our general conclusions are that starting from $7$, the “divisibility rule of
N” becomes a standard answer to the question. The problem is transformed into
a recursive problem of determining whether a transformed number is also
divisible by the original number.

Additionally, starting from $13$, the “Casting out $N$ method” becomes a
standard answer, which is numerically identical to the “divisibility rule of
$N$” method.

Finally, starting from $13$, the "Modular arithmetic" becomes a standard
answer. There is nothing wrong with the answer, but it defeats the purpose of
asking the question.

Prime $N$ |  Solution by ChatGPT on divisibility by $N$
---|---
$2$ |  To check if an integer can be divided by $2$, you only need to check if its last (least significant) digit is even or odd. If the last digit is even ($0,2,4,6,$ or $8$), then the number is divisible by $2$. Otherwise, if the last digit is odd ($1,3,5,7,$ or $9$), then the number is not divisible by $2$. [Correct]
$3$ |  To check if an integer can be divided by $3$, you can add up the digits of the number, and if the resulting sum is divisible by $3$, then the original number is also divisible by $3$. [Correct]
$5$ |  To check if an integer can be divided by $5$, you only need to check if its last (least significant) digit is either $0$ or $5$. If the last digit is $0$ or $5$, then the number is divisible by $5$. Otherwise, if the last digit is any other digit, then the number is not divisible by $5$. [Correct]
$7$ |  To check if an integer can be divided by $7$, there are different methods, including:  • Casting out sevens method: This method involves separating the last digit of the number, doubling it, and subtracting the result from the remaining truncated number. If the result is divisible by $7$, then the original number is also divisible by $7$. This process can be repeated until the remaining number is small enough to check by inspection. [Correct] • Divisibility rule of $7$: This rule states that if you take the last digit of the number, multiply it by $2$, and then subtract this result from the remaining truncated number, the result must be either $0$ or a multiple of $7$ for the original number to be divisible by $7$. [Correct] • Alternating sum method: This method involves adding and subtracting alternate digits of the number, starting from the rightmost digit. If the final result is either $0$ or a multiple of $7$, then the original number is divisible by $7$. [Wrong]
$11$ |  To check if an integer can be divided by 11, there are different methods, including:  • Alternating sum method: This method involves adding and subtracting alternate digits of the number, starting from the rightmost digit. If the final result is either $0$ or a multiple of $11$, then the original number is divisible by $11$. [Correct] • Divisibility rule of $11$: This rule states that if you take the alternating sum of the digits of the number (as described in the first method), and the result is a multiple of $11$, then the original number is divisible by $11$. [Correct] • Subtracting and comparing method: This method involves subtracting the last digit of the number from the truncated number formed by the remaining digits, and repeating this process until you obtain a number that is either divisible by $11$ or less than $11$. If the final result is divisible by $11$, then the original number is also divisible by $11$. [Correct]
Table 7: Solutions given by ChatGPT on the question “how to check if an integer can be divided by $N$” for $N=2,3,5,7$ and $11$. The bold face texts “[Correct]” or “[Wrong]” indicate whether the response from ChatGPT is a mathematically correct statement or not. Prime $N$ |  Solution by ChatGPT on divisibility by $N$
---|---
$13$ |  To check if an integer can be divided by $13$, there are different methods, including:  • Divisibility rule of $13$: This rule states that if you take the last digit of the number, multiply it by $4$, and then subtract this result from the truncated number formed by the remaining digits, the result must be either $0$ or a multiple of $13$ for the original number to be divisible by $13$. [Wrong] • Casting out thirteens method: This method involves separating the last digit of the number, multiplying it by $9$, and then subtracting the result from the truncated number formed by the remaining digits. We repeat this process with the new number, and continue until we obtain a number that is either divisible by $13$ or is less than $13$. If the final result is divisible by $13$, then the original number is also divisible by $13$. [Correct] • Modular arithmetic: This method involves calculating the remainder of the number when divided by $13$ using the modulo operator ($\%$). If the remainder is $0$, then the number is divisible by $13$. Otherwise, it is not divisible by $13$. [Correct]
$17$ |  To check if an integer can be divided by $17$, there are different methods, including:  • Divisibility rule of $17$: This rule states that if you take the last digit of the number, multiply it by $5$, and then subtract this result from the truncated number formed by the remaining digits, the result must be either $0$ or a multiple of $17$ for the original number to be divisible by $17$. [Correct] • Casting out seventeens method: This method involves separating the last digit of the number, multiplying it by $7$, and then subtracting the result from the truncated number formed by the remaining digits. We repeat this process with the new number, and continue until we obtain a number that is either divisible by $17$ or is less than $17$. If the final result is divisible by $17$, then the original number is also divisible by $17$. [Wrong] • Modular arithmetic: This method involves calculating the remainder of the number when divided by $17$ using the modulo operator ($\%$). If the remainder is $0$, then the number is divisible by $17$. Otherwise, it is not divisible by $17$. [Correct]
$19$ |  To check if an integer can be divided by $19$, there are different methods, including:  • Divisibility rule of $19$: This rule states that if you take the last two digits of the number, multiply the tens digit by $2$ and add it to the units digit, and then subtract this result from the truncated number formed by the remaining digits, the result must be either $0$ or a multiple of $19$ for the original number to be divisible by $19$. [Wrong] • Casting out nineteens method: This method involves separating the last digit of the number, multiplying it by $2$, and then subtracting the result from the truncated number formed by the remaining digits, multiplied by $10$. We repeat this process with the new number, and continue until we obtain a number that is either divisible by $19$ or is less than $19$. If the final result is divisible by $19$, then the original number is also divisible by $19$. [Wrong] • Modular arithmetic: This method involves calculating the remainder of the number when divided by $19$ using the modulo operator ($\%$). If the remainder is $0$, then the number is divisible by $19$. Otherwise, it is not divisible by $19$. [Correct]
Table 8: Continuation of Table 7: solutions given by ChatGPT on the question
“how to check if an integer can be divided by $N$” for $N=13,17$ and $19$. The
bold face texts “[Correct]” or “[Wrong]” indicate whether the response from
ChatGPT is a mathematically correct statement or not.

###  4.2 ChatGPT on prime number divisibility problems via deep neural
networks

Next we assess whether ChatGPT can design a deep neural network to address the
same problem.

> Prompt: Can you design a deep learning algorithm to determine if a number
> can be divided by $17$?
>
> —
>
> ChatGPT: Yes, we can design a deep learning algorithm to determine if a
> number can be divided by $17$. One approach is to use a type of neural
> network called a feedforward neural network, which consists of an input
> layer, one or more hidden layers, and an output layer.
>
> Here’s one way we could design the neural network:
>
>   * •
>
> Input layer: The input layer will consist of $17$ neurons, one for each
> possible remainder when dividing by $17$. For example, if the input number
> is $x$, then the input layer will consist of $17$ neurons representing
> $x\mod 17=0,x\mod 17=1,x\mod 17=2,...,x\mod 17=16$.
>
>   * •
>
> Hidden layers: We can use one or more hidden layers to allow the network to
> learn complex patterns in the input data. The number of neurons in the
> hidden layers can be chosen based on the complexity of the problem.
>
>   * •
>
> Output layer: The output layer will consist of a single neuron, which will
> output a value between $0$ and $1$ indicating the probability that the input
> number can be divided by $17$. If the output value is greater than $0.5$, we
> can say that the number can be divided by $17$.
>
>   * •
>
> Training data: We will need a dataset of input numbers and their
> corresponding labels ($1$ if the number can be divided by $17$, $0$
> otherwise) to train the network. We can generate this dataset by simply
> iterating over a range of numbers and checking if each number can be divided
> by $17$.
>
>   * •
>
> Training the network: We can use a variant of gradient descent, such as
> stochastic gradient descent, to train the network on the training data.
> During training, the network will adjust the weights and biases of the
> neurons to minimize the difference between its predicted outputs and the
> true labels in the training data.
>
>   * •
>
> Testing the network: Once the network is trained, we can test its
> performance on a separate set of test data. This will give us an idea of how
> well the network can generalize to new inputs.
>
>

>
> Note that while this approach may work for small input numbers, it may not
> be practical for very large numbers since the input layer would need to have
> $17^{n}$ neurons to handle $n$-digit numbers. In practice, other algorithms
> such as modular arithmetic or division can be used for large numbers.

The solution is not incorrect, and indeed it should work since the modulus
function is used as input neurons.

Next we changed the prompt as below:

> Prompt: Can you design a deep learning algorithm to determine if a number
> can be divided by 17 without using the modulus function?
>
> —
>
> ChatGPT: Yes, we can design a deep learning algorithm to determine if a
> number can be divided by $17$ without using the modulus function. One
> approach is to use a type of neural network called a recurrent neural
> network (RNN), which can be trained to recognize patterns in sequences of
> data. Here’s one way we could design the RNN:
>
>   * •
>
> Input encoding: We can encode the input number as a binary sequence, where
> each bit represents a power of $2$. For example, if the input number is $x$,
> we can represent it as a binary sequence $(a_{1},a_{2},...,a_{n})$, where
> $x=a_{1}\cdot 2^{0}+a_{2}\cdot 2^{1}+...+a_{n}\cdot 2^{n-1}$.
>
>   * •
>
> Hidden layers: We can use one or more layers of Long Short-Term Memory
> (LSTM) cells as the hidden layers of the RNN. LSTM cells are designed to
> capture long-term dependencies in sequential data.
>
>   * •
>
> Output layer: The output layer will consist of a single neuron, which will
> output a value between $0$ and $1$ indicating the probability that the input
> number can be divided by $17$. If the output value is greater than $0.5$, we
> can say that the number can be divided by $17$.
>
>   * •
>
> Training data: We will need a dataset of input numbers and their
> corresponding labels ($1$ if the number can be divided by $17$, $0$
> otherwise) to train the network. We can generate this dataset by iterating
> over a range of numbers and checking if each number can be divided by $17$.
>
>   * •
>
> Training the network: We can use a variant of backpropagation through time
> (BPTT) to train the RNN on the training data. During training, the network
> will adjust the weights and biases of the neurons to minimize the difference
> between its predicted outputs and the true labels in the training data.
>
>   * •
>
> Testing the network: Once the network is trained, we can test its
> performance on a separate set of test data. This will give us an idea of how
> well the network can generalize to new inputs.
>
>

>
> The key idea behind this approach is to use the binary encoding of the input
> number to create a sequence of bits that the LSTM cells can process. The
> LSTM cells will learn to recognize patterns in this sequence that are
> indicative of divisibility by $17$. Since the network does not use the
> modulus function, it can handle very large input numbers. However, it may
> require a large number of LSTM cells and a long training time to achieve
> good performance.

The solution above essentially builds a One-gram from a binary representation
of integers, and it is not expected to work well. In summary, ChatGPT is
unable to provide a satisfactory solution to the problem of determining
integer divisibility via deep neural networks. However, we stress that these
experiments were performed in March 2023, and it is likely that future version
of ChatGPT can address the problems outlined above.

##  5 Final Conclusions

In the current study, we tested multiple architectures of deep neural networks
and feature engineering approaches, and evaluated the scenario of determining
divisibility of large finite integers (up to $2^{32}-1$) by small prime
numbers. Most of the results are self-evident to explain and can be intuitive.
Our general observations are that regardless of the network framework or the
complexity of the network structure, the performance to predict prime number
divisibility critically depends on feature space fed into the deep learning
models. Widely used AutoML pipelines are not sufficient to help create useful
features unless they understand the specific scientific questions under study.
We proposed linearly solvable solution to the problem using ordinary linear
regression on Fourier series, and showed its generalizability to other
integers (not necessarily prime). To conclude, feature engineering remains an
important task to improve the performance, increase the interpretability and
reduce complexity of machine-learning models, even in the era of AutoML and
large-language models.

##  6 Acknowledgements

This project originated from a discussion between Umair Ahsan (CHOP), Qian Liu
(UNLV) and Kai Wang (CHOP/Penn) during the peak of COVID-19. We are grateful
to Drs. Xin Sun (Penn) and Herman Gluck (Penn) for their support in pursuing
scientific interests of our choosing.

## References

  * [1] Anders Krogh.  What are artificial neural networks?  Nature biotechnology, 26(2):195–197, 2008.
  * [2] Harsh Kukreja, N Bharath, CS Siddesh, and S Kuldeep.  An introduction to artificial neural network.  Int J Adv Res Innov Ideas Educ, 1:27–30, 2016.
  * [3] Yann Lecun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L.D. Jackel.  Handwritten digit recognition with a back-propagation network.  In David Touretzky, editor, Advances in Neural Information Processing Systems (NIPS 1989), Denver, CO, volume 2. Morgan Kaufmann, 1990.
  * [4] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the Institute of Radio Engineers, 86(11):2278–2323, 1998.
  * [5] Jiuxiang Gu, Zhenhua Wang, Jason Kuen, Lianyang Ma, Amir Shahroudy, Bing Shuai, Ting Liu, Xingxing Wang, Gang Wang, Jianfei Cai, and Tsuhan Chen.  Recent advances in convolutional neural networks.  Pattern Recogn., 77(C):354–377, may 2018.
  * [6] Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Janvin.  A neural probabilistic language model.  In Journal of machine learning research, 2003.
  * [7] Wim De Mulder, Steven Bethard, and Marie-Francine Moens.  A survey on the application of recurrent neural networks to statistical language modeling.  Computer Speech & Language, 30, 01 2014.
  * [8] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pages 4171–4186. Association for Computational Linguistics, 2019\.
  * [9] Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu.  A survey of transformers.  AI Open, 3:111–132, 2022.
  * [10] K. Han, Y. Wang, H. Chen, X. Chen, J. Guo, Z. Liu, Y. Tang, A. Xiao, C. Xu, Y. Xu, Z. Yang, Y. Zhang, and D. Tao.  A survey on vision transformer.  IEEE Transactions on Pattern Analysis & amp; Machine Intelligence, 45(01):87–110, jan 2023.
  * [11] Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah.  Transformers in Vision: A Survey.  arXiv e-prints, page arXiv:2101.01169, jan 2021.
  * [12] Prakhar Ganesh, Yao Chen, Xin Lou, Mohammad Ali Khan, Yin Yang, Hassan Sajjad, Preslav Nakov, Deming Chen, and Marianne Winslett.  Compressing Large-Scale Transformer-Based Models: A Case Study on BERT.  Transactions of the Association for Computational Linguistics, 9:1061–1080, 09 2021.
  * [13] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in Neural Information Processing Systems, volume 25. IEEE, 2012.
  * [14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016.
  * [15] Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov.  Transformer-XL: Attentive language models beyond a fixed-length context.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978–2988, Florence, Italy, July 2019. Association for Computational Linguistics.
  * [16] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 779–788, 2016.
  * [17] Xin He, Kaiyong Zhao, and Xiaowen Chu.  AutoML: A survey of the state-of-the-art.  Knowledge-Based Systems, 212:106622, 2021.
  * [18] R. Choksi.  Partial Differential Equations: A First Course.  Pure and Applied Undergraduate Texts. American Mathematical Society, 2022\.
  * [19] Wikipedia contributors.  Divisibility rule — Wikipedia, the free encyclopedia, 2023.  [Online; accessed 23-March-2023].