Is it possible to do Fizz Buzz in deep learning? After reading a joke Fizz Buzz in Tensorflow, I am curious to know if it is possible to do such simple task correctly with deep learning. Any theoretical explanation for the reason we can or we cannot?
It is modulo operation, if we can do Fizz Buzz, maybe deep learning also can be used in number theory, such as finding prime numbers?
 A: As the author of the linked blog post, I am happy to say that (with the correct choice of hyperparameters and a little luck) Fizz Buzz can be completely learned by a neural network with one hidden layer.
I spent some time investigating why it works, and the reason is somewhat interesting. It hinges upon the binary representation of the input and the following observation:


*

*if two numbers differ by a multiple of 15, then they belong to the same fizzbuzz "class" (as-is / fizz / buzz / fizzbuzz)


It turns out that there are a number of ways in which you can reverse two bits in a 10-digit binary number and get a number that differs by a multiple of 15. For example, if you start with some number x and turn on the 128 bit and turn off the 8 bit, you get x + 120. There are many other such examples.
And if you have a linear function of the bits that puts the identical weights on those two bits, it will produce the same output for x and x + 128.
As there are many such bit pairs, it turns out that the neural network basically 


*

*learns a bunch of equivalence classes (for example, one would contain x, x + 120, and a few other numbers), and

*"memorizes" the correct answer for each equivalence class


And so it turns out that when you train the model on the numbers 101 to 1023, you've got enough equivalence classes to predict correctly on 1 to 100.
(This is not formal, of course, this is just a high-level summary of what I learned when I investigated the network.)
--
As to your question about finding prime numbers, I'd be surprised if an approach like this worked. My sense is that the nice "same modulo 15" structure of this problem is what makes the neural net work, and it's hard to think of anything analogous for e.g. finding prime numbers.
A: Let me answer the question in a meme way.
Why (always) deep learning? All neural nets do is linear regression (x*w+b) with some non-linearity around the (intermediate) response.

Lets talk machine learning, better yet, optimization. The obvious general class of problems you are referring to is function approximation (not regression per se). So, why not to use method that was developed to do exactly this: writing programs. In theory, yes, you can use 'artificial intelligence' methods to create programs and one of them, given enough data and time, can theoretically be FizzBuzz. Or a programm that computes prime numbers (and that program could be theoretically the same when written by a human). -- No deep learning here --.
Learning from data
Well, can we learn from data? Yes, we can. But first we need to understand data and to engineer some features. Because only one numeric feature is not expressive enough... (for now).
Some code incoming:
library(tidyverse)

theData <- data_frame(a = as.double(1:100),
                      a3 = as.double(a %% 3 == 0),
                      a5 = as.double(a %% 5 == 0),
                      cl = case_when((a3 > 0) & (a5 > 0) ~ 'FizzBuzz',
                                     a3 > 0 ~ 'Fizz',
                                     a5 > 0 ~ 'Buzz',   
                                     TRUE ~ 'Number')) %>%
  mutate(cl = factor(cl))

Now we have a numerical feature a (numbers) and a3 and a5 te help with the decision ...

... tree. (╯°□°)╯︵ ┻━┻ again not deep learning here. But a stacked model: first level is DT and scond level is (using Viola-Jones-Cascades or simple filter on the Number response) a plain old linear regression with the solution $y=a$.
The DT first:
treeModel <- rpart::rpart(cl ~ ., theData, 
                          control = rpart::rpart.control(minsplit = 5))
rattle::fancyRpartPlot(treeModel, caption = '')


THAT IS CRAZY! A simple decision tree learned FizzBuzz! But did it?
Apply some test data:
testData <- data_frame(a = as.double(200:300),
                      a3 = as.double(a %% 3 == 0),
                      a5 = as.double(a %% 5 == 0),
                      cl = case_when((a3 > 0) & (a5 > 0) ~ 'FizzBuzz',
                                     a3 > 0 ~ 'Fizz',
                                     a5 > 0 ~ 'Buzz',   
                                     TRUE ~ 'Number'))

predictions <- predict(treeModel, testData, type = 'class')
table(testData$cl, predictions) 


        predictions
         Buzz Fizz FizzBuzz Number
Buzz       14    0        0      0
Fizz        0   27        0      0
FizzBuzz    0    0        7      0
Number      0    0        0     53

Perfect on test set for numbers 200 to 300!
Well, the second layer is easy:
lmModel <- lm(arep ~ a - 1, mutate(theData, arep = a))

The error estimating the number is
testData %>%
  mutate(pred = predict(treeModel, ., type = 'class')) %>%
  filter(pred == 'Number') %>%
  mutate(apred = predict(lmModel, .),
         error = a - apred) %>%
  pull(error) %>%
  summary()

     Min.   1st Qu.    Median      Mean   3rd Qu.      Max. 
5.684e-14 5.684e-14 5.684e-14 5.684e-14 5.684e-14 5.684e-1

... well very close to 0. Tada!
We learned FizzBuzz from data!
Derp learning
Probably you can do the same stuff with deep learning. You can also do stacked models with LSTM layers and convolution (ya know, because of modulo 3 and 5), and with a huge amount of data you may have a chance to generalize some patterns... yeah... no.
So hope this answer helps to clarify that yes it is possible. And no, you don't need deep learning to do the job. And now, from a single feature a even deep learning will not be able to learn FizzBuzz.
As for prime numbers... if you compute/engineer as many features as there are prime numbers, you can learn them from data, too. ¯_(ツ)_/¯
