Functional Python Programming

Chapter 2

()[ )

() ()[ )

True

coprime , ,

mod 0 coprime , 1,

ab

nab

na na b ab

 =

=

 ≠∧ + <

if

if

This version is relatively easy to confirm by examining the two cases, which are
given as follows:

• If the range is empty, ab= , we evaluate something like:
  coprime 131071( , 363,363[ )). The range contains no values, so the return is
  a trivial True.


• If the range is not empty, we ask something like coprime 131071( , 2 ,363[ )).

This decomposes into (^131071) ()mod 2 ≠∧0 c oprime 131071( , 3 ,363[ )). For this
example, we can see that the first clause is True, and we'll evaluate the
second clause recursively.
As an exercise for the reader: this recursion can be redefined to count down instead
of up, using [a,b-1) in the second case.
As a side note, some folks like to think of the empty interval as a ≥ b, not a=b.
This is needless, since a is incremented by 1 and we can easily guarantee that
a≤b, initially. There's no way for a to somehow leap past b by some error in the
function; we don't need to over-specify the rules for an empty interval.
Here is a Python code snippet that implements this definition of prime:
def isprimer(n):
def isprime(k, coprime):
"""Is k relatively prime to the value coprime?"""
if k < coprimecoprime: return True
if k % coprime == 0: return False
return isprime(k, coprime+2)
if n < 2: return False
if n == 2: return True
if n % 2 == 0: return False
return isprime(n, 3)
This shows a recursive definition of an isprime() function. The half-open
interval 2,1+ n) is reduced to just the low-end argument, a, which is renamed
coprime in this function to clarify its purpose. The base case is implemented as
n < coprimecoprime; the range of values from coprime to 1+math.sqrt(n)
would be empty.