Mainly Tech projects on Python and Electronic Design Automation.

Monday, February 24, 2014

A fluency in programming is not the same as being a programmer.

It seems the UK government (and the US too), think that we should be teaching more children to program. I think so too. I don't necessarily think that equates to us needing more "programmers".

Many jobs such as most engineering and science posts and an increasing amount of financial jobs needs not just maths, but an appreciation of programming to be able to understand critical and widespread aspects of the job. Now just as those people are not all mathematicians, but need some maths to do their job,

I think that a greater number of workers should know about programming and computers - without necessarily calling themselves programmers as the need is there.

Friday, February 21, 2014

Almost primes (with a StopIteration twist)

I just created the Almost primes task on Rosetta Code:
A k-Almost-prime number is a natural number n, that is the exact multiple of k primes.
So, for example if k is 1, then this is the series of prime numbers themselves. If k is 2 then this is the series of semiprimes.
The task is to write a function/method/subroutine/... that generates k-almost primes and use it to create a table of the first ten members of k-Almost primes for 1 < = K < = 5
A curious thing about its Python code is that I had to introduce a name terms for a partial result:


from prime_decomposition import decompose
from itertools import islice, count
try: 
    from functools import reduce
except: 
    pass
 
 
def almostprime(n, k=2):
    d = decompose(n)
    try:
        terms = [d.next() for i in range(k)]
        return reduce(int.__mul__, terms, 1) == n
    except:
        return False
 
if __name__ == '__main__':
    for k in range(1,6):
        print('%i: %r' % (k, list(islice((n for n in count() if almostprime(n, k)), 10))))

Output:

1: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
2: [4, 6, 9, 10, 14, 15, 21, 22, 25, 26]
3: [8, 12, 18, 20, 27, 28, 30, 42, 44, 45]
4: [16, 24, 36, 40, 54, 56, 60, 81, 84, 88]
5: [32, 48, 72, 80, 108, 112, 120, 162, 168, 176]

StopIteration swallowing

The following will not work as any StopIteration exception raised by trying to pull more prime decomposition values from the decompose operator will just stop the iterator when we need the exception to propagate to the except clause and so return False:

        return reduce(int.__mul__, 
                      (d.next() for i in range(k)), 1) == n


END.

Semiprimes in Python

Someone added a Semiprime task to Rosetta Code:
    > Semiprime numbers are natural numbers that are products of exactly two (possibly equal) prime numbers. 
    > Example: 1679 = 23 × 73 (This particular number was chosen as the length of the Arecibo message). 
    > Write a function determining whether a given number is semiprime.
I first looked for a prime generator and found one in part of an existing Prime decomposition tasks example code, where decompose is a generator for the prime factors of its argument.
In [ ]:
from __future__ import print_function

import sys
 
def is_prime(n):
    return zip((True, False), decompose(n))[-1][0]
 
class IsPrimeCached(dict):
    def __missing__(self, n):
        r = is_prime(n)
        self[n] = r
        return r
 
is_prime_cached = IsPrimeCached()
 
def primes():
    yield 2
    n = 3
    while n < sys.maxint - 2:
        yield n
        n += 2
        while n < sys.maxint - 2 and not is_prime_cached[n]:
            n += 2
 
def decompose(n):
    for p in primes():
        if p*p > n: break
        while n % p == 0:
            yield p
            n /=p
    if n > 1:
        yield n
 
if __name__ == '__main__':
    # Example: calculate factors of Mersenne numbers to M59 #
 
    import time
 
    for m in primes():
        p = 2 ** m - 1
        print( "2**{0:d}-1 = {0:d}, with factors:".format(m, p) )
        start = time.time()
        for factor in decompose(p):
            print (factor, end=' ')
            sys.stdout.flush()
 
        print( "=> {0:.2f}s".format( time.time()-start ) )
        if m >= 59:
            break

Semiprime

The code for semiprime kind'a wrote itself from the description. I have a generator of prime factors. Lets check if the first two prime factors multiply to give n for a semiprime. Any errors and it isn't:
In [8]
from prime_decomposition import decompose

def semiprime(n):
    d = decompose(n)
    try:
        return d.next() * d.next() == n
    except:
        return False
You can then play around in the interpreter with it:
In [9]:
semiprime(1679)
Out[9]:
True
In [10]:
[n for n in range(1,101) if semiprime(n)]
Out[10]:
[4,
 6,
 9,
 10,
 14,
 15,
 21,
 22,
 25,
 26,
 33,
 34,
 35,
 38,
 39,
 46,
 49,
 51,
 55,
 57,
 58,
 62,
 65,
 69,
 74,
 77,
 82,
 85,
 86,
 87,
 91,
 93,
 94,
 95]

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive