Can you write a Python program to check a sequence of numbers is an arithmetic progression or not?
To refresh your memory, a sequence is a set of things (usually numbers) that are in order. In an Arithmetic Sequence the difference between one term and the next is a constant. In other words, we just add the same value each time.
For example, the sequence 5, 7, 9, 11, 13, 15 ... is an arithmetic progression with common difference of 2.
We can write an Arithmetic Sequence as a rule:
xn = a + d(n−1)
How would you write it using Python? Try it yourself. If you cannot figure it out, see code on the next page.
Image from Pixabay
The Fibonacci sequence was first observed by the Italian mathematician Leonardo Fibonacci in 1202. He was investigating how fast rabbits could breed under ideal circumstances. He made the following assumptions:
Fibonacci asked how many pairs of rabbits would be produced in one year.
Can you create the numbers yourself? Remember to count the 'pairs' of rabbits and not the individual ones. Try it.
Were you able to come up with the Fibonacci numbers? If not, here is how you would do it.
The pattern comes out to be 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.
Fibonacci numbers are of interest to biologists and physicists because they are frequently observed in various natural objects and phenomena. For example, the branching patterns in trees and leaves are based on Fibonacci numbers.
On many plants, the number of petals is a Fibonacci number: buttercups have 5 petals; lilies and iris have 3 petals; some delphiniums have 8; corn marigolds have 13 petals; some asters have 21 whereas daisies can be found with 34, 55 or even 89 petals.
How can we create a rule (algorithm) for the fibonacci series (sequence)?
First, the terms are numbered from 0 onwards like this:
n = 0 1 2 3 4 5 6 7 8 9 10 ...
xn =0 1 1 2 3 5 8 13 21 34 55 ...
What rule can we create here? Well, if you look, x3 = x2 + x 1 (2 = 1 + 1) and x4 = x2 + x3 (3 = 1 + 2), etc.
So we can write the rule (algorithm) as: xn = x(n-1) + x(n-2).
Example: term 7 is calculated as:
x7= x(7-1) + x(7-2)
= x6 + x5
= 13 + 8
Let's write programs in Python to calculate the Fibonacci numbers.
1. With looping:
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
1. With recursion:
if n==1 or n==2:
N.B: No not copy and paste the python code as identation is important.
The greatest common divisor (GCD) or the highest common factor (HCF) of two numbers is the largest positive integer that perfectly divides the two given numbers. Solving this problem for a specific set of numbers is easy. For example, find the GCD of 12 and 18. The The divisors of 12 are 1, 2, 3, 4, 6, 12 and for 18 are 1, 2, 3, 6, 9, 18. The common factors are 1, 2, 3, and 6. So the greatest common factor is 6.
How would you find the GCD for any number? Here the problem is more challenging. Here is one solution. Let's take two integers a and b passed to a function which returns the GCD. In the function, we first determine the smaller of the two number since the GCD (HCF) can only be less than or equal to the smallest number. For example, the GCD of 12 and 14 can only be less than 12 and not greater. We then use a for loop to go from 1 to that number.
In each iteration, we check if our number perfectly divides both the input numbers. If so, we store the number as the GCD. At the completion of the loop we end up with the largest number that perfectly divides both the numbers.
Below is the algorithm in python.
def computeGCD(a, b):
if a < b:
smaller = a
smaller = b
for i in range(1, smaller+1):
if (a % i == 0) & (b % i == 0):
gcd = i
N.B: Do not cut and paste the above code. Make sure the indentation is correct.
The above method is easy to understand and implement but not efficient. A much more efficient method to find the GCD (HCF) is the Euclidean algorithm.
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. That is a mouthful! Let's make it simple by taking an example. 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 147 (252 − 105). Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.
A more efficient version of the algorithm shortcuts these steps, instead we divide the greater by smaller and take the remainder. Now, divide the smaller by this remainder. Repeat until the remainder is 0.
For example, if we want to find the H.C.F. of 54 and 24, we divide 54 by 24. The remainder is 6. Now, we divide 24 by 6 and the remainder is 0. Hence, 6 is the required GCD.
Python code for Euclidean Algorithm
def euclidAlgo(a, b):
a, b = b, a % b
Python code for Euclidean Algorithm using recursion:
def euclidAlgo(a, b):
if (b == 0):
return euclidAlgo(b, a % b)
Sources: Wikipedia; https://www.programiz.com/python-programming/examples/hcf
Free Image from Pixabay
Finding Prime Numbers
Prime numbers are very important, yet many students do not see the value of learning them. Primes have several applications, most importantly in information technology, such as public-key cryptography, which relies on the difficulty of factoring large numbers into their prime factors. One key challenge is to find prime numbers. Interestingly, Prime numbers and their properties were first studied extensively by the ancient Greek mathematicians. Euclid, for example, proved that there are infinitely many prime numbers.
Just to refresh our memory, a number greater than 1 is called a prime number, if it has only two factors, namely 1 and the number itself.
Proof by Contradiction
One of the first known proofs is the method of contradiction. It is used to calculate prime factors of large numbers. Calculating prime factors of small numbers is easy. For example, the factors of 17 is 1 and 17, so it is a prime number. What about large numbers? Let's look at the proof by contradiction method.
If a number n is not a prime, it can be factored into two factors a and b, such that n = a*b. For example, let's say a * b = 100, for various pairs of a and b.
If a = b, then they are equal, we have a*a = 100, or a^2 = 100, or a = 10, the square root of 100. If one of the numbers is less than 10, then the other has to be greater to make it to 100. For example, take 4 x 25 = 100. 4 is less than 10, the other number has to be greater than 10. In other words, if a * b, if one of them goes down, the other number has to get bigger to compensate so the product stays at 100. Put mathematically, the numbers revolve around the square root of their product.
Let's test if 101 is prime number. You could start dividing 101 by 2, 3, 5, 7, etc, but that is very tedious. A better way is to take the square root of 101, which is roughly equal to 10.049875621. So you only need to try the integers up through 10, including 10. 8, 9, and 10 are not themselves prime, so you only have to test up through 7, which is prime.
Because if there's a pair of factors with one of the numbers bigger than 10, the other of the pair has to be less than 10. If the smaller one doesn't exist, there is no matching larger factor of 101.
Let's now build an algorithm using this method to test any number for primality.
Algorithm in Python
if (num < 2):
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
N.B: Do not just copy the code because you have to be careful with indentation in python.
Try the above algorithm and let us know if you found it useful or have alternative solutions.
Write something about yourself. No need to be fancy, just an overview.