Chapter 31 Python Exercises

31.1 Multiples of 3 - 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6, 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

a = [x for x in range(1, 10) if (x%3==0 or x%5==0)]
sum(a)==23
## True
b = [x for x in range(1, 1000) if (x%3==0 or x%5==0)]
print(sum(b))
## 233168

31.2 Even Fibonacci numbers

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…

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

fib_list = [1, 2]

while True:
  
  x = fib_list[-1] + fib_list[-2]
  
  if x > 4000000:
    break
  
  fib_list.append(x)
  
even_sum = [x for x in fib_list if x%2==0]

sum(even_sum)
## 4613732

31.3 Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

# primes = [1, 2]
# 
# while True:
#   
#   for x in range(2, 10):
#     
#     x%i==0

31.4 Greatest Common Diviser

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Example usage:
print(gcd(55, 60))  # Output: 12
## 5

31.4.1 Question: triangle

given a list of integers (with at least 3 elements) representing triangle sides, count all combinations that you might be able to build a triangle with (if side3 is the longest, then it should satisfy side1+side2 > side3).

To solve this problem, we need to count all combinations of three sides from a given list of integers that can form a valid triangle. A valid triangle must satisfy the triangle inequality theorem, which states that for any three sides, if the longest side is side3, then it should hold that:

\[\text{side1} + \text{side2} > \text{side3}\]

31.4.2 Steps to Solve

  1. Sort the List: First, sort the list of integers in ascending order. This makes it easier to find valid combinations since once the list is sorted, we can safely assume that any triplet (i, j, k) with i < j < k will have side3 as the longest side.

  2. Use a Triplet Combination Check: For each potential triplet (side1, side2, side3), check if it satisfies the triangle inequality.

  3. Count Valid Combinations: Keep a counter to track the number of valid combinations.

31.4.3 Python Code Implementation

def count_valid_triangles(sides):
    # Step 1: Sort the list of sides
    sides.sort()
    n = len(sides)
    count = 0

    # Step 2: Use a triplet combination check
    # Iterate through all possible triplets
    for i in range(n - 2):  # i is the index for side1
        k = i + 2  # Initialize k for the triplet (side3)
        for j in range(i + 1, n - 1):  # j is the index for side2
            # Step 3: Find the rightmost side3 that satisfies the triangle inequality
            while k < n and sides[i] + sides[j] > sides[k]:
                k += 1
            # All combinations from j+1 to k-1 will satisfy the triangle condition
            count += k - j - 1

    return count

# Example usage
sides = [2, 3, 4, 5, 6]
print(count_valid_triangles(sides))  # Output: 7

31.4.4 Explanation of the Code

  1. Sorting the Sides: The list sides is sorted in ascending order.

  2. Two Nested Loops:

    • The outer loop (indexed by i) selects side1.
    • The middle loop (indexed by j) selects side2 (such that j > i).
    • The innermost loop uses a while loop to find the rightmost side3 (indexed by k) that satisfies the condition side1 + side2 > side3.

  3. Counting Valid Triangles:

    • For each side1 and side2, we find the number of valid side3 values that satisfy the triangle inequality.
    • We increment the count by k - j - 1, which is the number of valid combinations for that particular (i, j).

31.4.5 Time Complexity

  • Sorting: \(O(n \log n)\)
  • Two Loops: The nested loops run in \(O(n^2)\) time.
  • Overall Time Complexity: \(O(n^2)\)

31.4.6 Example

Given a list sides = [2, 3, 4, 5, 6]:

  • The valid triangles are (2, 3, 4), (2, 4, 5), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), and (4, 5, 6).
  • The output is 7.

This approach ensures all valid triangles are counted efficiently.

def count_possible_triangles(sides):
    """Count index triplets that can form a non-degenerate triangle."""
    values = sorted(sides)
    count = 0

    for largest in range(len(values) - 1, 1, -1):
        left = 0
        right = largest - 1

        while left < right:
            if values[left] + values[right] > values[largest]:
                # Every value from left through right - 1 also works with
                # values[right] and values[largest].
                count += right - left
                right -= 1
            else:
                left += 1

    return count


sides = [2, 3, 4, 5, 6]
result = count_possible_triangles(sides)
assert result == 7
result
## 7