Can a deep neural network be trained to classify an integer N1 as being divisible by another integer N2?

Question

So I’ve been working on my own little dynamic architecture for a deep neural network (any number of hidden layers with any number of nodes in every layer) and got it solving the XOR problem efficiently. I moved on to trying to see if I could train my network on how to classify a number as being divisible by another number or not while experimenting with different network structures and have noticed some odd things. I know this is a weird thing to try and train a neural network to do but I just thought it might be easy because I can simply generate the training data set and test data set programmatically.

From what I’ve tested, it seems that my network is only really good at identifying whether or not a number is divisible by a number who is a power of 2. If you test divisibility by a power of two, it converges on a very good solution very quickly. And it generalizes well on numbers outside of the training set - which I guess it kind of makes sense, as I’m inputting the numbers into the network in binary representation, so all the network has to learn is that a number n is only divisible by 2^m if the last m digits in the binary input vector are 0 (i.e. fire the output neuron if the last m neurons on the input layer don't fire, else don't). When checking divisibility by non-powers of two, however, there does not seem to be as much of a "positional" (maybe that's the word, maybe not) relationship between the input bits and whether or not the number is divisible. I thought though, that if I threw more neurons and layers at the problem that it might be able to solve classifying divisibility by other numbers – but that is not the case. The network seems to converge on not-so-optimal local minima on the cost function (for which I am using mean-squared-error) when dividing by numbers that are not powers of 2. I’ve tried different learning rates as well to no avail.

Do you have any idea what would cause something like this or how to go about trying to fix it? Or are plain deep neural networks maybe just not good at solving these types of problems?

Note: I should also add that I've tried using different activation functions for different layers (like having leaky-relu activation for your first hidden layer, then sigmoid activation for your output layer, etc.) which has also not seem to have made a difference

Here is my code if you feel so inclined as to look at it: https://github.com/bigstronkcodeman/Deep-Neural-Network/blob/master/Neural.py

(beware: it was all written from scratch by me in the quest to learn so some parts (namely the back-propagation) are not very pretty - I am really new to this whole neural network thing)

Answer 1

There is a recent development in research that was looking into effectiveness of neural networks on arithmetic. Interestingly, feed-forward neural networks (MLPs) with various activation functions as well as LSTMs (RNNs which are Turing-complete) are not able to model simple arithmetic operations (e.g. addition/multiplication), they designed a new logic unit which can solve all of the simple arithmetic problems.

See: Neural Arithmetic Logic Units

More recently, DL can solve symbolic maths: Deep Learning for Symbolic Mathematics

Answer 2

When you represent a number in base 2 (binary), you have already divided the number by 2 many times. If there is no remainder at the end, the number is obviously evenly divisible by 2. This hints that your AI could test for divisibility by dividing. Hmm-- not much gained there!

Unfortunately the problem is not one suited to solving via AI. That's why factorization of large numbers is a good basis for hard encryption schemes. I'd suggest finding a different sort of problem on which to test your AI.