Looking for a number with specific conditions in python

Question

So I need to create a function that finds the minimum natural number that can be divided by 2,3,4,5,6,7,8,9,10

This is what I got so far:

def divisible():
    number= 2
    if number % 2 == 0:
        if number % 3 == 0:
            if number % 5 == 0:
                if number % 7 == 0:
                    if number % 9 == 0:
                        print number
    else:
        number = number + 2
divisible() 

So this is what I did there:

If the natural number can be divided by 2 entirely, then it can also be divided by 4 and the same goes with 10 and 5, therefore I removed them. Then I'm checking if the division can be done entirely by all the other numbers. My idea is to print the number that can go through all those conditions(if's).

Also, as the number I'm looking for can be divided by 2, that means that it has to be an even number so I'm adding 2 to it every time.

The idea is to find a number that can be divided entirely by 2,3,4,5,6,7,8,9 and 10 and then print that number.

Can anyone give a little help?

Answer 1

Your code is not looping over numbers; number remains static, and since number = 2, the other tests all fail. That's because you didn't make a loop here.

You also eliminated the wrong numbers from your test; a number divisible by 2 is not necessarily divisible by 10, only the reverse is true. So you need to test for 6, 7, 8, 9 and 10 here. Instead of a nested set of if statements, you could use all() to test a series of numbers:

n = 0
while True:
    n += 10
    if all(n % i == 0 for i in (6, 7, 8, 9)):
        print(n)
        break

You need to increment by 10 at the very least, and once you increment in steps of 10 there is no point in testing if it is divisible by 10 either.

This generates the first such a number. If you needed to test if a number is divisible by all those factors, use % to test if there is no remainder for those 5 numbers:

def is_divisible(n):
    return all(n % i == 0 for i in (6, 7, 8, 9, 10))

Answer 2

Every time you call divisible() you set number to 2. And you will never reach else. What you need is to set number to 2 outside the function and then call the funcion in a loop with number as parameter till you find a number you are looking for.

That is:

def divisible(num):
    # here code to test in num is entirely divisible by number you want
    return result # True is divisible, False if not divisible

And call this function in loop:

x = 2
while not divisible(x):
     x = x + 2
print "Number " + str(x) + " is the minimum number entirely divisible by 2, 3, 4, 5, 6, 7, 8, 9 and 10." 

Note that this is not an optimal algorithm ti find such numbers.

Answer 3

This question is a problem of computing the least common multiple (LCM). Several standard methods for solving it are by using the greatest common divisor (GCD), prime factorization and reduction.

GCD comes into play since, for two integers a and b,

GCD(a,b)*LCM(a,b) = a*b

and computation of GCD is well known using the Euclidian algorithm, although maybe not by that name, but which can be expressed as

def gcd(x,y):
    while y:
        x,y = y,x%y
    return abs(x)

GCD and LCM for two numbers in themselves does not solve the problem for more than two, however they both share the property of associativity, which is a setup for reduction over more than two numbers. What that means is:

GCD(a,b,c,d)=GCD(GCD(GCD(a,b),c),d)  # associativity
LCM(a,b,c,d)=LCM(LCM(LCM(a,b),c),d)  # associativity

and for some function fun

reduce(fun,[a,b,c,d]) 

is equivalent to

fun(fun(fun(a,b),c),d) # expanded reductive form 

which implies that

GCD(a,b,c,d) = reduce(GCD,[a,b,c,d])

LCM associativity also implies that just a two argument LCM function is necessary for reduction over more than two and GCD is not needed. That's good because it decreases overhead, since computing LCM directly requires fewer operations than with GCD.

In case you're wondering, GCD and LCM are both also commutative. That simply means the order of elements in their argument lists does not affect the results.

Based on this information, review of over 150 LCM implementations and some testing, the following Python LCM function appears best in performance and simplicity:

def lcm(*args):
    def lcm2(x,y):
        tmp=x
        while (tmp%y)!=0:
            tmp+=x
       return tmp
    return reduce(lcm2,args)

This function is from the answer by Eratosthenes on Least common multiple for 3 or more numbers.

Let's see how it performs using Python 3.4.3 x64

from functools import reduce

a = [2, 3, 4, 5, 6, 7, 8, 9, 10]

lcm(*a)
Out[9]: 2520

timeit lcm(*a)
100000 loops, best of 3: 5.95 µs per loop  

timeit lcm(2, 3, 4, 5, 6, 7, 8, 9, 10)
100000 loops, best of 3: 5.9 µs per loop

For Python 2.7.10 x64

lcm(*a)
Out[60]: 2520

timeit lcm(*a)
100000 loops, best of 3: 4.36 µs per loop

timeit lcm(2, 3, 4, 5, 6, 7, 8, 9, 10)
100000 loops, best of 3: 4.33 µs per loop

LCM can also be computed using prime factorization. The fundamental theorem of arithmetic, also called the unique factorizaton theorem, says that "every integer greater than 1 either is prime itself or is the product of prime numbers, and this product is unique, up to the order of the factors." This means that each divisor in a list of divisors has a prime factorization and each prime in all these factorizations occurs a maximum number of times for at least one divisor. Therefore, the minimum natural number which can be evenly divided by all the divisors, AKA their LCM, is the product of all the occurring primes each raised to the power of its maximum number of times. Here is implementation code for this method:

from collections import defaultdict
from operator import mul
try:
    reduce
except:
    from functools import reduce

def findmnn(a):  

    def prime_factors(n):
        factors = defaultdict(int)
        d = 2
        step = 1
        while d*d <= n:
            while n>1:
                while n%d == 0:
                    factors[d] += 1
                    n = n/d
                d += step
                step = 2
        return factors

    d = defaultdict(int)

    for i in a:
        p = prime_factors(i)
        for j in p:
            if p[j] > d[j]:
                d[j] = p[j]

    return reduce(mul, map(lambda x: x**d[x], d))

Given the list of divisors as

a = [2, 3, 4, 5, 6, 7, 8, 9, 10]

findmnn(a)
Out[3]: 2520

Testing with timeit using Python 2.7.10 x64

timeit findmnn(a)
10000 loops, best of 3: 23.1 µs per loop

Testing with timeit using Python 3.4.3 x64 on the same platform:

timeit findmnn(a)
10000 loops, best of 3: 49.4 µs per loop

For comparison and on the same platform:

def mpmnn():
    n = 0
    while True:
        n += 10
        if all(n % i == 0 for i in (6, 7, 8, 9)):
            return n

Using Python 2.7.10 x64

timeit mpmnn()
1000 loops, best of 3: 245 µs per loop

And with Python 3.4.3 x64

timeit mpmnn()
1000 loops, best of 3: 244 µs per loop

Here are some references

1. Least Common Multiple (Wolfram World)
2. Least Common Multiple Code Examples (Rosetta Code)
3. Greatest Common Divisor (Wolfram World)
4. Euclidean Algorithm (Wolfram World)
5. Fundamental theorem of arithmetic (WikepediA)

Answer 4

This worked:

def divisible():
residu=0
numero = 1
for x in range(1,11): #Per a cada valor en el for definim el residu
    residu = numero%x + residu
    if (residu==0):#En cas de que el residu dongui 0, creem una variable div que será el nostre número i la definim com la variable del numero que anem provant
        div = numero

while (residu != 0):#Si el residu es diferent de 0
    numero=numero+1
    residu=0
    for x in range(1,11):#Per a cad valor del for calculem el residu i el sumem als residus de les operacions anteriors
        residu = numero%x + residu
        if (residu==0):#Si el residu dona 0, el numero es la nostra solució
            div = numero
print div

divisible()