snippets

This page contains snippets of codes and problems which I find memorable. The focus is on how to solve the problems using Python – consider it my not-so-subtle attempt at Python evangelism.

The 1346 problem
The problem statement: Use the numbers 1, 3, 4 and 6 (exactly once each) and the operators +. -, * and / (may be used more than once) to form the number 24.

For such a simple question, it was surprisingly hard. I tried solving it on paper but unfortunately I hit a mental block. So I wrote a small Python script (1346.py) to exhaust all possibilities and amazingly there was exactly one answer! The code illustrates the use of a generator function and some recursive functions. It requires Python 2.5 as it uses yield.

Update: Recently I was asked if this problem can be solved in a more general setting. Assuming that (i) the list of numbers are randomly chosen positive integers; (ii) the target is a positive integer; (iii) we need not use all the numbers and (iv) we do not use division, then it can probably be solved using the heuristics in the SubsetOps class. See the README.txt file within the TGZ file.

Primality testing using regular expressions
I read about this back when I used to hang around comp.lang.perl. It is a clever way to use regular expressions in Perl:

    perl -e 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' <number to test>

To convert it to Python, we need to import the sys and re module and code as follows:

    #!/usr/bin/env python
    import re, sys
    if not re.match(r'1?$|(11+?)\1+$', '1'*int(sys.argv[-1])):
        print "Prime"

Sieving for a million totient
Euler’s totient function t(n) is defined as the number of positive integers less than or equal to n that are coprime to n. It is easy to compute (see formula) if one knows the prime factors of n. But what if we want to compute the totient of the first million positive integers? Naively we can find the prime factors of every n from 1 to 1 million and apply the formula. But finding prime factors of large numbers can be slow. To speed up the work, we can use the concept of a sieve.

Assuming we have a function primes(n) returning a list of primes less than n (such a function may be implemented using the classic Sieve of Eratosthenes or the newer Sieve of Atkin), we can compute a list of totients up to n as follows:

    def totients(n):
    t = range(0,n)
    for p in primes(n): # sieving! for each p, visit those i that has p as factor
        for i in xrange(p, n, p):
            t[i] = (t[i]/p) * (p-1)
    return t
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: