© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022
M. IndenPython Challengeshttps://doi.org/10.1007/978-1-4842-7398-2_2

2. Mathematical Problems

Michael Inden1  
(1)
Zurich, Switzerland
 

In this chapter, you start learning some basics about a few mathematical operations, including prime numbers and the Roman numeral system. Additionally, I present a couple of ideas for number games. The chapter is rounded off by a short introduction to lambdas. With all this knowledge, you should be well prepared for the exercises.

2.1 Introduction

2.1.1 Short Introduction to Division and Modulo

Besides multiplication and division, the modulo operation (%) is also used quite frequently. It is intended to determine the remainder of a division. Let’s illustrate this as follows for integers where division remainders fall under the table:

(5 ∗ 7 + 3) // 7 = 38 // 7 = 5

(5 ∗ 7 + 3) % 7 = 38 % 7 = 3

Even with these few operations, you can solve various tasks. Please recall the following things for actions on (integer) numbers:

  • n / 10: Obviously divides by the value 10. Since Python 3, this returns a floating point number as result. If you need an integer, you can use a type conversion with int(), such as int(value / 10).

  • n // 10: Also divides by the value 10. Because the // operator performs an integer division without a remainder, it is possible to truncate the last digit with it.

  • n % 10: Determines the remainder of a division by 10 and thus the last digit.

Extraction of digits To extract the digits of a number, combine modulo and division as long as the remaining value is greater than 0.
def extract_digits(number):
    remaining_value = number
    while remaining_value > 0:
        digit = remaining_value % 10
        remaining_value = remaining_value // 10
        print(digit, end=' ')
    print()
In Python, there is another special feature with the built-in function divmod(), which returns both the divisor and the remainder as a result—as a shortcut for the operators that are often called in combination. In addition, you can exploit tuple unpacking in the following, whereby the result is assigned to the respective variable:
def extract_digits(number):
    remaining_value = number
    while remaining_value > 0:
        remaining_value, digit = divmod(remaining_value, 10)
        print(digit, end=' ')
    print()
Let’s call this method once to understand its way of working—please note that the digits are output in reverse order.
>>> extract_digits(123)
3 2 1
Determine number of digits Instead of extracting individual digits, you can also use a repeated division to determine the number of digits in a decimal number by simply dividing by 10 until there is no remainder left:
def count_digits(number):
    count = 0
    remaining_value = number
    while remaining_value > 0:
        remaining_value = remaining_value // 10
        count += 1
    return count

2.1.2 Short Introduction to Divider

