Simple Example with a Function

Write an algorithm to compute the weekly salary of a worker given the number of hours worked during the week and the hourly rate. The first 35 hours are paid at the hourly rate, the next 10 with a 50% supplement, and the rest with a 75% supplement.

GCD

Write an algorithm to compute the GCD of two given positive integers. Reminder: Let a and b be two positive integers. We have:

• gcd(a,b) = a if b = 0,
• gcd(a,b) = gcd(b,remainder(a,b)) if b != 0 where remainder(a,b) is the remainder of the integer division of a by b.

Fibonacci

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,... By considering the terms in the Fibonacci sequence whose values do not exceed four millions, find the sum of the even-valued terms. —source Project Euler

Approximation of the Exponential Function

Recall the Taylor expansion at 0 of e^x: E_n = 1 + x + (x²)/(2!) + ... + (x^n)/(n!). Write a function power and a function factorial. Then write a function exp_approx that computes an approximate value of e(x) to order k (given by the user).

Fast Exponentiation

We will improve the computation of x^n by performing fewer than n operations. The method explained here is called fast exponentiation. Here is an example:

x²³ = x × (x²)¹¹

x²³ = (x × x²) × (x⁴)⁵

x²³ = (x × x² × x⁴) × (x⁸)²

x²³ = x × x² × x⁴ × x¹⁶

Therefore, if we compute even powers of x along the way, we perform fewer operations (how many, in the example?).

• By appropriately naming the different parts of the equality: res, pow and k, obtain the following loop invariant: At each loop iteration, we have res * pow^k = x^n. How do you obtain res, pow, k for the next iteration? When do we stop?
• Write the function fast_pow that takes integers x and k as arguments and computes x^k with this algorithm.
• Test on several examples.

Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)

n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Prime Numbers

• Write a function that determines whether a number n is prime or not.
• The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
• By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?
• The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
• The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97. How many circular primes are there below one million?