Iteration

The factorial function is defined over the non-negative integers as:¹

\[n! = \begin{cases} 1, & \text{if } n = 0;\\ n \times (n - 1)!, & \text{if } n > 0. \end{cases}\]

Define a function that computes the factorial of a given non-negative integer \(n\) using iteration by while.

 def factorial(n):
     """Return the factorial of n (n>=0).

     >>> factorial(0)
     1
     >>> factorial(5)
     120
     >>> factorial(7)
     5040
     """

Solutions

 def factorial(n):
     """Return the factorial of n (n>=0).

     >>> factorial(0)
     1
     >>> factorial(5)
     120
     >>> factorial(7)
     5040
     """
     store = 1
     k = 1
     while k <= n:
         store *= k
         k += 1
     return store

Implement the modulo operation using iteration by while. The modulo operation \(a \bmod b\) returns the remainder of the division of \(a\) by \(b\). You can assume that \(a \geq 0\) and \(b > 0\).

 def modulo(a, b):
     """Return a mod b (a>=0, b>0).

     >>> modulo(10, 3)
     1
     >>> modulo(14, 5)
     4
     >>> modulo(9, 9)
     0
     """

Solutions

 def modulo(a, b):
     """Return a mod b (a>=0, b>0).

     >>> modulo(10, 3)
     1
     >>> modulo(14, 5)
     4
     >>> modulo(9, 9)
     0
     """
     while a >= b:
         a -= b
     return a

The Fibonacci function \(F_n\) is defined as:

\[F_n = \begin{cases} 0 & \text{if } n = 0, \\ 1 & \text{if } n = 1, \\ F_{n-1} + F_{n-2} & \text{if } n > 1. \end{cases}\]

There is a unique (and infinite) sequence of numbers called the Fibonacci sequence (or numbers) where the first number is 0, the second number is 1, and each subsequent number is the sum of the two preceding numbers.

Define a function that computes the n-th Fibonacci number using iteration by while. Write two versions, one that counts up, and one that counts down.

 def fibonacci(n):
     """Return the n-th Fibonacci number (n>=1).

     >>> fibonacci(1)
     0
     >>> fibonacci(2)
     1
     >>> fibonacci(8)
     13
     """

Solutions

 def fibonacci(n):
     """Return the n-th Fibonacci number (n>=1).

     >>> fibonacci(1)
     0
     >>> fibonacci(2)
     1
     >>> fibonacci(8)
     13
     """
     if n <= 2:
         return n - 1
     count = 3
     prev, curr = 0, 1
     while count <= n:
         prev, curr = curr, prev + curr
         count += 1
     return curr

You have a message source that emits random integers in the range 1–100 (check this for how to implement such a source). Define a function that listens to this source and returns the first three consecutive integers \(m\), \(n\) and \(p\) such that \(m\leq n \leq p\). You can assume that such a triplet will eventually be emitted by the source. When returning the result you can put comma between the variables (e.g. return m, n, p).

 def first_non_decreasing_triplet():
     """Return the first non-decreasing triplet of random integers between 1 and 100.

     >>> import random
     >>> random.seed(48)
     >>> first_non_decreasing_triplet()
     (17, 72, 92)
     """

Solutions

 def first_non_decreasing_triplet():
     """Return the first non-decreasing triplet of random integers between 1 and 100.

     >>> import random
     >>> random.seed(48)
     >>> first_non_decreasing_triplet()
     (17, 72, 92)
     """
     from random import randint
     m, n, p = randint(1, 100), randint(1, 100), randint(1, 100)
     while not (m <= n and  n <= p):  # not (x <= y <= z) for short
         m, n, p = n, p, randint(1, 100)
     return (m, n, p)

Define a function that takes a positive integer and returns the sum of its digits. Two mathematical operations that might be useful here are modulo and division.

 def sum_of_digits(n):
     """Return the sum of the digits of a positive integer n.

     >>> sum_of_digits(123)
     6
     >>> sum_of_digits(4096)
     19
     >>> sum_of_digits(7)
     7
     """

Solutions

 def sum_of_digits(n):
     """Return the sum of the digits of a positive integer n.

     >>> sum_of_digits(123)
     6
     >>> sum_of_digits(4096)
     19
     >>> sum_of_digits(7)
     7
     """
     total = 0
     while n > 0:
         digit = n % 10
         total += digit
         n = n // 10
     return total

Write a Python function gcd that implements Euclid’s algorithm. The function should return the greatest common divisor of the two input integers \(a\) and \(b\).
An aliquot sequence is a sequence seeded by a positive integer and each number in the sequence, except the seed, is equal to the sum of the proper divisors of the number immediately preceding it. Write a function that maps a given positive integer into the next item in its aliquot sequence.