In the following, you examine how to determine all real divisors of a number (i. e., those without the number itself). The algorithm is quite simple. Initially, the result contains the number 1, as this is always a valid divider. Then you go through all numbers starting by 2 up to half of the value (all higher values cannot be integer divisors if 2 is already a divisor) and check if they divide the given number without a remainder. If this is the case, then this number is a divisor and is included in a result list. You implement the whole thing as follows:
def find_proper_divisors(value):
    divisors = [1]
    for i in range(2, value // 2 + 1):
        if value % i == 0:
            divisors.append(i)
    return divisors

One more small note about naming: For loop variables, short names like i are common, but current_number would also be a readable alternative.

Using list comprehension1 you can write the calculation more concisely:
def find_proper_divisors(value):
    return [i for i in range(1, value // 2 + 1) if value % i == 0]
Let’s call this method once to understand its operation and confirm it to be working well based on the output conforming to expectations:
>>> find_proper_divisors(6)
[1, 2, 3]
>>> find_proper_divisors(24)
[1, 2, 3, 4, 6, 8, 12]

2.1.3 Short Introduction to Prime Numbers

A prime number is a natural number that is greater than 1 and exclusively divisible by itself and by 1. There are two quite understandable algorithms for checking whether a given number is prime or for calculating primes up to a given maximum value.

Brute force algorithm for prime numbers Whether a number is a prime number or not can be determined as follows. You look for the number to be checked starting from 2 up to at most half of the number, whether the current number is a divisor of the original number.2 In that case, it’s not a prime. Otherwise, it needs to be checked further. In Python, this can be written as follows:
def is_prime(potentially_prime):
    for i in range(2, potentially_prime // 2 + 1):
        if potentially_prime % i == 0:
            return False
    return True
To try it out, run the function in a loop and determine all prime numbers up to the value 25. The program output demonstrates that the functionality works correctly.
>>> primes = []
>>> for number in range(2, 25):
...     if is_prime(number):
...          primes.append(number)
... print(primes)
Using list comprehension, you can write this more concisely:
>>> primes = [number for number in range(2, 25) if is_prime(number)]
... print(primes)
In both cases, you get the prime numbers less than 25 as the correct result:
[2, 3, 4, 5, 7, 11, 13, 17, 19, 23]

Optimization: Sieve of Eratosthenes Another algorithm for determining prime numbers up to a given maximum value is called the Sieve of Eratosthenes . It dates back to the Greek mathematician with the same name.

The whole thing works as follows. Initially, all numbers starting at the value 2 up to the given maximum value are written down, for example

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

All numbers are initially considered as potential candidates for prime numbers. Now the numbers that cannot be prime numbers are eliminated step by step. The smallest unmarked number is taken, in this case, the number 2, which corresponds to the first prime number. Now all multiples of it are eliminated, in the example 4, 6, 8, 10, 12, 14:

You continue with the number 3, which is the second prime number. Again, the multiples are eliminated. These are the numbers 6, 9, 12, 15:

The next unmarked number and thus a prime number is 5. The procedure is repeated as long as there are still unmarked numbers after the current prime number:

This leads to the following result for all prime numbers smaller than 15:

2, 3, 5, 7, 11, 13

In exercise 4, you are supposed to implement the Sieve of Eratosthenes by yourself. Then you may use the following values to test your algorithm in addition to the above:

Limit

Result

25

[2, 3, 5, 7, 11, 13, 17, 19, 23]

50

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

HINT: POSSIBLE OPTIMIZATIONS

As you can see, numbers are often crossed out several times. If you are mathematically a little more experienced, you can prove that at least one prime factor of a composite number must always be smaller equal to the root of the number itself. The reason is that if x is a divisor greater than sqrt(n), then it holds that p = n/x is smaller than sqrt(n) and thus this value has already been tried. Thus you can optimize the multiples’ elimination. Firstly, you start the elimination with the square of the prime number since all smaller multiples are already eliminated. Secondly, the calculation has to be done only up to the root of the upper limit. More details are supplied under https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

2.1.4 Roman Numbers

The Roman numeral system works with special letters and combinations of them to represent numbers. The following basic mapping is applicable:3

Roman number

I

V

X

L

C

D

M

Value

1

5

10

50

100

500

1000

The corresponding value is usually calculated by adding the values of the individual digits from left to right. Normally (see the following rules), the largest number is on the left and the smallest number is on the right, for example, XVI for the value 16.

Rules

Roman numerals are composed according to certain rules:
  1. 1.

    Addition rule: The same digits next to each other are added, for example XXX = 30. Likewise, this applies to smaller digits after larger ones, so XII = 12.

     
  2. 2.

    Repetition rule: No more than three identical digits may follow each other. According to rule 1, you could write the number 4 as IIII, which this rule 2 forbids. This is where the subtraction rule comes into play.

     
  3. 3.
    Subtraction rule: If a smaller number symbol appears in front of a larger one, the corresponding value is subtracted. Let’s look again at 4. It can be represented as subtraction 5 − 1. This is expressed as IV in the Roman numeral system. The following rules apply to the subtraction:

    • I precedes only V and X.

    • X precedes only L and C.

    • C precedes only D and M.

     

Examples

For better understanding and clarification of the above rules, let’s look at some notations of Roman numerals and their corresponding values:
$$ {displaystyle egin{array}{l} VIIkern8em =5+1+1kern20.25em =7\ {} MDCLXVIkern2em =1000+500+100+50+10+5+1kern3em =1666\ {}egin{array}{l} MMXVIIIkern2.5em =1000+1000+10+5+1+1+1kern5.25em =2018\ {} MMXIXkern3.5em =1000+1000+10-1+10kern8.5em =2019end{array}end{array}} $$

Noteworthy

The Arabic numerals common in our modern world rely on the decimal system. The digits’ position determines their value: thus, 7 can be the number itself, but it can also represent 70 or 700. However, in the Roman numeral system, the V always stands for a 5, regardless of the position.

Because of this particular structure of Roman numerals, many math operations are complex; even a simple addition may cause a bigger or sometimes even a complete change of the number. This becomes very obvious for the numbers 2018 and 2019 or for the addition III + II = V. Even worse, significantly more complex is a multiplication or division—there are speculations that this was one of the factors why the Roman Empire collapsed.

NOTE: LARGER NUMBERS

There are special notations for representing larger Roman numerals (in the range of ten thousand and above) because no four or more Ms are allowed to follow each other. This has no relevance for the tasks of this book. If interested, you may consult the Internet or other sources.

2.1.5 Number Games

In this section, you’ll look at a few special number constellations:

  • Perfect numbers

  • Armstrong numbers

  • Checksums

In many of the algorithms used below, you subdivide numbers into their digits to be able to perform corresponding number games.

Perfect Numbers

By definition, a number is called a perfect number if its value is equal to the sum of its real divisors (i. e., excluding itself). This may sound a bit strange, but it is quite simple. Let’s consider the number 6 as an example. It possesses as real divisors the numbers 1, 2, and 3. Interestingly, it now holds

1 + 2 + 3 = 6

Let’s look at another counterpart: the number 20, which has the real divisors 1, 2, 4, 5, and 10, but their sum is 22 and not 20.

1 + 2 + 4 + 5 + 10 = 22

Armstrong Numbers

In this section you examine Armstrong numbers. These are numbers whose individual digits are first exponentiated by the number of digits in the number and then added together. If this sum then corresponds to the original number’s value, it is called an Armstrong number. To keep things a little simpler, let’s look at the special case of three-digit numbers. To be an Armstrong number, the following equation must be satisfied with this number:
$$ xast 100+yast 10+z={x}^3+{y}^3+{z}^3 $$

The digits of the number are modeled as x, y, and z and are all in the range from 0 to 9.

The formula x ∗ 100 + y ∗ 10 + z results from the position of the digits and a textual representation of "xyz", so
$$ {displaystyle egin{array}{l}1ast 100+5ast 10+3kern0.5em ={}^{"}{153}^{"} \ {}3ast 100+7ast 10+1kern0.5em ={kern0.5em }^{"}{371}^{"}end{array}} $$
Let’s consider two examples for which this formula is satisfied:
$$ {displaystyle egin{array}{l}153=1ast 100+5ast 10+3kern0.5em =kern0.5em {1}^3+{5}^3+{3}^3=1+125+27=153\ {}371=3ast 100+7ast 10+1kern0.5em =kern0.5em {3}^3+{7}^3+{1}^3=27+343+1=371end{array}} $$
Variation As a modification, it is also quite interesting for which digits or numbers of the following equation are fulfilled:
$$ xast 100+yast 10+z={x}^1+{y}^2+{z}^3 $$
or
$$ xast 100+yast 10+z={x}^3+{y}^2+{z}^1 $$

For the first equation, there are the following solutions:

[135, 175, 518, 598]

For the second equation, there is no solution for x, y, and z in the range up to 100. If you like, you can verify this yourself when implementing the bonus part of exercise 9—or look at the solutions.

Algorithm for a Simple Checksum

A checksum is coded into various numbers so that it is easy to prove validity. This applies, for example, to credit card numbers and to data transfers via special protocols.

Let’s assume that a checksum has to be calculated for a number with four digits (hereafter modeled as a to d). Then you can perform the following calculation based on the position:
$$ abcdRightarrow left(aast 1+bast 2+cast 3+dast 4 ight)\%10 $$
Once again, let’s illustrate the calculation with examples:

Input

Position calculation

Value

Checksum

1111

1 * 1 + 1 * 2 + 1 * 3 + 1 * 4

1 + 2 + 3 + 4 = 10

10 % 10 = 0

1234

1 * 1 + 2 * 2 + 3 * 3 + 4 * 4

1 + 4 + 9 + 16 = 30

30 % 10 = 0

4321

4 * 1 + 3 * 2 + 2 * 3 + 1 * 4

4 + 6 + 6 + 4 = 20

20 % 10 = 0

7271

7 * 1 + 2 * 2 + 7 * 3 + 1 * 4

7 + 4 + 21 + 4 = 36

36 % 10 = 6

0815

0 * 1 + 8 * 2 + 1 * 3 + 5 * 4

0 + 16 + 3 + 20 = 39

39 % 10 = 9

5180

5 * 1 + 1 * 2 + 8 * 3 + 0 * 4

5 + 2 + 24 + 0 = 31

31 % 10 = 1

2.1.6 Getting Started with Lambdas

This subsection briefly introduces lambda expressions (lambdas for short). The language construct lambda comes from functional programming. Lambdas reflect the mathematical concept of functions with input, processing, and output, for example a squaring f(x) = x ∗ x. This can also be implemented using functions in Python, but lambdas offer an even shorter notation. Simply speaking, a lambda is a container for some source code or an anonymous function, such as one without a function name. Although lambdas are useful in many ways, sometimes readability and comprehensibility suffer. Therefore the Python style guide (PEP 8) is not necessarily in favor of lambdas.

Lambda Syntax

Lambdas, unlike functions, have no name, no return, and do not need to be introduced with def. This results in an even shorter notation, reduced to the essentials, with the following syntax where only expressions are allowed, but not statements:
lambda parameter(s): expression
A few simple examples of lambdas are the addition of two numbers, the multiplication by a factor of 2 or two numbers, and the calculation of power. These actions can be written as lambdas as follows:
>>> add_one = lambda x: x + 1
>>> double_it = lambda x: x * 2
>>> mult = lambda a, b : a * b
>>> power_of = lambda x, y: x ** y

Please note that the PEP 8 style guide states to not assign a lambda expression and to use a def instead. Occasionally, as in the above case, I name lambdas for a better insight into how things work or to express more clearly what was intended even though they usually encapsulate only a tiny piece of functionality and thus should not be named.

As an example, to perform doubling as well as exponentiation:
>>> double_it = lambda x: x * 2
>>> power_of = lambda x, y: x ** y
>>> print(double_it(7))
14
>>> print(power_of(2,8))
256
In fact, these lambdas look pretty unspectacular, and in particular, it becomes clear that a lambda is just a small piece of executable source code. Let’s take another look at the corresponding function definitions for the first two examples to differentiate them:
def add_one(x):
    return x + 1
def double_it(x)
    return x * 2

Lambdas in Action with sort( )

For lists Python offers a method named sort() to sort the elements. To get started, let’s look at a list of numbers. First, you sort them according to their natural order:
>>> numbers = [11, 2, 30, 333, 14, 4444, 100, 2222]
>>> numbers.sort()
>>> print(numbers)
[2, 11, 14, 30, 100, 333, 2222, 4444]
When calling sort() you can use the named parameter key to control sorting. Now you want to sort the numbers by length. Therefore, you use a lambda to convert the numbers to strings using str() and sort them by their length with len() —within the same length the ordering is not defined.
>>> numbers = [11, 2, 30, 333, 14, 4444, 100, 2222]
>>> numbers.sort(key=lambda x: len(str(x)))
>>> print(numbers)
[2, 11, 30, 14, 333, 100, 4444, 2222]
A second sort criterion can easily be added using the following tuple:
>>> numbers.sort(key=lambda x: (len(str(x)), x))
>>> print(numbers)
[2, 11, 14, 30, 100, 333, 2222, 4444]

2.2 Exercises

2.2.1 Exercise 1: Basic Arithmetic (★✩✩✩✩)

Exercise 1a: Basic Arithmetic Operations (★✩✩✩✩)

Write function calc(m, n) that multiplies two variables m and n of type int, then divides the product by two, and outputs the remainder with respect to division by 7.

Examples

m

n

m * n

m * n // 2

Result ((n * m // 2) % 7)

6

7

42

21

0

5

5

25

12

5

A short reminder: With an integer division, the remainder is truncated. Therefore 25//2 results in the value 12.

Exercise 1b: Statistics (★★✩✩✩)

Count as well as sum up the natural numbers that are divisible by 2 or 7 up to a given maximum value (exclusive) and output it to the console. Write function calc_sum_and_count_all_numbers_div_by_2_or_7(max_exclusive). Extend it so that it returns the two values instead of performing the console output.

Examples

Maximum

Divisible by 2

Divisible by 7

Result

Count

Sum

3

2

-/-

1

2

8

2, 4, 6

7

4

19

15

2, 4, 6, 8, 10, 12, 14

7, 14

8

63

Exercise 1c: Even or Odd Number (★✩✩✩✩)

Create the functions is_even (n) and is_odd(n) that will check if the passed integer is even or odd, respectively.

2.2.2 Exercise 2: Number as Text (★★✩✩✩)

Write function number_as_text(n) which, for a given positive number, converts the respective digits into corresponding text.

Start with the following fragment for the last digit of a number:
def number_as_text(n):
    remainder = n % 10
    value_to_text = ""
    if remainder == 0:
        value_to_text = "ZERO"
    if remainder == 1:
        value_to_text = "ONE"
    # ...
    return value_to_text

Examples

Input

Result

7

“SEVEN”

42

“FOUR TWO”

24680

“TWO FOUR SIX EIGHT ZERO”

13579

“ONE THREE FIVE SEVEN NINE”

2.2.3 Exercise 3: Perfect Numbers (★★✩✩✩)

By definition, a natural number is called a perfect number if its value is equal to the sum of its real divisors. This is true, for example, for the numbers 6 and 28:

1 + 2 + 3 = 6

1 + 2 + 4 + 7 + 14 = 28

Write function calc_perfect_numbers(max_exclusive) that calculates the perfect numbers up to a maximum value, say 10,000.

Examples

Input

Result

1000

[6, 28, 496]

10000

[6, 28, 496, 8128]

2.2.4 Exercise 4: Prime Numbers (★★✩✩✩)

Write function calc_primes_up_to(max_value) to compute all prime numbers up to a given value. As a reminder, a prime number is a natural number greater than 1 and exclusively divisible by itself and by 1. To compute a prime number, the Sieve of Eratosthenes was described before.

Examples

Check your algorithm with the following values:

Input

Result

15

[2, 3, 5, 7, 11, 13]

25

[2, 3, 5, 7, 11, 13, 17, 19, 23]

50

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

2.2.5 Exercise 5: Prime Number Pairs (★★✩✩✩)

Compute all pairs of prime numbers with a distance of 2 (twin), 4 (cousin), and 6 (sexy) up to an upper bound for n. For twins then the following is true:
$$ is\_ Prime(n)&& is\_ Primeleft(n+2 ight) $$

Examples

The following results are expected for limit 50:

Type

Result

twin

{3: 5, 5: 7, 11: 13, 17: 19, 29: 31, 41: 43}

cousin

{3: 7, 7: 11, 13: 17, 19: 23, 37: 41, 43: 47}

sexy

{5: 11, 7: 13, 11: 17, 13: 19, 17: 23, 23: 29, 31: 37, 37: 43, 41: 47, 47: 53}

2.2.6 Exercise 6: Checksum (★★✩✩✩)

Create function calc_checksum(digits) that performs the following position-based calculation for the checksum of a number of any length given as a string, with the n digits modeled as z1 to zn:
$$ {z}_1{z}_2{z}_3dots {z}_nRightarrow left(1ast {z}_1+2ast {z}_2+3ast {z}_3+dots +nast {z}_n ight)\%10 $$

Examples

Input

Sum

Result

“11111”

1 + 2 + 3 + 4 + 5 = 15

15 % 10 = 5

“87654321”

8 + 14 + 18 + 20 + 20 + 18 + 14 + 8 = 120

120 % 10 = 0

2.2.7 Exercise 7: Roman Numbers (★★★★✩)

Exercise 7a: Roman Numbers ➤ Decimal Numbers (★★★✩✩)

Write function from_roman_number(roman_number) that computes the corresponding decimal number from a textually valid Roman number .4

Exercise 7b: Decimal Numbers ➤ Roman Numbers (★★★★✩)

Write function to_roman_number(value) that converts a decimal number to a (valid) Roman number.

Examples

Arabic

Roman

17

“XVII”

444

“CDXLIV”

1971

“MCMLXXI”

2020

“MMXX”

2.2.8 Exercise 8: Combinatorics (★★✩✩✩)

Exercise 8a: Computation of a2 + b2 = c2

Compute all combinations of the values a, b, and c (each starting from 1 and less than 100) for which the following formula holds:
$$ {a}^2+{b}^2={c}^2 $$

Bonus (★★★✩✩) Reduce the running time of O(n3) to O(n2). If needed, consult Appendix C for an introduction to O-notation.

Exercise 8b: Computation of a2 + b2 = c2 + d2

Compute all combinations of the values a, b, c, and d (each starting from 1 and less than 100) for which the following formula holds:
$$ {a}^2+{b}^2={c}^2+{d}^2 $$

Bonus (★★★✩✩) Reduce the running time of O(n4) to O(n3).

2.2.9 Exercise 9: Armstrong Numbers (★★✩✩✩)

This exercise deals with three-digit Armstrong numbers. By definition, these are numbers for whose digits x, y, and z from 1 to 9 satisfy the following equation:
$$ xast 100+yast 10+z={x}^3+{y}^3+{z}^3 $$

Write function calc_armstrong_numbers() to compute all Armstrong numbers for x, y, and z (each < 10).

Examples

$$ {displaystyle egin{array}{l}153=1ast 100+5ast 10+3kern0.5em =kern0.5em {1}^3+{5}^3+{3}^3=1+125+27=153\ {}371=3ast 100+7ast 10+1kern0.5em =kern0.5em {3}^3+{7}^3+{1}^3=27+343+1=371end{array}} $$
Bonus Find a generic version with functions or lambdas and then try the following three formulas:
$$ {displaystyle egin{array}{l}xast 100+yast 10+z={x}^3+{y}^3+{z}^3 \ {}xast 100+yast 10+z={x}^1+{y}^2+{z}^3 \ {}xast 100+yast 10+z={x}^3+{y}^2+{z}^1end{array}} $$

2.2.10 Exercise 10: Max Change Calculator (★★★★✩)

Suppose you have a collection of coins or numbers of different values. Write function calc_max_possible_change(values) that determines, for positive integers, what amounts can be seamlessly generated with it starting from the value 1. The maximum value should be returned as a result.

Examples

Input

Possible values

Maximum

1

1

1

1, 1

1, 2

2

1, 5

1

1

1, 2, 4

1, 2, 3, 4, 5, 6, 7

7

1, 2, 3, 7

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

13

1, 1, 1, 1, 5, 10, 20, 50

1, 2, 3, 4, 5, 6, ... 30, ... 39

39

2.2.11 Exercise 11: Related Numbers (★★✩✩✩)

Two numbers n1 and n2 are called friends (or related) if the sum of their divisors is equal to the other number:

sum(divisors(n1)) = n2

sum(divisors(n2)) = n1

Write function calc_friends(max_exclusive) to compute all friends numbers up to a passed maximum value.

Examples

Input

Divisors

∑(divisors(220)) = 284

div(220) = 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110

∑(divisors(284)) = 220

div(284) = 1, 2, 4, 71, 142

∑(divisors(1184)) = 1210

div(1184) = 1, 2, 4, 8, 16, 32, 37, 74, 148, 296, 592

∑(divisors(1210)) = 1184

div(1210) = 1, 2, 5, 10, 11, 22, 55, 110, 121, 242, 605

2.2.12 Exercise 12: Prime Factorization (★★★✩✩)

Any natural number greater than 1 can be represented as a multiplication of primes. Remember the fact that 2 is also a prime. Write function calc_prime_factors(value) that returns a list of prime numbers whose multiplication yields the desired number.

Examples

Input

Prime factors

Result

8

2 * 2 * 2

[2, 2, 2]

14

2 * 7

[2, 7]

42

2 * 3 * 7

[2, 3, 7]

1155

3 * 5 * 7 * 11

[3, 5, 7, 11]

2222

2 * 11 * 101

[2, 11, 101]

2.3 Solutions

2.3.1 Solution 1: Basic Arithmetic (★✩✩✩✩)

Solution 1a: Basic Arithmetic Operations (★✩✩✩✩)

Write function calc(m, n) that multiplies two variables m and n of type int, then divides the product by two, and outputs the remainder with respect to division by 7.

Examples

m

n

m * n

m * n // 2

Result ((n * m // 2) % 7)

6

7

42

21

0

5

5

25

12

5

A reminder: With an integer division, the remainder is truncated. Therefore 25//2 results in the value 12.

Algorithm The implementation directly follows the mathematical operations:
def calc(m, n):
    return m * n // 2 % 7
Instead of the particular operator //, you can also perform a conversion of the result of the simple division into an integer by calling int():
def calc_v2(m, n):
    return int(m * n / 2) % 7

Solution 1b: Statistics (★★✩✩✩)

Count as well as sum up the natural numbers that are divisible by 2 or 7 up to a given maximum value (exclusive) and output it to the console. Write function calc_sum_and_count_all_numbers_div_by_2_or_7(max_exclusive). Extend it so that it returns the two values instead of performing the console output.

Examples

Maximum

Divisible by 2

Divisible by 7

Result

Count

Sum

3

2

-/-

1

2

8

2, 4, 6

7

4

19

15

2, 4, 6, 8, 10, 12, 14

7, 14

8

63

Algorithm The implementation is a tiny bit more complex than before. It uses two variables for count and sum as well as a loop. The modulo operator helps to check whether divisibility is given.
def calc_sum_and_count_all_numbers_div_by_2_or_7(max_exclusive):
    count = 0
    sum = 0
    for i in range(1, max_exclusive):
        if i % 2 == 0 or i % 7 == 0:
            count += 1
            sum += i
    print("count:", count)
    print("sum:", sum)

What remains is the desire to return the two values. With Python, this is an easy task since tuples are applicable for this, for example, with return (sum, count) or the even shorter return sum, count.

It is even clearer to use a dictionary. This makes the unit test very readable in the end:
def calc_sum_and_count_all_numbers_div_by_2_or_7_v2(max_exclusive):
    count = 0
    sum = 0
    for i in range(1, max_exclusive):
        if i % 2 == 0 or i % 7 == 0:
            count += 1
            sum += i
    return {"sum": sum, "count": count}
NOTE: SHADOWING OF BUILT-INS IN SMALL SCOPES

Please note that there is a minor inconvenience in the two code samples: the shadowing of the built-in function sum() by the local variable named sum. Of course, it is easily possible to use sum_ as a variable name. But due to the small scope, I prefer to stick to the more readable but shadowing name sum. This should never cause a real problem.

If your functions grow and get more complex, please avoid shadowing to prevent bugs.

NOTE: STRUCTURING WITH BLANK LINES

Blank lines sometimes cause problems when processed in the Python command line interpreter. In IDEs like PyCharm, on the other hand, this is possible without problems. I will use empty lines for the examples if this means clearer source code.

Solution 1c: Even or Odd Number (★✩✩✩✩)

Create functions is_even(n) and is_odd(n) that will check if the passed integer is even or odd, respectively.

Algorithm The implementation uses the modulo operator in each case. A number is even if a division by 2 has no remainder; otherwise, it is odd.
def is_even(n):
    return n % 2 == 0
def is_odd(n):
    return n % 2 != 0

Verification

For the test of exercise 1a, use a parameterized test and a comma-separated enumeration for the specification of the input values for m and n and the result. To refresh your knowledge of pytest, look at Appendix A.
@pytest.mark.parametrize("m, n, expected",
                         [(6, 7, 0), (3, 4, 6), (5, 5, 5)])
def test_calc(m, n, expected):
    assert calc(m, n) == expected
To verify the exercise part 1b, use the Python command line:
>>> calc_sum_and_count_all_numbers_div_by_2_or_7(8)
count: 4
sum: 19
For professional programming, it is generally advisable to create unit tests. In other languages, even a combined return value would be a first hurdle. With Python and tuples in combination with dictionaries, this is very easy:
@pytest.mark.parametrize("n, expected",
                         [(3, {"sum": 2, "count": 1}),
                          (8, {"sum": 19, "count": 4}),
                          (15, {"sum": 63, "count": 8})])
def test_calc_sum_and_count_all_numbers_div_by_2_or_7_v2(n, expected):
    assert calc_sum_and_count_all_numbers_div_by_2_or_7_v2(n) == expected
Testing exercise 1c for even or odd is so simple that I’ll just limit the output to two exemplary calls in the Python command line:
>>> is_even(2)
True
>>> is_odd(7)
True

2.3.2 Solution 2: Number as Text (★★✩✩✩)

Write function number_as_text(n) which, for a given positive number, converts the respective digits into corresponding text.

Examples

Input

Result

7

“SEVEN”

42

“FOUR TWO”

24680

“TWO FOUR SIX EIGHT ZERO”

13579

“ONE THREE FIVE SEVEN NINE”

Algorithm Always compute the remainder (i. e., the last digit), print it out, and then divide by ten. Repeat this until no remainder exists anymore. Note that the digit’s representation must be appended to the text’s front since the last digit is always extracted. Otherwise, the digits would appear in the wrong order.
def number_as_text(n):
    value = ""
    remaining_value = n
    while remaining_value > 0:
        remainder_as_text = digit_as_text(remaining_value % 10)
        remaining_value = int(remaining_value / 10)
        value = remainder_as_text + " " + value
    return value.strip()
Implement the mapping from digit to text with a dictionary as follows:
value_to_text_mapping = {
    0: "ZERO", 1: "ONE", 2: "TWO", 3: "THREE", 4: "FOUR",
    5: "FIVE", 6: "SIX", 7: "SEVEN", 8: "EIGHT", 9: "NINE"
}
def digit_as_text(n):
    return value_to_text_mapping[n % 10]
Python shortcut As mentioned in the introduction, the built-in Python function divmod() is often useful for division and modulo. Therewith the process changes only minimally:
def number_as_text(n):
    value = ""
    remaining_value = n
    while remaining_value > 0:
        remaining_value, remainder = divmod(remaining_value, 10)
        value = digit_as_text(remainder) + " " + value
    return value.strip()
There is another variant that iterates character by character through the number. It is first converted into a string. To access the dictionary, you reconvert it into a number.
def number_as_text_shorter(n):
    value = ""
    for ch in str(n):
        value += digit_as_text(int(ch)) + " "
    return value.strip()

Verification

For testing, use a parameterized test that can be formulated elegantly using pytest:
@pytest.mark.parametrize("n, expected",
                         [(7, "SEVEN"),
                          (42, "FOUR TWO"),
                          (7271, "SEVEN TWO SEVEN ONE"),
                          (24680, "TWO FOUR SIX EIGHT ZERO"),
                          (13579, "ONE THREE FIVE SEVEN NINE")])
def test_number_as_text(n, expected):
    assert number_as_text(n) == expected

2.3.3 Solution 3: Perfect Numbers (★★✩✩✩)

By definition, a natural number is called a perfect number if its value is equal to the sum of its real divisors. This is true, for example, for the numbers 6 and 28:

1 + 2 + 3 = 6

1 + 2 + 4 + 7 + 14 = 28

Write function calc_perfect_numbers(max_exclusive) that calculates the perfect numbers up to a maximum value, say 10,000.

Examples

Input

Result

1000

[6, 28, 496]

10000

[6, 28, 496, 8128]

Algorithm The simplest variant is to check all numbers from 2 to half of the desired maximum value to see if they represent the original number’s divisor. In that case, the sum of the divisors is increased by exactly that value. The sum starts with the value 1 because this is invariably a valid divisor. Finally, you only have to compare the determined sum with the initial number.
def is_perfect_number_simple(number):
    # always divisible by 1
    sum_of_multipliers = 1
    for i in range(2, int(number / 2) + 1):
        if number % i == 0:
            sum_of_multipliers += i
    return sum_of_multipliers == number
Based on this, the actual function is straightforward to implement:
def calc_perfect_numbers(max_exclusive):
    results = []
    for i in range(2, max_exclusive):
        if is_perfect_number_simple(i):
            results.append(i)
    return results
Python shortcut Using list comprehensions, this can be written a little shorter and more elegantly:
def calc_perfect_numbers_comprehension(max_exclusive):
    return [i for i in range(2, max_exclusive) if is_perfect_number_simple(i)]

Verification

For testing, use the following inputs, which show the correct operation for dedicated numbers:
@pytest.mark.parametrize("n, expected",
                         [(6, True), (28, True),
                          (496, True), (8128, True)])
def test_is_perfect_number_simple(n, expected):
    assert is_perfect_number_simple(n) == expected
Now you have tested the basic building block of the examination. However, you should still make sure that no other values than perfect numbers are supplied—in fact, only these—for the testing, thus the first four perfect numbers are namely the numbers 6, 28, 496, and 8128:
@pytest.mark.parametrize("n, expected", [(50, [6, 28]),
                                         (1000, [6, 28, 496]),
                                         (10000, [6, 28, 496, 8128])])
def test_calc_perfect_numbers(n, expected):
    assert calc_perfect_numbers(n) == expected

Implementation Optimization

Based on the function find_proper_divisors(n) presented in the introductory section of this chapter that finds all true divisors, you can simplify the check as follows:
def is_perfect_number_based_on_proper_divisors(number):
    divisors = find_proper_divisors(number)
    return sum(divisors) == number

Conveniently, there is a built-in functionality in Python that sums the elements of a list. This is the function sum(), which you use here.

2.3.4 Solution 4: Prime Numbers (★★✩✩✩)

Write function calc_primes_up_to(max_value) to compute all prime numbers up to a given value. As a reminder, a prime number is a natural number greater than 1 and exclusively divisible by itself and by 1. To compute a prime number, the so-called Sieve of Eratosthenes was described before.

Examples

Check your algorithm with the following values:

Input

Result

15

[2, 3, 5, 7, 11, 13]

25

[2, 3, 5, 7, 11, 13, 17, 19, 23]

50

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Algorithm The algorithm follows the Sieve of Eratosthenes. At first, a list of booleans is created and initialized with True since all numbers are considered potential prime numbers. Mentally, this is analogous to initially writing down the numbers 2, 3, 4, ... up to a given maximum value:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Now, starting at the value 2, the “sieving” is started. Because the number 2 is not crossed out, it is included in the list of prime numbers. Afterwards every multiple of it is crossed out, because they can’t be prime numbers:

Iteratively you look for the next not-eliminated number. In this case, it is 3, which is the second prime number. Once again, all multiples of this number are eliminated:

This procedure is repeated until half of the maximum value is reached. This prime number calculation is implemented in Python as follows:
def calc_primes_up_to(max_value):
    # initially mark all values as potential prime number
    is_potentially_prime = [True for _ in range(1, max_value + 2)]
    # run through all numbers starting at 2, optimization only up to half
    for number in range(2, max_value // 2 + 1):
        if is_potentially_prime[number]:
            erase_multiples_of_current(is_potentially_prime, number)
    return build_primes_list(is_potentially_prime)
The crossing out or erasing the multiples is extracted to the helper function erase_multiples_of_current(). As a trick, use on the one hand the step size of i and on the other hand that the first multiple is determined by adding the start value. For first attempts, the commented console output can be helpful.
def erase_multiples_of_current(values, number):
    for n in range(number + number, len(values), number):
        values[n] = False
        # print("Eliminating:", n)
Finally, you need to reconstruct a list of numbers from the list of booleans. It is essential that you start from the value 2 because the two values below this value are not set to False (by mistake, but here without negative effect):
def build_primes_list(is_potentially_prime):
    primes = []
    for number in range(2, len(is_potentially_prime)):
        if is_potentially_prime[number]:
            primes.append(number)
    return primes
Python shortcut With the help of list comprehensions, this can be written a little shorter and more elegantly in Python:
def build_primes_list(is_potentially_prime):
    return [number for number in range(2, len(is_potentially_prime))
            if is_potentially_prime[number]]
Python shortcut I would like to show another variant based on compress() from the module itertools. This allows you to get a new sequence from a sequence of data and a sequence of selectors in the form of Boolean values with only the values for which the selector has the value True or 1:
>>> import itertools
>>> print(list(itertools.compress("ABCDEF", [1, 0, 1, 0, 1, 0])))
['A', 'C', 'E']
For the prime number calculation, you use this as follows:
import itertools
def calc_primes_up_to_v2(max_value):
    is_potentially_prime = [True for _ in range(1, max_value + 2)]
    for number in range(2, int(max_value / 2) + 1):
        if is_potentially_prime[number]:
            erase_multiples_of_current(is_potentially_prime, number)
    # mark values 0 and 1 as no prime number
    is_potentially_prime[0:2] = False, False
    # merging / selection of values
    return list(itertools.compress(range(len(is_potentially_prime)),
                                   is_potentially_prime))

Verification

For testing, use the following inputs that show the correct operation:
def input_and_expected():
    return [(2, [2]),
            (3, [2, 3]),
            (10, [2, 3, 5, 7]),
            (15, [2, 3, 5, 7, 11, 13]),
            (20, [2, 3, 5, 7, 11, 13, 17, 19]),
            (25, [2, 3, 5, 7, 11, 13, 17, 19, 23]),
            (50, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47])]
@pytest.mark.parametrize("n, expected",
                         input_and_expected())
def test_calc_primes_up_to(n, expected):
    assert calc_primes_up_to(n) == expected
@pytest.mark.parametrize("n, expected",
                         input_and_expected())
def test_calc_primes_up_to_v2(n, expected):
    assert calc_primes_up_to_v2(n) == expected

2.3.5 Solution 5: Prime Number Pairs (★★✩✩✩)

Compute all pairs of prime numbers with a distance of 2 (twin), 4 (cousin), and 6 (sexy) up to an upper bound for n. For twins then the following is true:

Is_Prime(n) && is_Prime(n + 2)

Examples

The following results are expected for limit 50:

Type

Result

Twin

{3: 5, 5: 7, 11: 13, 17: 19, 29: 31, 41: 43}

Cousin

{3: 7, 7: 11, 13: 17, 19: 23, 37: 41, 43: 47}

Sexy

{5: 11, 7: 13, 11: 17, 13: 19, 17: 23, 23: 29, 31: 37, 37: 43, 41: 47, 47: 53}

Algorithm As a first step, you need to define the conditions for pairs. This can be done explicitly via if statements or more elegantly by the definition of suitable predicates. For all numbers starting at 2 up to a desired upper limit, you must check whether the number itself and the corresponding other number added by 2, 4, or 6 are prime numbers. For this purpose, you can call function is_prime(n), which in turn uses the previously written function for determining the prime numbers. For twins, I still use the rather non-Pythonic for loop with if check here. For the other two, dict comprehensions come into play. For more details on prime twins, see https://en.wikipedia.org/wiki/Twin_prime.
def main():
    def is_twin_pair(n):
        return is_prime(n) and is_prime(n + 2)
    def is_cousin_pair(n):
        return is_prime(n) and is_prime(n + 4)
    def is_sexy_pair(n):
        return is_prime(n) and is_prime(n + 6)
    # manual update
    twin_pairs = {}
    for i in range(1, 50):
        if is_twin_pair(i):
            twin_pairs.update({i: i + 2})
    # dict comprehensions
    cousin_pairs = {i: i + 4 for i in range(1, 50) if is_cousin_pair(i)}
    sexy_pairs = {i : i + 6 for i in range(1, 50) if is_sexy_pair(i)}
    print("Twins:", twin_pairs)
    print("Cousins:", cousin_pairs)
    print("Sexy:", sexy_pairs)
def is_prime(n):
    primes = calc_primes_up_to(n + 1)
    return n in primes
The realization shown here uses already implemented functionality, which is preferable in principle, but has two drawbacks in this case:
  1. 1.

    Every time all prime numbers are computed again up to the given maximum value. This can be optimized by performing the computation only once and caching the results appropriately.

     
  2. 2.

    At the moment, the checks are still all interwoven. It is clearer to use a validation function that checks only one condition and returns only one result.

     

Optimization of the Implementation

Vulnerability 1: Repeated calls First, you should compute the primes up to the maximum value only once. In this case, you need to raise the limit by 7 so that you can map all pairs correctly.
def calc_prime_pairs(max_value):
    primes = calc_primes_up_to(max_value + 7)
    def is_twin_pair(n):
        return is_prime(primes, n) and is_prime(primes, n + 2)
    def is_cousin_pair(n):
        return is_prime(primes, n) and is_prime(primes, n + 4)
    def is_sexy_pair(n):
        return is_prime(primes, n) and is_prime(primes, n + 6)
    # manual update
    twin_pairs = {}
    for i in range(1, max_value):
        if is_twin_pair(i):
            twin_pairs.update({i: i + 2})
    # dict comprehensions
    cousin_pairs = {i: i + 4 for i in range(1, max_value) if is_cousin_pair(i)}
    sexy_pairs = {i: i + 6 for i in range(1, max_value) if is_sexy_pair(i)}
    print("Twins: ", twin_pairs)
    print("Cousins: ", cousin_pairs)
    print("Sexy: ", sexy_pairs)

Computing the prime numbers is performed once at the beginning of the function. Thus you achieve a significant performance improvement.

Finally, you move the check for a prime number to the following function:
def is_prime(primes, n):
    return n in primes
Vulnerability 2: Unclear program structure Your goal is to write more general-purpose functions. You have already created the basic building blocks. However, the determination of the pairs should be moved to function calc_pairs(). This way, you can write it more clearly and understandably as follows:
def calc_prime_pairs_improved(max_value):
    twin_pairs = calc_pairs(max_value, 2)
    cousin_pairs = calc_pairs(max_value, 4)
    sexy_pairs = calc_pairs(max_value, 6)
    print("Twins:", twin_pairs)
    print("Cousins:", cousin_pairs)
    print("Sexy:", sexy_pairs)
def calc_pairs(max_value, distance):
    primes = calc_primes_up_to(max_value + distance)
    return {number: number + distance for number in range(1, max_value)
            if is_prime(primes, number) and is_prime(primes, number + distance)}

This conversion also lays the foundation to be able to test the whole thing with unit tests.

Verification

If you call the method with the maximum value of 50, you get this result:
Twins: {3: 5, 5: 7, 11: 13, 17: 19, 29: 31, 41: 43}
Cousins: {3: 7, 7: 11, 13: 17, 19: 23, 37: 41, 43: 47}
Sexy: {5: 11, 7: 13, 11: 17, 13: 19, 17: 23, 23: 29, 31: 37, 37: 43, 41: 47, 47: 53}
Now let’s create another unit test with one test function per special case:
@pytest.mark.parametrize("n, expected",
                         [(2, {3: 5, 5: 7, 11: 13, 17: 19, 29: 31, 41: 43}),
                          (4, {3: 7, 7: 11, 13: 17, 19: 23, 37: 41, 43: 47}),
                          (6, {5: 11, 7: 13, 11: 17, 13: 19, 17: 23, 23: 29, 31: 37, 37: 43, 41: 47, 47: 53})])
def test_calc_pairs(n, expected):
    max_value = 50
    assert calc_pairs(max_value, n) == expected

2.3.6 Solution 6: Checksum (★★✩✩✩)

Create function calc_checksum(digits) that performs the following position-based calculation for the checksum of a number of any length given as a string, with the n digits modeled as z1 to zn:
$$ {z}_1{z}_2{z}_3dots {z}_nRightarrow left(1ast {z}_1+2ast {z}_2+3ast {z}_3+dots +nast {z}_n ight)\%10 $$

Examples

Digits

Sum

Result

“11111”

1 + 2 + 3 + 4 + 5 = 15

15 % 10 = 5

“87654321”

8 + 14 + 18 + 20 + 20 + 18 + 14 + 8 = 120

120 % 10 = 0

Algorithm Traverse all digits from the front to the last position, extract the digit at the given position, and multiply its numerical value by the current position. Add this to the sum. Finally, the modulo operation maps the sum to a digit.
def calc_checksum(digits):
    if not digits.isdigit():
        raise ValueError("illegal chars: not only digits")
    crc = 0
    for i, current_char in enumerate(digits):
        value = (int(current_char)) * (i + 1)
        crc += value
    return int(crc % 10)

Verification

For testing, use the following inputs, which show the correct operation for valid inputs and check the handling of errors for wrong inputs:
@pytest.mark.parametrize("n, expected",
                         [("11111", 5),
                          ("22222", 0),
                          ("111111", 1),
                          ("12345678", 4),
                          ("87654321", 0)])
def test_calc_checksum(n, expected):
    assert calc_checksum(n) == expected
def test_calc_checksum_with_letters_as_wrong_input():
    with pytest.raises(ValueError) as excinfo:
        calc_checksum("ABC")
    assert "illegal chars" in str(excinfo.value)

2.3.7 Solution 7: Roman Numbers (★★★★✩)

Solution 7a: Roman Numbers ➤ Decimal Numbers (★★★✩✩)

Write function from_roman_number(roman_number) that computes the corresponding decimal number from a textually valid Roman number .5

Examples

Arabic

Roman

17

“XVII”

444

“CDXLIV”

1971

“MCMLXXI”

2020

“MMXX”

Algorithm You must pay particular attention to the addition rule described in section 2.1.1: The relevant value is normally obtained by adding the individual digits’ values from left to right whenever a larger character precedes a smaller one. However, if a smaller number character precedes a larger one, the corresponding value is subtracted.

With this knowledge, you traverse the characters from right to left and look up the relevant value in a dictionary. To decide between addition or subtraction, remember the last relevant character.
def from_roman_number(roman_number):
    value = 0
    last_digit_value = 0
    # for i in range(len(roman_number) - 1, -1, -1):
    #     roman_digit = roman_number[i]
    for roman_digit in reversed(roman_number):
        digit_value = value_map[roman_digit]
        add_mode = digit_value >= last_digit_value
        if add_mode:
            value += digit_value
            last_digit_value = digit_value
        else:
            value -= digit_value
    return value
value_map = {"I": 1, "V": 5, "X": 10, "L": 50,
             "C": 100, "D": 500, "M": 1000}

In the code, I use a nicer variant of the traversal. Using the standard functionality reversed(), you get an iterator that traverses the data in the opposite direction and provides access to the respective element. Shown in the comment is index-based processing, which is a little less Python-like (Pythonic).

Solution 7b: Decimal Numbers ➤ Roman Numbers (★★★★✩)

Write function to_roman_number(value) that converts a decimal number to a (valid) Roman number.

Algorithm When converting a decimal number to a Roman numeral, you again use a dictionary. You sort this in descending order so that the largest value (1000) is at the beginning. The current number value is divided by this factor. This yields the number of required repetitions of this value. Now the remainder is determined by modulo. The procedure is repeated until all values are checked and the remainder is greater than 0. In the following, the procedure is shown for the number 7:
7 =>  7 / 1000 => 0 => 0 x 'M'
          ...
           7 / 5 = 1 => 1 x 'V'
           7 % 5 = 2
           2 / 1 = 2 => 2 x 'I'
           2 % 1 = 0
     => 'VII'
The procedure is implemented in Python as follows (please note that a little pitfall is included):
def to_roman_number(value):
    result = ""
    remainder = value
    # descending order => start with largest value
    for i in sorted(int_to_roman_digit_map.keys(), reverse=True):
        if remainder > 0:
            multiplier = i
            roman_digit = int_to_roman_digit_map[i]
            times = remainder // multiplier
            remainder = remainder % multiplier
            result += roman_digit * times
    return result
int_to_roman_digit_map = {1: "I", 5: "V", 10: "X", 50: "L",
                          100: "C", 500: "D", 1000: "M"}
Here again the function divmod() is a good choice. Then the invocation
times = remainder // multiplier
remainder = remainder % multiplier
results in the following one-liner:
times, remainder = divmod(remainder, multiplier)
However, the conversion shown above is not yet 100 % correct because it does not respect the rule of three and also repeats digits four times. Try it yourself using 147 as input, resulting in CXXXXVII. To fix this problem, you may think about implementing special treatments that are only hinted at below:
multiplier = i
roman_digit = int_to_roman_digit_map[i]
if remainder >= 900 and roman_digit == 'D':
    result += "CM"
    remainder -= 900}
# ...
elif remainder >= 4 and roman_digit == 'I':
    result += "IV"
    remainder -= 4
else:
    times = remainder / multiplier
    remainder = remainder % multiplier
    result += roman_digit * times

However, this quickly becomes confusing.

More elegant is the insertion of other lookup values for the exceptional cases:
int_to_roman_digit_map = {1: "I", 4: "IV", 5: "V", 9: "IX", 10: "X",
                          40: "XL", 50: "L", 90: "XC", 100: "C",
                          400: "CD", 500: "D", 900: "CM", 1000: "M"}

Using this enhanced lookup dictionary solves the problem and you get correct answers.

Verification

Let’s start the unit test with different values that show the correct conversion , especially including the four values 17, 444, 1971, and 2020 from the example:
def arabic_to_roman_number_map():
    return [(1, "I"), (2, "II"), (3, "III"), (4, "IV"),
            (5, "V"), (7, "VII"), (9, "IX"), (17, "XVII"),
            (40, "XL"), (90, "XC"), (400, "CD"), (444, "CDXLIV"),
            (500, "D"), (900, "CM"), (1000, "M"), (1666, "MDCLXVI"),
            (1971, "MCMLXXI"), (2018, "MMXVIII"), (2019, "MMXIX"),
            (2020, "MMXX"), (3000, "MMM")]
# attention different order, so you do not have to define it twice
@pytest.mark.parametrize("expected, roman_number",
                         arabic_to_roman_number_map())
def test_from_roman_number(roman_number, expected):
    assert from_roman_number(roman_number) == expected
Now let’s take a look at how the testing of the reverse direction is accomplished. Here you already benefit from the previously defined function arabic_to_roman_number_map() to provide the test results.
@pytest.mark.parametrize("roman_number, expected",
                         arabic_to_roman_number_map())
def test_to_roman_number(roman_number, expected):
    assert to_roman_number(roman_number) == expected

Without the extraction of the values into a list of tuples, there would have been a duplication of the specifications. Only when specifying expected and roman_number, you have to be a bit careful because this is a bidirectional mapping.

Providing data in a CSV file To avoid duplication, you could also read the values from a file. With the help of the csv module, reading from a CSV file is implemented as follows:
def arabic_to_roman_number_map():
    result = []
    with open('arabicroman2.csv','rt') as file:
        data = csv.reader(file)
        skip_first = True
        for row in data:
            if not skip_first:
                result.append((int(row[0].strip()), row[1].strip()))
            skip_first = False
    return result
Assume that the content has the correct structure, as shown below. Furthermore, the CSV file looks like the following:
arabic,roman
1, I
2, II
3, III
4, IV
5, V
7, VII
...

2.3.8 Solution 8: Combinatorics (★★✩✩✩)

Solution 8a: Computation of a2 + b2 = c2

Compute all combinations of the values a, b, and c (each starting from 1 and less than 100) for which the following formula holds:
$$ {a}^2+{b}^2={c}^2 $$
Algorithm The brute force solution uses three nested loops and then checks if the above formula is satisfied.
# brute force, three nested loops
def solve_quadratic_simple():
    for a in range(1, 100):
        for b in range(1, 100):
            for c in range(1, 100):
                # if a ** 2 + b ** 2 == c ** 2:
                # if pow(a, 2) + pow(b, 2) == pow(c, 2):
                if a * a + b * b == c * c:
                    print("a =", a, "/ b =", b, "/ c =", c)

For squaring, simple multiplication provides better readability than the use of pow() or of the operator ** implied in the comment.

Python shortcut By using list comprehension, you can have all tuples generated. However, such construction is already a bit stylistically dubious.
def solve_quadratic_shorter():
    return [(a,b,c) for a in range(1, 100) for b in range(1, 100)
                    for c in range(1, 100) if a * a + b * b == c * c]
Bonus: Reduce the Running Time of O(n3) to O(n2) (★★★✩✩)
You see three nested loops in the upper solution, resulting in a running time of O(n3). Now let’s reduce this to O(n2). To achieve this, apply the following transformation (resolving to c):
$$ c=sqrt{a^{ast } a+{b}^{ast } b} $$
Based on this transformation or resolution of the equation to c, the square root is calculated and then the formula is verified:
import math
def solve_quadratic():
    for a in range(1, 100):
        for b in range(1, 100):
            c = int(math.sqrt(a * a + b * b))
            if a * a + b * b == c * c:
                print("a =", a, "/ b =", b, "/ c =", c)
This solution still contains a small flaw. Now c can also be greater than 100! Therefore, you must ensure that c is below 100. To this end, you supplement the check as follows:
def solve_quadratic():
    for a in range(1, 100):
        for b in range(1, 100):
            c = int(math.sqrt(a * a + b * b))
            if c < 100 and a * a + b * b == c * c:
                print("a =", a, "/ b =", b, "/ c =", c)

Verification

For testing, call the function solve_quadratic() and perform the computation for some values:
>>> solve_quadratic()
a = 3 / b = 4 / c = 5
a = 4 / b = 3 / c = 5
a = 5 / b = 12 / c = 13
a = 6 / b = 8 / c = 10
...
NOTE: WHY DOES THE COMPUTATION WORK AT ALL?
Looking only briefly at the conversion, you might wonder why the computation does not yield a successful comparison for all values. In fact, this would be the case purely mathematically, since you are deriving c from a and b. However, you also use a cast to an int.
c = int(math.sqrt(a * a + b * b))
if a * a + b * b == c * c:
    print("a =", a, "/ b =", b, "/ c =", c)

As a result, the decimal digits are truncated. This, in turn, leads to the comparison being successful only for certain values.

Solution 8b: Computation of a2 + b2 = c2 + d2

Compute all combinations of the values a, b, c, and d (each starting from 1 and less than 100) for which the following formula holds:
$$ {a}^2+{b}^2={c}^2+{d}^2 $$
Algorithm Analogous to the previous part of the exercise, the brute force solution consists of four nested loops. Therein a check whether the above formula is satisfied is performed. In this particular case, the simple multiplication offers, to my taste, slightly better readability than the use of the operator **.
# brute force, four nested loops
def solve_cubic_simple():
    for a in range(1, 100):
        for b in range(1, 100):
            for c in range(1, 100):
                for d in range(1, 100):
                    if a * a + b * b == c * c + d * d:
                        print("a =", a, " / b =", b, " / c =", c, " / d =", d)
Python shortcut By using list comprehension, you can have all tuples generated, although such a structure is already stylistically a bit questionable, since it is slightly too complex:
def solve_cubic_shorter():
    return [(a, b, c, d)
            for a in range(1, 100) for b in range(1, 100)
            for c in range(1, 100) for d in range(1, 100)
            if a * a + b * b == c * c + d * d]

Please note that both variants are not optimal in respect to performance. The next task is to improve this.

Bonus: Reduce the Running Time of O(n  4) to O(n  3) (★★★✩✩)

As can easily be seen, the solution uses four nested loops, resulting in a running time of O(n4). Now you want to reduce this to O(n3). For that purpose, use transformations. First, you separate to d and then you resolve to d:
$$ {d}^{ast } d={a}^{ast } a+{b}^{ast } b-{c}^{ast } cRightarrow d=kern0.5em sqrt{a^{ast } a+{b}^{ast } b-{c}^{ast } c} $$
Based on this transformation or resolution of the equation to d, you can compute the square root and then validate the formula. Additionally, you must ensure that the value is not negative and the resulting d is below 100.
import math
def solve_cubic():
    for a in range(1, 100):
        for b in range(1, 100):
            for c in range(1, 100):
                value = a * a + b * b - c * c
                if value > 0:
                    d = int(math.sqrt(value))
                    if d < 100 and a * a + b * b == c * c + d * d:
                        print("a =", a, " / b =", b, " / c =", c, " / d =", d)

Verification

For testing, use a function call and check some of the values:
>>> solve_cubic()
a = 1 / b = 1 / c = 1 / d = 1
a = 1 / b = 2 / c = 1 / d = 2
a = 1 / b = 2 / c = 2 / d = 1
a = 1 / b = 3 / c = 1 / d = 3
a = 1 / b = 3 / c = 3 / d = 1
...

2.3.9 Solution 9: Armstrong Numbers (★★✩✩✩)

This exercise deals with three-digit Armstrong numbers. By definition, these are numbers for whose digits x, y, and z from 1 to 9 satisfy the following equation:
$$ xast 100+yast 10+z={x}^3+{y}^3+{z}^3 $$

Write function calc_armstrong_numbers() to compute all Armstrong numbers for x, y, and z (each < 10).

Examples

$$ {displaystyle egin{array}{l}153=1ast 100+5ast 10+3kern0.5em =kern0.5em {1}^3+{5}^3+{3}^3=1+125+27=153\ {}371=3ast 100+7ast 10+1kern0.5em =kern0.5em {3}^3+{7}^3+{1}^3=27+343+1=371end{array}} $$
Algorithm Iterate through all combinations of three-digit numbers using three nested loops. The numeric value is calculated based on the position using the formula x∗100+ y ∗ 10 + z. Also, compute the third power for each digit, sum them, and check if the sum matches the number.
def calc_armstrong_numbers():
    results = []
    for x in range(1, 10):
        for y in range(1, 10):
            for z in range(1, 10):
                numeric_value = x * 100 + y * 10 + z
                cubic_value = int(pow(x, 3) + pow(y, 3) + pow(z, 3))
                if numeric_value == cubic_value:
                    results.append(numeric_value)
    return results
NOTE: WHY DON’T THE LOOPS START AT 0?

Although you could also use the value 0, this is unusual. In the first place, a value assignment with x = 0 and y = 0 would correspond to the value z. However, there is another reason not to start with 0. A leading 0 is used to mark octal numbers, so we will not use it here. By the way, since Python 3.8, octal numbers start with the prefix 0o.

Verification

To test, call the above method and examine whether the two combinations of values given as examples are included in the result list:
def test_calc_armstrong_numbers():
    assert calc_armstrong_numbers() == [153, 371]

Bonus (★★★✩✩)

Find a generic version with functions or lambdas and then try the following three formulas:
$$ {displaystyle egin{array}{l}xast 100+yast 10+z={x}^3+{y}^3+{z}^3 \ {}xast 100+yast 10+z={x}^1+{y}^2+{z}^3 \ {}xast 100+yast 10+z={x}^3+{y}^2+{z}^1end{array}} $$
Algorithm Instead of the concrete calculation, you invoke a matching cubic_function:
def calc_numbers(cubic_function):
    results = []
    for x in range(1, 10):
        for y in range(1, 10):
            for z in range(1, 10):
                numeric_value = x * 100 + y * 10 + z
                cubic_value = int(cubic_function(x, y, z))
                if numeric_value == cubic_value:
                    results.append(numeric_value)
    return results
Thus, the computation can be expressed as a function or a lambda. Please note that lambdas usually encapsulate only a tiny piece of functionality and thus you should not name them and assign them to a variable. In this book, I sometimes break this PEP-8 rule for a better insight into how things work or express more clearly what was intended.
def special(x,y,z):
    return int(pow(x, 3) + pow(y, 3) + pow(z, 3))
special_as_lambda = lambda x, y, z: int(pow(x, 3) + pow(y, 3) + pow(z, 3))
Based on this more general solution, you can now easily try other variants of computation rules without much effort:
def special2(x, y, z):
    return int(pow(x, 1) + pow(y, 2) + pow(z, 3))
Likewise, you finally define the following:
def special3(x, y, z):
    return int(pow(x, 3) + pow(y, 2) + pow(z, 1))

Verification

For testing, you invoke above function with different computation rules and look for that of Armstrong numbers whether the two combinations of values given as examples are included in the result list:
>>> def special(x,y,z):
...     return int(pow(x, 3) + pow(y, 3) + pow(z, 3))
...
>>> print(calc_numbers(special))
[153, 371]
>>> def special2(x,y,z):
...     return int(pow(x, 1) + pow(y, 2) + pow(z, 3))
...
>>> print(calc_numbers(special2))
[135, 175, 518, 598]
>>> special3 = lambda x, y, z: int(pow(x, 3) + pow(y, 2) + pow(z, 1))
>>> print(calc_numbers(special3))
[]

2.3.10 Solution 10: Max Change Calculator (★★★★✩)

Suppose you have a collection of coins or numbers of different values. Write function calc_max_possible_change(values) that determines, for positive integers, what amounts can be seamlessly generated with it starting from the value 1. The maximum value should be returned as a result.

Examples

Input

Possible values

Maximum

1

1

1

1, 1

1, 2

2

1, 5

1

1

1, 2, 4

1, 2, 3, 4, 5, 6, 7

7

1, 2, 3, 7

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

13

1, 1, 1, 1, 5, 10, 20, 50

1, 2, 3, 4, 5, 6, ... , 30, ... , 39

39

Algorithm You could try solving this exercise by computing a mapping to all permutations of the sum of the numbers, but this gets complex fast. Let’s consider another approach and start sorting the values for ease of use.

Input

Possible values

Maximum

1, 2, 3, 7

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

13

1, 2, 3, 8

1, 2, 3, 4, 5, 6, => _ <= , 8, 9, 10, 11, 12, 13, 14

6

If you take a look at the two examples, you may recognize for the cases 1, 2, 3, 7 and 1, 2, 3, 8 the clue to simplify the calculation decisively. Instead of always calculating all permutations and then checking for a gap in the number line, here indicated by an underscore (_), it is possible to start at the first number, always add the numbers to the previous sum, and repeat this iteratively until next_number > sum + 1 becomes true.

Let’s apply this to Python. First, sort the input values. Start with the assumption that there is nothing to change initially, so max_possible_change = 0. Now check the following condition for each value. If current_value > max_possible_change + 1 holds, then it is impossible to change. Otherwise, add the current value to max_possible_change. Repeat this until all values are processed or until the termination condition is met. This leads to the following implementation:
def calc_max_possible_change(values):
    # wrappng / copying necessary so that we do not sort the original
    sorted_numbers = list(values)
    sorted_numbers.sort()
    max_possible_change = 0
    for current_value in sorted_numbers:
        if current_value > max_possible_change + 1:
            break
        max_possible_change += current_value
    return max_possible_change

Verification

For testing, use the following inputs, which show the correct operation:
@pytest.mark.parametrize("coins, max_change",
                         [([1], 1),
                          ([1, 1], 2),
                          ([1, 5], 1),
                          ([1, 2, 4], 7),
                          ([1, 2, 3, 7], 13),
                          ([1, 2, 3, 8], 6),
                          ([1, 1, 1, 1, 5, 10, 20, 50], 39)])
def test_calc_max_possible_change(coins, max_change):
    assert calc_max_possible_change(coins) == max_change

2.3.11 Solution 11: Related Numbers (★★✩✩✩)

Two numbers n1 and n2 are called friends (or related) if the sum of their divisors is equal to the other number:

sum(divisors(n1)) = n2

sum(divisors(n2)) = n1

Write method function calc_friends(max_exclusive) to compute all friends numbers up to a passed maximum value.

Examples

Input

Divisors

∑(divisors(220)) = 284

div(220) = 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110

∑(divisors(284)) = 220

div(284) = 1, 2, 4, 71, 142

∑(divisors(1184)) = 1210

div(1184) = 1, 2, 4, 8, 16, 32, 37, 74, 148, 296, 592

∑(divisors(1210)) = 1184

div(1210) = 1, 2, 5, 10, 11, 22, 55, 110, 121, 242, 605

Algorithm It is easy to check whether two numbers are friends by determining for each number its divisors and therefrom its sum. Now the divisors can be determined from this sum and then added together. If this second sum is equal to the original number, then the numbers are friends.
def calc_friends(max_exclusive):
    friends = {}
    for i in range(2, max_exclusive):
        divisors1 = find_proper_divisors(i)
        sum_div1 = sum(divisors1)
        divisors2 = find_proper_divisors(sum_div1)
        sum_div2 = sum(divisors2)
        if i == sum_div2 and sum_div1 != sum_div2:
            friends[i] = sum_div1
    return friends

For the implementation, you also use the function find_proper_divisors() to find all real divisors. This was already presented in the introduction. Once again, it shows the advantage of subdividing software into smaller, self-contained functionalities.

Verification

In this case, you again use a parameterized test, which returns both the maximum value and a dictionary with the two numbers:
@pytest.mark.parametrize("max, friends",
                         [(250, {220: 284}),
                          (300, {220: 284, 284: 220}),
                          (2_000, {220: 284, 284: 220,
                                   1_184: 1_210, 1_210: 1_184})])
def test_calc_friends(max, friends):
    assert calc_friends(max) == friends

For some numbers I use the notation of separating the digits with an underscore, which is an excellent way to simulate a thousand point. This is especially helpful with larger numbers and serves here only for demonstration.

2.3.12 Solution 12: Prime Factorization (★★★✩✩)

Any natural number greater than 1 can be represented as a multiplication of primes. Remember the fact that 2 is also a prime. Write function calc_prime_factors(value) that returns a list of prime numbers whose multiplication yields the desired number.

Examples

Input

Prime factors

Result

8

2 * 2 * 2

[2, 2, 2]

14

2 * 7

[2, 7]

42

2 * 3 * 7

[2, 3, 7]

1155

3 * 5 * 7 * 11

[3, 5, 7, 11]

2222

2 * 11 * 101

[2, 11, 101]

Algorithm Start by dividing the number by 2 as long as the number is even and greater than 2. Then, at some point, you reach an odd number. If it is 1, you are done (see the case for the number 8). Otherwise, you check if the odd number is a prime number and collect it. In this case, you are done (for example, above for the number 14). If not, you have to split the odd number further. Let’s take 50 as an example. First, you divide by 2, there 25 remains, which is not a prime number. For these, you check for all prime numbers if they represent a divisor. You continue this procedure until you reach the number 1, which means that all divisors have been collected. For more info, see https://en.wikipedia.org/wiki/Integer_factorization.
def calc_prime_factors(value):
    all_primes = calc_primes_up_to(value)
    prime_factors = []
    remaining_value = value
    # as long as even, divide by 2 again and again
    while remaining_value % 2 == 0 and remaining_value >= 2:
        remaining_value = remaining_value // 2
        prime_factors.append(2)
    # check remainder for prime
    if is_prime(all_primes, remaining_value):
        prime_factors.append(remaining_value)
    else:
        # remainder is not a prime number, further check
        while remaining_value > 1:
            for current_prime in all_primes:
                if remaining_value % current_prime == 0:
                    remaining_value = remaining_value // current_prime
                    prime_factors.append(current_prime)
                    # start again from the beginning, because every divisor
                    # may occur more than once
                    break
    return prime_factors
def is_prime(all_primes, n):
    return n in all_primes
Optimized algorithm If you look at the algorithm just developed, you might be bothered by all the special treatments. With a little thought, you may conclude that you don’t need to check number 2 separately since it is also a prime number. Thus, this is covered by the while loop. Instead of the break for repeated checking of the same number, this can be expressed in a more stylistically pleasing way with a while loop. With these preliminary considerations, you arrive at the following implementation:
def calc_prime_factors_optimized(value):
    all_primes = calc_primes_up_to(value)
    prime_factors = []
    remaining_value = value
    while remaining_value > 1:
        for current_prime in all_primes:
            while remaining_value % current_prime == 0:
                remaining_value = remaining_value // current_prime
                prime_factors.append(current_prime)
    return prime_factors

Verification

For testing, use the following inputs, which show the correct operation:
def value_and_prime_factors():
    return [(8, [2, 2, 2]),
            (14, [2, 7]),
            (42, [2, 3, 7]),
            (1155, [3, 5, 7, 11]),
            (2222, [2, 11, 101])]
@pytest.mark.parametrize("value, primefactors",
                         value_and_prime_factors())
def test_calc_prime_factors(value, primefactors):
    assert calc_prime_factors(value) == primefactors
@pytest.mark.parametrize("value, primefactors",
                         value_and_prime_factors())
def test_calc_prime_factors_optimized(value, primefactors):
    assert calc_prime_factors_optimized(value) == primefactors

2.4 Summary: What You Learned

This chapter on basic mathematical knowledge introduces the modulo operator, which is quite essential, for example, for the extraction of digits and in the calculation of checksums. The exercises on combinatorics have shown how small tricks can easily reduce the running time by an order of magnitude. Also, prime numbers offer some interesting facets, such as variants to their calculation. In retrospect, this turns out to be much easier than perhaps first thought. In general, when trying to find a solution for a problem, the algorithm and the approach should be roughly understood because then, for example, even the the decomposition into prime factors loses its possible horror.

Now let’s move on to recursion as an important technique to break down a more complex task into several simpler subtasks.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset