You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
"""Project Euler Problem 1=======================If we list all the natural numbers below 10 that are multiples of 3 or 5,we get 3, 5, 6 and 9. The sum of these multiples is 23.Find the sum of all the multiples of 3 or 5 below 1000."""
Problem 2
"""Project Euler Problem 2=======================Each new term in the Fibonacci sequence is generated by adding theprevious two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...Find the sum of all the even-valued terms in the sequence which do notexceed four million."""
Problem 3
"""Project Euler Problem 3=======================The prime factors of 13195 are 5, 7, 13 and 29.What is the largest prime factor of the number 600851475143?"""
Problem 4
"""Project Euler Problem 4=======================A palindromic number reads the same both ways. The largest palindrome madefrom the product of two 2-digit numbers is 9009 = 91 * 99.Find the largest palindrome made from the product of two 3-digit numbers."""
Problem 5
"""Project Euler Problem 5=======================2520 is the smallest number that can be divided by each of the numbersfrom 1 to 10 without any remainder.What is the smallest number that is evenly divisible by all of the numbersfrom 1 to 20?"""
Problem 6
"""Project Euler Problem 6=======================The sum of the squares of the first ten natural numbers is, 1^2 + 2^2 + ... + 10^2 = 385The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)^2 = 55^2 = 3025Hence the difference between the sum of the squares of the first tennatural numbers and the square of the sum is 3025 - 385 = 2640.Find the difference between the sum of the squares of the first onehundred natural numbers and the square of the sum."""
Problem 7
"""Project Euler Problem 7=======================By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can seethat the 6th prime is 13.What is the 10001st prime number?"""
Problem 8
"""Project Euler Problem 8=======================Find the greatest product of thirteen consecutive digits in the 1000-digitnumber. 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450"""
Problem 9
"""Project Euler Problem 9=======================A Pythagorean triplet is a set of three natural numbers, a < b < c, forwhich, a^2 + b^2 = c^2For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.There exists exactly one Pythagorean triplet for which a + b + c = 1000.Find the product abc."""
Problem 10
"""Project Euler Problem 10========================The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.Find the sum of all the primes below two million."""
"""Project Euler Problem 12========================The sequence of triangle numbers is generated by adding the naturalnumbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 =28. The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...Let us list the factors of the first seven triangle numbers: 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over fivedivisors.What is the value of the first triangle number to have over five hundreddivisors?"""
"""Project Euler Problem 14========================The following iterative sequence is defined for the set of positiveintegers:n->n/2 (n is even)n->3n+1 (n is odd)Using the rule above and starting with 13, we generate the followingsequence: 13->40->20->10->5->16->8->4->2->1It 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."""
Problem 15
"""Project Euler Problem 15========================Starting in the top left corner of a 2 * 2 grid, there are 6 routes(without backtracking) to the bottom right corner.How many routes are there through a 20 * 20 grid?"""
Problem 16
"""Project Euler Problem 16========================2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.What is the sum of the digits of the number 2^1000?"""
Problem 17
"""Project Euler Problem 17========================If the numbers 1 to 5 are written out in words: one, two, three, four,five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.If all the numbers from 1 to 1000 (one thousand) inclusive were writtenout in words, how many letters would be used?NOTE: Do not count spaces or hyphens. For example, 342 (three hundred andforty-two) contains 23 letters and 115 (one hundred and fifteen) contains20 letters. The use of "and" when writing out numbers is in compliancewith British usage."""
Problem 18
"""Project Euler Problem 18========================By starting at the top of the triangle below and moving to adjacentnumbers on the row below, the maximum total from top to bottom is 23. 3 7 4 2 4 6 8 5 9 3That is, 3 + 7 + 4 + 9 = 23.Find the maximum total from top to bottom of the triangle below: 75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge witha triangle containing one-hundred rows; it cannot be solved by bruteforce, and requires a clever method! ;o)"""
Problem 19
"""Project Euler Problem 19========================You are given the following information, but you may prefer to do someresearch for yourself. * 1 Jan 1900 was a Monday. * Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, Which has twenty-eight, rain or shine. And on leap years, twenty-nine. * A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.How many Sundays fell on the first of the month during the twentiethcentury (1 Jan 1901 to 31 Dec 2000)?"""
Problem 20
"""Project Euler Problem 20========================n! means n * (n - 1) * ... * 3 * 2 * 1Find the sum of the digits in the number 100!"""
Problem 21
"""Project Euler Problem 21========================Let d(n) be defined as the sum of proper divisors of n (numbers less thann which divide evenly into n).If d(a) = b and d(b) = a, where a =/= b, then a and b are an amicable pairand each of a and b are called amicable numbers.For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22,44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1,2, 4, 71 and 142; so d(284) = 220.Evaluate the sum of all the amicable numbers under 10000."""
Problem 22
"""Project Euler Problem 22========================Using names.txt, a 46K text file containing over five-thousand first names,begin by sorting it into alphabetical order. Then working out thealphabetical value for each name, multiply this value by its alphabeticalposition in the list to obtain a name score.For example, when the list is sorted into alphabetical order, COLIN, whichis worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So,COLIN would obtain a score of 938 * 53 = 49714.What is the total of all the name scores in the file?"""
Problem 23
"""Project Euler Problem 23========================A perfect number is a number for which the sum of its proper divisors isexactly equal to the number. For example, the sum of the proper divisorsof 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfectnumber.A number whose proper divisors are less than the number is calleddeficient and a number whose proper divisors exceed the number is calledabundant.As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, thesmallest number that can be written as the sum of two abundant numbers is24. By mathematical analysis, it can be shown that all integers greaterthan 28123 can be written as the sum of two abundant numbers. However,this upper limit cannot be reduced any further by analysis even though itis known that the greatest number that cannot be expressed as the sum oftwo abundant numbers is less than this limit.Find the sum of all the positive integers which cannot be written as thesum of two abundant numbers."""
Problem 24
"""Project Euler Problem 24========================A permutation is an ordered arrangement of objects. For example, 3124 isone possible permutation of the digits 1, 2, 3 and 4. If all of thepermutations are listed numerically or alphabetically, we call itlexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210What is the millionth lexicographic permutation of the digits 0, 1, 2, 3,4, 5, 6, 7, 8 and 9?"""
Problem 25
"""Project Euler Problem 25========================The Fibonacci sequence is defined by the recurrence relation: F[n] = F[n[1]] + F[n[2]], where F[1] = 1 and F[2] = 1.Hence the first 12 terms will be: F[1] = 1 F[2] = 1 F[3] = 2 F[4] = 3 F[5] = 5 F[6] = 8 F[7] = 13 F[8] = 21 F[9] = 34 F[10] = 55 F[11] = 89 F[12] = 144The 12th term, F[12], is the first term to contain three digits.What is the first term in the Fibonacci sequence to contain 1000 digits?"""
Problem 26
"""Project Euler Problem 26========================A unit fraction contains 1 in the numerator. The decimal representation ofthe unit fractions with denominators 2 to 10 are given: 1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It canbe seen that ^1/[7] has a 6-digit recurring cycle.Find the value of d < 1000 for which ^1/[d] contains the longest recurringcycle in its decimal fraction part."""
Problem 27
"""Project Euler Problem 27========================Euler published the remarkable quadratic formula: n^2 + n + 41It turns out that the formula will produce 40 primes for the consecutivevalues n = 0 to 39. However, when n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41is divisible by 41, and certainly when n = 41, 41^2 + 41 + 41 is clearlydivisible by 41.Using computers, the incredible formula n^2 - 79n + 1601 was discovered,which produces 80 primes for the consecutive values n = 0 to 79. Theproduct of the coefficients, 79 and 1601, is 126479.Considering quadratics of the form: n^2 + an + b, where |a| < 1000 and |b| < 1000 where |n| is the modulus/absolute value of n e.g. |11| = 11 and |-4| = 4Find the product of the coefficients, a and b, for the quadraticexpression that produces the maximum number of primes for consecutivevalues of n, starting with n = 0."""
Problem 28
"""Project Euler Problem 28========================Starting with the number 1 and moving to the right in a clockwisedirection a 5 by 5 spiral is formed as follows: 21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13It can be verified that the sum of both diagonals is 101.What is the sum of both diagonals in a 1001 by 1001 spiral formed in thesame way?"""
Problem 29
"""Project Euler Problem 29========================Consider all integer combinations of a^b for 2 a 5 and 2 b 5: 2^2=4, 2^3=8, 2^4=16, 2^5=32 3^2=9, 3^3=27, 3^4=81, 3^5=243 4^2=16, 4^3=64, 4^4=256, 4^5=1024 5^2=25, 5^3=125, 5^4=625, 5^5=3125If they are then placed in numerical order, with any repeats removed, weget the following sequence of 15 distinct terms: 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125How many distinct terms are in the sequence generated by a^b for2 <= a <= 100 and 2 <= b <= 100?"""
Problem 30
"""Project Euler Problem 30========================Surprisingly there are only three numbers that can be written as the sumof fourth powers of their digits: 1634 = 1^4 + 6^4 + 3^4 + 4^4 8208 = 8^4 + 2^4 + 0^4 + 8^4 9474 = 9^4 + 4^4 + 7^4 + 4^4As 1 = 1^4 is not a sum it is not included.The sum of these numbers is 1634 + 8208 + 9474 = 19316.Find the sum of all the numbers that can be written as the sum of fifthpowers of their digits."""
Problem 31
"""Project Euler Problem 31========================In England the currency is made up of pound, -L-, and pence, p, and thereare eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, -L-1 (100p) and -L-2 (200p).It is possible to make -L-2 in the following way: 1 * -L-1 + 1 * 50p + 2 * 20p + 1 * 5p + 1 * 2p + 3 * 1pHow many different ways can -L-2 be made using any number of coins?"""
Problem 32
"""Project Euler Problem 32========================We shall say that an n-digit number is pandigital if it makes use of allthe digits 1 to n exactly once; for example, the 5-digit number, 15234,is 1 through 5 pandigital.The product 7254 is unusual, as the identity, 39 * 186 = 7254, containingmultiplicand, multiplier, and product is 1 through 9 pandigital.Find the sum of all products whose multiplicand/multiplier/productidentity can be written as a 1 through 9 pandigital.HINT: Some products can be obtained in more than one way so be sure toonly include it once in your sum."""
Problem 33
"""Project Euler Problem 33========================The fraction 49/98 is a curious fraction, as an inexperiencedmathematician in attempting to simplify it may incorrectly believe that49/98 = 4/8, which is correct, is obtained by cancelling the 9s.We shall consider fractions like, 30/50 = 3/5, to be trivial examples.There are exactly four non-trivial examples of this type of fraction, lessthan one in value, and containing two digits in the numerator anddenominator.If the product of these four fractions is given in its lowest commonterms, find the value of the denominator."""
Problem 34
"""Project Euler Problem 34========================145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.Find the sum of all numbers which are equal to the sum of the factorial oftheir digits.Note: as 1! = 1 and 2! = 2 are not sums they are not included."""
Problem 35
"""Project Euler Problem 35========================The number, 197, is called a circular prime because all rotations of thedigits: 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?"""
Problem 36
"""Project Euler Problem 36========================The decimal number, 585 = 1001001001[2] (binary), is palindromic in bothbases.Find the sum of all numbers, less than one million, which are palindromicin base 10 and base 2.(Please note that the palindromic number, in either base, may not includeleading zeros.)"""
Problem 37
"""Project Euler Problem 37========================The number 3797 has an interesting property. Being prime itself, it ispossible to continuously remove digits from left to right, and remainprime at each stage: 3797, 797, 97, and 7. Similarly we can work fromright to left: 3797, 379, 37, and 3.Find the sum of the only eleven primes that are both truncatable from leftto right and right to left.NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes."""
Problem 38
"""Project Euler Problem 38========================Take the number 192 and multiply it by each of 1, 2, and 3: 192 * 1 = 192 192 * 2 = 384 192 * 3 = 576By concatenating each product we get the 1 to 9 pandigital, 192384576. Wewill call 192384576 the concatenated product of 192 and (1,2,3)The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4,and 5, giving the pandigital, 918273645, which is the concatenated productof 9 and (1,2,3,4,5).What is the largest 1 to 9 pandigital 9-digit number that can be formed asthe concatenated product of an integer with (1,2, ... , n) where n > 1?"""
Problem 39
"""Project Euler Problem 39========================If p is the perimeter of a right angle triangle with integral lengthsides, {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?"""
Problem 40
"""Project Euler Problem 40========================An irrational decimal fraction is created by concatenating the positiveintegers: 0.123456789101112131415161718192021... ^It can be seen that the 12th digit of the fractional part is 1.If d[n] represents the n-th digit of the fractional part, find the valueof the following expression. d[1] * d[10] * d[100] * d[1000] * d[10000] * d[100000] * d[1000000]"""
Problem 41
"""Project Euler Problem 41========================We shall say that an n-digit number is pandigital if it makes use of allthe digits 1 to n exactly once. For example, 2143 is a 4-digit pandigitaland is also prime.What is the largest n-digit pandigital prime that exists?"""
Problem 42
"""Project Euler Problem 42========================The n-th term of the sequence of triangle numbers is given by, t[n] =1/2n(n+1); so the first ten triangle numbers are: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...By converting each letter in a word to a number corresponding to itsalphabetical position and adding these values we form a word value. Forexample, the word value for SKY is 19 + 11 + 25 = 55 = t[10]. If the wordvalue is a triangle number then we shall call the word a triangle word.Using words.txt, a 16K text file containing nearly two-thousand commonEnglish words, how many are triangle words?"""
Problem 43
"""Project Euler Problem 43========================The number, 1406357289, is a 0 to 9 pandigital number because it is madeup of each of the digits 0 to 9 in some order, but it also has a ratherinteresting sub-string divisibility property.Let d[1] be the 1st digit, d[2] be the 2nd digit, and so on. In thisway, we note the following: * d[2]d[3]d[4]=406 is divisible by 2 * d[3]d[4]d[5]=063 is divisible by 3 * d[4]d[5]d[6]=635 is divisible by 5 * d[5]d[6]d[7]=357 is divisible by 7 * d[6]d[7]d[8]=572 is divisible by 11 * d[7]d[8]d[9]=728 is divisible by 13 * d[8]d[9]d[10]=289 is divisible by 17Find the sum of all 0 to 9 pandigital numbers with this property."""
Problem 44
"""Project Euler Problem 44========================Pentagonal numbers are generated by the formula, P[n]=n(3n-1)/2. The firstten pentagonal numbers are: 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...It can be seen that P[4] + P[7] = 22 + 70 = 92 = P[8]. However, theirdifference, 70 - 22 = 48, is not pentagonal.Find the pair of pentagonal numbers, P[j] and P[k], for which their sumand difference is pentagonal and D = |P[k] - P[j]| is minimised; what isthe value of D?"""
Problem 45
"""Project Euler Problem 45========================Triangle, pentagonal, and hexagonal numbers are generated by the followingformulae:Triangle T[n]=n(n+1)/2 1, 3, 6, 10, 15, ...Pentagonal P[n]=n(3n-1)/2 1, 5, 12, 22, 35, ...Hexagonal H[n]=n(2n-1) 1, 6, 15, 28, 45, ...It can be verified that T[285] = P[165] = H[143] = 40755.Find the next triangle number that is also pentagonal and hexagonal."""
Problem 46
"""Project Euler Problem 46========================It was proposed by Christian Goldbach that every odd composite number canbe written as the sum of a prime and twice a square.9 = 7 + 2 * 1^215 = 7 + 2 * 2^221 = 3 + 2 * 3^225 = 7 + 2 * 3^227 = 19 + 2 * 2^233 = 31 + 2 * 1^2It turns out that the conjecture was false.What is the smallest odd composite that cannot be written as the sum of aprime and twice a square?"""
Problem 47
"""Project Euler Problem 47========================The first two consecutive numbers to have two distinct prime factors are:14 = 2 * 715 = 3 * 5The first three consecutive numbers to have three distinct prime factorsare:644 = 2^2 * 7 * 23645 = 3 * 5 * 43646 = 2 * 17 * 19.Find the first four consecutive integers to have four distinct primesfactors. What is the first of these numbers?"""
Problem 48
"""Project Euler Problem 48========================The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000."""
Problem 49
"""Project Euler Problem 49========================The arithmetic sequence, 1487, 4817, 8147, in which each of the termsincreases by 3330, is unusual in two ways: (i) each of the three terms areprime, and, (ii) each of the 4-digit numbers are permutations of oneanother.There are no arithmetic sequences made up of three 1-, 2-, or 3-digitprimes, exhibiting this property, but there is one other 4-digitincreasing sequence.What 12-digit number do you form by concatenating the three terms in thissequence?"""
Problem 50
"""Project Euler Problem 50========================The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13This is the longest sum of consecutive primes that adds to a prime belowone-hundred.The longest sum of consecutive primes below one-thousand that adds to aprime, contains 21 terms, and is equal to 953.Which prime, below one-million, can be written as the sum of the mostconsecutive primes?"""
Problem 51
"""Project Euler Problem 51========================By replacing the 1st digit of *57, it turns out that six of the possiblevalues: 157, 257, 457, 557, 757, and 857, are all prime.By replacing the 3rd and 4th digits of 56**3 with the same digit, this5-digit number is the first example having seven primes, yielding thefamily: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently56003, being the first member of this family, is the smallest prime withthis property.Find the smallest prime which, by replacing part of the number (notnecessarily adjacent digits) with the same digit, is part of an eightprime value family."""
Problem 52
"""Project Euler Problem 52========================It can be seen that the number, 125874, and its double, 251748, containexactly the same digits, but in a different order.Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x,contain the same digits."""
Problem 53
"""Project Euler Problem 53========================There are exactly ten ways of selecting three from five, 12345: 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345In combinatorics, we use the notation, nCr(5,3) = 10.In general,nCr(n,r) = n!/(r!(n-r)!), where r =< n, n! = n * (n1) * ... * 3 * 2 * 1,and 0! = 1.It is not until n = 23, that a value exceeds one-million: nCr(23,10) =1144066.How many values of nCr(n,r), for 1 =< n =< 100, are greater than one-million?"""
Problem 54
"""Project Euler Problem 54========================In the card game poker, a hand consists of five cards and are ranked, fromlowest to highest, in the following way: * High Card: Highest value card. * One Pair: Two cards of the same value. * Two Pairs: Two different pairs. * Three of a Kind: Three cards of the same value. * Straight: All cards are consecutive values. * Flush: All cards of the same suit. * Full House: Three of a kind and a pair. * Four of a Kind: Four cards of the same value. * Straight Flush: All cards are consecutive values of same suit. * Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.The cards are valued in the order:2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.If two players have the same ranked hands then the rank made up of thehighest value wins; for example, a pair of eights beats a pair of fives(see example 1 below). But if two ranks tie, for example, both playershave a pair of queens, then highest cards in each hand are compared (seeexample 4 below); if the highest cards tie then the next highest cards arecompared, and so on.Consider the following five hands dealt to two players: Hand Player 1 Player 2 Winner 1 5H 5C 6S 7S KD 2C 3S 8S 8D TD Player 2 Pair of Fives Pair of Eights 2 5D 8C 9S JS AC 2C 5C 7D 8S QH Player 1 Highest card Ace Highest card Queen 3 2D 9C AS AH AC 3D 6D 7D TD QD Player 2 Three Aces Flush with Diamonds 4D 6S 9H QH QC 3D 6D 7H QD QS 4 Pair of Queens Pair of Queens Player 1 Highest card Nine Highest card Seven 2H 2D 4C 4D 4S 3C 3D 3S 9S 9D 5 Full House Full House Player 1 With Three Fours with Three ThreesThe file poker.txt contains one-thousand random hands dealt to two players.Each line of the file contains ten cards (separated by a single space): thefirst five are Player 1's cards and the last five are Player 2's cards. Youcan assume that all hands are valid (no invalid characters or repeatedcards), each player's hand is in no specific order, and in each hand thereis a clear winner.How many hands does Player 1 win?"""
Problem 55
"""Project Euler Problem 55========================If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.Not all numbers produce palindromes so quickly. For example,349 + 943 = 1292,1292 + 2921 = 42134213 + 3124 = 7337That is, 349 took three iterations to arrive at a palindrome.Although no one has proved it yet, it is thought that some numbers, like196, never produce a palindrome. A number that never forms a palindromethrough the reverse and add process is called a Lychrel number. Due to thetheoretical nature of these numbers, and for the purpose of this problem,we shall assume that a number is Lychrel until proven otherwise. Inaddition you are given that for every number below ten-thousand, it willeither (i) become a palindrome in less than fifty iterations, or, (ii) noone, with all the computing power that exists, has managed so far to mapit to a palindrome. In fact, 10677 is the first number to be shown torequire over fifty iterations before producing a palindrome:4668731596684224866951378664 (53 iterations, 28-digits).Surprisingly, there are palindromic numbers that are themselves Lychrelnumbers; the first example is 4994.How many Lychrel numbers are there below ten-thousand?NOTE: Wording was modified slightly on 24 April 2007 to emphasise thetheoretical nature of Lychrel numbers."""
Problem 56
"""Project Euler Problem 56========================A googol (10^100) is a massive number: one followed by one-hundred zeros;100^100 is almost unimaginably large: one followed by two-hundred zeros.Despite their size, the sum of the digits in each number is only 1.Considering natural numbers of the form, a^b, where a, b < 100, what isthe maximum digital sum?"""
Problem 57
"""Project Euler Problem 57========================It is possible to show that the square root of two can be expressed as aninfinite continued fraction. 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...By expanding this for the first four iterations, we get:1 + 1/2 = 3/2 = 1.51 + 1/(2 + 1/2) = 7/5 = 1.41 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...The next three expansions are 99/70, 239/169, and 577/408, but the eighthexpansion, 1393/985, is the first example where the number of digits inthe numerator exceeds the number of digits in the denominator.In the first one-thousand expansions, how many fractions contain anumerator with more digits than denominator?"""
Problem 58
"""Project Euler Problem 58========================Starting with 1 and spiralling anticlockwise in the following way, asquare spiral with side length 7 is formed. 37 36 35 34 33 32 31 38 17 16 15 14 13 30 39 18 5 4 3 12 29 40 19 6 1 2 11 28 41 20 7 8 9 10 27 42 21 22 23 24 25 26 43 44 45 46 47 48 49It is interesting to note that the odd squares lie along the bottom rightdiagonal, but what is more interesting is that 8 out of the 13 numberslying along both diagonals are prime; that is, a ratio of 8/13 62%.If one complete new layer is wrapped around the spiral above, a squarespiral with side length 9 will be formed. If this process is continued,what is the side length of the square spiral for which the ratio of primesalong both diagonals first falls below 10%?"""
Problem 59
"""Project Euler Problem 59========================Each character on a computer is assigned a unique code and the preferredstandard is ASCII (American Standard Code for Information Interchange).For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.A modern encryption method is to take a text file, convert the bytes toASCII, then XOR each byte with a given value, taken from a secret key. Theadvantage with the XOR function is that using the same encryption key onthe cipher text, restores the plain text; for example, 65 XOR 42 = 107,then 107 XOR 42 = 65.For unbreakable encryption, the key is the same length as the plain textmessage, and the key is made up of random bytes. The user would keep theencrypted message and the encryption key in different locations, andwithout both "halves", it is impossible to decrypt the message.Unfortunately, this method is impractical for most users, so the modifiedmethod is to use a password as a key. If the password is shorter than themessage, which is likely, the key is repeated cyclically throughout themessage. The balance for this method is using a sufficiently long passwordkey for security, but short enough to be memorable.Your task has been made easy, as the encryption key consists of threelower case characters. Using cipher1.txt, a file containing the encryptedASCII codes, and the knowledge that the plain text must contain commonEnglish words, decrypt the message and find the sum of the ASCII valuesin the original text."""
Problem 60
"""Project Euler Problem 60========================The primes 3, 7, 109, and 673, are quite remarkable. By taking any twoprimes and concatenating them in any order the result will always beprime. For example, taking 7 and 109, both 7109 and 1097 are prime. Thesum of these four primes, 792, represents the lowest sum for a set of fourprimes with this property.Find the lowest sum for a set of five primes for which any two primesconcatenate to produce another prime."""
Problem 61
"""Project Euler Problem 61========================Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbersare all figurate (polygonal) numbers and are generated by the followingformulae:Triangle P[3,n]=n(n+1)/2 1, 3, 6, 10, 15, ...Square P[4,n]=n^2 1, 4, 9, 16, 25, ...Pentagonal P[5,n]=n(3n-1)/2 1, 5, 12, 22, 35, ...Hexagonal P[6,n]=n(2n-1) 1, 6, 15, 28, 45, ...Heptagonal P[7,n]=n(5n-3)/2 1, 7, 18, 34, 55, ...Octagonal P[8,n]=n(3n-2) 1, 8, 21, 40, 65, ...The ordered set of three 4-digit numbers: 8128, 2882, 8281, has threeinteresting properties. 1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first). 2. Each polygonal type: triangle (P[3,127]=8128), square (P[4,91]=8281), and pentagonal (P[5,44]=2882), is represented by a different number in the set. 3. This is the only set of 4-digit numbers with this property.Find the sum of the only ordered set of six cyclic 4-digit numbers forwhich each polygonal type: triangle, square, pentagonal, hexagonal,heptagonal, and octagonal, is represented by a different number in theset."""
Problem 62
"""Project Euler Problem 62========================The cube, 41063625 (345^3), can be permuted to produce two other cubes:56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is the smallestcube which has exactly three permutations of its digits which are alsocube.Find the smallest cube for which exactly five permutations of its digitsare cube."""
Problem 63
"""Project Euler Problem 63========================The 5-digit number, 16807=7^5, is also a fifth power. Similarly, the9-digit number, 134217728=8^9, is a ninth power.How many n-digit positive integers exist which are also an nth power?"""
Problem 64
"""Project Euler Problem 64========================All square roots are periodic when written as continued fractions and canbe written in the form:N = a[0] + 1 a[1] + 1 a[2] + 1 a[3] + ...For example, let us consider 23:23 = 4 + 23 -- 4 = 4 + 1 = 4 + 1 1 1 + 23 - 3 23--4 7If we continue we would get the following expansion:23 = 4 + 1 1 + 1 3 + 1 1 + 1 8 + ...The process can be summarised as follows:a[0] = 4, 1 = 23+4 = 1 + 23--3 23--4 7 7a[1] = 1, 7 = 7(23+3) = 3 + 23--3 23--3 14 2a[2] = 3, 2 = 2(23+3) = 1 + 23--4 23--3 14 7a[3] = 1, 7 = 7(23+4) = 8 + 23--4 23--4 7a[4] = 8, 1 = 23+4 = 1 + 23--3 23--4 7 7a[5] = 1, 7 = 7(23+3) = 3 + 23--3 23--3 14 2a[6] = 3, 2 = 2(23+3) = 1 + 23--4 23--3 14 7a[7] = 1, 7 = 7(23+4) = 8 + 23--4 23--4 7It can be seen that the sequence is repeating. For conciseness, we use thenotation 23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeatsindefinitely.The first ten continued fraction representations of (irrational) squareroots are:2=[1;(2)], period=13=[1;(1,2)], period=25=[2;(4)], period=16=[2;(2,4)], period=27=[2;(1,1,1,4)], period=48=[2;(1,4)], period=210=[3;(6)], period=111=[3;(3,6)], period=212= [3;(2,6)], period=213=[3;(1,1,1,1,6)], period=5Exactly four continued fractions, for N 13, have an odd period.How many continued fractions for N 10000 have an odd period?"""
Problem 65
"""Project Euler Problem 65========================The square root of 2 can be written as an infinite continued fraction.2 = 1 + 1 2 + 1 2 + 1 2 + 1 2 + ...The infinite continued fraction can be written, 2 = [1;(2)], (2) indicatesthat 2 repeats ad infinitum. In a similar way, 23 = [4;(1,3,1,8)].It turns out that the sequence of partial values of continued fractionsfor square roots provide the best rational approximations. Let us considerthe convergents for 2.1 + 1 = 3/2 21 + 1 = 7/5 2 + 1 21 + 1 = 17/12 2 + 1 2 + 1 21 + 1 = 41/29 2 + 1 2 + 1 2 + 1 2Hence the sequence of the first ten convergents for 2 are:1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378,...What is most surprising is that the important mathematical constant,e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].The first ten terms in the sequence of convergents for e are:2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.Find the sum of digits in the numerator of the 100th convergent of thecontinued fraction for e."""
Problem 66
"""Project Euler Problem 66========================Consider quadratic Diophantine equations of the form: x^2 - Dy^2 = 1For example, when D=13, the minimal solution in x is 649^2 - 13 * 180^2 =1.It can be assumed that there are no solutions in positive integers when Dis square.By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain thefollowing:3^2 - 2 * 2^2 = 12^2 - 3 * 1^2 = 19^2 - 5 * 4^2 = 15^2 - 6 * 2^2 = 18^2 - 7 * 3^2 = 1Hence, by considering minimal solutions in x for D 7, the largest x isobtained when D=5.Find the value of D 1000 in minimal solutions of x for which the largestvalue of x is obtained."""
Problem 67
"""Project Euler Problem 67========================By starting at the top of the triangle below and moving to adjacentnumbers on the row below, the maximum total from top to bottom is 23. 3 7 4 2 4 6 8 5 9 3That is, 3 + 7 + 4 + 9 = 23.Find the maximum total from top to bottom in triangle.txt, a 15K text filecontaining a triangle with one-hundred rows.NOTE: This is a much more difficult version of Problem 18. It is notpossible to try every route to solve this problem, as there are 2^99altogether! If you could check one trillion (10^12) routes every second itwould take over twenty billion years to check them all. There is anefficient algorithm to solve it. ;o)"""
Problem 68
"""Project Euler Problem 68========================Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6,and each line adding to nine.Working clockwise, and starting from the group of three with thenumerically lowest external node (4,3,2 in this example), each solutioncan be described uniquely. For example, the above solution can bedescribed by the set: 4,3,2; 6,2,1; 5,1,3.It is possible to complete the ring with four different totals: 9, 10, 11,and 12. There are eight solutions in total. Total Solution Set 9 4,2,3; 5,3,1; 6,1,2 9 4,3,2; 6,2,1; 5,1,3 10 2,3,5; 4,5,1; 6,1,3 10 2,5,3; 6,3,1; 4,1,5 11 1,4,6; 3,6,2; 5,2,4 11 1,6,4; 5,4,2; 3,2,6 12 1,5,6; 2,6,4; 3,4,5 12 1,6,5; 3,5,4; 2,4,6By concatenating each group it is possible to form 9-digit strings; themaximum string for a 3-gon ring is 432621513.Using the numbers 1 to 10, and depending on arrangements, it is possibleto form 16- and 17-digit strings. What is the maximum 16-digit string fora "magic" 5-gon ring?"""
Problem 69
"""Project Euler Problem 69========================Euler's Totient function, f(n) [sometimes called the phi function], isused to determine the number of numbers less than n which are relativelyprime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nineand relatively prime to nine, f(9)=6.+------------------------------------------+| n | Relatively Prime | f(n) | n/f(n) ||----+------------------+------+-----------|| 2 | 1 | 1 | 2 ||----+------------------+------+-----------|| 3 | 1,2 | 2 | 1.5 ||----+------------------+------+-----------|| 4 | 1,3 | 2 | 2 ||----+------------------+------+-----------|| 5 | 1,2,3,4 | 4 | 1.25 ||----+------------------+------+-----------|| 6 | 1,5 | 2 | 3 ||----+------------------+------+-----------|| 7 | 1,2,3,4,5,6 | 6 | 1.1666... ||----+------------------+------+-----------|| 8 | 1,3,5,7 | 4 | 2 ||----+------------------+------+-----------|| 9 | 1,2,4,5,7,8 | 6 | 1.5 ||----+------------------+------+-----------|| 10 | 1,3,7,9 | 4 | 2.5 |+------------------------------------------+It can be seen that n=6 produces a maximum n/f(n) for n 10.Find the value of n 1,000,000 for which n/f(n) is a maximum."""
Problem 70
"""Project Euler Problem 70========================Euler's Totient function, f(n) [sometimes called the phi function], isused to determine the number of positive numbers less than or equal to nwhich are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, areall less than nine and relatively prime to nine, f(9)=6.The number 1 is considered to be relatively prime to every positivenumber, so f(1)=1.Interestingly, f(87109)=79180, and it can be seen that 87109 is apermutation of 79180.Find the value of n, 1 < n < 10^7, for which f(n) is a permutation of nand the ratio n/f(n) produces a minimum."""
Problem 71
"""Project Euler Problem 71========================Consider the fraction, n/d, where n and d are positive integers. If n < dand HCF(n,d)=1, it is called a reduced proper fraction.If we list the set of reduced proper fractions for d 8 in ascending orderof size, we get:1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8It can be seen that 2/5 is the fraction immediately to the left of 3/7.By listing the set of reduced proper fractions for d 1,000,000 inascending order of size, find the numerator of the fraction immediately tothe left of 3/7."""
Problem 72
"""Project Euler Problem 72========================Consider the fraction, n/d, where n and d are positive integers. If n < dand HCF(n,d)=1, it is called a reduced proper fraction.If we list the set of reduced proper fractions for d 8 in ascending orderof size, we get:1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8It can be seen that there are 21 elements in this set.How many elements would be contained in the set of reduced properfractions for d 1,000,000?"""
Problem 73
"""Project Euler Problem 73========================Consider the fraction, n/d, where n and d are positive integers. If n < dand HCF(n,d)=1, it is called a reduced proper fraction.If we list the set of reduced proper fractions for d 8 in ascending orderof size, we get:1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8It can be seen that there are 3 fractions between 1/3 and 1/2.How many fractions lie between 1/3 and 1/2 in the sorted set of reducedproper fractions for d 10,000?"""
Problem 74
"""Project Euler Problem 74========================The number 145 is well known for the property that the sum of thefactorial of its digits is equal to 145:1! + 4! + 5! = 1 + 24 + 120 = 145Perhaps less well known is 169, in that it produces the longest chain ofnumbers that link back to 169; it turns out that there are only three suchloops that exist:169 363601 1454 169871 45361 871872 45362 872It is not difficult to prove that EVERY starting number will eventuallyget stuck in a loop. For example,69 363600 1454 169 363601 ( 1454)78 45360 871 45361 ( 871)540 145 ( 145)Starting with 69 produces a chain of five non-repeating terms, but thelongest non-repeating chain with a starting number below one million issixty terms.How many chains, with a starting number below one million, contain exactlysixty non-repeating terms?"""
Problem 75
"""Project Euler Problem 75========================It turns out that 12 cm is the smallest length of wire can be bent to forma right angle triangle in exactly one way, but there are many moreexamples.12 cm: (3,4,5)24 cm: (6,8,10)30 cm: (5,12,13)36 cm: (9,12,15)40 cm: (8,15,17)48 cm: (12,16,20)In contrast, some lengths of wire, like 20 cm, cannot be bent to form aright angle triangle, and other lengths allow more than one solution to befound; for example, using 120 cm it is possible to form exactly threedifferent right angle triangles.120 cm: (30,40,50), (20,48,52), (24,45,51)Given that L is the length of the wire, for how many values of L 2,000,000can exactly one right angle triangle be formed?"""
Problem 76
"""Project Euler Problem 76========================It is possible to write five as a sum in exactly six different ways:4 + 13 + 23 + 1 + 12 + 2 + 12 + 1 + 1 + 11 + 1 + 1 + 1 + 1How many different ways can one hundred be written as a sum of at leasttwo positive integers?"""
Problem 77
"""Project Euler Problem 77========================It is possible to write ten as the sum of primes in exactly five differentways:7 + 35 + 55 + 3 + 23 + 3 + 2 + 22 + 2 + 2 + 2 + 2What is the first value which can be written as the sum of primes in overfive thousand different ways?"""
Problem 78
"""Project Euler Problem 78========================Let p(n) represent the number of different ways in which n coins can beseparated into piles. For example, five coins can separated into piles inexactly seven different ways, so p(5)=7. OOOOO OOOO O OOO OO OOO O O OO OO O OO O O O O O O O OFind the least value of n for which p(n) is divisible by one million."""
Problem 79
"""Project Euler Problem 79========================A common security method used for online banking is to ask the user forthree random characters from a passcode. For example, if the passcode was531278, they may asked for the 2nd, 3rd, and 5th characters; the expectedreply would be: 317.The text file keylog.txt contains fifty successful login attempts.Given that the three characters are always asked for in order, analyse thefile so as to determine the shortest possible secret passcode of unknownlength."""
Problem 80
"""Project Euler Problem 80========================It is well known that if the square root of a natural number is not aninteger, then it is irrational. The decimal expansion of such square rootsis infinite without any repeating pattern at all.The square root of two is 1.41421356237309504880..., and the digital sumof the first one hundred decimal digits is 475.For the first one hundred natural numbers, find the total of the digitalsums of the first one hundred decimal digits for all the irrational squareroots."""
Problem 81
"""Project Euler Problem 81========================In the 5 by 5 matrix below, the minimal path sum from the top left to thebottom right, by only moving to the right and down, is indicated in redand is equal to 2427. 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331Find the minimal path sum, in matrix.txt, a 31K text file containing a 80 by80 matrix, from the top left to the bottom right by only moving right and down."""
Problem 82
"""Project Euler Problem 82======================== NOTE: This problem is a more challenging version of Problem 81.The minimal path sum in the 5 by 5 matrix below, by starting in any cellin the left column and finishing in any cell in the right column, and onlymoving up, down, and right, is indicated in red; the sum is equal to 994. 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331Find the minimal path sum, in matrix.txt, a 31K text file containing a 80 by80 matrix, from the left column to the right column."""
Problem 83
"""Project Euler Problem 83========================NOTE: This problem is a significantly more challenging version of Problem 81.In the 5 by 5 matrix below, the minimal path sum from the top left to thebottom right, by moving left, right, up, and down, is indicated in red andis equal to 2297. 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331Find the minimal path sum, in matrix.txt, a 31K text file containing a 80 by80 matrix, from the top left to the bottom right by moving left, right, up,and down."""
Problem 84
"""Project Euler Problem 84========================In the game, Monopoly, the standard board is set up in the following way: GO A1 CC1 A2 T1 R1 B1 CH1 B2 B3 JAIL H2 C1 T2 U1 H1 C2 CH3 C3 R4 R2 G3 D1 CC3 CC2 G2 D2 G1 D3 G2J F3 U2 F2 F1 R3 E3 E2 CH2 E1 FPA player starts on the GO square and adds the scores on two 6-sided diceto determine the number of squares they advance in a clockwise direction.Without any further rules we would expect to visit each square with equalprobability: 2.5%. However, landing on G2J (Go To Jail), CC (communitychest), and CH (chance) changes this distribution.In addition to G2J, and one card from each of CC and CH, that orders theplayer to go to directly jail, if a player rolls three consecutivedoubles, they do not advance the result of their 3rd roll. Instead theyproceed directly to jail.At the beginning of the game, the CC and CH cards are shuffled. When aplayer lands on CC or CH they take a card from the top of the respectivepile and, after following the instructions, it is returned to the bottomof the pile. There are sixteen cards in each pile, but for the purpose ofthis problem we are only concerned with cards that order a movement; anyinstruction not concerned with movement will be ignored and the playerwill remain on the CC/CH square. * Community Chest (2/16 cards): 1. Advance to GO 2. Go to JAIL * Chance (10/16 cards): 1. Advance to GO 2. Go to JAIL 3. Go to C1 4. Go to E3 5. Go to H2 6. Go to R1 7. Go to next R (railway company) 8. Go to next R 9. Go to next U (utility company) 10. Go back 3 squares.The heart of this problem concerns the likelihood of visiting a particularsquare. That is, the probability of finishing at that square after a roll.For this reason it should be clear that, with the exception of G2J forwhich the probability of finishing on it is zero, the CH squares will havethe lowest probabilities, as 5/8 request a movement to another square, andit is the final square that the player finishes at on each roll that weare interested in. We shall make no distinction between "Just Visiting"and being sent to JAIL, and we shall also ignore the rule about requiringa double to "get out of jail", assuming that they pay to get out on theirnext turn.By starting at GO and numbering the squares sequentially from 00 to 39 wecan concatenate these two-digit numbers to produce strings that correspondwith sets of squares.Statistically it can be shown that the three most popular squares, inorder, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO(3.09%) = Square 00. So these three most popular squares can be listedwith the six-digit modal string: 102400.If, instead of using two 6-sided dice, two 4-sided dice are used, find thesix-digit modal string."""
Problem 85
"""Project Euler Problem 85========================By counting carefully it can be seen that a rectangular grid measuring 3by 2 contains eighteen rectangles:Although there exists no rectangular grid that contains exactly twomillion rectangles, find the area of the grid with the nearest solution."""
Problem 86
"""Project Euler Problem 86========================A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3,and a fly, F, sits in the opposite corner. By travelling on the surfacesof the room the shortest "straight line" distance from S to F is 10 andthe path is shown on the diagram.However, there are up to three "shortest" path candidates for any givencuboid and the shortest route is not always integer.By considering all cuboid rooms up to a maximum size of M by M by M, thereare exactly 2060 cuboids for which the shortest distance is integer whenM=100, and this is the least value of M for which the number of solutionsfirst exceeds two thousand; the number of solutions is 1975 when M=99.Find the least value of M such that the number of solutions first exceedsone million."""
Problem 87
"""Project Euler Problem 87========================The smallest number expressible as the sum of a prime square, prime cube,and prime fourth power is 28. In fact, there are exactly four numbersbelow fifty that can be expressed in such a way:28 = 2^2 + 2^3 + 2^433 = 3^2 + 2^3 + 2^449 = 5^2 + 2^3 + 2^447 = 2^2 + 3^3 + 2^4How many numbers below fifty million can be expressed as the sum of aprime square, prime cube, and prime fourth power?"""
Problem 88
"""Project Euler Problem 88========================A natural number, N, that can be written as the sum and product of a givenset of at least two natural numbers, {a[1], a[2], ... , a[k]} is called aproduct-sum number: N = a[1] + a[2] + ... + a[k] = a[1] * a[2] * ... *a[k].For example, 6 = 1 + 2 + 3 = 1 * 2 * 3.For a given set of size, k, we shall call the smallest N with thisproperty a minimal product-sum number. The minimal product-sum numbers forsets of size, k = 2, 3, 4, 5, and 6 are as follows.k=2: 4 = 2 * 2 = 2 + 2k=3: 6 = 1 * 2 * 3 = 1 + 2 + 3k=4: 8 = 1 * 1 * 2 * 4 = 1 + 1 + 2 + 4k=5: 8 = 1 * 1 * 2 * 2 * 2 = 1 + 1 + 2 + 2 + 2k=6: 12 = 1 * 1 * 1 * 1 * 2 * 6 = 1 + 1 + 1 + 1 + 2 + 6Hence for 2k6, the sum of all the minimal product-sum numbers is 4+6+8+12= 30; note that 8 is only counted once in the sum.In fact, as the complete set of minimal product-sum numbers for 2k12 is{4, 6, 8, 12, 15, 16}, the sum is 61.What is the sum of all the minimal product-sum numbers for 2k12000?"""
Problem 89
"""Project Euler Problem 89========================The rules for writing Roman numerals allow for many ways of writing eachnumber. However, there is always a "best" way of writing a particular number.For example, the following represent all of the legitimate ways of writingthe number sixteen:IIIIIIIIIIIIIIIIVIIIIIIIIIIIVVIIIIIIXIIIIIIVVVIXVIThe last example being considered the most efficient, as it uses the leastnumber of numerals.The 11K text file roman.txt contains one thousand numbers written in valid,but not necessarily minimal, Roman numerals; that is, they are arranged indescending units and obey the subtractive pair rule (see FAQ for thedefinitive rules for this problem).Find the number of characters saved by writing each of these in theirminimal form.Note: You can assume that all the Roman numerals in the file contain nomore than four consecutive identical units.FAQ Link: http://projecteuler.net/about=roman_numerals"""
Problem 90
"""Project Euler Problem 90========================Each of the six faces on a cube has a different digit (0 to 9) written onit; the same is done to a second cube. By placing the two cubesside-by-side in different positions we can form a variety of 2-digitnumbers.For example, the square number 64 could be formed:In fact, by carefully choosing the digits on both cubes it is possible todisplay all of the square numbers below one-hundred: 01, 04, 09, 16, 25,36, 49, 64, and 81.For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9}on one cube and {1, 2, 3, 4, 8, 9} on the other cube.However, for this problem we shall allow the 6 or 9 to be turnedupside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3,4, 6, 7} allows for all nine square numbers to be displayed; otherwise itwould be impossible to obtain 09.In determining a distinct arrangement we are interested in the digits oneach cube, not the order.{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}But because we are allowing 6 and 9 to be reversed, the two distinct setsin the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9}for the purpose of forming 2-digit numbers.How many distinct arrangements of the two cubes allow for all of thesquare numbers to be displayed?"""
Problem 91
"""Project Euler Problem 91========================The points P (x[1], y[1]) and Q (x[2], y[2]) are plotted at integerco-ordinates and are joined to the origin, O(0,0), to form DOPQ.There are exactly fourteen triangles containing a right angle that can beformed when each co-ordinate lies between 0 and 2 inclusive; that is,0 x[1], y[1], x[2], y[2] 2.Given that 0 x[1], y[1], x[2], y[2] 50, how many right triangles can beformed?"""
Problem 92
"""Project Euler Problem 92========================A number chain is created by continuously adding the square of the digitsin a number to form a new number until it has been seen before.For example,44 32 13 10 1 185 89 145 42 20 4 16 37 58 89Therefore any chain that arrives at 1 or 89 will become stuck in anendless loop. What is most amazing is that EVERY starting number willeventually arrive at 1 or 89.How many starting numbers below ten million will arrive at 89?"""
Problem 93
"""Project Euler Problem 93========================By using each of the digits from the set, {1, 2, 3, 4}, exactly once, andmaking use of the four arithmetic operations (+, , *, /) andbrackets/parentheses, it is possible to form different positive integertargets.For example,8 = (4 * (1 + 3)) / 214 = 4 * (3 + 1 / 2)19 = 4 * (2 + 3) 136 = 3 * 4 * (2 + 1)Note that concatenations of the digits, like 12 + 34, are not allowed.Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one differenttarget numbers of which 36 is the maximum, and each of the numbers 1 to 28can be obtained before encountering the first non-expressible number.Find the set of four distinct digits, a < b < c < d, for which the longestset of consecutive positive integers, 1 to n, can be obtained, giving youranswer as a string: abcd."""
Problem 94
"""Project Euler Problem 94========================It is easily proved that no equilateral triangle exists with integrallength sides and integral area. However, the almost equilateral triangle5-5-6 has an area of 12 square units.We shall define an almost equilateral triangle to be a triangle for whichtwo sides are equal and the third differs by no more than one unit.Find the sum of the perimeters of every almost equilateral triangle withintegral side lengths and area and whose perimeters do not exceed onebillion (1,000,000,000)."""
Problem 95
"""Project Euler Problem 95========================The proper divisors of a number are all the divisors excluding the numberitself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. Asthe sum of these divisors is equal to 28, we call it a perfect number.Interestingly the sum of the proper divisors of 220 is 284 and the sum ofthe proper divisors of 284 is 220, forming a chain of two numbers. Forthis reason, 220 and 284 are called an amicable pair.Perhaps less well known are longer chains. For example, starting with12496, we form an amicable chain of five numbers: 12496 14288 15472 14536 14264 ( 12496 ...)Find the smallest member of the longest amicable chain with no elementexceeding one million."""
Problem 96
"""Project Euler Problem 96========================Su Doku (Japanese meaning number place) is the name given to a popularpuzzle concept. Its origin is unclear, but credit must be attributed toLeonhard Euler who invented a similar, and much more difficult, puzzleidea called Latin Squares. The objective of Su Doku puzzles, however, isto replace the blanks (or zeros) in a 9 by 9 grid in such that each row,column, and 3 by 3 box contains each of the digits 1 to 9. Below is anexample of a typical starting puzzle grid and its solution grid. +-----------------------+ +-----------------------+ | 0 0 3 | 0 2 0 | 6 0 0 | | 4 8 3 | 9 2 1 | 6 5 7 | | 9 0 0 | 3 0 5 | 0 0 1 | | 9 6 7 | 3 4 5 | 8 2 1 | | 0 0 1 | 8 0 6 | 4 0 0 | | 2 5 1 | 8 7 6 | 4 9 3 | |-------+-------+-------| |-------+-------+-------| | 0 0 8 | 1 0 2 | 9 0 0 | | 5 4 8 | 1 3 2 | 9 7 6 | | 7 0 0 | 0 0 0 | 0 0 8 | | 7 2 9 | 5 6 4 | 1 3 8 | | 0 0 6 | 7 0 8 | 2 0 0 | | 1 3 6 | 7 9 8 | 2 4 5 | |-------+-------+-------| |-------+-------+-------| | 0 0 2 | 6 0 9 | 5 0 0 | | 3 7 2 | 6 8 9 | 5 1 4 | | 8 0 0 | 2 0 3 | 0 0 9 | | 8 1 4 | 2 5 3 | 7 6 9 | | 0 0 5 | 0 1 0 | 3 0 0 | | 6 9 5 | 4 1 7 | 3 8 2 | +-----------------------+ +-----------------------+A well constructed Su Doku puzzle has a unique solution and can be solvedby logic, although it may be necessary to employ "guess and test" methodsin order to eliminate options (there is much contested opinion over this).The complexity of the search determines the difficulty of the puzzle; theexample above is considered easy because it can be solved by straightforward direct deduction.The 6K text file sudoku.txt contains fifty different Su Doku puzzles rangingin difficulty, but all with unique solutions (the first puzzle in the file isthe example above).By solving all fifty puzzles find the sum of the 3-digit numbers found inthe top left corner of each solution grid; for example, 483 is the 3-digitnumber found in the top left corner of the solution grid above."""
Problem 97
"""Project Euler Problem 97========================The first known prime found to exceed one million digits was discovered in1999, and is a Mersenne prime of the form 2^69725931; it contains exactly2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p1,have been found which contain more digits.However, in 2004 there was found a massive non-Mersenne prime whichcontains 2,357,207 digits: 28433 * 2^7830457+1.Find the last ten digits of this prime number."""
Problem 98
"""Project Euler Problem 98========================By replacing each of the letters in the word CARE with 1, 2, 9, and 6respectively, we form a square number: 1296 = 36^2. What is remarkable isthat, by using the same digital substitutions, the anagram, RACE, alsoforms a square number: 9216 = 96^2. We shall call CARE (and RACE) a squareanagram word pair and specify further that leading zeroes are notpermitted, neither may a different letter have the same digital value asanother letter.Using words.txt, a 16K text file containing nearly two-thousand common Englishwords, find all the square anagram word pairs (a palindromic word is NOTconsidered to be an anagram of itself).What is the largest square number formed by any member of such a pair?NOTE: All anagrams formed must be contained in the given text file."""
Problem 99
"""Project Euler Problem 99========================Comparing two numbers written in index form like 2^11 and 3^7 is notdifficult, as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.However, confirming that 632382^518061 > 519432^525806 would be much moredifficult, as both numbers contain over three million digits.Using base_exp.txt, a 22K text file containing one thousand lines with abase/exponent pair on each line, determine which line number has thegreatest numerical value.NOTE: The first two lines in the file represent the numbers in the examplegiven above."""
Problem 100
"""Project Euler Problem 100=========================If a box contains twenty-one coloured discs, composed of fifteen bluediscs and six red discs, and two discs were taken at random, it can beseen that the probability of taking two blue discs, P(BB) = (15/21) *(14/20) = 1/2.The next such arrangement, for which there is exactly 50% chance of takingtwo blue discs at random, is a box containing eighty-five blue discs andthirty-five red discs.By finding the first arrangement to contain over 10^12 = 1,000,000,000,000discs in total, determine the number of blue discs that the box wouldcontain."""
Problem 101
"""Project Euler Problem 101=========================If we are presented with the first k terms of a sequence it is impossibleto say with certainty the value of the next term, as there are infinitelymany polynomial functions that can model the sequence.As an example, let us consider the sequence of cube numbers. This isdefined by the generating function, u[n] = n^3: 1, 8, 27, 64, 125, 216,...Suppose we were only given the first two terms of this sequence. Workingon the principle that "simple is best" we should assume a linearrelationship and predict the next term to be 15 (common difference 7).Even if we were presented with the first three terms, by the sameprinciple of simplicity, a quadratic relationship should be assumed.We shall define OP(k, n) to be the nth term of the optimum polynomialgenerating function for the first k terms of a sequence. It should beclear that OP(k, n) will accurately generate the terms of the sequence forn k, and potentially the first incorrect term (FIT) will be OP(k, k+1); inwhich case we shall call it a bad OP (BOP).As a basis, if we were only given the first term of sequence, it would bemost sensible to assume constancy; that is, for n 2, OP(1, n) = u[1].Hence we obtain the following OPs for the cubic sequence:OP(1, n) = 1 1, 1, 1, 1, ...OP(2, n) = 7n6 1, 8, 15, ...OP(3, n) = 6n^211n+6 1, 8, 27, 58, ...OP(4, n) = n^3 1, 8, 27, 64, 125, ...Clearly no BOPs exist for k 4.By considering the sum of FITs generated by the BOPs (indicated in redabove), we obtain 1 + 15 + 58 = 74.Consider the following tenth degree polynomial generating function: u[n] = 1 n + n^2 n^3 + n^4 n^5 + n^6 n^7 + n^8 n^9 + n^10Find the sum of FITs for the BOPs."""
Problem 102
"""Project Euler Problem 102=========================Three distinct points are plotted at random on a Cartesian plane, forwhich -1000 x, y 1000, such that a triangle is formed.Consider the following two triangles: A(-340,495), B(-153,-910), C(835,-947) X(-175,41), Y(-421,-714), Z(574,-645)It can be verified that triangle ABC contains the origin, whereas triangleXYZ does not.Using triangles.txt, a 27K text file containing the co-ordinates of onethousand "random" triangles, find the number of triangles for which theinterior contains the origin.NOTE: The first two examples in the file represent the triangles in theexample given above."""
Problem 103
"""Project Euler Problem 103=========================Let S(A) represent the sum of elements in set A of size n. We shall callit a special sum set if for any two non-empty disjoint subsets, B and C,the following properties are true: 1. S(B) S(C); that is, sums of subsets cannot be equal. 2. If B contains more elements than C then S(B) > S(C).If S(A) is minimised for a given n, we shall call it an optimum specialsum set. The first five optimum special sum sets are given below.n = 1: {1}n = 2: {1, 2}n = 3: {2, 3, 4}n = 4: {3, 5, 6, 7}n = 5: {6, 9, 11, 12, 13}It seems that for a given optimum set, A = {a[1], a[2], ... , a[n]}, thenext optimum set is of the form B = {b, a[1]+b, a[2]+b, ... ,a[n]+b},where b is the "middle" element on the previous row.By applying this "rule" we would expect the optimum set for n = 6 to be A= {11, 17, 20, 22, 23, 24}, with S(A) = 117. However, this is not theoptimum set, as we have merely applied an algorithm to provide a nearoptimum set. The optimum set for n = 6 is A = {11, 18, 19, 20, 22, 25},with S(A) = 115 and corresponding set string: 111819202225.Given that A is an optimum special sum set for n = 7, find its set string.NOTE: This problem is related to problems 105 and 106."""
Problem 104
"""Project Euler Problem 104=========================The Fibonacci sequence is defined by the recurrence relation: F[n] = F[n[1]] + F[n[2]], where F[1] = 1 and F[2] = 1.It turns out that F[541], which contains 113 digits, is the firstFibonacci number for which the last nine digits are 1-9 pandigital(contain all the digits 1 to 9, but not necessarily in order). AndF[2749], which contains 575 digits, is the first Fibonacci number forwhich the first nine digits are 1-9 pandigital.Given that F[k] is the first Fibonacci number for which the first ninedigits AND the last nine digits are 1-9 pandigital, find k."""
Problem 105
"""Project Euler Problem 105=========================Let S(A) represent the sum of elements in set A of size n. We shall callit a special sum set if for any two non-empty disjoint subsets, B and C,the following properties are true: 1. S(B) S(C); that is, sums of subsets cannot be equal. 2. If B contains more elements than C then S(B) > S(C).For example, {81, 88, 75, 42, 87, 84, 86, 65} is not a special sum setbecause 65 + 87 + 88 = 75 + 81 + 84, whereas {157, 150, 164, 119, 79, 159,161, 139, 158} satisfies both rules for all possible subset paircombinations and S(A) = 1286.Using sets.txt, a 4K text file with one-hundred sets containing seven totwelve elements (the two examples given above are the first two sets in thefile), identify all the special sum sets, A[1], A[2], ..., A[k], and find thevalue of S(A[1]) + S(A[2]) + ... + S(A[k]).NOTE: This problem is related to problems 103 and 106."""
Problem 106
"""Project Euler Problem 106=========================Let S(A) represent the sum of elements in set A of size n. We shall callit a special sum set if for any two non-empty disjoint subsets, B and C,the following properties are true: 1. S(B) S(C); that is, sums of subsets cannot be equal. 2. If B contains more elements than C then S(B) > S(C).For this problem we shall assume that a given set contains n strictlyincreasing elements and it already satisfies the second rule.Surprisingly, out of the 25 possible subset pairs that can be obtainedfrom a set for which n = 4, only 1 of these pairs need to be tested forequality (first rule). Similarly, when n = 7, only 70 out of the 966subset pairs need to be tested.For n = 12, how many of the 261625 subset pairs that can be obtained needto be tested for equality?NOTE: This problem is related to problems 103 and 105."""
Problem 107
"""Project Euler Problem 107=========================The following undirected network consists of seven vertices and twelveedges with a total weight of 243.The same network can be represented by the matrix below. +-----------------------------------------+ | | A | B | C | D | E | F | G | |------+----+----+----+----+----+----+----| | A | - | 16 | 12 | 21 | - | - | - | |------+----+----+----+----+----+----+----| | B | 16 | - | - | 17 | 20 | - | - | |------+----+----+----+----+----+----+----| | C | 12 | - | - | 28 | - | 31 | - | |------+----+----+----+----+----+----+----| | D | 21 | 17 | 28 | - | 18 | 19 | 23 | |------+----+----+----+----+----+----+----| | E | - | 20 | - | 18 | - | - | 11 | |------+----+----+----+----+----+----+----| | F | - | - | 31 | 19 | - | - | 27 | |------+----+----+----+----+----+----+----| | G | - | - | - | 23 | 11 | 27 | - | +-----------------------------------------+However, it is possible to optimise the network by removing some edges andstill ensure that all points on the network remain connected. The networkwhich achieves the maximum saving is shown below. It has a weight of 93,representing a saving of 243 93 = 150 from the original network.Using network.txt, a 6K text file containing a network with forty vertices,and given in matrix form, find the maximum saving which can be achieved byremoving redundant edges whilst ensuring that the network remains connected."""
Problem 108
"""Project Euler Problem 108=========================In the following equation x, y, and n are positive integers. 1 + 1 = 1 x y nFor n = 4 there are exactly three distinct solutions: 1 + 1 = 1 5 20 4 1 + 1 = 1 6 12 4 1 + 1 = 1 8 8 4What is the least value of n for which the number of distinct solutionsexceeds one-thousand?NOTE: This problem is an easier version of problem 110; it is stronglyadvised that you solve this one first."""
Problem 109
"""Project Euler Problem 109=========================In the game of darts a player throws three darts at a target board whichis split into twenty equal sized sections numbered one to twenty.The score of a dart is determined by the number of the region that thedart lands in. A dart landing outside the red/green outer ring scoreszero. The black and cream regions inside this ring represent singlescores. However, the red/green outer ring and middle ring score double andtreble scores respectively.At the centre of the board are two concentric circles called the bullregion, or bulls-eye. The outer bull is worth 25 points and the inner bullis a double, worth 50 points.There are many variations of rules but in the most popular game theplayers will begin with a score 301 or 501 and the first player to reducetheir running total to zero is a winner. However, it is normal to play a"doubles out" system, which means that the player must land a double(including the double bulls-eye at the centre of the board) on their finaldart to win; any other dart that would reduce their running total to oneor lower means the score for that set of three darts is "bust".When a player is able to finish on their current score it is called a"checkout" and the highest checkout is 170: T20 T20 D25 (two treble 20sand double bull).There are exactly eleven distinct ways to checkout on a score of 6: +--------+ |D3| | | |--+--+--| |D1|D2| | |--+--+--| |S2|D2| | |--+--+--| |D2|D1| | |--+--+--| |S4|D1| | |--+--+--| |S1|S1|D2| |--+--+--| |S1|T1|D1| |--+--+--| |S1|S3|D1| |--+--+--| |D1|D1|D1| |--+--+--| |D1|S2|D1| |--+--+--| |S2|S2|D1| +--------+Note that D1 D2 is considered different to D2 D1 as they finish ondifferent doubles. However, the combination S1 T1 D1 is considered thesame as T1 S1 D1.In addition we shall not include misses in considering combinations; forexample, D3 is the same as 0 D3 and 0 0 D3.Incredibly there are 42336 distinct ways of checking out in total.How many distinct ways can a player checkout with a score less than 100?"""
Problem 110
"""Project Euler Problem 110=========================In the following equation x, y, and n are positive integers. 1 + 1 = 1 x y nIt can be verified that when n = 1260 there are 113 distinct solutions andthis is the least value of n for which the total number of distinctsolutions exceeds one hundred.What is the least value of n for which the number of distinct solutionsexceeds four million?NOTE: This problem is a much more difficult version of problem 108 andas it is well beyond the limitations of a brute force approach it requiresa clever implementation."""
Problem 111
"""Project Euler Problem 111=========================Considering 4-digit primes containing repeated digits it is clear thatthey cannot all be the same: 1111 is divisible by 11, 2222 is divisible by22, and so on. But there are nine 4-digit primes containing three ones: 1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111We shall say that M(n, d) represents the maximum number of repeated digitsfor an n-digit prime where d is the repeated digit, N(n, d) represents thenumber of such primes, and S(n, d) represents the sum of these primes.So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digitprime where one is the repeated digit, there are N(4, 1) = 9 such primes,and the sum of these primes is S(4, 1) = 22275. It turns out that for d =0, it is only possible to have M(4, 0) = 2 repeated digits, but there areN(4, 0) = 13 such cases.In the same way we obtain the following results for 4-digit primes. +----------------------------------------+ | Digit, d | M(4, d) | N(4, d) | S(4, d) | |----------+---------+---------+---------| | 0 | 2 | 13 | 67061 | |----------+---------+---------+---------| | 1 | 3 | 9 | 22275 | |----------+---------+---------+---------| | 2 | 3 | 1 | 2221 | |----------+---------+---------+---------| | 3 | 3 | 12 | 46214 | |----------+---------+---------+---------| | 4 | 3 | 2 | 8888 | |----------+---------+---------+---------| | 5 | 3 | 1 | 5557 | |----------+---------+---------+---------| | 6 | 3 | 1 | 6661 | |----------+---------+---------+---------| | 7 | 3 | 9 | 57863 | |----------+---------+---------+---------| | 8 | 3 | 1 | 8887 | |----------+---------+---------+---------| | 9 | 3 | 7 | 48073 | +----------------------------------------+For d = 0 to 9, the sum of all S(4, d) is 273700.Find the sum of all S(10, d)."""
Problem 112
"""Project Euler Problem 112=========================Working from left-to-right if no digit is exceeded by the digit to itsleft it is called an increasing number; for example, 134468.Similarly if no digit is exceeded by the digit to its right it is called adecreasing number; for example, 66420.We shall call a positive integer that is neither increasing nor decreasinga "bouncy" number; for example, 155349.Clearly there cannot be any bouncy numbers below one-hundred, but justover half of the numbers below one-thousand (525) are bouncy. In fact, theleast number for which the proportion of bouncy numbers first reaches 50%is 538.Surprisingly, bouncy numbers become more and more common and by the timewe reach 21780 the proportion of bouncy numbers is equal to 90%.Find the least number for which the proportion of bouncy numbers isexactly 99%."""
Problem 113
"""Project Euler Problem 113=========================Working from left-to-right if no digit is exceeded by the digit to itsleft it is called an increasing number; for example, 134468.Similarly if no digit is exceeded by the digit to its right it is called adecreasing number; for example, 66420.We shall call a positive integer that is neither increasing nor decreasinga "bouncy" number; for example, 155349.As n increases, the proportion of bouncy numbers below n increases suchthat there are only 12951 numbers below one-million that are not bouncyand only 277032 non-bouncy numbers below 10^10.How many numbers below a googol (10^100) are not bouncy?"""
Problem 114
"""Project Euler Problem 114=========================A row measuring seven units in length has red blocks with a minimum lengthof three units placed on it, such that any two red blocks (which areallowed to be different lengths) are separated by at least one blacksquare. There are exactly seventeen ways of doing this. +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+How many ways can a row measuring fifty units in length be filled?NOTE: Although the example above does not lend itself to the possibility,in general it is permitted to mix block sizes. For example, on a rowmeasuring eight units in length you could use red (3), black (1), and red(4)."""
Problem 115
"""Project Euler Problem 115=========================NOTE: This is a more difficult version of problem 114.A row measuring n units in length has red blocks with a minimum length ofm units placed on it, such that any two red blocks (which are allowed tobe different lengths) are separated by at least one black square.Let the fill-count function, F(m, n), represent the number of ways that arow can be filled.For example, F(3, 29) = 673135 and F(3, 30) = 1089155.That is, for m = 3, it can be seen that n = 30 is the smallest value forwhich the fill-count function first exceeds one million.In the same way, for m = 10, it can be verified that F(10, 56) = 880711and F(10, 57) = 1148904, so n = 57 is the least value for which thefill-count function first exceeds one million.For m = 50, find the least value of n for which the fill-count functionfirst exceeds one million."""
Problem 116
"""Project Euler Problem 116=========================A row of five black square tiles is to have a number of its tiles replacedwith coloured oblong tiles chosen from red (length two), green (lengththree), or blue (length four).If red tiles are chosen there are exactly seven ways this can be done. +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+If green tiles are chosen there are three ways. +----+ +----+ +----+ +----+ +----+ +----+And if blue tiles are chosen there are two ways. +----+ +----+ +----+ +----+Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways ofreplacing the black tiles in a row measuring five units in length.How many different ways can the black tiles in a row measuring fifty unitsin length be replaced if colours cannot be mixed and at least one colouredtile must be used?NOTE: This is related to problem 117."""
Problem 117
"""Project Euler Problem 117=========================Using a combination of black square tiles and oblong tiles chosen from:red tiles measuring two units, green tiles measuring three units, and bluetiles measuring four units, it is possible to tile a row measuring fiveunits in length in exactly fifteen different ways. +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+How many ways can a row measuring fifty units in length be tiled?NOTE: This is related to problem 116."""
Problem 118
"""Project Euler Problem 118=========================Using all of the digits 1 through 9 and concatenating them freely to formdecimal integers, different sets can be formed. Interestingly with the set{2,5,47,89,631}, all of the elements belonging to it are prime.How many distinct sets containing each of the digits one through nineexactly once contain only prime elements?"""
Problem 119
"""Project Euler Problem 119=========================The number 512 is interesting because it is equal to the sum of its digitsraised to some power: 5 + 1 + 2 = 8, and 8^3 = 512. Another example of anumber with this property is 614656 = 28^4.We shall define a[n] to be the nth term of this sequence and insist that anumber must contain at least two digits to have a sum.You are given that a[2] = 512 and a[10] = 614656.Find a[30]."""
Problem 120
"""Project Euler Problem 120=========================Let r be the remainder when (a1)^n + (a+1)^n is divided by a^2.For example, if a = 7 and n = 3, then r = 42: 6^3 + 8^3 = 728 42 mod 49.And as n varies, so too will r, but for a = 7 it turns out that r[max] =42.For 3 a 1000, find r[max]."""
Problem 121
"""Project Euler Problem 121=========================A bag contains one red disc and one blue disc. In a game of chance aplayer takes a disc at random and its colour is noted. After each turn thedisc is returned to the bag, an extra red disc is added, and another discis taken at random.The player pays -L-1 to play and wins if they have taken more blue discsthan red discs at the end of the game.If the game is played for four turns, the probability of a player winningis exactly 11/120, and so the maximum prize fund the banker shouldallocate for winning in this game would be -L-10 before they would expectto incur a loss. Note that any payout will be a whole number of pounds andalso includes the original -L-1 paid to play the game, so in the examplegiven the player actually wins -L-9.Find the maximum prize fund that should be allocated to a single game inwhich fifteen turns are played."""
Problem 122
"""Project Euler Problem 122=========================The most naive way of computing n^15 requires fourteen multiplications:n * n * ... * n = n^15But using a "binary" method you can compute it in six multiplications:n * n = n^2n^2 * n^2 = n^4n^4 * n^4 = n^8n^8 * n^4 = n^12n^12 * n^2 = n^14n^14 * n = n^15However it is yet possible to compute it in only five multiplications:n * n = n^2n^2 * n = n^3n^3 * n^3 = n^6n^6 * n^6 = n^12n^12 * n^3 = n^15We shall define m(k) to be the minimum number of multiplications tocompute n^k; for example m(15) = 5.For 1 k 200, find m(k)."""
Problem 123
"""Project Euler Problem 123=========================Let p[n] be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainderwhen (p[n]1)^n + (p[n]+1)^n is divided by p[n]^2.For example, when n = 3, p[3] = 5, and 4^3 + 6^3 = 280 5 mod 25.The least value of n for which the remainder first exceeds 10^9 is 7037.Find the least value of n for which the remainder first exceeds 10^10."""
Problem 124
"""Project Euler Problem 124=========================The radical of n, rad(n), is the product of distinct prime factors of n.For example, 504 = 2^3 * 3^2 * 7, so rad(504) = 2 * 3 * 7 = 42.If we calculate rad(n) for 1 n 10, then sort them on rad(n), and sortingon n if the radical values are equal, we get: Unsorted Sorted n rad(n) n rad(n) k 1 1 1 1 1 2 2 2 2 2 3 3 4 2 3 4 2 8 2 4 5 5 3 3 5 6 6 9 3 6 7 7 5 5 7 8 2 6 6 8 9 3 7 7 9 10 10 10 10 10Let E(k) be the kth element in the sorted n column; for example, E(4) = 8and E(6) = 9.If rad(n) is sorted for 1 n 100000, find E(10000)."""
Problem 125
"""Project Euler Problem 125=========================The palindromic number 595 is interesting because it can be written as thesum of consecutive squares: 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2.There are exactly eleven palindromes below one-thousand that can bewritten as consecutive square sums, and the sum of these palindromes is4164. Note that 1 = 0^2 + 1^2 has not been included as this problem isconcerned with the squares of positive integers.Find the sum of all the numbers less than 10^8 that are both palindromicand can be written as the sum of consecutive squares."""
Problem 126
"""Project Euler Problem 126=========================The minimum number of cubes to cover every visible face on a cuboidmeasuring 3 x 2 x 1 is twenty-two.If we then add a second layer to this solid it would require forty-sixcubes to cover every visible face, the third layer would requireseventy-eight cubes, and the fourth layer would require one-hundred andeighteen cubes to cover every visible face.However, the first layer on a cuboid measuring 5 x 1 x 1 also requirestwenty-two cubes; similarly the first layer on cuboids measuring5 x 3 x 1, 7 x 2 x 1, and 11 x 1 x 1 all contain forty-six cubes.We shall define C(n) to represent the number of solids that contain ncubes in one of its layers. So C(22) = 2, C(46) = 4, C(78) = 5, and C(118)= 8.It turns out that 154 is the least value of n for which C(n) = 10.Find the least value of n for which C(n) = 1000."""
Problem 127
"""Project Euler Problem 127=========================The radical of n, rad(n), is the product of distinct prime factors of n.For example, 504 = 2^3 * 3^2 * 7, so rad(504) = 2 * 3 * 7 = 42.We shall define the triplet of positive integers (a, b, c) to be anabc-hit if: 1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1 2. a < b 3. a + b = c 4. rad(abc) < cFor example, (5, 27, 32) is an abc-hit, because: 1. GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1 2. 5 < 27 3. 5 + 27 = 32 4. rad(4320) = 30 < 32It turns out that abc-hits are quite rare and there are only thirty-oneabc-hits for c < 1000, with c = 12523.Find c for c < 110000."""
Problem 128
"""Project Euler Problem 128=========================A hexagonal tile with number 1 is surrounded by a ring of six hexagonaltiles, starting at "12 o'clock" and numbering the tiles 2 to 7 in ananti-clockwise direction.New rings are added in the same fashion, with the next rings beingnumbered 8 to 19, 20 to 37, 38 to 61, and so on. The diagram below showsthe first three rings.By finding the difference between tile n and each its six neighbours weshall define PD(n) to be the number of those differences which are prime.For example, working clockwise around tile 8 the differences are 12, 29,11, 6, 1, and 13. So PD(8) = 3.In the same way, the differences around tile 17 are 1, 17, 16, 1, 11, and10, hence PD(17) = 2.It can be shown that the maximum value of PD(n) is 3.If all of the tiles for which PD(n) = 3 are listed in ascending order toform a sequence, the 10th tile would be 271.Find the 2000th tile in this sequence."""
Problem 129
"""Project Euler Problem 129=========================A number consisting entirely of ones is called a repunit. We shall defineR(k) to be a repunit of length k; for example, R(6) = 111111.Given that n is a positive integer and GCD(n, 10) = 1, it can be shownthat there always exists a value, k, for which R(k) is divisible by n, andlet A(n) be the least such value of k; for example, A(7) = 6 and A(41) =5.The least value of n for which A(n) first exceeds ten is 17.Find the least value of n for which A(n) first exceeds one-million."""
Problem 130
"""Project Euler Problem 130=========================A number consisting entirely of ones is called a repunit. We shall defineR(k) to be a repunit of length k; for example, R(6) = 111111.Given that n is a positive integer and GCD(n, 10) = 1, it can be shownthat there always exists a value, k, for which R(k) is divisible by n, andlet A(n) be the least such value of k; for example, A(7) = 6 and A(41) =5.You are given that for all primes, p > 5, that p 1 is divisible by A(p).For example, when p = 41, A(41) = 5, and 40 is divisible by 5.However, there are rare composite values for which this is also true; thefirst five examples being 91, 259, 451, 481, and 703.Find the sum of the first twenty-five composite values of n for whichGCD(n, 10) = 1 and n 1 is divisible by A(n)."""
Problem 131
"""Project Euler Problem 131=========================There are some prime values, p, for which there exists a positive integer,n, such that the expression n^3 + n^2p is a perfect cube.For example, when p = 19, 8^3 + 8^2 * 19 = 12^3.What is perhaps most surprising is that for each prime with this propertythe value of n is unique, and there are only four such primes belowone-hundred.How many primes below one million have this remarkable property?"""
Problem 132
"""Project Euler Problem 132=========================A number consisting entirely of ones is called a repunit. We shall defineR(k) to be a repunit of length k.For example, R(10) = 1111111111 = 11 * 41 * 271 * 9091, and the sum ofthese prime factors is 9414.Find the sum of the first forty prime factors of R(10^9)."""
Problem 133
"""Project Euler Problem 133=========================A number consisting entirely of ones is called a repunit. We shall defineR(k) to be a repunit of length k; for example, R(6) = 111111.Let us consider repunits of the form R(10^n).Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) isdivisible by 17. Yet there is no value of n for which R(10^n) will divideby 19. In fact, it is remarkable that 11, 17, 41, and 73 are only fourprimes below one-hundred that can ever be a factor of R(10^n).Find the sum of all the primes below one-hundred thousand that will neverbe a factor of R(10^n)."""
Problem 134
"""Project Euler Problem 134=========================Consider the consecutive primes p[1] = 19 and p[2] = 23. It can beverified that 1219 is the smallest number such that the last digits areformed by p[1] whilst also being divisible by p[2].In fact, with the exception of p[1] = 3 and p[2] = 5, for every pair ofconsecutive primes, p[2] > p[1], there exist values of n for which thelast digits are formed by p[1] and n is divisible by p[2]. Let S be thesmallest of these values of n.Find S for every pair of consecutive primes with 5 p[1] 1000000."""
Problem 135
"""Project Euler Problem 135=========================Given the positive integers, x, y, and z, are consecutive terms of anarithmetic progression, the least value of the positive integer, n, forwhich the equation, x^2 y^2 z^2 = n, has exactly two solutions is n = 27: 34^2 27^2 20^2 = 12^2 9^2 6^2 = 27It turns out that n = 1155 is the least value which has exactly tensolutions.How many values of n less than one million have exactly ten distinctsolutions?"""
Problem 136
"""Project Euler Problem 136=========================The positive integers, x, y, and z, are consecutive terms of an arithmeticprogression. Given that n is a positive integer, the equation, x^2 y^2 z^2= n, has exactly one solution when n = 20: 13^2 10^2 7^2 = 20In fact there are twenty-five values of n below one hundred for which theequation has a unique solution.How many values of n less than fifty million have exactly one solution?"""
Problem 137
"""Project Euler Problem 137=========================Consider the infinite polynomial series A[F](x) = xF[1] + x^2F[2] +x^3F[3] + ..., where F[k] is the kth term in the Fibonacci sequence: 1, 1,2, 3, 5, 8, ... ; that is, F[k] = F[k[1]] + F[k[2]], F[1] = 1 and F[2] =1.For this problem we shall be interested in values of x for which A[F](x)is a positive integer.Surprisingly A[F](1/2) = (1/2).1 + (1/2)^2.1 + (1/2)^3.2 + (1/2)^4.3 + (1/2)^5.5 + ... = 1/2 + 1/4 + 2/8 + 3/16 + 5/32 + ... = 2The corresponding values of x for the first five natural numbers are shownbelow. +---------------+ |x |A[F](x)| |-------+-------| |21 |1 | |-------+-------| |1/2 |2 | |-------+-------| |(132)/3|3 | |-------+-------| |(895)/8|4 | |-------+-------| |(343)/5|5 | +---------------+We shall call A[F](x) a golden nugget if x is rational, because theybecome increasingly rarer; for example, the 10th golden nugget is74049690.Find the 15th golden nugget."""
Problem 138
"""Project Euler Problem 138=========================Consider the isosceles triangle with base length, b = 16, and legs, L =17.By using the Pythagorean theorem it can be seen that the height of thetriangle, h = (17^2 8^2) = 15, which is one less than the base length.With b = 272 and L = 305, we get h = 273, which is one more than the baselength, and this is the second smallest isosceles triangle with theproperty that h = b 1.Find L for the twelve smallest isosceles triangles for which h = b 1 andb, L are positive integers."""
Problem 139
"""Project Euler Problem 139=========================Let (a, b, c) represent the three sides of a right angle triangle withintegral length sides. It is possible to place four such trianglestogether to form a square with length c.For example, (3, 4, 5) triangles can be placed together to form a 5 by 5square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5square can be tiled with twenty-five 1 by 1 squares.However, if (5, 12, 13) triangles were used then the hole would measure 7by 7 and these could not be used to tile the 13 by 13 square.Given that the perimeter of the right triangle is less than one-hundredmillion, how many Pythagorean triangles would allow such a tiling to takeplace?"""
Problem 140
"""Project Euler Problem 140=========================Consider the infinite polynomial series A[G](x) = xG[1] + x^2G[2] +x^3G[3] + ..., where G[k] is the kth term of the second order recurrencerelation G[k] = G[k[1]] + G[k[2]], G[1] = 1 and G[2] = 4; that is, 1, 4,5, 9, 14, 23, ... .For this problem we shall be concerned with values of x for which A[G](x)is a positive integer.The corresponding values of x for the first five natural numbers are shownbelow. +-----------------+ |x |A[G](x)| |---------+-------| |(51)/4 |1 | |---------+-------| |2/5 |2 | |---------+-------| |(222)/6 |3 | |---------+-------| |(1375)/14|4 | |---------+-------| |1/2 |5 | +-----------------+We shall call A[G](x) a golden nugget if x is rational, because theybecome increasingly rarer; for example, the 20th golden nugget is211345365.Find the sum of the first thirty golden nuggets."""
Problem 141
"""Project Euler Problem 141=========================A positive integer, n, is divided by d and the quotient and remainder areq and r respectively. In addition d, q, and r are consecutive positiveinteger terms in a geometric sequence, but not necessarily in that order.For example, 58 divided by 6 has quotient 9 and remainder 4. It can alsobe seen that 4, 6, 9 are consecutive terms in a geometric sequence (commonratio 3/2).We will call such numbers, n, progressive.Some progressive numbers, such as 9 and 10404 = 102^2, happen to also beperfect squares.The sum of all progressive perfect squares below one hundred thousand is124657.Find the sum of all progressive perfect squares below one trillion(10^12)."""
Problem 142
"""Project Euler Problem 142=========================Find the smallest x + y + z with integers x > y > z > 0 such that x + y, xy, x + z, x z, y + z, y z are all perfect squares."""
Problem 143
"""Project Euler Problem 143=========================Let ABC be a triangle with all interior angles being less than 120degrees. Let X be any point inside the triangle and let XA = p, XB = q,and XC = r.Fermat challenged Torricelli to find the position of X such that p + q + rwas minimised.Torricelli was able to prove that if equilateral triangles AOB, BNC andAMC are constructed on each side of triangle ABC, the circumscribedcircles of AOB, BNC, and AMC will intersect at a single point, T, insidethe triangle. Moreover he proved that T, called the Torricelli/Fermatpoint, minimises p + q + r. Even more remarkable, it can be shown thatwhen the sum is minimised, AN = BM = CO = p + q + r and that AN, BM and COalso intersect at T.If the sum is minimised and a, b, c, p, q and r are all positive integerswe shall call triangle ABC a Torricelli triangle. For example, a = 399, b= 455, c = 511 is an example of a Torricelli triangle, with p + q + r =784.Find the sum of all distinct values of p + q + r 110000 for Torricellitriangles."""
Problem 144
"""Project Euler Problem 144=========================In laser physics, a "white cell" is a mirror system that acts as a delayline for the laser beam. The beam enters the cell, bounces around on themirrors, and eventually works its way back out.The specific white cell we will be considering is an ellipse with theequation 4x^2 + y^2 = 100The section corresponding to 0.01 x +0.01 at the top is missing, allowingthe light to enter and exit through the hole.The light beam in this problem starts at the point (0.0,10.1) just outsidethe white cell, and the beam first impacts the mirror at (1.4,-9.6).Each time the laser beam hits the surface of the ellipse, it follows theusual law of reflection "angle of incidence equals angle of reflection."That is, both the incident and reflected beams make the same angle withthe normal line at the point of incidence.In the figure on the left, the red line shows the first two points ofcontact between the laser beam and the wall of the white cell; the blueline shows the line tangent to the ellipse at the point of incidence ofthe first bounce.The slope m of the tangent line at any point (x,y) of the given ellipseis: m = 4x/yThe normal line is perpendicular to this tangent line at the point ofincidence.The animation on the right shows the first 10 reflections of the beam.How many times does the beam hit the internal surface of the white cellbefore exiting?"""
Problem 145
"""Project Euler Problem 145=========================Some positive integers n have the property that the sum [ n + reverse(n) ]consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409,and 904 are reversible. Leading zeroes are not allowed in either n orreverse(n).There are 120 reversible numbers below one-thousand.How many reversible numbers are there below one-billion (10^9)?"""
Problem 146
"""Project Euler Problem 146=========================The smallest positive integer n for which the numbers n^2+1, n^2+3, n^2+7,n^2+9, n^2+13, and n^2+27 are consecutive primes is 10. The sum of allsuch integers n below one-million is 1242490.What is the sum of all such integers n below 150 million?"""
Problem 147
"""Project Euler Problem 147=========================In a 3x2 cross-hatched grid, a total of 37 different rectangles could besituated within that grid as indicated in the sketch.There are 5 grids smaller than 3x2, vertical and horizontal dimensionsbeing important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them iscross-hatched, the following number of different rectangles could besituated within those smaller grids:1x1: 12x1: 43x1: 81x2: 42x2: 18Adding those to the 37 of the 3x2 grid, a total of 72 different rectanglescould be situated within 3x2 and smaller grids.How many different rectangles could be situated within 47x43 and smallergrids?"""
Problem 148
"""Project Euler Problem 148=========================We can easily verify that none of the entries in the first seven rows ofPascal's triangle are divisible by 7: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1However, if we check the first one hundred rows, we will find that only2361 of the 5050 entries are not divisible by 7.Find the number of entries which are not divisible by 7 in the first onebillion (10^9) rows of Pascal's triangle."""
Problem 149
"""Project Euler Problem 149=========================Looking at the table below, it is easy to verify that the maximum possiblesum of adjacent numbers in any direction (horizontal, vertical, diagonalor anti-diagonal) is 16 (= 8 + 7 + 1). +-----------------+ | 2 | 5 | 3 | 2 | |---+---+---+-----| | 9 | 6 | 5 | 1 | |---+---+---+-----| | 3 | 2 | 7 | 3 | |---+---+---+-----| | 1 | 8 | 4 | 8 | +-----------------+Now, let us repeat the search, but on a much larger scale:First, generate four million pseudo-random numbers using a specific formof what is known as a "Lagged Fibonacci Generator":For 1 k 55, s[k] = [100003 200003k + 300007k^3] (modulo 1000000) 500000.For 56 k 4000000, s[k] = [s[k24] + s[k55] + 1000000] (modulo 1000000)500000.Thus, s[10] = 393027 and s[100] = 86613.The terms of s are then arranged in a 2000 * 2000 table, using the first2000 numbers to fill the first row (sequentially), the next 2000 numbersto fill the second row, and so on.Finally, find the greatest sum of (any number of) adjacent entries in anydirection (horizontal, vertical, diagonal or anti-diagonal)."""
Problem 150
"""Project Euler Problem 150=========================In a triangular array of positive and negative integers, we wish to find asub-triangle such that the sum of the numbers it contains is the smallestpossible.In the example below, it can be easily verified that the marked trianglesatisfies this condition having a sum of 42.We wish to make such a triangular array with one thousand rows, so wegenerate 500500 pseudo-random numbers s[k] in the range 2^19, using a typeof random number generator (known as a Linear Congruential Generator) asfollows:t := 0for k = 1 up to k = 500500: t := (615949*t + 797807) modulo 2^20 s[k] := t2^19Thus: s[1] = 273519, s[2] = 153582, s[3] = 450905 etcOur triangular array is then formed using the pseudo-random numbers thus: s[1 ]s[2] s[3 ]s[4] s[5] s[6] s[7] s[8] s[9] s[10 ]...Sub-triangles can start at any element of the array and extend down as faras we like (taking-in the two elements directly below it from the nextrow, the three elements directly below from the row after that, and soon).The "sum of a sub-triangle" is defined as the sum of all the elements itcontains.Find the smallest possible sub-triangle sum."""
Problem 151
"""Project Euler Problem 151=========================A printing shop runs 16 batches (jobs) every week and each batch requiresa sheet of special colour-proofing paper of size A5.Every Monday morning, the foreman opens a new envelope, containing a largesheet of the special paper with size A1.He proceeds to cut it in half, thus getting two sheets of size A2. Then hecuts one of them in half to get two sheets of size A3 and so on until heobtains the A5-size sheet needed for the first batch of the week.All the unused sheets are placed back in the envelope.At the beginning of each subsequent batch, he takes from the envelope onesheet of paper at random. If it is of size A5, he uses it. If it islarger, he repeats the 'cut-in-half' procedure until he has what he needsand any remaining sheets are always placed back in the envelope.Excluding the first and last batch of the week, find the expected numberof times (during each week) that the foreman finds a single sheet of paperin the envelope.Give your answer rounded to six decimal places using the format x.xxxxxx ."""
Problem 152
"""Project Euler Problem 152=========================There are several ways to write the number 1/2 as a sum of inverse squaresusing distinct integers.For instance, the numbers {2,3,4,5,7,12,15,20,28,35} can be used:In fact, only using integers between 2 and 45 inclusive, there are exactlythree ways to do it, the remaining two being:{2,3,4,6,7,9,10,20,28,35,36,45} and {2,3,4,6,7,9,12,15,28,30,35,36,45}.How many ways are there to write the number 1/2 as a sum of inversesquares using distinct integers between 2 and 80 inclusive?"""
Problem 153
"""Project Euler Problem 153=========================As we all know the equation x^2=-1 has no solutions for real x.If we however introduce the imaginary number i this equation has twosolutions: x=i and x=-i.If we go a step further the equation (x-3)^2=-4 has two complex solutions:x=3+2i and x=3-2i.x=3+2i and x=3-2i are called each others' complex conjugate.Numbers of the form a+bi are called complex numbers.In general a+bi and abi are each other's complex conjugate.A Gaussian Integer is a complex number a+bi such that both a and b areintegers.The regular integers are also Gaussian integers (with b=0).To distinguish them from Gaussian integers with b 0 we call such integers"rational integers."A Gaussian integer is called a divisor of a rational integer n if theresult is also a Gaussian integer.If for example we divide 5 by 1+2i we can simplify in the followingmanner:Multiply numerator and denominator by the complex conjugate of 1+2i: 12i.The result is .So 1+2i is a divisor of 5.Note that 1+i is not a divisor of 5 because .Note also that if the Gaussian Integer (a+bi) is a divisor of a rationalinteger n, then its complex conjugate (abi) is also a divisor of n.In fact, 5 has six divisors such that the real part is positive: {1, 1 +2i, 1 2i, 2 + i, 2 i, 5}.The following is a table of all of the divisors for the first fivepositive rational integers: +--------------------------------------------------+ | n | Gaussian integer divisors | Sum s(n) of | | | with positive real part | thesedivisors | |---+------------------------------+---------------| | 1 | 1 | 1 | |---+------------------------------+---------------| | 2 | 1, 1+i, 1-i, 2 | 5 | |---+------------------------------+---------------| | 3 | 1, 3 | 4 | |---+------------------------------+---------------| | 4 | 1, 1+i, 1-i, 2, 2+2i, 2-2i,4 | 13 | |---+------------------------------+---------------| | 5 | 1, 1+2i, 1-2i, 2+i, 2-i, 5 | 12 | +--------------------------------------------------+For divisors with positive real parts, then, we have: .For 1 n 10^5, s(n)=17924657155.What is s(n) for 1 n 10^8?"""
Problem 154
"""Project Euler Problem 154=========================A triangular pyramid is constructed using spherical balls so that eachball rests on exactly three balls of the next lower level.Then, we calculate the number of paths leading from the apex to eachposition:A path starts at the apex and progresses downwards to any of the threespheres directly below the current position.Consequently, the number of paths to reach a certain position is the sumof the numbers immediately above it (depending on the position, there areup to three numbers above it).The result is Pascal's pyramid and the numbers at each level n are thecoefficients of the trinomial expansion (x + y + z)^n.How many coefficients in the expansion of (x + y + z)^200000 are multiplesof 10^12?"""
Problem 155
"""Project Euler Problem 155=========================An electric circuit uses exclusively identical capacitors of the samevalue C.The capacitors can be connected in series or in parallel to formsub-units, which can then be connected in series or in parallel with othercapacitors or other sub-units to form larger sub-units, and so on up to afinal circuit.Using this simple procedure and up to n identical capacitors, we can makecircuits having a range of different total capacitances. For example,using up to n=3 capacitors of 60 F each, we can obtain the following 7distinct total capacitance values:If we denote by D(n) the number of distinct total capacitance values wecan obtain when using up to n equal-valued capacitors and the simpleprocedure described above, we have: D(1)=1, D(2)=3, D(3)=7 ...Find D(18).Reminder : When connecting capacitors C[1], C[2] etc in parallel, thetotal capacitance is C[T] = C[1] + C[2] +...,whereas when connecting them in series, the overall capacitance is givenby:"""
Problem 156
"""Project Euler Problem 156=========================Starting from zero the natural numbers are written down in base 10 likethis:0 1 2 3 4 5 6 7 8 9 10 11 12....Consider the digit d=1. After we write down each number n, we will updatethe number of ones that have occurred and call this number f(n,1). Thefirst values for f(n,1), then, are as follows: n f(n,1) 0 0 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 11 4 12 5Note that f(n,1) never equals 3.So the first two solutions of the equation f(n,1)=n are n=0 and n=1. Thenext solution is n=199981.In the same manner the function f(n,d) gives the total number of digits dthat have been written down after the number n has been written.In fact, for every digit d 0, 0 is the first solution of the equationf(n,d)=n.Let s(d) be the sum of all the solutions for which f(n,d)=n.You are given that s(1)=22786974071.Find s(d) for 1 d 9.Note: if, for some n, f(n,d)=n for more than one value of d this value ofn is counted again for every value of d for which f(n,d)=n."""
Problem 157
"""Project Euler Problem 157=========================Consider the diophantine equation ^1/[a]+^1/[b]= ^p/[10^n] with a, b, p, npositive integers and a b.For n=1 this equation has 20 solutions that are listed below:/[1]+^1/[1]=^20/[10 ]^1/[1]+^1/[2]=^15/[10 ]^1/[1]+^1/[5]=^12/[10 ]^1/[1]+^1/[10]=^11/[10 ]^1/[2]+^1/[2]=^10/[10/[2]+^1/[5]=^7/[10 ]^1/[2]+^1/[10]=^6/[10 ]^1/[3]+^1/[6]=^5/[10 ]^1/[3]+^1/[15]=^4/[10 ]^1/[4]+^1/[4]=^5/[10/[4]+^1/[20]=^3/[10 ]^1/[5]+^1/[5]=^4/[10 ]^1/[5]+^1/[10]=^3/[10 ]^1/[6]+^1/[30]=^2/[10 ]^1/[10]+^1/[10]=^2/[10/[11]+^1/[110]=^1/[10 ]^1/[12]+^1/[60]=^1/[10 ]^1/[14]+^1/[35]=^1/[10 ]^1/[15]+^1/[30]=^1/[10 ]^1/[20]+^1/[20]=^1/[10]How many solutions has this equation for 1 n 9?"""
Problem 158
"""Project Euler Problem 158=========================Taking three different letters from the 26 letters of the alphabet,character strings of length three can be formed.Examples are 'abc', 'hat' and 'zyx'.When we study these three examples we see that for 'abc' two characterscome lexicographically after its neighbour to the left.For 'hat' there is exactly one character that comes lexicographicallyafter its neighbour to the left. For 'zyx' there are zero characters thatcome lexicographically after its neighbour to the left.In all there are 10400 strings of length 3 for which exactly one charactercomes lexicographically after its neighbour to the left.We now consider strings of n 26 different characters from the alphabet.For every n, p(n) is the number of strings of length n for which exactlyone character comes lexicographically after its neighbour to the left.What is the maximum value of p(n)?"""
Problem 159
"""Project Euler Problem 159=========================A composite number can be factored many different ways. For instance, notincluding multiplication by one, 24 can be factored in 7 distinct ways:24 = 2x2x2x324 = 2x3x424 = 2x2x624 = 4x624 = 3x824 = 2x1224 = 24Recall that the digital root of a number, in base 10, is found by addingtogether the digits of that number, and repeating that process until anumber is arrived at that is less than 10. Thus the digital root of 467 is8.We shall call a Digital Root Sum (DRS) the sum of the digital roots of theindividual factors of our number.The chart below demonstrates all of the DRS values for 24. +------------------------------+ |Factorisation|Digital Root Sum| |-------------+----------------| |2x2x2x3 | 9 | |-------------+----------------| |2x3x4 | 9 | |-------------+----------------| |2x2x6 | 10 | |-------------+----------------| |4x6 | 10 | |-------------+----------------| |3x8 | 11 | |-------------+----------------| |2x12 | 5 | |-------------+----------------| |24 | 6 | +------------------------------+The maximum Digital Root Sum of 24 is 11.The function mdrs(n) gives the maximum Digital Root Sum of n. Somdrs(24)=11.Find mdrs(n) for 1 < n < 1,000,000."""
Problem 160
"""Project Euler Problem 160=========================For any N, let f(N) be the last five digits before the trailing zeroes inN!.For example,9! = 362880 so f(9)=3628810! = 3628800 so f(10)=3628820! = 2432902008176640000 so f(20)=17664Find f(1,000,000,000,000)"""
Problem 161
"""Project Euler Problem 161=========================A triomino is a shape consisting of three squares joined via theedges.There are two basic forms:If all possible orientations are taken into account there are six:Any n by m grid for which nxm is divisible by 3 can be tiled withtriominoes.If we consider tilings that can be obtained by reflection or rotation fromanother tiling as different there are 41 ways a 2 by 9 grid can be tiledwith triominoes:In how many ways can a 9 by 12 grid be tiled in this way by triominoes?"""
Problem 162
"""Project Euler Problem 162=========================In the hexadecimal number system numbers are represented using 16different digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,FThe hexadecimal number AF when written in the decimal number system equals10x16+15=175.In the 3-digit hexadecimal numbers 10A, 1A0, A10, and A01 the digits 0,1and A are all present.Like numbers written in base ten we write hexadecimal numbers withoutleading zeroes.How many hexadecimal numbers containing at most sixteen hexadecimal digitsexist with all of the digits 0,1, and A present at least once?Give your answer as a hexadecimal number.(A,B,C,D,E and F in upper case, without any leading or trailing code thatmarks the number as hexadecimal and without leading zeroes , e.g. 1A3F andnot: 1a3f and not 0x1a3f and not $1A3F and not #1A3F and not 0000001A3F)"""
Problem 163
"""Project Euler Problem 163=========================Consider an equilateral triangle in which straight lines are drawn fromeach vertex to the middle of the opposite side, such as in the size 1triangle in the sketch below.Sixteen triangles of either different shape or size or orientation orlocation can now be observed in that triangle. Using size 1 triangles asbuilding blocks, larger triangles can be formed, such as the size 2triangle in the above sketch. One-hundred and four triangles of eitherdifferent shape or size or orientation or location can now be observed inthat size 2 triangle.It can be observed that the size 2 triangle contains 4 size 1 trianglebuilding blocks. A size 3 triangle would contain 9 size 1 trianglebuilding blocks and a size n triangle would thus contain n^2 size 1triangle building blocks.If we denote T(n) as the number of triangles present in a triangle of sizen, thenT(1) = 16T(2) = 104Find T(36)."""
Problem 164
"""Project Euler Problem 164=========================How many 20 digit numbers n (without any leading zero) exist such that nothree consecutive digits of n have a sum greater than 9?"""
Problem 165
"""Project Euler Problem 165=========================A segment is uniquely defined by its two endpoints.By considering two line segments in plane geometry there are threepossibilities:the segments have zero points, one point, or infinitely many points incommon.Moreover when two segments have exactly one point in common it might bethe case that that common point is an endpoint of either one of thesegments or of both. If a common point of two segments is not an endpointof either of the segments it is an interior point of both segments.We will call a common point T of two segments L[1] and L[2] a trueintersection point of L[1] and L[2] if T is the only common point of L[1]and L[2] and T is an interior point of both segments.Consider the three segments L[1], L[2], and L[3]:L[1]: (27, 44) to (12, 32)L[2]: (46, 53) to (17, 62)L[3]: (46, 70) to (22, 40)It can be verified that line segments L[2] and L[3] have a trueintersection point. We note that as the one of the end points of L[3]:(22,40) lies on L[1] this is not considered to be a true point ofintersection. L[1] and L[2] have no common point. So among the three linesegments, we find one true intersection point.Now let us do the same for 5000 line segments. To this end, we generate20000 numbers using the so-called "Blum Blum Shub" pseudo-random numbergenerator.s[0] = 290797s[n+1] = s[n] * s[n] (modulo 50515093)t[n] = s[n] (modulo 500)To create each line segment, we use four consecutive numbers t[n]. Thatis, the first line segment is given by:(t[1], t[2]) to (t[3], t[4])The first four numbers computed according to the above generator shouldbe: 27, 144, 12 and 232. The first segment would thus be (27,144) to(12,232).How many distinct true intersection points are found among the 5000 linesegments?"""
Problem 166
"""Project Euler Problem 166=========================A 4x4 grid is filled with digits d, 0 d 9.It can be seen that in the grid 6 3 3 0 5 0 4 3 0 7 1 4 1 2 4 5the sum of each row and each column has the value 12. Moreover the sum ofeach diagonal is also 12.In how many ways can you fill a 4x4 grid with the digits d, 0 d 9 so thateach row, each column, and both diagonals have the same sum?"""
Problem 167
"""Project Euler Problem 167=========================For two positive integers a and b, the Ulam sequence U(a,b) is defined byU(a,b)[1] = a, U(a,b)[2] = b and for k > 2,U(a,b)[k] is the smallestinteger greater than U(a,b)[(k-1)] which can be written in exactly one wayas the sum of two distinct previous members of U(a,b).For example, the sequence U(1,2) begins with1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8;5 does not belong to it because 5 = 1 + 4 = 2 + 3 has two representationsas the sum of two previous members, likewise 7 = 1 + 6 = 3 + 4.Find U(2,2n+1)[k] for 2 n 10, where k = 10^11."""
Problem 168
"""Project Euler Problem 168=========================Consider the number 142857. We can right-rotate this number by moving thelast digit (7) to the front of it, giving us 714285.It can be verified that 714285=5 * 142857.This demonstrates an unusual property of 142857: it is a divisor of itsright-rotation.Find the last 5 digits of the sum of all integers n, 10 < n < 10^100, thathave this property."""
Problem 169
"""Project Euler Problem 169=========================Define f(0)=1 and f(n) to be the number of different ways n can beexpressed as a sum of integer powers of 2 using each power no more thantwice.For example, f(10)=5 since there are five different ways to express 10:1 + 1 + 81 + 1 + 4 + 41 + 1 + 2 + 2 + 42 + 4 + 42 + 8What is f(10^25)?"""
Problem 170
"""Project Euler Problem 170=========================Take the number 6 and multiply it by each of 1273 and 9854:6 * 1273 = 76386 * 9854 = 59124By concatenating these products we get the 1 to 9 pandigital 763859124. Wewill call 763859124 the "concatenated product of 6 and (1273,9854)".Notice too, that the concatenation of the input numbers, 612739854, isalso 1 to 9 pandigital.The same can be done for 0 to 9 pandigital numbers.What is the largest 0 to 9 pandigital 10-digit concatenated product of aninteger with two or more other integers, such that the concatenation ofthe input numbers is also a 0 to 9 pandigital 10-digit number?"""
Problem 171
"""Project Euler Problem 171=========================For a positive integer n, let f(n) be the sum of the squares of the digits(in base 10) of n, e.g.f(3) = 3^2 = 9,f(25) = 2^2 + 5^2 = 4 + 25 = 29,f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4 = 36Find the last nine digits of the sum of all n, 0 < n < 10^20, such thatf(n) is a perfect square."""
Problem 172
"""Project Euler Problem 172=========================How many 18-digit numbers n (without leading zeros) are there such that nodigit occurs more than three times in n?"""
Problem 173
"""Project Euler Problem 173=========================We shall define a square lamina to be a square outline with a square"hole" so that the shape possesses vertical and horizontal symmetry. Forexample, using exactly thirty-two square tiles we can form two differentsquare laminae:With one-hundred tiles, and not necessarily using all of the tiles at onetime, it is possible to form forty-one different square laminae.Using up to one million tiles how many different square laminae can beformed?"""
Problem 174
"""Project Euler Problem 174=========================We shall define a square lamina to be a square outline with a square"hole" so that the shape possesses vertical and horizontal symmetry.Given eight tiles it is possible to form a lamina in only one way: 3x3square with a 1x1 hole in the middle. However, using thirty-two tiles itis possible to form two distinct laminae.If t represents the number of tiles used, we shall say that t = 8 is typeL(1) and t = 32 is type L(2).Let N(n) be the number of t 1000000 such that t is type L(n); for example,N(15) = 832.What is N(n) for 1 n 10?"""
Problem 175
"""Project Euler Problem 175=========================Define f(0)=1 and f(n) to be the number of ways to write n as a sum ofpowers of 2 where no power occurs more than twice.For example, f(10)=5 since there are five different ways to express 10:10 = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1It can be shown that for every fraction p/q (p > 0, q > 0) there exists atleast one integer n such thatf(n)/f(n-1)=p/q.For instance, the smallest n for which f(n)/f(n-1)=13/17 is 241.The binary expansion of 241 is 11110001.Reading this binary number from the most significant bit to the leastsignificant bit there are 4 one's, 3 zeroes and 1 one. We shall call thestring 4,3,1 the Shortened Binary Expansion of 241.Find the Shortened Binary Expansion of the smallest n for whichf(n)/f(n-1)=123456789/987654321.Give your answer as comma separated integers, without any whitespaces."""
Problem 176
"""Project Euler Problem 176=========================The four rectangular triangles with sides (9,12,15), (12,16,20), (5,12,13)and (12,35,37) all have one of the shorter sides (catheti) equal to 12. Itcan be shown that no other integer sided rectangular triangle exists withone of the catheti equal to 12.Find the smallest integer that can be the length of a cathetus of exactly47547 different integer sided rectangular triangles."""
Problem 177
"""Project Euler Problem 177=========================Let ABCD be a convex quadrilateral, with diagonals AC and BD. At eachvertex the diagonal makes an angle with each of the two sides, creatingeight corner angles.For example, at vertex A, the two angles are CAD, CAB.We call such a quadrilateral for which all eight corner angles haveinteger values when measured in degrees an "integer angled quadrilateral".An example of an integer angled quadrilateral is a square, where all eightcorner angles are 45DEG. Another example is given by DAC = 20DEG, BAC =60DEG, ABD = 50DEG, CBD = 30DEG, BCA = 40DEG, DCA = 30DEG, CDB = 80DEG,ADB = 50DEG.What is the total number of non-similar integer angled quadrilaterals?Note: In your calculations you may assume that a calculated angle isintegral if it is within a tolerance of 10^-9 of an integer value."""
Problem 178
"""Project Euler Problem 178=========================Consider the number 45656.It can be seen that each pair of consecutive digits of 45656 has adifference of one.A number for which every pair of consecutive digits has a difference ofone is called a step number.A pandigital number contains every decimal digit from 0 to 9 at leastonce.How many pandigital step numbers less than 10^40 are there?"""
Problem 179
"""Project Euler Problem 179=========================Find the number of integers 1 < n < 10^7, for which n and n + 1 have thesame number of positive divisors. For example, 14 has the positivedivisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15."""
Problem 180
"""Project Euler Problem 180=========================For any integer n, consider the three functionsf[1,n](x,y,z) = x^n+1 + y^n+1 z^n+1f[2,n](x,y,z) = (xy + yz + zx)*(x^n-1 + y^n-1 z^n-1)f[3,n](x,y,z) = xyz*(x^n-2 + y^n-2 z^n-2)and their combinationf[n](x,y,z) = f[1,n](x,y,z) + f[2,n](x,y,z) f[3,n](x,y,z)We call (x,y,z) a golden triple of order k if x, y, and z are all rationalnumbers of the form a / b with0 < a < b k and there is (at least) one integer n, so that f[n](x,y,z) =0.Let s(x,y,z) = x + y + z.Let t = u / v be the sum of all distinct s(x,y,z) for all golden triples(x,y,z) of order 35.All the s(x,y,z) and t must be in reduced form.Find u + v."""
Problem 181
"""Project Euler Problem 181=========================Having three black objects B and one white object W they can be grouped in7 ways like this: (BBBW) (B,BBW) (B,B,BW) (B,B,B,W) (B,BB,W) (BBB,W) (BB,BW)In how many ways can sixty black objects B and forty white objects W bethus grouped?"""
Problem 182
"""Project Euler Problem 182=========================The RSA encryption is based on the following procedure:Generate two distinct primes p and q.Compute n=pq and f=(p-1)(q-1).Find an integer e, 1 < e < f, such that gcd(e,f)=1.A message in this system is a number in the interval [0,n-1].A text to be encrypted is then somehow converted to messages (numbers inthe interval [0,n-1]).To encrypt the text, for each message, m, c=m^e mod n is calculated.To decrypt the text, the following procedure is needed: calculate d suchthat ed=1 mod f, then for each encrypted message, c, calculate m=c^d modn.There exist values of e and m such that m^e mod n=m.We call messages m for which m^e mod n=m unconcealed messages.An issue when choosing e is that there should not be too many unconcealedmessages.For instance, let p=19 and q=37.Then n=19*37=703 and f=18*36=648.If we choose e=181, then, although gcd(181,648)=1 it turns out that allpossible messagesm (0mn-1) are unconcealed when calculating m^e mod n.For any valid choice of e there exist some unconcealed messages.It's important that the number of unconcealed messages is at a minimum.Choose p=1009 and q=3643.Find the sum of all values of e, 1 < e < f(1009,3643) and gcd(e,f)=1, sothat the number of unconcealed messages for this value of e is at aminimum."""
Problem 183
"""Project Euler Problem 183=========================Let N be a positive integer and let N be split into k equal parts, r =N/k, so that N = r + r + ... + r.Let P be the product of these parts, P = r * r * ... * r = r^k.For example, if 11 is split into five equal parts, 11 = 2.2 + 2.2 + 2.2 +2.2 + 2.2, then P = 2.2^5 = 51.53632.Let M(N) = P[max] for a given value of N.It turns out that the maximum for N = 11 is found by splitting eleven intofour equal parts which leads to P[max] = (11/4)^4; that is, M(11) =14641/256 = 57.19140625, which is a terminating decimal.However, for N = 8 the maximum is achieved by splitting it into threeequal parts, so M(8) = 512/27, which is a non-terminating decimal.Let D(N) = N if M(N) is a non-terminating decimal and D(N) = -N if M(N) isa terminating decimal.For example, SD(N) for 5 N 100 is 2438.Find SD(N) for 5 N 10000."""
Problem 184
"""Project Euler Problem 184=========================Consider the set I[r] of points (x,y) with integer co-ordinates in theinterior of the circle with radius r, centered at the origin, i.e. x^2 +y^2 < r^2.For a radius of 2, I[2] contains the nine points (0,0), (1,0), (1,1),(0,1), (-1,1), (-1,0), (-1,-1), (0,-1) and (1,-1). There are eighttriangles having all three vertices in I[2] which contain the origin inthe interior. Two of them are shown below, the others are obtained fromthese by rotation.For a radius of 3, there are 360 triangles containing the origin in theinterior and having all vertices in I[3] and for I[5] the number is 10600.How many triangles are there containing the origin in the interior andhaving all three vertices in I[105]?"""
Problem 185
"""Project Euler Problem 185=========================The game Number Mind is a variant of the well known game Master Mind.Instead of coloured pegs, you have to guess a secret sequence of digits.After each guess you're only told in how many places you've guessed thecorrect digit. So, if the sequence was 1234 and you guessed 2036, you'd betold that you have one correct digit; however, you would NOT be told thatyou also have another digit in the wrong place.For instance, given the following guesses for a 5-digit secret sequence,90342 ;2 correct70794 ;0 correct39458 ;2 correct34109 ;1 correct51545 ;2 correct12531 ;1 correctThe correct sequence 39542 is unique.Based on the following guesses,5616185650518293 ;2 correct3847439647293047 ;1 correct5855462940810587 ;3 correct9742855507068353 ;3 correct4296849643607543 ;3 correct3174248439465858 ;1 correct4513559094146117 ;2 correct7890971548908067 ;3 correct8157356344118483 ;1 correct2615250744386899 ;2 correct8690095851526254 ;3 correct6375711915077050 ;1 correct6913859173121360 ;1 correct6442889055042768 ;2 correct2321386104303845 ;0 correct2326509471271448 ;2 correct5251583379644322 ;2 correct1748270476758276 ;3 correct4895722652190306 ;1 correct3041631117224635 ;3 correct1841236454324589 ;3 correct2659862637316867 ;2 correctFind the unique 16-digit secret sequence."""
Problem 186
"""Project Euler Problem 186=========================Here are the records from a busy telephone system with one million users: +-------------------------------------+ |RecNr | Caller | Called | |-----------------+---------+---------| | 1 | 200007 | 100053 | |-----------------+---------+---------| | 2 | 600183 | 500439 | |-----------------+---------+---------| | 3 | 600863 | 701497 | |-----------------+---------+---------| | ... | ... | ... | +-------------------------------------+The telephone number of the caller and the called number in record n areCaller(n) = S[2n-1] and Called(n) = S[2n] where S[1,2,3,...] come from the"Lagged Fibonacci Generator":For 1 k 55, S[k] = [100003 - 200003k + 300007k^3] (modulo 1000000)For 56 k, S[k] = [S[k-24] + S[k-55]] (modulo 1000000)If Caller(n) = Called(n) then the user is assumed to have misdialled andthe call fails; otherwise the call is successful.From the start of the records, we say that any pair of users X and Y arefriends if X calls Y or vice-versa. Similarly, X is a friend of a friendof Z if X is a friend of Y and Y is a friend of Z; and so on for longerchains.The Prime Minister's phone number is 524287. After how many successfulcalls, not counting misdials, will 99% of the users (including the PM) bea friend, or a friend of a friend etc., of the Prime Minister?"""
Problem 187
"""Project Euler Problem 187=========================A composite is a number containing at least two prime factors. Forexample, 15 = 3 * 5; 9 = 3 * 3; 12 = 2 * 2 * 3.There are ten composites below thirty containing precisely two, notnecessarily distinct, prime factors:4, 6, 9, 10, 14, 15, 21, 22, 25, 26.How many composite integers, n < 10^8, have precisely two, not necessarilydistinct, prime factors?"""
Problem 188
"""Project Euler Problem 188=========================The hyperexponentiation or tetration of a number a by a positive integerb, denoted by a-^-^b or ^ba, is recursively defined by:a-^-^1 = a,a-^-^(k+1) = a^(a-^-^k).Thus we have e.g. 3-^-^2 = 3^3 = 27, hence 3-^-^3 = 3^27 = 7625597484987and 3-^-^4 is roughly 10^3.6383346400240996*10^12.Find the last 8 digits of 1777-^-^1855."""
Problem 189
"""Project Euler Problem 189=========================Consider the following configuration of 64 triangles:We wish to colour the interior of each triangle with one of three colours:red, green or blue, so that no two neighbouring triangles have the samecolour. Such a colouring shall be called valid. Here, two triangles aresaid to be neighbouring if they share an edge.Note: if they only share a vertex, then they are not neighbours.For example, here is a valid colouring of the above grid:A colouring C' which is obtained from a colouring C by rotation orreflection is considered distinct from C unless the two are identical.How many distinct valid colourings are there for the above configuration?"""
Problem 190
"""Project Euler Problem 190=========================Let S[m] = (x[1], x[2], ... , x[m]) be the m-tuple of positive realnumbers with x[1] + x[2] + ... + x[m] = m for which P[m] = x[1] * x[2]^2 *... * x[m]^m is maximised.For example, it can be verified that [P[10]] = 4112 ([ ] is the integerpart function).Find S[P[m]] for 2 m 15."""
Problem 191
"""Project Euler Problem 191=========================A particular school offers cash rewards to children with good attendanceand punctuality. If they are absent for three consecutive days or late onmore than one occasion then they forfeit their prize.During an n-day period a trinary string is formed for each childconsisting of L's (late), O's (on time), and A's (absent).Although there are eighty-one trinary strings for a 4-day period that canbe formed, exactly forty-three strings would lead to a prize:OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOAOAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOOAOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOLAALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAALAOO LAOA LAAOHow many "prize" strings exist over a 30-day period?"""
Problem 192
"""Project Euler Problem 192=========================Let x be a real number.A best approximation to x for the denominator bound d is a rational numberr/s in reduced form, with s d, such that any rational number which iscloser to x than r/s has a denominator larger than d: |p/q-x| < |r/s-x| q > dFor example, the best approximation to 13 for the denominator bound 20 is18/5 and the best approximation to 13 for the denominator bound 30 is101/28.Find the sum of all denominators of the best approximations to n for thedenominator bound 10^12, where n is not a perfect square and 1 < n 100000."""
Problem 193
"""Project Euler Problem 193=========================A positive integer n is called squarefree, if no square of a prime dividesn, thus 1, 2, 3, 5, 6, 7, 10, 11 are squarefree, but not 4, 8, 9, 12.How many squarefree numbers are there below 2^50?"""
Problem 194
"""Project Euler Problem 194=========================Consider graphs built with the units A: and B: , where the units are gluedalongthe vertical edges as in the graph .A configuration of type (a,b,c) is a graph thus built of a units A and bunits B, where the graph's vertices are coloured using up to c colours, sothat no two adjacent vertices have the same colour.The compound graph above is an example of a configuration of type (2,2,6),in fact of type (2,2,c) for all c 4.Let N(a,b,c) be the number of configurations of type (a,b,c).For example, N(1,0,3) = 24, N(0,2,4) = 92928 and N(2,2,3) = 20736.Find the last 8 digits of N(25,75,1984)."""
Problem 195
"""Project Euler Problem 195=========================Let's call an integer sided triangle with exactly one angle of 60 degreesa 60-degree triangle.Let r be the radius of the inscribed circle of such a 60-degree triangle.There are 1234 60-degree triangles for which r 100.Let T(n) be the number of 60-degree triangles for which r n, soT(100) = 1234, T(1000) = 22767, and T(10000) = 359912.Find T(1053779)."""
Problem 196
"""Project Euler Problem 196=========================Build a triangle from all positive integers in the following way: 1 2 3 4 5 6 7 8 9 1011 12 13 14 1516 17 18 19 20 2122 23 24 25 26 27 2829 30 31 32 33 34 35 3637 38 39 40 41 42 43 44 4546 47 48 49 50 51 52 53 54 5556 57 58 59 60 61 62 63 64 65 66. . .Each positive integer has up to eight neighbours in the triangle.A set of three primes is called a prime triplet if one of the three primeshas the other two as neighbours in the triangle.For example, in the second row, the prime numbers 2 and 3 are elements ofsome prime triplet.If row 8 is considered, it contains two primes which are elements of someprime triplet, i.e. 29 and 31.If row 9 is considered, it contains only one prime which is an element ofsome prime triplet: 37.Define S(n) as the sum of the primes in row n which are elements of anyprime triplet.Then S(8)=60 and S(9)=37.You are given that S(10000)=950007619.Find S(5678027) + S(7208785)."""
Problem 197
"""Project Euler Problem 197=========================Given is the function f(x) = 2^30.403243784-x^2 * 10^-9 ( is thefloor-function),the sequence u[n] is defined by u[0] = -1 and u[n+1] = f(u[n]).Find u[n] + u[n+1] for n = 10^12.Give your answer with 9 digits after the decimal point."""
Problem 198
"""Project Euler Problem 198=========================A best approximation to a real number x for the denominator bound d is arational number r/s (in reduced form) with s d, so that any rationalnumber p/q which is closer to x than r/s has q > d.Usually the best approximation to a real number is uniquely determined forall denominator bounds. However, there are some exceptions, e.g. 9/40 hasthe two best approximations 1/4 and 1/5 for the denominator bound 6.Weshall call a real number x ambiguous, if there is at least one denominatorbound for which x possesses two best approximations. Clearly, an ambiguousnumber is necessarily rational.How many ambiguous numbers x = p/q,0 < x < 1/100, are there whosedenominator q does not exceed 10^8?"""
Problem 199
"""Project Euler Problem 199=========================Three circles of equal radius are placed inside a larger circle such thateach pair of circles is tangent to one another and the inner circles donot overlap. There are four uncovered "gaps" which are to be fillediteratively with more tangent circles.At each iteration, a maximally sized circle is placed in each gap, whichcreates more gaps for the next iteration. After 3 iterations (pictured),there are 108 gaps and the fraction of the area which is not covered bycircles is 0.06790342, rounded to eight decimal places.What fraction of the area is not covered by circles after 10 iterations?Give your answer rounded to eight decimal places using the formatx.xxxxxxxx ."""
Problem 200
"""Project Euler Problem 200=========================We shall define a sqube to be a number of the form, p^2q^3, where p and qare distinct primes.For example, 200 = 5^22^3 or 120072949 = 23^261^3.The first five squbes are 72, 108, 200, 392, and 500.Interestingly, 200 is also the first number for which you cannot changeany single digit to make a prime; we shall call such numbers, prime-proof.The next prime-proof sqube which contains the contiguous sub-string "200"is 1992008.Find the 200th prime-proof sqube containing the contiguous sub-string"200"."""
Problem 201
"""Project Euler Problem 201=========================For any set A of numbers, let sum(A) be the sum of the elements of A.Consider the set B = {1,3,6,8,10,11}.There are 20 subsets of B containing three elements, and their sums are:sum({1,3,6}) = 10,sum({1,3,8}) = 12,sum({1,3,10}) = 14,sum({1,3,11}) = 15,sum({1,6,8}) = 15,sum({1,6,10}) = 17,sum({1,6,11}) = 18,sum({1,8,10}) = 19,sum({1,8,11}) = 20,sum({1,10,11}) = 22,sum({3,6,8}) = 17,sum({3,6,10}) = 19,sum({3,6,11}) = 20,sum({3,8,10}) = 21,sum({3,8,11}) = 22,sum({3,10,11}) = 24,sum({6,8,10}) = 24,sum({6,8,11}) = 25,sum({6,10,11}) = 27,sum({8,10,11}) = 29.Some of these sums occur more than once, others are unique.For a set A, let U(A,k) be the set of unique sums of k-element subsets ofA, in our example we find U(B,3) = {10,12,14,18,21,25,27,29} andsum(U(B,3)) = 156.Now consider the 100-element set S = {1^2, 2^2, ... , 100^2}.S has 100891344545564193334812497256 50-element subsets.Determine the sum of all integers which are the sum of exactly one of the50-element subsets of S, i.e. find sum(U(S,50))."""
Problem 202
"""Project Euler Problem 202=========================Three mirrors are arranged in the shape of an equilateral triangle, withtheir reflective surfaces pointing inwards. There is an infinitesimal gapat each vertex of the triangle through which a laser beam may pass.Label the vertices A, B and C. There are 2 ways in which a laser beam mayenter vertex C, bounce off 11 surfaces, then exit through the same vertex:one way is shown below; the other is the reverse of that.[Image: 202_laserbeam.gif]There are 80840 ways in which a laser beam may enter vertex C, bounce off1000001 surfaces, then exit through the same vertex.In how many ways can a laser beam enter at vertex C, bounce off12017639147 surfaces, then exit through the same vertex?"""
Problem 203
"""Project Euler Problem 203=========================The binomial coefficients ^nC[k] can be arranged in triangular form,Pascal's triangle, like this: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 .........It can be seen that the first eight rows of Pascal's triangle containtwelve distinct numbers: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 and 35.A positive integer n is called squarefree if no square of a prime dividesn.Of the twelve distinct numbers in the first eight rows of Pascal'striangle, all except 4 and 20 are squarefree.The sum of the distinctsquarefree numbers in the first eight rows is 105.Find the sum of the distinct squarefree numbers in the first 51 rows ofPascal's triangle."""
Problem 204
"""Project Euler Problem 204=========================A Hamming number is a positive number which has no prime factor largerthan 5.So the first few Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.There are 1105 Hamming numbers not exceeding 10^8.We will call a positive number a generalised Hamming number of type n, ifit has no prime factor larger than n.Hence the Hamming numbers are the generalised Hamming numbers of type 5.How many generalised Hamming numbers of type 100 are there which don'texceed 10^9?"""
Problem 205
"""Project Euler Problem 205=========================Peter has nine four-sided (pyramidal) dice, each with faces numbered 1, 2,3, 4.Colin has six six-sided (cubic) dice, each with faces numbered 1, 2, 3, 4,5, 6.Peter and Colin roll their dice and compare totals: the highest totalwins. The result is a draw if the totals are equal.What is the probability that Pyramidal Pete beats Cubic Colin? Give youranswer rounded to seven decimal places in the form 0.abcdefg"""
Problem 206
"""Project Euler Problem 206=========================Find the unique positive integer whose square has the form1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit."""
Problem 207
"""Project Euler Problem 207=========================For some positive integers k, there exists an integer partition of theform 4^t = 2^t + k, where 4^t, 2^t, and k are all positive integers andt is a real number.The first two such partitions are 4^1 = 2^1 + 2 and 4^1.5849625... =2^1.5849625... + 6.Partitions where t is also an integer are called perfect.For any m ≥ 1 let P(m) be the proportion of such partitions that areperfect with k ≤ m.Thus P(6) = 1/2.In the following table are listed some values of P(m) P(5) = 1/1 P(10) = 1/2 P(15) = 2/3 P(20) = 1/2 P(25) = 1/2 P(30) = 2/5 ... P(180) = 1/4 P(185) = 3/13Find the smallest m for which P(m) < 1/12345"""
Problem 208
"""Project Euler Problem 208=========================A robot moves in a series of one-fifth circular arcs (72°), with a freechoice of a clockwise or an anticlockwise arc for each step, but noturning on the spot.One of 70932 possible closed paths of 25 arcs starting northward is:[Image: 208_robotwalk.gif]Given that the robot starts facing North, how many journeys of 70 arcs inlength can it take that return it, after the final arc, to its startingposition?(Any arc may be traversed multiple times.)"""
Problem 209
"""Project Euler Problem 209=========================A k-input binary truth table is a map from k input bits(binary digits, 0[false] or 1 [true]) to 1 output bit. For example, the 2-input binarytruth tables for the logical AND and XOR functions are: ┌────┬────┬─────────┐ ┌────┬────┬─────────┐ │ x │ y │ x AND y │ │ x │ y │ x XOR y │ ├────┼────┼─────────┤ ├────┼────┼─────────┤ │ 0 │ 0 │ 0 │ │ 0 │ 0 │ 0 │ ├────┼────┼─────────┤ ├────┼────┼─────────┤ │ 0 │ 1 │ 0 │ │ 0 │ 1 │ 1 │ ├────┼────┼─────────┤ ├────┼────┼─────────┤ │ 1 │ 0 │ 0 │ │ 1 │ 0 │ 1 │ ├────┼────┼─────────┤ ├────┼────┼─────────┤ │ 1 │ 1 │ 1 │ │ 1 │ 1 │ 0 │ └────┴────┴─────────┘ └────┴────┴─────────┘How many 6-input binary truth tables, τ, satisfy the formula τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0"""
Problem 210
"""Project Euler Problem 210========================= Consider the set S(r) of points (x,y) with integer coordinates satisfying |x| + |y| ≤ r. Let O be the point (0,0) and C the point (r/4,r/4). Let N(r) be the number of points B in S(r), so that the triangle OBC has an obtuse angle, i.e. the largest angle α satisfies 90°<α<180°. So, for example, N(4)=24 and N(8)=100. What is N(1,000,000,000)?"""
Problem 211
"""Project Euler Problem 211=========================For a positive integer n, let σ[2](n) be the sum of the squares of itsdivisors. For example, σ[2](10) = 1 + 4 + 25 + 100 = 130.Find the sum of all n, 0 < n < 64,000,000 such that σ[2](n) is a perfectsquare."""
Problem 212
"""Project Euler Problem 212=========================An axis-aligned cuboid, specified by parameters { (x[0],y[0],z[0]),(dx,dy,dz) }, consists of all points (X,Y,Z) such that x[0] ≤ X ≤ x[0]+dx,y[0] ≤ Y ≤ y[0]+dy and z[0] ≤ Z ≤ z[0]+dz. The volume of the cuboid is theproduct, dx × dy × dz. The combined volume of a collection of cuboids isthe volume of their union and will be less than the sum of the individualvolumes if any cuboids overlap.Let C[1],...,C[50000] be a collection of 50000 axis-aligned cuboids suchthat C[n] has parametersx[0] = S[6n-5] modulo 10000y[0] = S[6n-4] modulo 10000z[0] = S[6n-3] modulo 10000dx = 1 + (S[6n-2] modulo 399)dy = 1 + (S[6n-1] modulo 399)dz = 1 + (S[6n] modulo 399)where S[1],...,S[300000] come from the "Lagged Fibonacci Generator":For 1 ≤ k ≤ 55, S[k] = [100003 - 200003k + 300007k^3] (modulo 1000000)For 56 ≤ k, S[k] = [S[k-24] + S[k-55]] (modulo 1000000)Thus, C[1] has parameters {(7,53,183),(94,369,56)}, C[2] has parameters{(2383,3563,5079),(42,212,344)}, and so on.The combined volume of the first 100 cuboids, C[1],...,C[100], is723581599.What is the combined volume of all 50000 cuboids, C[1],...,C[50000]?"""
Problem 213
"""Project Euler Problem 213=========================A 30×30 grid of squares contains 900 fleas, initially one flea per square.When a bell is rung, each flea jumps to an adjacent square at random(usually 4 possibilities, except for fleas on the edge of the grid or atthe corners).What is the expected number of unoccupied squares after 50 rings of thebell? Give your answer rounded to six decimal places."""
Problem 214
"""Project Euler Problem 214=========================Let φ be Euler's totient function, i.e. for a natural number n,φ(n) is thenumber of k, 1 ≤ k ≤ n, for which gcd(k,n) = 1.By iterating φ, each positive integer generates a decreasing chain ofnumbers ending in 1.E.g. if we start with 5 the sequence 5,4,2,1 is generated.Here is a listing of all chains with length 4: 5,4,2,1 7,6,2,1 8,4,2,1 9,6,2,1 10,4,2,1 12,4,2,1 14,6,2,1 18,6,2,1Only two of these chains start with a prime, their sum is 12.What is the sum of all primes less than 40000000 which generate a chain oflength 25?"""
Problem 215
"""Project Euler Problem 215=========================Consider the problem of building a wall out of 2×1 and 3×1 bricks(horizontal×vertical dimensions) such that, for extra strength, the gapsbetween horizontally-adjacent bricks never line up in consecutive layers,i.e. never form a "running crack".For example, the following 9×3 wall is not acceptable due to the runningcrack shown in red:[Image: 215_crackfree.gif]There are eight ways of forming a crack-free 9×3 wall, written W(9,3) = 8.Calculate W(32,10)."""
Problem 216
"""Project Euler Problem 216========================= Consider numbers t(n) of the form t(n) = 2n^2-1 with n > 1. The first such numbers are 7, 17, 31, 49, 71, 97, 127 and 161. It turns out that only 49 = 7*7 and 161 = 7*23 are not prime. For n ≤ 10000 there are 2202 numbers t(n) that are prime. How many numbers t(n) are prime for n ≤ 50,000,000?"""
Problem 217
"""Project Euler Problem 217=========================A positive integer with k (decimal) digits is called balanced if its first⌈^k/[2]⌉ digits sum to the same value as its last ⌈^k/[2]⌉ digits, where⌈x⌉, pronounced ceiling of x, is the smallest integer ≥ x, thus ⌈π⌉ = 4and ⌈5⌉ = 5.So, for example, all palindromes are balanced, as is 13722.Let T(n) be the sum of all balanced numbers less than 10^n.Thus: T(1) = 45, T(2) = 540 and T(5) = 334795890.Find T(47) mod 3^15"""
Problem 218
"""Project Euler Problem 218=========================Consider the right angled triangle with sides a=7, b=24 and c=25.The areaof this triangle is 84, which is divisible by the perfect numbers 6 and28.Moreover it is a primitive right angled triangle as gcd(a,b)=1 andgcd(b,c)=1.Also c is a perfect square.We will call a right angled triangle perfect if-it is a primitive right angled triangle-its hypotenuse is a perfect squareWe will call a right angled triangle super-perfect if-it is a perfect right angled triangle and-its area is a multiple of the perfect numbers 6 and 28.How many perfect right-angled triangles with c≤10^16 exist that are notsuper-perfect?"""
Problem 219
"""Project Euler Problem 219=========================Let A and B be bit strings (sequences of 0's and 1's).If A is equal to the leftmost length(A) bits of B, then A is said to be aprefix of B.For example, 00110 is a prefix of 001101001, but not of 00111 or 100110.A prefix-free code of size n is a collection of n distinct bit stringssuch that no string is a prefix of any other. For example, this is aprefix-free code of size 6: 0000, 0001, 001, 01, 10, 11Now suppose that it costs one penny to transmit a '0' bit, but four penceto transmit a '1'.Then the total cost of the prefix-free code shown above is 35 pence, whichhappens to be the cheapest possible for the skewed pricing scheme inquestion.In short, we write Cost(6) = 35.What is Cost(10^9) ?"""
Problem 220
"""Project Euler Problem 220=========================Let D[0] be the two-letter string "Fa". For n≥1, derive D[n] from D[n-1]by the string-rewriting rules:"a" → "aRbFR""b" → "LFaLb"Thus, D[0] = "Fa", D[1] = "FaRbFR", D[2] = "FaRbFRRLFaLbFR", and so on.These strings can be interpreted as instructions to a computer graphicsprogram, with "F" meaning "draw forward one unit", "L" meaning "turn left90 degrees", "R" meaning "turn right 90 degrees", and "a" and "b" beingignored. The initial position of the computer cursor is (0,0), pointing uptowards (0,1).Then D[n] is an exotic drawing known as the Heighway Dragon of order n.For example, D[10] is shown below; counting each "F" as one step, thehighlighted spot at (18,16) is the position reached after 500 steps.[Image: 220.gif]What is the position of the cursor after 10^12 steps in D[50]?Give your answer in the form x,y with no spaces."""
Problem 221
"""Project Euler Problem 221=========================We shall call a positive integer A an "Alexandrian integer", if thereexist integers p, q, r such that:A = p · q · r and 1 = 1 + 1 + 1 A p q rFor example, 630 is an Alexandrian integer (p = 5, q = −7, r = −18).Infact, 630 is the 6th Alexandrian integer, the first 6 Alexandrianintegers being: 6, 42, 120, 156, 420 and 630.Find the 150000th Alexandrian integer."""
Problem 222
"""Project Euler Problem 222=========================What is the length of the shortest pipe, of internal radius 50mm, that canfully contain 21 balls of radii 30mm, 31mm, ..., 50mm?Give your answer in micrometres (10^-6 m) rounded to the nearest integer."""
Problem 223
"""Project Euler Problem 223=========================Let us call an integer sided triangle with sides a ≤ b ≤ c barely acute ifthe sides satisfy a^2 + b^2 = c^2 + 1.How many barely acute triangles are there with perimeter ≤ 25,000,000?"""
Problem 224
"""Project Euler Problem 224=========================Let us call an integer sided triangle with sides a ≤ b ≤ c barely obtuseif the sides satisfy a^2 + b^2 = c^2 - 1.How many barely obtuse triangles are there with perimeter ≤ 75,000,000?"""
Problem 225
"""Project Euler Problem 225=========================The sequence 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 ...is defined by T[1] = T[2] = T[3] = 1 and T[n] = T[n-1] + T[n-2] + T[n-3].It can be shown that 27 does not divide any terms of this sequence.In fact, 27 is the first odd number with this property.Find the 124th odd number that does not divide any terms of the abovesequence."""
Problem 226
"""Project Euler Problem 226=========================The blancmange curve is the set of points (x,y) such that 0 ≤ x ≤ 1 and[Image: 226_formula.gif]where s(x) = the distance from x to the nearest integer.The area under the blancmange curve is equal to ½, shown in pink in thediagram below.[Image: 226_scoop2.gif]Let C be the circle with centre (¼,½) and radius ¼, shown in black in thediagram.What area under the blancmange curve is enclosed by C?Give your answer rounded to eight decimal places in the form 0.abcdefgh"""
Problem 227
"""Project Euler Problem 227========================="The Chase" is a game played with two dice and an even number of players.The players sit around a table; the game begins with two opposite playershaving one die each. On each turn, the two players with a die roll it.If a player rolls a 1, he passes the die to his neighbour on the left; ifhe rolls a 6, he passes the die to his neighbour on the right; otherwise,he keeps the die for the next turn.The game ends when one player has both dice after they have been rolledand passed; that player has then lost.In a game with 100 players, what is the expected number of turns the gamelasts?Give your answer rounded to ten significant digits."""
Problem 228
"""Project Euler Problem 228=========================Let S[n] be the regular n-sided polygon – or shape – whose vertices v[k](k = 1,2,…,n) have coordinates: x[k] = cos( ^2k-1/[n] × 180° ) y[k] = sin( ^2k-1/[n] × 180° )Each S[n] is to be interpreted as a filled shape consisting of all pointson the perimeter and in the interior.The Minkowski sum, S+T, of two shapes S and T is the result of addingevery point in S to every point in T, where point addition is performedcoordinate-wise: (u, v) + (x, y) = (u+x, v+y).For example, the sum of S[3] and S[4] is the six-sided shape shown in pinkbelow:[Image: 228.png]How many sides does S[1864] + S[1865] + … + S[1909] have?"""
Problem 229
"""Project Euler Problem 229=========================Consider the number 3600. It is very special, because3600 = 48^2 + 36^23600 = 20^2 + 2×40^23600 = 30^2 + 3×30^23600 = 45^2 + 7×15^2Similarly, we find that 88201 = 99^2 + 280^2 = 287^2 + 2×54^2 = 283^2 +3×52^2 = 197^2 + 7×84^2.In 1747, Euler proved which numbers are representable as a sum of twosquares.We are interested in the numbers n which admit representations ofall of the following four types:n = a[1]^2 + b[1]^2n = a[2]^2 + 2×b[2]^2n = a[3]^2 + 3×b[3]^2n = a[7]^2 + 7×b[7]^2,where the a[k] and b[k] are positive integers.There are 75373 such numbers that do not exceed 10^7.How many such numbers are there that do not exceed 2×10^9?"""
Problem 230
"""Project Euler Problem 230=========================For any two strings of digits, A and B, we define F[A,B] to be thesequence (A,B,AB,BAB,ABBAB,...) in which each term is the concatenation ofthe previous two.Further, we define D[A,B](n) to be the n-th digit in the first term ofF[A,B] that contains at least n digits.Example:Let A=1415926535, B=8979323846. We wish to find D[A,B](35), say.The first few terms of F[A,B] are:141592653589793238461415926535897932384689793238461415926535897932384614159265358979323846897932384614159265358979323846Then D[A,B](35) is the 35th digit in the fifth term, which is 9.Now we use for A the first 100 digits of π behind the decimal point:1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679and for B the next hundred digits:8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196.Find ∑[n = 0,1,...,17] 10^n× D[A,B]((127+19n)×7^n)."""
Problem 231
"""Project Euler Problem 231=========================The binomial coefficient ^10C[3] = 120.120 = 2^3 × 3 × 5 = 2 × 2 × 2 × 3 × 5, and 2 + 2 + 2 + 3 + 5 = 14.So the sum of the terms in the prime factorisation of ^10C[3] is 14.Find the sum of the terms in the prime factorisation of^20000000C[15000000]."""
Problem 232
"""Project Euler Problem 232=========================Two players share an unbiased coin and take it in turns to play "TheRace". On Player 1's turn, he tosses the coin once: if it comes up Heads,he scores one point; if it comes up Tails, he scores nothing. On Player2's turn, she chooses a positive integer T and tosses the coin T times: ifit comes up all Heads, she scores 2^T-1 points; otherwise, she scoresnothing. Player 1 goes first. The winner is the first to 100 or morepoints.On each turn Player 2 selects the number, T, of coin tosses that maximisesthe probability of her winning.What is the probability that Player 2 wins?Give your answer rounded to eight decimal places in the form 0.abcdefgh."""
Problem 233
"""Project Euler Problem 233=========================Let f(N) be the number of points with integer coordinates that are on acircle passing through (0,0), (N,0),(0,N), and (N,N).It can be shown that f(10000) = 36.What is the sum of all positive integers N ≤ 10^11 such that f(N) = 420?"""
Problem 234
"""Project Euler Problem 234=========================For an integer n ≥ 4, we define the lower prime square root of n, denotedby lps(n), as the largest prime ≤ √n and the upper prime square root of n,ups(n), as the smallest prime ≥ √n.So, for example, lps(4) = 2 = ups(4), lps(1000) = 31, ups(1000) = 37.Let us call an integer n ≥ 4 semidivisible, if one of lps(n) and ups(n)divides n, but not both.The sum of the semidivisible numbers not exceeding 15 is 30, the numbersare 8, 10 and 12.15 is not semidivisible because it is a multiple of both lps(15) = 3 andups(15) = 5.As a further example, the sum of the 92 semidivisible numbers up to 1000is 34825.What is the sum of all semidivisible numbers not exceeding 999966663333?"""
Problem 235
"""Project Euler Problem 235=========================Given is the arithmetic-geometric sequence u(k) = (900-3k)r^k-1.Let s(n) = Σ[k=1...n]u(k).Find the value of r for which s(5000) = -600,000,000,000.Give your answer rounded to 12 places behind the decimal point."""
Problem 236
"""Project Euler Problem 236=========================Suppliers 'A' and 'B' provided the following numbers of products for theluxury hamper market: Product 'A' 'B' Beluga Caviar 5248 640 Christmas Cake 1312 1888 Gammon Joint 2624 3776 Vintage Port 5760 3776 Champagne Truffles 3936 5664Although the suppliers try very hard to ship their goods in perfectcondition, there is inevitably some spoilage - i.e. products gone bad.The suppliers compare their performance using two types of statistic: • The five per-product spoilage rates for each supplier are equal to the number of products gone bad divided by the number of products supplied, for each of the five products in turn. • The overall spoilage rate for each supplier is equal to the total number of products gone bad divided by the total number of products provided by that supplier.To their surprise, the suppliers found that each of the five per-productspoilage rates was worse (higher) for 'B' than for 'A' by the same factor(ratio of spoilage rates), m>1; and yet, paradoxically, the overallspoilage rate was worse for 'A' than for 'B', also by a factor of m.There are thirty-five m>1 for which this surprising result could haveoccurred, the smallest of which is 1476/1475.What's the largest possible value of m?Give your answer as a fraction reduced to its lowest terms, in the formu/v."""
Problem 237
"""Project Euler Problem 237=========================Let T(n) be the number of tours over a 4 × n playing board such that: • The tour starts in the top left corner. • The tour consists of moves that are up, down, left, or right one square. • The tour visits each square exactly once. • The tour ends in the bottom left corner.The diagram shows one tour over a 4 × 10 board:[Image: 237.gif]T(10) is 2329. What is T(10^12) modulo 10^8?"""
Problem 238
"""Project Euler Problem 238=========================Create a sequence of numbers using the "Blum Blum Shub" pseudo-randomnumber generator: s[0] = 14025256 s[n+1] = s[n]^2 mod 20300713Concatenate these numbers s[0]s[1]s[2]… to create a string w of infinitelength.Then, w = 14025256741014958470038053646…For a positive integer k, if no substring of w exists with a sum of digitsequal to k, p(k) is defined to be zero. If at least one substring of wexists with a sum of digits equal to k, we define p(k) = z, where z is thestarting position of the earliest such substring.For instance:The substrings 1, 14, 1402, …with respective sums of digits equal to 1, 5, 7, …start at position 1, hence p(1) = p(5) = p(7) = … = 1.The substrings 4, 402, 4025, …with respective sums of digits equal to 4, 6, 11, …start at position 2, hence p(4) = p(6) = p(11) = … = 2.The substrings 02, 0252, …with respective sums of digits equal to 2, 9, …start at position 3, hence p(2) = p(9) = … = 3.Note that substring 025 starting at position 3, has a sum of digits equalto 7, but there was an earlier substring (starting at position 1) with asum of digits equal to 7, so p(7) = 1, not 3.We can verify that, for 0 < k ≤ 10^3, ∑ p(k) = 4742.Find ∑ p(k), for 0 < k ≤ 2·10^15."""
Problem 239
"""Project Euler Problem 239=========================A set of disks numbered 1 through 100 are placed in a line in randomorder.What is the probability that we have a partial derangement such thatexactly 22 prime number discs are found away from their natural positions?(Any number of non-prime disks may also be found in or out of theirnatural positions.)Give your answer rounded to 12 places behind the decimal point in the form0.abcdefghijkl."""
Problem 240
"""Project Euler Problem 240=========================There are 1111 ways in which five 6-sided dice (sides numbered 1 to 6) canbe rolled so that the top three sum to 15. Some examples are:D[1],D[2],D[3],D[4],D[5] = 4,3,6,3,5D[1],D[2],D[3],D[4],D[5] = 4,3,3,5,6D[1],D[2],D[3],D[4],D[5] = 3,3,3,6,6D[1],D[2],D[3],D[4],D[5] = 6,6,3,3,3In how many ways can twenty 12-sided dice (sides numbered 1 to 12) berolled so that the top ten sum to 70?"""
Problem 241
"""Project Euler Problem 241=========================For a positive integer n, let σ(n) be the sum of all divisors of n, soe.g. σ(6) = 1 + 2 + 3 + 6 = 12.A perfect number, as you probably know, is a number with σ(n) = 2n.Let us define the perfection quotient of a positive integer asp(n) = σ(n) / n.Find the sum of all positive integers n ≤ 10^18 for which p(n) has theform k + ^1⁄[2], where k is an integer."""
Problem 242
"""Project Euler Problem 242=========================Given the set {1,2,...,n}, we define f(n,k) as the number of its k-elementsubsets with an odd sum of elements. For example, f(5,3) = 4, since theset {1,2,3,4,5} has four 3-element subsets having an odd sum of elements,i.e.: {1,2,4}, {1,3,5}, {2,3,4} and {2,4,5}.When all three values n, k and f(n,k) are odd, we say that they makean odd-triplet [n,k,f(n,k)].There are exactly five odd-triplets with n ≤ 10, namely:[1,1,f(1,1) = 1], [5,1,f(5,1) = 3], [5,5,f(5,5) = 1], [9,1,f(9,1) = 5] and[9,9,f(9,9) = 1].How many odd-triplets are there with n ≤ 10^12?"""
Problem 243
"""Project Euler Problem 243=========================A positive fraction whose numerator is less than its denominator is calleda proper fraction.For any denominator, d, there will be d−1 proper fractions; for example,with d = 12:1/12 , 2/12 , 3/12 , 4/12 , 5/12 , 6/12 , 7/12 ,8/12 , 9/12 , 10/12 , 11/12 .We shall call a fraction that cannot be cancelled down a resilientfraction.Furthermore we shall define the resilience of a denominator, R(d), to bethe ratio of its proper fractions that are resilient; for example, R(12) =4/11.In fact, d = 12 is the smallest denominator having a resilience R(d) <4/10.Find the smallest denominator d, having a resilience R(d) < 15499/94744."""
Problem 244
"""Project Euler Problem 244=========================You probably know the game Fifteen Puzzle. Here, instead of numberedtiles, we have seven red tiles and eight blue tiles.A move is denoted by the uppercase initial of the direction (Left, Right,Up, Down) in which the tile is slid, e.g. starting from configuration (S),by the sequence LULUR we reach the configuration (E):(S): [Image: 244_start.gif](E): [Image: 244_example.gif]For each path, its checksum is calculated by (pseudocode):checksum = 0checksum = (checksum × 243 + m[1]) mod 100 000 007checksum = (checksum × 243 + m[2]) mod 100 000 007 …checksum = (checksum × 243 + m[n]) mod 100 000 007where m[k] is the ASCII value of the k-th letter in the move sequence and the ASCII values for the moves are: ┌──────┬─────┐ │L │76 │ ├──────┼─────┤ │R │82 │ ├──────┼─────┤ │U │85 │ ├──────┼─────┤ │D │68 │ └──────┴─────┘For the sequence LULUR given above, the checksum would be 19761398.Now, starting from configuration (S), find all shortest ways to reachconfiguration (T).(S): [Image: 244_start.gif](T): [Image: 244_target.gif]What is the sum of all checksums for the paths having the minimal length?"""
Problem 245
"""Project Euler Problem 245=========================We shall call a fraction that cannot be cancelled down a resilientfraction. Furthermore we shall define the resilience of a denominator,R(d), to be the ratio of its proper fractions that are resilient; forexample, R(12) = 4⁄/11.The resilience of a number d > 1 is then φ(d) / (d - 1), where φ is Euler'stotient function.We further define the coresilience of a number n > 1 asC(n) = (n - φ(n)) / (n-1).The coresilience of a prime p is C(p) = 1 / (p - 1).Find the sum of all composite integers 1 < n ≤ 2×10^11, for which C(n) isa unit fraction."""
Problem 246
"""Project Euler Problem 246=========================A definition for an ellipse is:Given a circle c with centre M and radius r and a point G such thatd(G,M)<r, the locus of the points that are equidistant from c and G forman ellipse.The construction of the points of the ellipse is shown below.[Image: 246_anim.gif]Given are the points M(-2000,1500) and G(8000,1500).Given is also the circle c with centre M and radius 15000.The locus of the points that are equidistant from G and c form an ellipsee.From a point P outside e the two tangents t[1] and t[2] to the ellipse aredrawn.Let the points where t[1] and t[2] touch the ellipse be R and S.[Image: 246_ellipse.gif]For how many lattice points P is angle RPS greater than 45 degrees?"""
Problem 247
"""Project Euler Problem 247=========================Consider the region constrained by 1 ≤ x and 0 ≤ y ≤ 1/x.Let S[1] be the largest square that can fit under the curve.Let S[2] be the largest square that fits in the remaining area, and so on.Let the index of S[n] be the pair (left, below) indicating the number ofsquares to the left of S[n] and the number of squares below S[n].[Image: 247_hypersquares.gif]The diagram shows some such squares labelled by number.S[2] has one square to its left and none below, so the index of S[2] is(1,0).It can be seen that the index of S[32] is (1,1) as is the index of S[50].50 is the largest n for which the index of S[n] is (1,1).What is the largest n for which the index of S[n] is (3,3)?"""
Problem 248
"""Project Euler Problem 248=========================The first number n for which φ(n)=13! is 6227180929.Find the 150,000th such number."""
Problem 249
"""Project Euler Problem 249=========================Let S = {2, 3, 5, ..., 4999} be the set of prime numbers less than 5000.Find the number of subsets of S, the sum of whose elements is a primenumber.Enter the rightmost 16 digits as your answer."""
Problem 250
"""Project Euler Problem 250=========================Find the number of non-empty subsets of {1^1, 2^2, 3^3, ...,250250^250250}, the sum of whose elements is divisible by 250. Enter therightmost 16 digits as your answer."""
Problem 251
"""Project Euler Problem 251=========================A triplet of positive integers (a,b,c) is called a Cardano Triplet if itsatisfies the condition:[Image: 251_cardano.gif]For example, (2,1,5) is a Cardano Triplet.There exist 149 Cardano Triplets for which a+b+c ≤ 1000.Find how many Cardano Triplets exist such that a+b+c ≤ 110,000,000."""
Problem 252
"""Project Euler Problem 252=========================Given a set of points on a plane, we define a convex hole to be a convexpolygon having as vertices any of the given points and not containing anyof the given points in its interior (in addition to the vertices, othergiven points may lie on the perimeter of the polygon).As an example, the image below shows a set of twenty points and a few suchconvex holes. The convex hole shown as a red heptagon has an area equal to1049694.5 square units, which is the highest possible area for a convexhole on the given set of points.[Image: 252_convexhole.gif]For our example, we used the first 20 points (T[2k−1], T[2k]), fork = 1,2,…,20, produced with the pseudo-random number generator: S[0] = 290797 S[n+1] = S[n]^2 mod 50515093 T[n] = ( S[n] mod 2000 ) − 1000i.e. (527, 144), (−488, 732), (−454, −947), …What is the maximum area for a convex hole on the set containing the first500 points in the pseudo-random sequence?Specify your answer including one digit after the decimal point."""
Problem 253
"""Project Euler Problem 253=========================A small child has a “number caterpillar” consisting of forty jigsawpieces, each with one number on it, which, when connected together in aline, reveal the numbers 1 to 40 in order.Every night, the child's father has to pick up the pieces of thecaterpillar that have been scattered across the play room. He picks up thepieces at random and places them in the correct order.As the caterpillar is built up in this way, it forms distinct segmentsthat gradually merge together.The number of segments starts at zero (no pieces placed), generallyincreases up to about eleven or twelve, then tends to drop again beforefinishing at a single segment (all pieces placed).For example: ┌────────────┬───────────────┐ │Piece Placed│Segments So Far│ ├────────────┼───────────────┤ │ 12 │ 1 │ ├────────────┼───────────────┤ │ 4 │ 2 │ ├────────────┼───────────────┤ │ 29 │ 3 │ ├────────────┼───────────────┤ │ 6 │ 4 │ ├────────────┼───────────────┤ │ 34 │ 5 │ ├────────────┼───────────────┤ │ 5 │ 4 │ ├────────────┼───────────────┤ │ 35 │ 4 │ ├────────────┼───────────────┤ │ … │ … │ └────────────┴───────────────┘Let M be the maximum number of segments encountered during a randomtidy-up of the caterpillar.For a caterpillar of ten pieces, the number of possibilities for each M is ┌────────┬─────────────┐ │ M │Possibilities│ ├────────┼─────────────┤ │ 1 │ 512 │ ├────────┼─────────────┤ │ 2 │ 250912 │ ├────────┼─────────────┤ │ 3 │1815264 │ ├────────┼─────────────┤ │ 4 │1418112 │ ├────────┼─────────────┤ │ 5 │ 144000 │ └────────┴─────────────┘so the most likely value of M is 3 and the average value is^385643⁄[113400] = 3.400732, rounded to six decimal places.The most likely value of M for a forty-piece caterpillar is 11; but whatis the average value of M?Give your answer rounded to six decimal places."""
Problem 254
"""Project Euler Problem 254=========================Define f(n) as the sum of the factorials of the digits of n. For example,f(342) = 3! + 4! + 2! = 32.Define sf(n) as the sum of the digits of f(n). So sf(342) = 3 + 2 = 5.Define g(i) to be the smallest positive integer n such that sf(n) = i.Though sf(342) is 5, sf(25) is also 5, and it can be verified that g(5) is25.Define sg(i) as the sum of the digits of g(i). So sg(5) = 2 + 5 = 7.Further, it can be verified that g(20) is 267 and ∑ sg(i) for 1 ≤ i ≤ 20is 156.What is ∑ sg(i) for 1 ≤ i ≤ 150?"""
Problem 255
"""Project Euler Problem 255=========================We define the rounded-square-root of a positive integer n as the squareroot of n rounded to the nearest integer.The following procedure (essentially Heron's method adapted to integerarithmetic) finds the rounded-square-root of n:Let d be the number of digits of the number n.If d is odd, set x[0] = 2×10^((d-1)⁄/2).If d is even, set x[0] = 7×10^((d-2)⁄/2).Repeat:[Image: 255_Heron.gif]until x[k+1] = x[k].As an example, let us find the rounded-square-root of n = 4321.n has 4 digits, so x[0] = 7×10^(4-2)⁄2 = 70.[Image: 255_Example.gif]Since x[2] = x[1], we stop here.So, after just two iterations, we have found that the rounded-square-rootof 4321 is 66 (the actual square root is 65.7343137…).The number of iterations required when using this method is surprisinglylow.For example, we can find the rounded-square-root of a 5-digit integer(10,000 ≤ n ≤ 99,999) with an average of 3.2102888889 iterations (theaverage value was rounded to 10 decimal places).Using the procedure described above, what is the average number ofiterations required to find the rounded-square-root of a 14-digit number(10^13 ≤ n < 10^14)?Give your answer rounded to 10 decimal places.Note: The symbols ⌊x⌋ and ⌈x⌉ represent the floor function and ceilingfunction respectively."""
Problem 256
"""Project Euler Problem 256=========================Tatami are rectangular mats, used to completely cover the floor of a room,without overlap.Assuming that the only type of available tatami has dimensions 1×2, thereare obviously some limitations for the shape and size of the rooms thatcan be covered.For this problem, we consider only rectangular rooms with integerdimensions a, b and even size s = a·b.We use the term 'size' to denote the floor surface area of the room, and —without loss of generality — we add the condition a ≤ b.There is one rule to follow when laying out tatami: there must be nopoints where corners of four different mats meet.For example, consider the two arrangements below for a 4×4 room:[Image: 256_tatami3.gif]The arrangement on the left is acceptable, whereas the one on the right isnot: a red "X" in the middle, marks the point where four tatami meet.Because of this rule, certain even-sized rooms cannot be covered withtatami: we call them tatami-free rooms.Further, we define T(s) as the number of tatami-free rooms of size s.The smallest tatami-free room has size s = 70 and dimensions 7×10.All the other rooms of size s = 70 can be covered with tatami; they are:1×70, 2×35 and 5×14.Hence, T(70) = 1.Similarly, we can verify that T(1320) = 5 because there are exactly 5tatami-free rooms of size s = 1320:20×66, 22×60, 24×55, 30×44 and 33×40.In fact, s = 1320 is the smallest room-size s for which T(s) = 5.Find the smallest room-size s for which T(s) = 200."""
Problem 257
"""Project Euler Problem 257=========================Given is an integer sided triangle ABC with sides a ≤ b ≤ c. (AB = c, BC =a and AC = b).The angular bisectors of the triangle intersect the sides at points E, Fand G (see picture below).[Image: 257_bisector.gif]The segments EF, EG and FG partition the triangle ABC into four smallertriangles: AEG, BFE, CGF and EFG.It can be proven that for each of these four triangles the ratioarea(ABC)/area(subtriangle) is rational.However, there exist triangles for which some or all of these ratios areintegral.How many triangles ABC with perimeter ≤ 100,000,000 exist so that the ratioarea(ABC)/area(AEG) is integral?"""
Problem 258
"""Project Euler Problem 258=========================A sequence is defined as: • g[k] = 1, for 0 ≤ k ≤ 1999 • g[k] = g[k-2000] + g[k-1999], for k ≥ 2000.Find g[k] mod 20092010 for k = 10^18."""
Problem 259
"""Project Euler Problem 259=========================A positive integer will be called reachable if it can result from anarithmetic expression obeying the following rules: • Uses the digits 1 through 9, in that order and exactly once each. • Any successive digits can be concatenated (for example, using the digits 2, 3 and 4 we obtain the number 234). • Only the four usual binary arithmetic operations (addition, subtraction, multiplication and division) are allowed. • Each operation can be used any number of times, or not at all. • Unary minus is not allowed. • Any number of (possibly nested) parentheses may be used to define the order of operations.For example, 42 is reachable, since (1/23) * ((4*5)-6) * (78-9) = 42.What is the sum of all positive reachable integers?"""
Problem 260
"""Project Euler Problem 260=========================A game is played with three piles of stones and two players.At her turn, a player removes one or more stones from the piles. However,if she takes stones from more than one pile, she must remove the samenumber of stones from each of the selected piles.In other words, the player chooses some N>0 and removes: • N stones from any single pile; or • N stones from each of any two piles (2N total); or • N stones from each of the three piles (3N total).The player taking the last stone(s) wins the game.A winning configuration is one where the first player can force a win.For example, (0,0,13), (0,11,11) and (5,5,5) are winning configurationsbecause the first player can immediately remove all stones.A losing configuration is one where the second player can force a win, nomatter what the first player does.For example, (0,1,2) and (1,3,3) are losing configurations: any legal moveleaves a winning configuration for the second player.Consider all losing configurations (x[i],y[i],z[i]) where x[i] ≤ y[i] ≤z[i] ≤ 100. We can verify that Σ(x[i]+y[i]+z[i]) = 173895 for these.Find Σ(x[i]+y[i]+z[i]) where (x[i],y[i],z[i]) ranges over the losingconfigurations with x[i] ≤ y[i] ≤ z[i] ≤ 1000."""
Problem 261
"""Project Euler Problem 261=========================Let us call a positive integer k a square-pivot, if there is a pair ofintegers m > 0 and n ≥ k, such that the sum of the (m+1) consecutivesquares up to k equals the sum of the m consecutive squares from (n+1) on: (k-m)^2 + ... + k^2 = (n+1)^2 + ... + (n+m)^2.Some small square-pivots are • 4: 3^2 + 4^2 = 5^2 • 21: 20^2 + 21^2 = 29^2 • 24: 21^2 + 22^2 + 23^2 + 24^2 = 25^2 + 26^2 + 27^2 • 110: 108^2 + 109^2 + 110^2 = 133^2 + 134^2Find the sum of all distinct square-pivots ≤ 10^10."""
Problem 262
"""Project Euler Problem 262=========================The following equation represents the continuous topography of amountainous region, giving the elevation h at any point (x,y):[Image: 262_formula1.gif]A mosquito intends to fly from A(200,200) to B(1400,1400), without leavingthe area given by 0 ≤ x, y ≤ 1600.Because of the intervening mountains, it first rises straight up to apoint A', having elevation f. Then, while remaining at the same elevationf, it flies around any obstacles until it arrives at a point B' directlyabove B.First, determine f[min] which is the minimum constant elevation allowingsuch a trip from A to B, while remaining in the specified area.Then, find the length of the shortest path between A' and B', while flyingat that constant elevation f[min].Give that length as your answer, rounded to three decimal places.Note: For convenience, the elevation function in the image above can bewritten as the following in Python (the math module must be imported):def elevation(x, y): first = 5000.0 - ((x**2 + y**2 + x*y)/200.0) + (12.5*(x+y)) second = (0.000001 * (x**2 + y**2)) - (0.0015*(x+y)) + 0.7 return first * math.exp(-abs(second))"""
Problem 263
"""Project Euler Problem 263=========================Consider the number 6. The divisors of 6 are: 1,2,3 and 6.Every number from 1 up to and including 6 can be written as a sum ofdistinct divisors of 6: 1=1, 2=2, 3=1+2, 4=1+3, 5=2+3, 6=6.A number n is called a practical number if every number from 1 up to andincluding n can be expressed as a sum of distinct divisors of n.A pair of consecutive prime numbers with a difference of six is called asexy pair (since "sex" is the Latin word for "six"). The first sexy pairis (23, 29).We may occasionally find a triple-pair, which means three consecutive sexyprime pairs, such that the second member of each pair is the first memberof the next pair.We shall call a number n such that: • (n-9, n-3), (n-3,n+3), (n+3, n+9) form a triple-pair, and • the numbers n-8, n-4, n, n+4 and n+8 are all practical,an engineers’ paradise.Find the sum of the first four engineers’ paradises."""
Problem 264
"""Project Euler Problem 264=========================Consider all the triangles having: • All their vertices on lattice points. • Circumcentre at the origin O. • Orthocentre at the point H(5, 0).There are nine such triangles having a perimeter ≤ 50.Listed and shown in ascending order of their perimeter, they are:A(-4, 3), B(5, 0), C(4, -3)A(4, 3), B(5, 0), C(-4, -3)A(-3, 4), B(5, 0), C(3, -4)A(3, 4), B(5, 0), C(-3, -4)A(0, 5), B(5, 0), C(0, -5)A(1, 8), B(8, -1), C(-4, -7)A(8, 1), B(1, -8), C(-4, 7)A(2, 9), B(9, -2), C(-6, -7)A(9, 2), B(2, -9), C(-6, 7)[Image: 264_TriangleCentres.gif]The sum of their perimeters, rounded to four decimal places, is 291.0089.Find all such triangles with a perimeter ≤ 10^5.Enter as your answer the sum of their perimeters rounded to four decimalplaces."""
Problem 265
"""Project Euler Problem 265=========================2^N binary digits can be placed in a circle so that all the N-digitclockwise subsequences are distinct.For N=3, two such circular arrangements are possible, ignoring rotations:[Image: 265_BinaryCircles.gif]For the first arrangement, the 3-digit subsequences, in clockwise order,are: 000, 001, 010, 101, 011, 111, 110 and 100.Each circular arrangement can be encoded as a number by concatenating thebinary digits starting with the subsequence of all zeros as the mostsignificant bits and proceeding clockwise. The two arrangements for N=3are thus represented as 23 and 29: 00010111 [2] = 23 00011101 [2] = 29Calling S(N) the sum of the unique numeric representations, we can seethat S(3) = 23 + 29 = 52.Find S(5)."""
Problem 266
"""Project Euler Problem 266=========================The divisors of 12 are: 1, 2, 3, 4, 6, and 12.The largest divisor of 12 that does not exceed the square root of 12 is 3.We shall call the largest divisor of an integer n that does not exceed thesquare root of n the pseudo square root (PSR) of n.It can be seen that PSR(3102) = 47.Let p be the product of the primes below 190. Find PSR(p) mod 10^16."""
Problem 267
"""Project Euler Problem 267=========================You are given a unique investment opportunity.Starting with £1 of capital, you can choose a fixed proportion, f, of yourcapital to bet on a fair coin toss repeatedly for 1000 tosses.Your return is double your bet for heads and you lose your bet for tails.For example, if f = 1/4, for the first toss you bet £0.25, and if headscomes up you win £0.5 and so then have £1.5. You then bet £0.375 and ifthe second toss is tails, you have £1.125.Choosing f to maximize your chances of having at least £1,000,000,000after 1,000 flips, what is the chance that you become a billionaire?All computations are assumed to be exact (no rounding), but give youranswer rounded to 12 digits behind the decimal point in the form0.abcdefghijkl."""
Problem 268
"""Project Euler Problem 268=========================It can be verified that there are 23 positive integers less than 1000 thatare divisible by at least four distinct primes less than 100.Find how many positive integers less than 10^16 are divisible by at leastfour distinct primes less than 100."""
Problem 269
"""Project Euler Problem 269=========================A root or zero of a polynomial P(x) is a solution to the equation P(x) = 0.Define P[n] as the polynomial whose coefficients are the digits of n.For example, P[5703](x) = 5x^3 + 7x^2 + 3.We can see that: • P[n](0) is the last digit of n, • P[n](1) is the sum of the digits of n, • P[n](10) is n itself.Define Z(k) as the number of positive integers, n, not exceeding k forwhich the polynomial P[n] has at least one integer root.It can be verified that Z(100 000) is 14696.What is Z(10^16)?"""
Problem 270
"""Project Euler Problem 270=========================A square piece of paper with integer dimensions N×N is placed with acorner at the origin and two of its sides along the x- and y-axes. Then,we cut it up respecting the following rules: • We only make straight cuts between two points lying on different sides of the square, and having integer coordinates. • Two cuts cannot cross, but several cuts can meet at the same border point. • Proceed until no more legal cuts can be made.Counting any reflections or rotations as distinct, we call C(N) the numberof ways to cut an N×N square. For example, C(1) = 2 and C(2) = 30 (shownbelow).[Image: 270_CutSquare.gif]What is C(30) mod 10^8?"""
Problem 271
"""Project Euler Problem 271=========================For a positive number n, define S(n) as the sum of the integers x, forwhich 1 < x < n and x^3 ≡ 1 mod n.When n=91, there are 8 possible values for x, namely: 9, 16, 22, 29, 53,74, 79, 81. Thus, S(91)=9+16+22+29+53+74+79+81=363.Find S(13082761331670030)."""
Problem 272
"""Project Euler Problem 272=========================For a positive number n, define C(n) as the number of the integers x, forwhich 1 < x < n and x^3 ≡ 1 mod n.When n=91, there are 8 possible values for x, namely: 9, 16, 22, 29, 53,74, 79, 81. Thus, C(91)=8.Find the sum of the positive numbers n ≤ 10^11 for which C(n) = 242."""
Problem 273
"""Project Euler Problem 273=========================Consider equations of the form: a^2 + b^2 = N, 0 ≤ a ≤ b, a, b and Ninteger.For N=65 there are two solutions:a=1, b=8 and a=4, b=7.We call S(N) the sum of the values of a of all solutions of a^2 + b^2 = N,0 ≤ a ≤ b, a, b and N integer.Thus S(65) = 1 + 4 = 5.Find ∑S(N), for all squarefree N only divisible by primes of the form 4k+1with 4k+1 < 150."""
Problem 274
"""Project Euler Problem 274=========================For each integer p > 1 coprime to 10 there is a positive divisibilitymultiplier m < p which preserves divisibility by p for the followingfunction on any positive integer, n:f(n) = (all but the last digit of n) + (the last digit of n) * mThat is, if m is the divisibility multiplier for p, then f(n) is divisibleby p if and only if n is divisible by p.(When n is much larger than p, f(n) will be less than n and repeatedapplication of f provides a multiplicative divisibility test for p.)For example, the divisibility multiplier for 113 is 34.f(76275) = 7627 + 5 * 34 = 7797 : 76275 and 7797 are both divisible by 113f(12345) = 1234 + 5 * 34 = 1404 : 12345 and 1404 are both not divisible by113The sum of the divisibility multipliers for the primes that are coprime to10 and less than 1000 is 39517. What is the sum of the divisibilitymultipliers for the primes that are coprime to 10 and less than 10^7?"""
Problem 275
"""Project Euler Problem 275=========================Let us define a balanced sculpture of order n as follows: • A polyomino made up of n+1 tiles known as the blocks (n tiles) and the plinth (remaining tile); • the plinth has its centre at position (x = 0, y = 0); • the blocks have y-coordinates greater than zero (so the plinth is the unique lowest tile); • the centre of mass of all the blocks, combined, has x-coordinate equal to zero.When counting the sculptures, any arrangements which are simplyreflections about the y-axis, are not counted as distinct. For example,the 18 balanced sculptures of order 6 are shown below; note that each pairof mirror images (about the y-axis) is counted as one sculpture:[Image: 275_sculptures2.gif]There are 964 balanced sculptures of order 10 and 360505 of order 15.How many balanced sculptures are there of order 18?"""
Problem 276
"""Project Euler Problem 276=========================Consider the triangles with integer sides a, b and c with a ≤ b ≤ c.An integer sided triangle (a,b,c) is called primitive if gcd(a,b,c)=1.How many primitive integer sided triangles exist with a perimeter notexceeding 10 000 000?"""
Problem 277
"""Project Euler Problem 277=========================A modified Collatz sequence of integers is obtained from a starting valuea[1] in the following way:a[n+1] = a[n]/3 if a[n] is divisible by 3. We shall denote this as a largedownward step, "D".a[n+1] = (4a[n] + 2)/3 if a[n] divided by 3 gives a remainder of 1. Weshall denote this as an upward step, "U".a[n+1] = (2a[n] - 1)/3 if a[n] divided by 3 gives a remainder of 2. Weshall denote this as a small downward step, "d".The sequence terminates when some a[n] = 1.Given any integer, we can list out the sequence of steps.For instance if a[1]=231, then the sequence{a[n]}={231,77,51,17,11,7,10,14,9,3,1} corresponds to the steps"DdDddUUdDD".Of course, there are other sequences that begin with that same sequence"DdDddUUdDD....".For instance, if a[1]=1004064, then the sequence isDdDddUUdDDDdUDUUUdDdUUDDDUdDD.In fact, 1004064 is the smallest possible a[1] > 10^6 that begins with thesequence DdDddUUdDD.What is the smallest a[1] > 10^15 that begins with the sequence"UDDDUdddDDUDDddDdDddDDUDDdUUDd"?"""
Problem 278
"""Project Euler Problem 278=========================Given the values of integers 1 < a[1] < a[2] <... < a[n], consider thelinear combinationq[1]a[1] + q[2]a[2] + ... + q[n]a[n] = b, using only integer values q[k] ≥0.Note that for a given set of a[k], it may be that not all values of b arepossible.For instance, if a[1] = 5 and a[2] = 7, there are no q[1] ≥ 0 and q[2] ≥ 0such that b could be1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 or 23.In fact, 23 is the largest impossible value of b for a[1] = 5 and a[2] =7.We therefore call f(5, 7) = 23.Similarly, it can be shown that f(6, 10, 15)=29 and f(14, 22, 77) = 195.Find ∑ f(p*q,p*r,q*r), where p, q and r are prime numbers and p < q < r <5000."""
Problem 279
"""Project Euler Problem 279=========================How many triangles are there with integral sides, at least one integralangle (measured in degrees), and a perimeter that does not exceed 10^8?"""
Problem 280
"""Project Euler Problem 280=========================A laborious ant walks randomly on a 5x5 grid. The walk starts from thecentral square. At each step, the ant moves to an adjacent square atrandom, without leaving the grid; thus there are 2, 3 or 4 possible movesat each step depending on the ant's position.At the start of the walk, a seed is placed on each square of the lowerrow. When the ant isn't carrying a seed and reaches a square of the lowerrow containing a seed, it will start to carry the seed. The ant will dropthe seed on the first empty square of the upper row it eventually reaches.What's the expected number of steps until all seeds have been dropped inthe top row? Give your answer rounded to 6 decimal places."""
Problem 281
"""Project Euler Problem 281=========================You are given a pizza (perfect circle) that has been cut into m·n equalpieces and you want to have exactly one topping on each slice.Let f(m,n) denote the number of ways you can have toppings on the pizzawith m different toppings (m ≥ 2), using each topping on exactly n slices(n ≥ 1). Reflections are considered distinct, rotations are not.Thus, for instance, f(2,1) = 1, f(2,2) = f(3,1) = 2 and f(3,2) = 16.f(3,2) is shown below:[Image: 281_pizza.gif]Find the sum of all f(m,n) such that f(m,n) ≤ 10^15."""
Problem 282
"""Project Euler Problem 282=========================For non-negative integers m, n, the Ackermann function A(m, n) is definedas follows:[Image: 282_formula.gif]For example A(1, 0) = 2, A(2, 2) = 7 and A(3, 4) = 125.Find A(n, n) and give your answer mod 14^8."""
Problem 283
"""Project Euler Problem 283=========================Consider the triangle with sides 6, 8 and 10. It can be seen that theperimeter and the area are both equal to 24. So the area/perimeter ratiois equal to 1.Consider also the triangle with sides 13, 14 and 15. The perimeter equals42 while the area is equal to 84. So for this triangle the area/perimeterratio is equal to 2.Find the sum of the perimeters of all integer sided triangles for whichthe area/perimeter ratios are equal to positive integers not exceeding1000."""
Problem 284
"""Project Euler Problem 284=========================The 3-digit number 376 in the decimal numbering system is an example ofnumbers with the special property that its square ends with the samedigits: 376^2 = 141376. Let's call a number with this property a steadysquare.Steady squares can also be observed in other numbering systems. In thebase 14 numbering system, the 3-digit number c37 is also a steady square:c37^2 = aa0c37, and the sum of its digits is c + 3 + 7 = 18 in the samenumbering system. The letters a, b, c and d are used for the 10, 11, 12and 13 digits respectively, in a manner similar to the hexadecimalnumbering system.For 1 ≤ n ≤ 9, the sum of the digits of all the n-digit steady squares inthe base 14 numbering system is 2d8 (582 decimal). Steady squares withleading 0's are not allowed.Find the sum of the digits of all the n-digit steady squares in the base14 numbering system for 1 ≤ n ≤ 10000 (decimal) and give your answer inthe base 14 system using lower case letters where necessary."""
Problem 285
"""Project Euler Problem 285=========================Albert chooses a positive integer k, then two real numbers a, b arerandomly chosen in the interval [0,1] with uniform distribution.The square root of the sum (k·a+1)^2 + (k·b+1)^2 is then computed androunded to the nearest integer. If the result is equal to k, he scores kpoints; otherwise he scores nothing.For example, if k = 6, a = 0.2 and b = 0.85, then(k·a+1)^2 + (k·b+1)^2 = 42.05.The square root of 42.05 is 6.484... and when rounded to the nearestinteger, it becomes 6. This is equal to k, so he scores 6 points.It can be shown that if he plays 10 turns with k = 1, k = 2, ..., k = 10,the expected value of his total score, rounded to five decimal places, is10.20914.If he plays 10^5 turns with k = 1, k = 2, k = 3, ..., k = 10^5, what isthe expected value of his total score, rounded to five decimal places?"""
Problem 286
"""Project Euler Problem 286=========================Barbara is a mathematician and a basketball player. She has found that theprobability of scoring a point when shooting from a distance x is exactly(1 - ^x/[q]), where q is a real constant greater than 50.During each practice run, she takes shots from distances x = 1, x = 2,..., x = 50 and, according to her records, she has precisely a 2 % chanceto score a total of exactly 20 points.Find q and give your answer rounded to 10 decimal places."""
Problem 287
"""Project Euler Problem 287=========================The quadtree encoding allows us to describe a 2^N×2^N black and whiteimage as a sequence of bits (0 and 1). Those sequences are to be read fromleft to right like this: • the first bit deals with the complete 2^N×2^N region; • "0" denotes a split: the current 2^n×2^n region is divided into 4 sub-regions of dimension 2^n-1×2^n-1, the next bits contains the description of the top left, top right, bottom left and bottom right sub-regions - in that order; • "10" indicates that the current region contains only black pixels; • "11" indicates that the current region contains only white pixels.Consider the following 4×4 image (colored marks denote places where asplit can occur):[Image: 287_quadtree.gif]This image can be described by several sequences, for example:"001010101001011111011010101010", of length 30, or "0100101111101110",of length 16, which is the minimal sequence for this image.For a positive integer N, define D[N] as the 2^N×2^N image with thefollowing coloring scheme: • the pixel with coordinates x = 0, y = 0 corresponds to the bottom left pixel, • if (x - 2^N-1)^2 + (y - 2^N-1)^2 ≤ 2^2N-2 then the pixel is black, • otherwise the pixel is white.What is the length of the minimal sequence describing D[24]?"""
Problem 288
"""Project Euler Problem 288=========================For any prime p the number N(p,q) is defined byN(p,q) = ∑[n=0 to q]T[n]*p^n with T[n] generated by the following random number generator:S[0] = 290797S[n+1] = S[n]^2 mod 50515093T[n] = S[n] mod pLet Nfac(p,q) be the factorial of N(p,q).Let NF(p,q) be the number of factors p in Nfac(p,q).You are given that NF(3,10000) mod 3^20=624955285.Find NF(61,10^7) mod 61^10."""
Problem 289
"""Project Euler Problem 289=========================Let C(x,y) be a circle passing through the points (x, y), (x, y+1),(x+1, y) and (x+1, y+1).For positive integers m and n, let E(m,n) be a configuration whichconsists of the m·n circles:{ C(x,y): 0 ≤ x < m, 0 ≤ y < n, x and y are integers }An Eulerian cycle on E(m,n) is a closed path that passes through each arcexactly once.Many such paths are possible on E(m,n), but we are only interested inthose which are not self-crossing: A non-crossing path just touches itselfat lattice points, but it never crosses itself.The image below shows E(3,3) and an example of an Eulerian non-crossingpath.[Image: 289_euler.gif]Let L(m,n) be the number of Eulerian non-crossing paths on E(m,n).For example, L(1,2) = 2, L(2,2) = 37 and L(3,3) = 104290.Find L(6,10) mod 10^10."""
Problem 290
"""Project Euler Problem 290=========================How many integers 0 ≤ n < 10^18 have the property that the sum of thedigits of n equals the sum of digits of 137n?"""
Problem 291
"""Project Euler Problem 291=========================A prime number p is called a Panaitopol prime if:[Image: 291_formula.gif]for some positive integers x and y.Find how many Panaitopol primes are less than 5×10^15."""
Problem 292
"""Project Euler Problem 292=========================We shall define a Pythagorean polygon to be a convex polygon with thefollowing properties: • there are at least three vertices, • no three vertices are aligned, • each vertex has integer coordinates, • each edge has integer length.For a given integer n, define P(n) as the number of distinct Pythagoreanpolygons for which the perimeter is ≤ n.Pythagorean polygons should be considered distinct as long as none is atranslation of another.You are given that P(4) = 1, P(30) = 3655 and P(60) = 891045.Find P(120)."""
Problem 293
"""Project Euler Problem 293=========================An even positive integer N will be called admissible, if it is a power of2 or its distinct prime factors are consecutive primes.The first twelve admissible numbers are 2,4,6,8,12,16,18,24,30,32,36,48.If N is admissible, the smallest integer M > 1 such that N+M is prime,will be called the pseudo-Fortunate number for N.For example, N=630 is admissible since it is even and its distinct primefactors are the consecutive primes 2,3,5 and 7.The next prime number after 631 is 641; hence, the pseudo-Fortunate numberfor 630 is M=11.It can also be seen that the pseudo-Fortunate number for 16 is 3.Find the sum of all distinct pseudo-Fortunate numbers for admissiblenumbers N less than 10^9."""
Problem 294
"""Project Euler Problem 294=========================For a positive integer k, define d(k) as the sum of the digits of k in itsusual decimal representation.Thus d(42) = 4+2 = 6.For a positive integer n, define S(n) as the number of positive integers k< 10^n with the following properties : • k is divisible by 23 and • d(k) = 23.You are given that S(9) = 263626 and S(42) = 6377168878570056.Find S(11^12) and give your answer mod 10^9."""
Problem 295
"""Project Euler Problem 295=========================We call the convex area enclosed by two circles a lenticular hole if: • The centres of both circles are on lattice points. • The two circles intersect at two distinct lattice points. • The interior of the convex area enclosed by both circles does not contain any lattice points.Consider the circles:C[0]: x^2+y^2=25C[1]: (x+4)^2+(y-4)^2=1C[2]: (x-12)^2+(y-4)^2=65The circles C[0], C[1] and C[2] are drawn in the picture below.[Image: 295_lenticular.gif]C[0] and C[1] form a lenticular hole, as well as C[0] and C[2].We call an ordered pair of positive real numbers (r[1], r[2]) a lenticularpair if there exist two circles with radii r[1] and r[2] that form alenticular hole. We can verify that (1, 5) and (5, √65) are the lenticularpairs of the example above.Let L(N) be the number of distinct lenticular pairs (r[1], r[2]) for which0 < r[1] ≤ r[2] ≤ N. We can verify that L(10) = 30 and L(100) = 3442.Find L(100 000)."""
Problem 296
"""Project Euler Problem 296=========================Given is an integer sided triangle ABC with BC ≤ AC ≤ AB.k is the angular bisector of angle ACB.m is the tangent at C to the circumscribed circle of ABC.n is a line parallel to m through B.The intersection of n and k is called E.How many triangles ABC with a perimeter not exceeding 100 000 exist suchthat BE has integral length?"""
Problem 297
"""Project Euler Problem 297=========================Each new term in the Fibonacci sequence is generated by adding theprevious two terms. Starting with 1 and 2, the first 10 terms willbe: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.Every positive integer can be uniquely written as a sum of nonconsecutiveterms of the Fibonacci sequence. For example, 100 = 3 + 8 + 89.Such a sum is called the Zeckendorf representation of the number.For any integer n>0, let z(n) be the number of terms in the Zeckendorfrepresentation of n. Thus, z(5) = 1, z(14) = 2, z(100) = 3 etc.Also, for 0<n<10^6, ∑ z(n) = 7894453.Find ∑ z(n) for 0<n<10^17."""
Problem 298
"""Project Euler Problem 298=========================Larry and Robin play a memory game involving of a sequence of randomnumbers between 1 and 10, inclusive, that are called out one at a time.Each player can remember up to 5 previous numbers. When the called numberis in a player's memory, that player is awarded a point. If it's not, theplayer adds the called number to his memory, removing another number ifhis memory is full.Both players start with empty memories. Both players always add new missednumbers to their memory but use a different strategy in deciding whichnumber to remove:Larry's strategy is to remove the number that hasn't been called in thelongest time.Robin's strategy is to remove the number that's been in the memory thelongest time.Example game: Turn Called Larry's Larry's Robin's Robin's number memory score memory score 1 1 1 0 1 0 2 2 1,2 0 1,2 0 3 4 1,2,4 0 1,2,4 0 4 6 1,2,4,6 0 1,2,4,6 0 5 1 1,2,4,6 1 1,2,4,6 1 6 8 1,2,4,6,8 1 1,2,4,6,8 1 7 10 1,4,6,8,10 1 2,4,6,8,10 1 8 2 1,2,6,8,10 1 2,4,6,8,10 2 9 4 1,2,4,8,10 1 2,4,6,8,10 3 10 1 1,2,4,8,10 2 1,4,6,8,10 3Denoting Larry's score by L and Robin's score by R, what is the expectedvalue of |L-R| after 50 turns? Give your answer rounded to eight decimalplaces using the format x.xxxxxxxx ."""
Problem 299
"""Project Euler Problem 299=========================Four points with integer coordinates are selected:A(a, 0), B(b, 0), C(0, c) and D(0, d), with 0 < a < b and 0 < c < d.Point P, also with integer coordinates, is chosen on the line AC so thatthe three triangles ABP, CDP and BDP are all similar.[Image: 299_ThreeSimTri.gif]It is easy to prove that the three triangles can be similar, only if a=c.So, given that a=c, we are looking for triplets (a,b,d) such that at leastone point P (with integer coordinates) exists on AC, making the threetriangles ABP, CDP and BDP all similar.For example, if (a,b,d)=(2,3,4), it can be easily verified that pointP(1,1) satisfies the above condition. Note that the triplets (2,3,4) and(2,4,3) are considered as distinct, although point P(1,1) is common forboth.If b+d < 100, there are 92 distinct triplets (a,b,d) such that point Pexists.If b+d < 100 000, there are 320471 distinct triplets (a,b,d) such thatpoint P exists.If b+d < 100 000 000, how many distinct triplets (a,b,d) are there suchthat point P exists?"""
Problem 300
"""Project Euler Problem 300=========================In a very simplified form, we can consider proteins as strings consistingof hydrophobic (H) and polar (P) elements, e.g. HHPPHHHPHHPH.For this problem, the orientation of a protein is important; e.g. HPP isconsidered distinct from PPH. Thus, there are 2^n distinct proteinsconsisting of n elements.When one encounters these strings in nature, they are always folded insuch a way that the number of H-H contact points is as large as possible,since this is energetically advantageous.As a result, the H-elements tend to accumulate in the inner part, with theP-elements on the outside.Natural proteins are folded in three dimensions of course, but we willonly consider protein folding in two dimensions.The figure below shows two possible ways that our example protein could befolded (H-H contact points are shown with red dots).[Image: 300_protein.gif]The folding on the left has only six H-H contact points, thus it wouldnever occur naturally.On the other hand, the folding on the right has nine H-H contact points,which is optimal for this string.Assuming that H and P elements are equally likely to occur in any positionalong the string, the average number of H-H contact points in an optimalfolding of a random protein string of length 8 turns out to be850 / 2^8 = 3.3203125.What is the average number of H-H contact points in an optimal folding ofa random protein string of length 15?Give your answer using as many decimal places as necessary for an exactresult."""