<jupyter_start><jupyter_text>Solving three problems from the Euler Project (with increasing difficulty)  Problem 5: Smallest Multiple    Description: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.  What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?      After reading this question, I immediately thought about prime factorization and factor trees. The goal is to program a factor tree and work backwards from the prime factors to calculate the smallest number that is evenly divisible by all numbers from 1 to 20. Note that 2520 has to be divisible by the prime numbers from 1 to 10 in order to be divisible by all numbers 1 to 10 without any remainder. Knowing this, we can save time by not checking whether 2520 is divisible by every number from 1 to 10.    So to begin, we will define a function to return a list of all the prime numbers from 1 to a given number. This will help us code our factor tree.<jupyter_code>def prime_num(n):
    """
    return list of prime numbers given a number
    """
    primes = []
    # prime numbers have to be greater than 1
    for number in range(2, n + 1):
        for i in range(2, number):
            if (number % i) == 0:
                # number is not prime (divisible by a number other than one and itself)
                # return to outer for loop and increment by one
                break
        else:
            # number is prime so add to list
            primes.append(number)
    return primes<jupyter_output><empty_output><jupyter_text>Next, the goal is to code a factor tree where the "ends" or what is returned are all the prime factors of the given number.    We will find the prime factors of this given number (n) using knowledge about whether a number is prime in range 1 to n from the above function that returns the prime numbers in range 1 to n. Recursion works well here because we want to break down n into smaller parts each time until n equals 1 and we cannot find any more prime factors.<jupyter_code>def find_prime_factors(n):
    """
    recursively find prime factors of number given prime numbers in range 1 to that number
    """
    prime_numbers = prime_num(20)
    if n == 1:
        # base case: if n = 1, there are no more prime factors
        return []
    for num in prime_numbers:
        # loop through each number in the list of prime numbers in range 1 to n
        if n % num == 0:
            # return the prime factor and use recursion to find next prime factor
            return [num] + find_prime_factors(n / num)<jupyter_output><empty_output><jupyter_text>We will write a final function that uses the two functions we have written. We know the prime numbers from 1 to a given number from the first function. We can also find the prime factors of a number from the second function.  Now, we will find the prime factors of every number 20 and below (using the second function). We will keep track of the maximum prime factors. For example, the prime factors of 2 and 3, respectively, are 2 and 3 and the prime factors of 4 are 2 and 2. So, the maximum count of the prime factor 2 is 2 and of 3 is 1 and the prime factors of the smallest number evenly divisible by 2, 3, and 4, are 2, 2, and 3 and NOT 2, 3, 2, and 2. This means the smallest number evenly divisible by 2, 3, and 4 equals (2)(2)(3) = 12.    Using this same logic, we will use the maximum prime factors of numbers 20 and below to calculate the smallest number evenly divisible by all of the numbers from 1 to 20.  We recently reviewed the collections module, so we will use that to count the maximum number of each prime factor.<jupyter_code>from collections import Counter

def main():
    """
    print smallest number evenly divisible by all numbers from 1 to 20
    """
    max_primes = Counter()
    
    for i in range(2, 21):
        # creating a factor tree for each number from 2 to 20
        prime_factors = Counter(find_prime_factors(i))
        # keeps maximum of counts of each prime factor
        max_primes = prime_factors | max_primes
        
    smallest_num = 1
    for prime, count in max_primes.items():
        # based on prime factors, calculate smallest number by multiplying
        smallest_num = smallest_num * (prime ** count)
    
    print(smallest_num)

