Arithmetic

Problem 31

intermediate

Determine whether a given integer number is prime.

Example

is_prime(7) == true

Problem 32

intermediate

Determine the greatest common divisor of two positive integer numbers. Use Euclid's algorithm.

Example

gcd(36, 63) == 9

Problem 33

easy

Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.

Example

coprime(35, 64) == true

Problem 34

intermediate

Calculate Euler's totient function $ϕ (m)$ .

Euler's so-called totient function $ϕ (m)$ is defined as the number of positive integers $r, 1 \leq r < m$ that are coprime to $m$ .

Example

$m = 10, r = 1, 3, 7, 9$ thus $ϕ (10) = 4$ . Note the special case: $ϕ (1) = 1$ .

Find out what the value of $ϕ (m)$ is if $m$ is a prime number.

Euler's totient function plays an important role in one of the most widely used public key cryptography methods (RSA). In this exercise you should use the most primitive method to calculate this function (there are smarter ways that we shall discuss later).

Problem 35

intermediate

Determine the prime factors of a given positive integer.

Construct a flat list containing the prime factors in ascending order.

Example

prime_factors(315) == [3,3,5,7]

Problem 36

intermediate

Determine the prime factors of a given positive integer (2).

Construct a list containing the prime factors and their multiplicity.

Example

prime_factors_mult(315) == [[3,2],[5,1],[7,1]]

Hint: The problem is similar to problem P13.

Problem 37

intermediate

Calculate Euler's totient function $ϕ (m)$ (improved).

See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number $m$ is known in the form of problem P36 then the function $ϕ (m)$ can be efficiently calculated as follows: Let [[p1,m1],[p2,m2],[p3,m3],...] be the list of prime factors (and their multiplicities) of a given number $m$ . Then $ϕ (m)$ can be calculated with the following formula:

$ϕ (m) = (p_{1} - 1) \times p_{1}^{(m_{1} - 1)} \times (p_{2} - 1) \times p_{2}^{(m_{2} - 1)} \times (p_{3} - 1) \times p_{3}^{(m_{3} - 1)} \dots$

Problem 38

easy

Compare the two methods of calculating Euler's totient function.

Use the solutions of problems P34 and P37 to compare the algorithms. Take the number of logical inferences as a measure for efficiency. Try to calculate $ϕ (10090)$ as an example.

Problem 39

easy

A list of prime numbers.

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

Problem 40

intermediate

Goldbach's conjecture.

Goldbach's conjecture says that every positive even number greater than $2$ is the sum of two prime numbers. Example: $28 = 5 + 23$ .

It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers. Write a function to find the two prime numbers that sum up to a given even integer.

Example

goldbach(28) == [5,23]

Problem 41

intermediate

A list of Goldbach compositions.

Given a range of integers by its lower and upper limit, return a list of all even numbers and their Goldbach composition.

Example

goldbach_list(9,20) == [
        [ 10,   3,  7   ], 
        [ 12,   5,  7   ], 
        [ 14,   3,  11  ],
        [ 16,   3,  13  ], 
        [ 18,   5,  13  ], 
        [ 20,   3,  17  ]
    ]

In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50. Try to find out how many such cases there are in the range $2, \dots, 3000$ .

Example (for a print limit of 50)

goldbach_list(1,2000,50) == [
    [ 992,  73, 91  ],
    [ 1382, 61, 132 ],
    [ 1856, 67, 178 ],
    [ 1928, 61, 186 ],
]

99 Problems