An integer is happy if it divides the sum of the numbers in its collatz sequence. The pride of an integer is the total number of happy integers in its collatz sequence, excluding itself if it is happy. Define a function that computes the largest and most proud integer less than a given positive integer \(k\).

Criteria

Those who solved this can use Python’s built-in sum. You can use collatz_sequence from collatz module.

Solution

 from collatz import *

 def happy(n):
     """n>1 is happy if it can divide the sum of its Collatz sequence"""
     from collatz import collatz_sequence
     return sum(collatz_sequence(n)) % n == 0

 def pride(n):
     """The number of happy integers in n's Collatz sequence"""
     return len([x for x in collatz_sequence(n) if happy(x)])

 def most_proud(k):
     """return the most proud largest integer less than k"""
     return proc({'n':1,'maxpride':0, 'maxn':1},
                 lambda s: s['n']<k,
                 lambda s: {'n': (newn := s['n'] + 1)}|
                           ({'maxpride': newpride, 'maxn': newn}
                            if (newpride := pride(newn)) > s['maxpride']
                            else s|{'n': s['n']+1}))

Alternative definitions of pride:

 pride = lambda n: sum([int(happy(x)) for x in collatz_sequence(n)])

 from functools import reduce
 pride = lambda n: reduce(lambda acc, x: acc + int(happy(x)),
                          collatz_sequence(n),
                          0)

Define a function bonacci(n, k) that computes the nth k-bonacci number. The k-bonacci numbers are defined as follows:
\[B(n, k) = \begin{cases} 0 & \text{if } n < k - 1, \\ 1 & \text{if } n = k - 1, \\ \sum_{i=1}^{k} B(n - i, k) & \text{if } n \geq k. \end{cases}\]
For example, the Fibonacci numbers are the 2-bonacci numbers.
Criteria and hints
- You can also solve by while but make sure you can also solve with proc_seq or proc from funcutils.
- Use a tuple (or list) as memory.
- You need to figure out how to construct your memory. The following “trick” is not allowed:
  >>> a = (1,)*5 # a tuple of five 1s >>> a (1, 1, 1, 1, 1)
- Do NOT use built-in sum, unless you solved this.
- Use slicing and concatenation (+) to manipulate memory. Slicing:
  >>> t = (1, 2, 3, 4, 5) >>> t[1:] # all but the first element (2, 3, 4, 5) >>> t[:-1] # all but the last element (1, 2, 3, 4) >>> t[1:3] # elements at index 1 and 2 (2, 3)
For integers \(n,m > 1\) and \(m\neq n\), we say ‘\(n\) governs \(m\)’ iff \(m\) is in the Collatz sequence seeded by \(n\). Define a function governors that maps n and k to the list of governors of \(n\) that are less than k.
Solution

I provide only the comprehension based solution here, which is almost plain English. I also wanted to show how to have docstrings for lambda expression. But note that it is not good style to use lambda to define named functions with docstrings. The only reason to use lambda for such functions is to make sure you are writing a expression-based function without statements.
```
 governors = lambda n, k: [m for m in range(1,k) if n in collatz_sequence(m)]
 governors.__doc__= """return list of m<k s.t. n is in m's Collatz sequence"""
```

Define mutual_government(k) that returns all pairs of integers \((m,n)\) with \(m,n < k\) such that \(m\) governs \(n\) and \(n\) governs \(m\).

Solution

 mutual_government = lambda k: []

No need to bother for a program here, as mutual government is mathematically impossible. Why?

But taken as a programming exercise, mutual government can be computed by:

 governs = lambda m, n: m!=n  and n in collatz_sequence(m)
 mutual_government = lambda k: [(m,n)
                                for m in range(1,k)
                                for n in range(1,k)
                                if  governs(m,n) and governs(n,m)]

Given integers \(n,m\) with \(n,m >1\) and \(n\neq m\), \(n\) is an observer for \(m\), iff \(n\) divides the sum of the numbers in the Collatz sequence seeded by \(m\). An observer \(n\) of \(m\) is an external observer if \(n\) is not in the Collatz sequence seeded by \(m\). An observer \(n\) of \(m\) is said to be proper if \(n < m\).

Define a function observers(n, external=False, proper=False, prime=False) that returns the list of observers of \(n\) with the given properties. The parameters external, proper, and prime are boolean flags that indicate which type of observers the caller is interested in.

Solutions

 def observers(n, external=False, proper=False, prime=False):
     """Return the list of observers of n"""
     from collatz import collatz_sequence
     divides = lambda a,b: b % a == 0
     colseq = collatz_sequence(n)
     sumcolseq = sum(colseq)
     return [m for m in range(2,n)
             if divides(m, sumcolseq)
                and
                (not external or m not in colseq)
                and
                (not proper or m < n)
                and
                (not prime or isprime(m))
            ]

The factorial function is usually written as \(n!\) instead of the standard \(f(n)\) syntax. ↩