main()<jupyter_output>232792560<jupyter_text>The smallest positive number that is evenly divisible by all of the numbers from 1 to 20 is 232792560.  Problem 39: Integer Right Triangles    Description: If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.  {20,48,52}, {24,45,51}, {30,40,50}  For which value of p ≤ 1000, is the number of solutions maximised? This question involves pythagorean theorem (a^2 + b^2 = c^2). The first step is to define a function that returns the number of solutions that meet the right angle triangle side length definition given a perimeter.  We know that a and b have to be at least 1 and cannot be more than half the perimeter. So, we will use a to loop through all integers from 1 to p/2.Given these two equations:  a^2 + b^2 = c^2  (pythagorean theorem)   a + b + c = p  (definition of perimeter)We can solve for b and c.  1) a + b + c = p --> b+c = p-a  2) a^2 + b^2 = c^2 --> c-b = a^2/(p-a)  3) (c-b) + (c+b) = a^2/(p-a) + (p-a) --> c = (a^2 + (p-a)^2)/(2 *(p-a)Then, using pythagorean theorem, b = sqrt(c^2 - a^2)  The final step is to check whether the definition of perimeter is met and make sure we have the correct value for a.<jupyter_code>def find_side_lengths(p):
    """
    return number of solutions that meet the definition of right angle triangle side lengths given a perimeter
    """
    num_solutions = 0
    
    # an integer side length of a right triangle has to be at least 1 and not more than half the perimeter
    for a in range(1, p//2):
        # solve pythagorean theorem for c and b
        c = (a**2 + (p-a)**2) // (2 * (p-a))
        b = (c**2 - a**2) ** 0.5
        
        # if definition of perimeter is met, increment solutions by one
        if a + b + c == p:
            num_solutions += 1
    
    # a and b can be switched in a solution, but we only want one solution of possible integral side lengths
    return num_solutions//2<jupyter_output><empty_output><jupyter_text>Next, we want to find the perimeter where the number of solutions, given that we know the number of solutions for a perimeter from the previous equation, is maximized for perimeters ≤ 1000. We will use a dictionary to store the perimeter and the number of solutions for that perimeter.<jupyter_code>def maximized(perimeter):
    """
    print perimeter where the number of solutions is maximized for perimeter <= 1000 
    """
    data = {"perimeter": 0, "solutions": 0} # store perimeter value and number of solutions
    for p in range(perimeter + 1):
        # if the number of solutions of the current perimeter is greater than the solutions for all perimeters smaller
        # then store that perimeter and the corresponding number of solutions
        solutions = find_side_lengths(p)
        if solutions > data['solutions']:
            data['solutions'] = solutions
            data['perimeter'] = p
    return data['perimeter']

print(maximized(1000))<jupyter_output>840<jupyter_text>The number of solutions is maximised at a perimeter of 840.   Problem 112: Bouncy Numbers    Decription: Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.    Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.    We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.    Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.    Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.    Find the least number for which the proportion of bouncy numbers is exactly 99%.      The first step is to determine if a number is bouncy. Using the properties of a bouncy number, that it is neither increasing nor decreasing, we will define a function that returns true if the number is bouncy.<jupyter_code>def bouncy(n):
    """
    return true if the number is bouncy and false otherwise
    """
    number = list(map(int, str(n))) # list of digits
    increasing = sorted(number) # if number is sorted, it is increasing
    decreasing = increasing[::-1] # if number is sorted in reverse, it is decreasing
    return increasing != number and decreasing != number<jupyter_output><empty_output><jupyter_text>Next, we will find the least number for which the proportion of bouncy numbers is exactly 99%.   I found that a while loop would work well in this case because we want the loop to run until we find the number when the proportion equals 99%. Each iteration we will check whether the number is bouncy and whether the proportion of bouncy numbers equals 99% beginning at 100.<jupyter_code>def prop_bouncy():
    """
    return least number where the proportion of bouncy numbers that is exactly 99%
    """
    total = 100 # no bouncy numbers below 100
    bouncy_n = 0 
    
    # continue finding bouncy numbers until proportion hits 99%
    while bouncy_n / total != 0.99:
        # determine if number is bouncy then increment count by one if is bouncy
        if bouncy(total) is True:
            bouncy_n += 1
        # if proportion is eactly 99%, return number
        if bouncy_n / total == 0.99:
            return total
        # increment total to continue finding least number
        else:
            total += 1 
            
print(prop_bouncy())<jupyter_output>1587000
{'fraction_non_alphanumeric': 0.058993811139948095, 'fraction_numerical': 0.02725094829307247, 'mean_word_length': 3.171107410491257, 'pattern_counts': {'":': 2, '<': 27, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '37077', 'license': 'Apache-2.0', 'n_tokens_mistral': 2906, 'n_tokens_neox': 2631, 'n_words': 1485, 'path': '_notebooks/2021-09-03-eulerproblems.ipynb', 'repo_name': 'saahithirao/bios-823-blog', 'size': '10018'}