Saturday Puzzle #28 – Ones and Zeros

I like puzzles that are easy to state and don’t require a lengthy explanation. Today’s puzzle falls into that category. It comes from my good friend of 30 years, Ken O’Brien, who asked me this simple but perplexing question: “What is the smallest number evenly divisible by 225 that contains only the digits 1 and 0?”

If you’re not able to find the answer analytically, see if you can solve it algorithmically. In other words, see if you can come up with a procedure (brute force method or something more efficient) for finding the answer and leave me a comment with your results (I’ll post the answer on Tuesday). Oh, and by the way, don’t try to use ones and zeros for commercial purposes – they’re patented.

Solution: I know of three ways to solve this problem:

  1. The Slow Search Method – This approach starts with 225 and multiplies it by an ever-increasing sequence of integers looking for a number that contains only ones and zeros. Here’s the Python code to implement this method:

    import time
    
    start = 225    # starting number
    num = start
    cnt = 1
    binary_digits = ('0', '1')
    keep_looking = True
    
    # capture start time
    start_time = time.clock()
    
    while keep_looking:
        num += start
        # check for all 1s and 0s in num
        keep_looking = False # assume we found desired number
        for i in str(num):
            if i not in binary_digits:
                keep_looking = True # nope, not the desired number
                break
        cnt += 1
        
    elapsed = time.clock() - start_time # calculate elapsed time
    
    # we exit the above loop when we've found the desired number
    print('after', cnt, 'iterations and', elapsed, 'seconds:', num)

    Which prints the following result:
    after 49382716 iterations and 83.33 seconds: 11111111100

  2. The Fast Search Method – This strategy observes that the desired result looks like a binary number (albeit in base 10) so it tests a sequence of binary numbers, treating each as a base 10 number, looking for one that’s evenly divisible by 225. This is much faster than the previous method because it automatically skips all the base 10 numbers that have digits other than 1 and 0. Here’s the Python code:

    import time
    
    def convert(num, b1, b2):
        '''convert the passed num from base b1 to base b2'''
        result = 0
        digits = []
        while num:
            digits.append(num % b1)       
            num //= b1
        digits.reverse()
        for i in digits:
            result = (result * b2) + i
        return result
    
    start = 225
    num = 1000 # start with smallest possible answer > 225
    cnt = 1
    
    # capture start time
    start_time = time.clock()
    
    while True:
        if (num % start) == 0:       
            break
        # convert to base 2, increment, then convert back to base 10
        num = convert(num, 10, 2)
        num += 1
        num = convert(num, 2, 10)
        cnt += 1
        
    elapsed = time.clock() - start_time # calculate elapsed time
    
    # we exit the above loop when we've found the desired number
    print('after', cnt, 'iterations and', elapsed, 'seconds:', num)

    which prints the following result:
    after 2037 iterations and 0.04 seconds: 11111111100

  3. The Analytical Method – Because 225 ends in 25, multiples of 225 will end in one of four possible digit pairs: 25, 50, 75 or 00. The only one that meets our requirements (only 1s and 0s allowed) is the last one so we know that the result must end with two 0s. We can also see that 225 is divisible by 9 (recall the rule from grade school about summing the digits to check if a number is divisible by 9) and, therefore, any multiple of 225 must also be divisible by 9. Thus, the digits in the result must also sum to 9, so the smallest possible number meeting our requirements will contain nine consecutive 1s and will end with two 0s: 11111111100.

Obviously the fast search method is much more efficient than the slow search method (nearly 50,000,000 fewer loop iterations and 2,000 times faster) but the analytical approach is the clear winner because it doesn’t require any searching at all. The most efficient program of all is the one you don’t need to write. :)

3 thoughts on “Saturday Puzzle #28 – Ones and Zeros”

  1. It has to be even multiple of 225, otherwise it will end in 5. Thus, we simply ask what the smallest number divisible by 450 that contains only 1′s and zeros is. Once again, because the lowest place not held by an placeholding 0 is the ten’s place, and that place is held by a 5, it must be an even multiple of 450, or it will contain a 5, so we can ask what the smallest number divisible by 900 that contains only 1′s and zeros is. At this point it’s easy, because the 1′s and 10′s places are only held by 0′s, we simply find the smallest number divisible by 9 that has only 1′s and zeros, and multiply that by 100. I’m sure all of the math nerds out there know that the easiest way to test if a number is divisible by 9 is to check if the digits add up to a number divisible by 9. (i.e. for 10998, 1+0+9+9+8=27, which is divisible by 9, thus 10998 is divisible by 9) We can use this to our advantage here. Any number that is divisible by 9 must have digit’s whose sum is equal to a multiple of 9. Thus, trying to find the smallest number divisible by 9 is simply finding the shortest combination of 1′s and 0′s whose sum is 9. Ergo, 111111111 is the smallest number divisible by 9 that contains only 1′s and zeros, and 11111111100 is the smallest number divisible by 225 that contains only the digits 1 and 0. I already posted this via facebook, but I’m not sure if it’s visible to everyone.

  2. The answer is that there is none.
    Here’s my proof. Multiplying 225 by any random number N will produce 0 or 5
    in the least significant digit. So we know N must be even.
    With N=2 we get 450. Now the 2nd digit will also flip between 0 and 5 again for N**2,
    or 4. 225*4 = 900. Now the problem simplifies to 9 * X = 1′s & 0′s,
    900 times anything will leave the 00 in place.
    Now 9*1=9, 9*2=18, …9*5=45,…9*9=81, 9*10 = 90. Another 0! Now we are 9000.
    And we have 9 again. There is nothing you can multiply 9 by to get to a number with only 1′s and 0′s.
    I’m not feeling super sure about this, but I’ll submit and think more during the weekend.

  3. Nice, I really appreciate it. How am I now to prove that I found the solution on my own with this *rglmbrmpf”-Spoiler posting it publicly on the first day?

    Hope that can be run differently next time.

    Olaf

Leave a Reply