CODEWITHSUNDEEP
pythonrecursionfunctional-programming
Nicola Amadio
Nicola Amadio

Reputation: 159

Functional Programming Python: smallest number divisible by each of the numbers 1 to 20

I want to build a while loop in python using its functional programming capabilities, but until now I'm failing.

What I have accomplished is this peace of code, which should calculate the smallest number divisible by each of the numbers 1 to 20. But it doens't seem it's using functional programming capabilities a lot. And also gives me the error as below:

"RuntimeError: maximum recursion depth exceeded" at the line of the incrementation of "i";

even if this should be limited to 20.

def byYmult(x, y): return x % y == 0
def first20div():
    i=0
    for y in range(1,20):
        i += byYmult(x, y)
    return i >= 20

def while_block():
    global x
    if first20div(): 
        print(x)
        return 1
    else:
        x += 1
    return 0

x = 0
while_FP = lambda: ((not first20div()) and while_block() ) or while_FP()
while_FP()

Upvotes: 1

Views: 411

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476669

This is non-functial for a lot of reasons:

  1. you do not pass, nor return functions;
  2. you only construct a named lambda expression at the bottom, but this is usually considered un-Pythonic;
  3. usually functional programming means you do not alter data, but here you define a global x, that you update;
  4. by some globals are also seen as non-functional: all data should be passed to the function.

So there is a lot to work with. Furthermore the algorithm you describe is not very optimal. Instead of performing a brute force approach where we keep guessing the number until finally we got lucky, a better approach is to calculate the least common multiple (LCM) of the numbers 1..20.

We can first define - in a functional way - we can calculate the LCM by calculating the greatest common divider (GCD) first, and this can be done by the Euclidean Algorithm. Lucky for us, it is already in the math package:

from math import gcd

Now the LCM is:

def lcm(a,b):
    return (a*b)//gcd(a,b)

The LCM of three or more numbers can be calculated by calculating the LCM of the first two numbers and then pass it as first argument to the LCM with the third number, or more formally:

lcm(x,y,z) == lcm(lcm(x,y),z)

and this can be done by using reduce from functools:

from functools import reduce

def lcm_multiple(xs):
    return reduce(lcm, xs)

and now we can calculate the answer, by passing it a range(2,20) object:

answer = lcm_multiple(range(2, 20))

Or in full:

from math import gcd
from functools import reduce

def lcm(a,b):
    return (a*b)//gcd(a,b)

def lcm_multiple(xs):
    return reduce(lcm, xs)

answer = lcm_multiple(range(2, 20))

Upvotes: 5

Related Questions