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.
Monday, February 24, 2014
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.A curious thing about its Python code is that I had to introduce a name terms for a partial result:
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.
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]