<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 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
Step1:  We are only looking for combinations with $i<limit$
Step2:  Procedural Style - square
here we simple generate the square $i_4,i_9 = 1\ldots limit$
Step3:  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
$$
Step4:  Functional Style
Here use a more pythonic functional style
1. we generate the ranges $(0,4,8,\ldots)$ and $(0,9,18,\ldots)$
1. we generate the cartesian product range $(0,0), (4,0), \ldots$
1. we generate the sum range $0, 4, 8, \ldots$
1. we generate the set of numbers in the sum range ${0, 4, 8, \ldots}$
1. we calculate ${1\ldots 100} - {0,4,8\ldots}$
Step5:  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+
<ASSISTANT_TASK:>
Python Code:
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
Explanation: 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
End of explanation
limit = 250
Explanation: We are only looking for combinations with $i<limit$
End of explanation
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
Explanation: Procedural Style - square
here we simple generate the square $i_4,i_9 = 1\ldots limit$
End of explanation
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
Explanation: 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
$$
End of explanation
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)
Explanation: Functional Style
Here use a more pythonic functional style
1. we generate the ranges $(0,4,8,\ldots)$ and $(0,9,18,\ldots)$
1. we generate the cartesian product range $(0,0), (4,0), \ldots$
1. we generate the sum range $0, 4, 8, \ldots$
1. we generate the set of numbers in the sum range ${0, 4, 8, \ldots}$
1. we calculate ${1\ldots 100} - {0,4,8\ldots}$
End of explanation
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))
Explanation: 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+
End of explanation
<END_TASK>