n_multiple_min_N_zeros_ones

During my recent wanderings, I faced a mathematical problem which had to be solved by a Java program. The problem is:
You are given a number n. Find the smallest number N, which is divided by n, with the condition that N should have only 0s and 1s.

So what does one do? Attack it with the obvious, non-smart, longish way a.k.a brute-force method. Which is: Start multiplying n by 1 and see if the product n*1 has any digit other than 0 or 1 and if yes, reject it. Then multiply n with 2 and do the check again. Keep doing this until you find a number that has only zeros or ones.

See the brute force solution below, I have put all programs of this blog post together. This seems to work fine. But then you realize that the program puffs and heaves and puffs, in other words, very slow for 9. This makes the brute force solution unacceptable for 9 and multiples of 9. It's very slow.

At which point, one realizes that perhaps it is better to understand the mathematics behind the solution. So I googled. On math.stackexchange question 388165, the mathematical solution is available:

If you understood the above in one go, you are a mathematician already. Normally people don't understand it in one go. We are programmers. How much mathematics does a programmer have to know? This is an interesting topic, so let me take a digression here.

Mathematics and Programming
In the online book A Programmer's Guide To Data Mining, Ron Zacharski writes in the section on Minkowski Distance: "Arghhhh Math! When you see formulas like this in a book you have several options. One option is to see the formula -- brain neurons fire that say math formula -- and then you quickly skip over it to the next English bit. I have to admit that I was once a skipper. The other option is to see the formula, pause, and dissect it. I think this holds true to a lot of us -- once we are out of college, we forget the math that was taught and we all become math skippers."

Sarah Mei deals with the subject of math and programming in her blog post, Programming Is Not Math A lot of important points are made in that article, and I will summarize the key ones for you.

The vast majority of developer jobs only required middle-school math at the most. People with a math background did fine, of course, but people with a heavy language background often did better. Bilingual kids often took to programming more easily than monolingual kids. Here are some things people often say when asserting that people must be good at math to be good developers. Generally, they fall into three categories: 1. “You need to know math to be a good programmer.” * 1A. …because computer science comes from math. -- This is true. Academically speaking, most computer science departments trace their lineage to the mathematics department. * 1B. …because without a mathematical foundation, you’ll have only a surface understanding of programming. -- So, if you don’t actually need to know math to be a successful developer, perhaps instead the very act of learning it primes you to think the right way? 2. “You need to learn math to get the skills you need for programming.” * 2A. …because it teaches abstract problem solving, which you need to be good at programming. -- So while math is one way to learn to think about abstraction, it is not the only way. * 2B. …because programming based on the mathematical concepts of logic. -- if you don’t need to know math to be a developer, and you don’t need to learn math to be good at development…wait! But some jobs still do! 3. “Plenty of programming is still math!” -- If a small and shrinking set of programming applications require math, so much so that we cordon you off into your own language to do it, then it’s pretty clear that heavy math is, these days, a minor specialization. -- And even if you are writing code to do math-y things, you’re probably not very good at it unless you’re also good at language. Why does the idea that “if you’re good at math, you’ll be good at programming” persist so strongly? It makes sense that slow-moving academia hasn’t caught up yet. And the programmers who today are the senior developers, the old guard, came of age when this wasn’t yet true. So of course they think the path to success looks like theirs.

There are very interesting comments on the above article, and further links to explore this topic, but the one line that interested me most is :
Math is a language.

If this whetted your apetite, further ideas and information to explore are at programmers.stackexchange question 136987 -- What does mathematics have to do with programming?

Enough of digression
Coming back to our problem, even if you didn't understand the mathematical solution, you don't stop - you got to get the code working. You google more. Programmers are blessed with a variety of wonderful options such as forums, open source and stack overflow / exchange. And then you land on a mathpuzzle.com C solution to our problem.

So I want to understand what it tries to do and want to convert it to Java, and mention it to a techie (Tamjeed), who promptly sends the Java version back the next morning itself. Code is available below.

No issues, one can still get a crack at it. My usual method: convert the program to one's favourite language, which in my case is Ruby. Scripting languages like Ruby and Python often read like pseudo-code, so they help in easier understanding of algorithms. Ruby version is also given below.

I ran the programs for all integers from 2 to 2000. On my 6-year old Compaq laptop running Ubuntu 14.04 LTS, I timed them with the time command. Here's how the three versions (C, Java, and Ruby) fared:

	C	Java	Ruby
real	0m0.547s	0m2.790s	0m9.924s
user	0m0.445s	0m2.445s	0m9.409s
sys	0m0.041s	0m0.294s	0m0.296s

C took about half a second, Java about 3 seconds, and Ruby nearly 10 seconds. Ruby is beautiful but awfully slow.

---

Programs
Brute force in java
C solution from mathpuzzle.com
Java version
Ruby version