Saturday, January 8, 2011

Python in Liouville

This morning I came across the following little piece of mathematical trivia:

Choose any number (e.g. 14) and write down its divisors:

14
1, 2, 7, 14

Then write down the number of divisors of each of these divisors:
14
1, 2, 7, 14
1, 2, 2, 4

Now the square of the sum of this last group will always equal the sum of its member's cubes:
(1 + 2 + 2 + 4)2 = 13 + 23 + 23 + 43

Discovered by Joseph Liouville.

Well, I learned two new things today. Some mathematical trivia and that there was a French Mathematician that I had never heard of called Liouville.

Since I am always on the lookout for simple problems that can work as Python programming exercises, I decided to use the above problem.

Here is my first attempt:

def factorise(n):
    '''
    Given a number return a list of the factors of that number.
    '''
    factors = [1]
    i = 2
    while i <= n:
        if n % i == 0:
            factors.append(i)
        i += 1
    return factors


def try_num(n):
    factors = factorise(n)
    num_factors = []
    for factor in factors:
        num_factors.append(len(factorise(factor)))

    print 'Factors: ', num_factors
    print 'Square of sum: ', sum(num_factors) * sum(num_factors)
    print 'Sum of cubes: ', sum([factor * factor * factor for factor in num_factors])


def main():
    try_num(14)
    try_num(144)
    try_num(65536)

if __name__ == '__main__':
    main()
It works, but while making some small changes, I also noticed that we can do the factorising as a single list comprehension. In other words, we can replace
factors = [1]
i = 2
while i <= n:
    if n % i == 0:
        factors.append(i)
    i += 1
    return factors
with
return [x + 1 for x in xrange(n) if n % (x + 1) == 0]
Also, we can use a list comprehension for the loop in try_num. This led to the second version of the program:
def factorise(n):
    '''
    Given a number return a list of the factors of that number.
    '''
    return [x + 1 for x in xrange(n) if n % (x + 1) == 0]

def try_num(n):
    num_factors = [len(factorise(factor)) for factor in factorise(n)]

   print 'Factors: ', num_factors
   print 'Square of sum: ', sum(num_factors) ** 2
   print 'Sum of cubes: ', sum([factor ** 3 for factor in num_factors])

def main():
    try_num(14)
    try_num(144)
    try_num(2011)
    try_num(65536)

if __name__ == '__main__':
    main()


Even after years of using Python, I am still impressed by its ability to express certain things lucidly and compact way.

2 comments:

  1. If you're using Python for mathematics, you should look at Sage (http://www.sagemath.com) which is based on Python. Here, for example, is Liouville's result in Sage:

    sage: n=1001
    sage: L=[number_of_divisors(i) for i in divisors(n)]; L
    [1, 2, 2, 2, 4, 4, 4, 8]
    sage: sum(L)^2, sum(i^3 for i in L)
    (729, 729)

    ReplyDelete
  2. There's a proof and discussion of this result on my own blog: http://bit.ly/hJZjqB

    cheers,
    Alasdair

    ReplyDelete