Friday Puzzle

Question

What numbers that can not be written in the form $i_4 * 4 + i_9*9$ where the $i$ are positive integers?

Solution generate all possible combinations of sums of 4's and 9's (up to a maximum of $i<limit$), put them into a set, and see what numbers are missing from this set

source



In [ ]:

    
import time
def timer():
    start = time.time()
    def f(report=False):
        elapsed = time.time() - start
        if report:
            print ("time elapsed %5.3f" % elapsed)
        return elapsed
    return f

We are only looking for combinations with $i<limit$



In [55]:

    
limit = 250

Procedural Style - square

here we simple generate the square $i_4,i_9 = 1\ldots limit$



In [56]:

    
mytimer = timer()
can_reach = set() 
numbers = set(range(1,100))
for i in range(0,limit):
    for j in range (0,limit):
        num = 4*i + 9*j
        can_reach = can_reach | {num}

can_not_reach = numbers - can_reach
t_sqr = mytimer(True)
can_not_reach









    



time elapsed 5.650






    Out[56]:





{1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 19, 23}

Procedural Style - triangle

here we are somewhat smarter, using that the addition commutes, and only sum over the triangle, ie the following series $$ 0,\ 4,\ 9, 4+4,\ 4+9,\ 9+9,\ 4+4+4,\ 4+4+9,\ \ldots $$



In [57]:

    
mytimer = timer()
can_reach = set() 
numbers = set(range(1,100))
for i in range(0,limit):
    for j in range (0,i+1):
        num = 4*j + 9*(i-j)
        #print ("%i = 4*%i + 9*%i" % (num,j,i-j))
        can_reach = can_reach | {num}

can_not_reach = numbers - can_reach
t_tria = mytimer(True)
can_not_reach









    



time elapsed 1.523






    Out[57]:





{1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 19, 23}

Functional Style

Here use a more pythonic functional style

we generate the ranges $(0,4,8,\ldots)$ and $(0,9,18,\ldots)$
we generate the cartesian product range $(0,0), (4,0), \ldots$
we generate the sum range $0, 4, 8, \ldots$
we generate the set of numbers in the sum range ${0, 4, 8, \ldots}$
we calculate ${1\ldots 100} - {0,4,8\ldots}$



In [58]:

    
from operator import add
from itertools import product

mytimer = timer()
fours = range(0,4*limit,4)
nines = range(0,9*limit,9)
fours_and_nines = product(fours, nines)
fours_plus_nines = map( lambda x: add (*x), fours_and_nines)
set(range(100)) - set(fours_plus_nines)
t_func = mytimer(True)









    



time elapsed 0.032

Results

the triangle solution is an improvement by a factor 4, as expected; the Pythonic way of doing things is an improvement by a factor of almost 50x vs the triangle method. Note that the pythonic way is a square method, so raw-speedup is 150x+



In [59]:

    
print ("triangle sum vs square sum = %2.0fx" % (t_sqr / t_tria))
print ("functional vs triangle sum = %2.0fx" % (t_tria / t_func))
print ("functional vs square sum = %2.0fx" % (t_sqr / t_func))









    



triangle sum vs square sum =  4x
functional vs triangle sum = 48x
functional vs square sum = 178x



In [59]: