Here’s the problem:

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

1.The number should be divisible by 9.

2.If the rightmost digit is removed, the remaining number should be divisible by 8.

3.If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.

4.And so on, until there’s only one digit (which will necessarily be divisible by 1).

The folks over at Programmable Gatorade wanted to take this classic math problem and put their Altera Cyclone IV FPGA board to use in solving it. The design uses the board’s 50MHz clock and finds the solution in approximately 2.2ms. There are three main components to the design: a module to calculate all of the unique combinations of the digits, a module to perform the division on the resulting combinations, and a LCD interface module to display the answer once found.

It became clear that the process is recursive: to find all the unique combinations of the elements in a set you pull out each element in turn and find the unique combinations of the remaining elements. I try to show this process in the graph below.

Long story short – with the design properly implemented on the FPGA the answer could be calculated in only 2.2 ms! Feel free to check out the entire article by Programmable Gatorade for the skinny on creating the design, coding it, and more! Great job guys. You’re helping to keep math exciting!

So go ahead, give it a try, and chime in in the comments section with your results!

(via Programmable Gatorade)