Project Euler Problem #47

Problem #47 is one of the many Project Euler problems that involves prime numbers. The problem reads:

Project Euler Problem 47: Distinct primes factors
The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 7
15 = 3 × 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

As you can probably guess, my solution involves iterative brute force. Here is my solution:

Solution #1: Brute Force Approach

We simply iterate through all the numbers, counting the number of factors of each one while maintaining a “streak” counter of consecutive numbers with exactly 4 factors. When counting the prime factors of a number, once 5 factors have been counted, we can stop counting. In addition, all prime factors can be divided out once found to reduce the size of the number that needs to be factored. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #47
 '''
 
 import time
 from math import sqrt
 
 def countPrimes(n,k):
     total = 0
     if(n%2==0):
         total+=1
         while(n%2==0):
             n/=2
     c = 3
     while(c<=sqrt(n)):
         if(n%c==0):
             total+=1
             if(total>k):
                 return False
             while(n%c==0):
                 n/=c
         c+=2
     if(n>1):
         total+=1
     return total == k
 
 def projectEulerProblemFortySeven(n,k):
     c = 14
     streak = 0
     while(streak<n):
         if(countPrimes(c,k)):
             streak+=1
             if(streak==n):
                 return (c-n+1)
         else:
             streak = 0
         c+=1
     return "HOW"
 
 start = time.time()
 print projectEulerProblemFortySeven(4, 4)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 134043
 --- 0.572690010071 seconds ---
 
 for input of n = 4, k = 4
 '''

As shown above, brute force can be quite effective. I am sure that there is a more efficient solution to this problem, and I may come back to look for a more efficient approach later.

Thanks for reading! See you tomorrow.

Project Euler Problem #46

Problem #46 involves a disproved conjecture by the famous mathematician Christian Goldbach. The problem reads:

Project Euler Problem 46: Goldbach's other conjecture
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

As usual, my solution involves brute force. The solution could be simplified by using a sieve to list all primes up to an upper bound, but unless the first exception is known, it is difficult to establish an upper bound. Thus, I used the naive method of determining whether numbers were prime.

Solution #1: Brute Force Approach

We simply iterate through all the odd composites and check every possible square number less than half of the odd composite to see if it satisfies Goldbach’s Conjecture. If no squares in this range satisfy the conjecture, then the odd composite is a counterexample. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #46
 '''
 
 import time
 from math import sqrt
 from math import ceil
 
 def isPrime(n):
     if(n<=1):
         return False
     if(n<4):
         return True
     if(n%2==0):
         return False
     c = 3
     while(c<=sqrt(n)):
         if(n%c==0):
             return False
         c+=2
     return True
 
 def projectEulerProblemFortySix(n):
     total = 0
     c = 15
     current = -1
     while(total<n):
         if(not isPrime(c)):
             a = 1
             found = False
             while(a<=ceil(sqrt(c/2))):
                 if isPrime(c-2*a*a):
                     found = True
                     break
                 a+=1
             if not found:
                 total+=1
                 current = c
         c+=2
     return current
 
 start = time.time()
 print projectEulerProblemFortySix(1)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 5777
 --- 0.0163691043854 seconds ---
 
 for input of n = 1
 '''

As shown above, brute force can be very effective at validating various hypotheses in the mathematical world. One point of interest is that with my program, I was only able to find the counterexamples of 5777 and 5993. According to Wikipedia, these are the only counterexamples that are known (they are also called odd composite Stern numbers). It would be interesting to prove whether the number of counterexamples is finite.

Thanks for reading! See you tomorrow.

Project Euler Problem #45

Problem #45 is yet another problem that involves figurate numbers. The problem reads: 

Project Euler Problem 45: Triangular, pentagonal, and hexagonal
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2     1, 3, 6, 10, 15, ...
Pentagonal Pn=n(3n−1)/2  1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n−1)     1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.

My solution for this problem still probably falls into the category of brute force. However, it is slightly optimized over the naive interpretation of this problem. Here is my solution:

Solution #1: Brute Force Approach

We can observe that the nth Hexagonal number H_n = n(2n-1) can be rewritten as H_n = n(2n-1) = ((2n-1)(2n-1+1))/2 = T_(2n-1). Thus, every hexagonal number is also a triangular number. Therefore, it satisfies to find the next hexagonal number which is also a pentagonal number.

Thus, we iterate through the hexagonal numbers after H_143 and check each one for being a pentagonal number. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #45
 '''
 
 import time
 from math import sqrt
 from math import ceil
 
 def isPentagon(p):
     if(p==1):
         return True
     n = int(ceil(sqrt(2*p/3)))
     if(n*(3*n-1)/2 == p):
         return True
     return False
 
 def projectEulerProblemFortyFive(n):
     c = n+1
     while(True):
         if(isPentagon(c*(2*c-1))):
             return c*(2*c-1)
         c+=1
     return "HOW"
 
 start = time.time()
 print projectEulerProblemFortyFive(143)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 1533776805
 --- 0.0135638713837 seconds ---
 
 for input of n = 143
 '''

While this solution is plenty efficient for this problem, I am sure that there must be a faster way to solve this problem. Many similar questions can be reduced to finding the solutions to a Pell Equation which can be done recursively. For instance, there is another Project Euler Problem which involves finding triangular numbers that are also square numbers, and that problem can be reduced to solving a Pell Equation. Because the formulas for pentagonal and hexagonal numbers are similar, it is likely that this problem can also be reduced to a Pell Equation. Alas, I am too lazy to solve this diophantine equation at the moment. I may come back to look for a more efficient solution at some point.

Thanks for reading! See you tomorrow.

Project Euler Problem #44:

Problem #44 concerns a somewhat obscure class of numbers known as the pentagonal numbers. It is also (in my opinion) the most difficult question in the first 50 problems of Project Euler, and the only one that I have yet to find a solution for that runs in under a minute. (I’m a very sloppy programmer right now) Here’s the problem:

Project Euler Problem 44: Pentagon numbers
Pentagonal numbers are generated by the formula, Pn=n
(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

As stated above, my solution to this problem is extremely inefficient, and I definitely need to come back to this problem at some point. Here’s my solution:

Solution #1: Very Inefficient Brute Force Approach

We list all of the pentagonal numbers up to an arbitrary upper bound and check all quadruples of pentagonal numbers for the given property. To optimize this search a bit, I did casework on the pentagonal number which is the sum of two smaller pentagonal numbers first, and then I did casework on the pentagonal number which is the smaller of the two summand pentagonal numbers second. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #44
 '''
 
 import time
 
 def projectEulerProblemFortyFour(n):
     myPentagons = [1,5]
     c = 3
     minDifference = 10**30
     while(c<=n):
         myPentagons.append(c*(3*c-1)/2)
         c+=1
     for a in myPentagons:
         for b in myPentagons:
             if(2*b<=a):
                 if (a-b) in myPentagons:
                     if (a-2*b) in myPentagons:
                         if (a-2*b) < minDifference:
                             minDifference = (a-2*b)
             else:
                 break
     return minDifference
 
 start = time.time()
 print projectEulerProblemFortyFour(4000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 5482660
 --- 227.999250889 seconds ---
 
 for input of n = 4000
 '''

Yikes! That took nearly 4 minutes to run, nearly 4 times the maximum time that all solutions on Project Euler should run within. I definitely need to come back to this problem at some point.

Thanks for reading! See you tomorrow.

Project Euler Problem #43

Problem #43 is yet another problem that involves digits and primes. This time, we’re looking at pandigital numbers where each subsequence is divisible by a different prime. Here’s the problem:

Project Euler Problem 43: Sub-string divisibility
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

d2d3d4=406 is divisible by 2
d3d4d5=063 is divisible by 3
d4d5d6=635 is divisible by 5
d5d6d7=357 is divisible by 7
d6d7d8=572 is divisible by 11
d7d8d9=728 is divisible by 13
d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

My solution for this problem is probably one of the least optimized brute force solutions of all of my solutions for the first 50 problems. Therefore, I definitely want to look at this problem again in the future. Here’s my solution:

Solution #1: Brute Force Approach

We simply list all 0-9 pandigital numbers and check each one for the given property. By converting each number to a string and using Python’s interface for accessing substrings, this can be done very easily. It is also worth noting that it is better to start checking for the larger primes as less numbers will have substrings that are divisible by the larger primes. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #43
 '''
 
 import time
 
 def listPermutations(myList):
     if(len(myList)==1):
         return [myList]
     a = myList[0]
     b = listPermutations(myList[1:])
     total = []
     for x in b:
         for c in range(len(x)+1):
             temp = x[0:c]
             temp.append(a)
             temp.extend(x[c:])
             total.append(temp)
     return total
 
 def projectEulerProblemFortyThree(myList):
     a = listPermutations(myList)
     total = 0
     for x in a:
         y = ""
         for b in x:
             y+=str(b)
         if(y[0]!="0" and int(y[7:10])%17==0 and int(y[6:9])%13==0 and int(y[5:8])%11==0 and int(y[4:7])%7==0 and int(y[3:6])%5==0 and int(y[2:5])%3==0 and int(y[1:4])%2==0):
             total+=int(y)
     return total
 
 start = time.time()
 print projectEulerProblemFortyThree([0,1,2,3,4,5,6,7,8,9])
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 16695334890
 --- 10.1015229225 seconds ---
 
 for input of myList =[0,1,2,3,4,5,6,7,8,9]
 '''

Oh boy. This solution took over 10 seconds to run! I definitely need to return to this problem. However, it is nice to know that Python is able to generate all 3628800 permutations of the first 10 numbers in only 10 seconds, even with my sloppy recursive method.

Thanks for reading!

Project Euler Problem #42

Problem #42 is yet another simple question that involves analyzing a file with tons of data. The question reads:

Project Euler Problem 42: Coded triangle numbers
The nth term of the sequence of triangle numbers is given by, tn = ½n(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 its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

This problem is genuinely uninteresting. We have already seen plenty of questions involving analyzing text files and triangle numbers. With that being said, here’s my solution:

Solution #1: Brute Force Approach

This time, I stored the text in a file called “PE42Words.txt”. We simply iterate through all of the words in the file. We calculate the total for each word and store the maximum total. Then we generate a list of all triangular numbers up to that maximum total, and we count the number of totals that are in that list. Here’s an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #42
 '''
 
 import time
 
 f = open("PE42Words.txt", "r")
 
 if(f.mode == "r"):
     contents = f.readlines()
     realContents = []
     for x in contents:
         realContents.append(x.split(","))
 else:
     raise ValueError("Cannot read from file")
 
 finalList = realContents[0]
 
 def getValueString(myString):
     total = 0
     
     for x in myString:
         if("A"<=x<="Z"):
             total+=(ord(x)-ord("A")+1)
     return total
 
 def projectEulerProblemFortyTwo(myList):
     totalsList = []
     maxTotal = 0
     for x in myList:
         a = getValueString(x)
         totalsList.append(a)
         if(a>maxTotal):
             maxTotal = a
     triangles = []
     c = 1
     while(c*(c+1)/2<=maxTotal):
         triangles.append(c*(c+1)/2)
         c+=1
     finalCount = 0
     for x in totalsList:
         if x in triangles:
             finalCount+=1
     return finalCount
 
 start = time.time()
 print projectEulerProblemFortyTwo(finalList)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 162
 --- 0.00270199775696 seconds ---
 
 for input of n = given list of words
 '''

As shown above, iteration is a very powerful tool that can be used to solve many interesting problems. Unfortunately, this was not one of them.

Thanks for reading!

Project Euler Problem #41:

Problem #41 is yet another problem that involves digits in the prime numbers. The question reads:

Project Euler Problem 41: Pandigital prime
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

Unlike some of the most recent problems involving the primes, my solution to this problem does not involve the Sieve of Eratosthenes. Here is my solution:

Solution #1: Permutation Brute Force Approach

We simply list all permutations of the first n digits and check each one for being prime. Here is an implementation of this method in Python 2.7 given the fact that there is a 7-digit pandigital prime.

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #41
 '''
 
 import time
 from math import sqrt
 
 def listPermutations(myList):
     if(len(myList)==1):
         return [myList]
     a = myList[0]
     b = listPermutations(myList[1:])
     total = []
     for x in b:
         for c in range(len(x)+1):
             temp = x[0:c]
             temp.append(a)
             temp.extend(x[c:])
             total.append(temp)
     return total
 
 def isPrime(n):
     if(n<=1):
         return False
     if(n<4):
         return True
     if(n%2==0):
         return False
     c = 3
     while(c<=sqrt(n)):
         if(n%c==0):
             return False
         c+=2
     return True
 
 def projectEulerProblemFortyOne(n):
     digits = []
     for x in range(1,n+1):
         digits.append(x)
     allPossible = listPermutations(digits)
     maxFound = 0
     for p in allPossible:
         a = ""
         for x in p:
             a+=str(x)
         b = int(a)
         if(isPrime(b)):
             if(b>maxFound):
                 maxFound = b
     return maxFound
 
 start = time.time()
 print projectEulerProblemFortyOne(7)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 7652413
 --- 0.0887989997864 seconds ---
 
 for input of n = 7
 '''

I’m not entirely satisfied with this solution, and I may come back to this problem. However, it seems like listing all of the permutations was more than efficient enough for solving this problem.

Thanks for reading!

Project Euler Problem #40:

Problem #40 involves an obscure constant in mathematics known as the Champernowne constant. This constant is relevant because it is one of the few numbers that has been proven to be transcendental. The problem reads:

Project Euler Problem 40: Champernowne's constant
An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

If you expected an elegant method of finding the nth digit of Champernowne’s constant, I’m sorry, but you’re probably going to be disappointed.

Solution #1: Brute Force Approach

We count digits of the first x numbers until we get the number x with the nth digit in Champernowne’s constant. We do this for each of the digits in the product and multiply the results. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #40
 '''
 
 import time
 from math import ceil
 
 def calculateChampernowneDigit(n):
     c = 1
     total = 0
     while(n-total>c*9*(10**(c-1))):
         total+=c*9*(10**(c-1))
         c+=1
     n-=total
     numbers = int(ceil(1.0*n/(1.0*c)))
     theNumber = 10**(c-1) + numbers-1
     a = str(theNumber)
     return int(a[((n-1)%c)])
 
 def projectEulerProblemForty(myList):
     total = 1
     for x in myList:
         total*=calculateChampernowneDigit(x)
     return total
 
 start = time.time()
 print projectEulerProblemForty([1,10,100,1000,10000,100000,1000000])
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 210
 --- 3.88622283936e-05 seconds ---
 
 for input of myList = [1,10,100,1000,10000,100000,1000000]
 '''

As shown above, there are many questions in mathematics where inelegant solutions are acceptable.

Thanks for reading!

Project Euler Problem #39:

Problem #39 is one of the many problems on Project Euler that involves Pythagorean Triples. In fact, this type of problem is so common that my solution to this problem is nearly identical to my solution for Problem #9. The question reads:

Project Euler Problem 39: Integer right triangles
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

If you look back at my post for Problem #9, you’ll find that these two problems ask for essentially the same thing. Thus, I will not fully explain my solution this time.

Solution #1: Brute Force Approach

We simply use the same method to count Pythagorean Triples with a given perimeter as we did in Problem #9. This involves writing every Pythagorean Triple in the form d(m^2-n^2), d(2mn), d(m^2+n^2) for some integers d, m, and n. By factoring the perimeter, we can count the number of possible triples {d,m,n}. Doing so for every possible perimeter, we can find the perimeter with the maximum number of solutions. Here is an implementation of this method in Python 2.7 that is nearly identical to my solution from Problem #9:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #39
 '''
 
 import time
 from math import sqrt
 
 def listFactors(n):
     primes = []
     exponents = []
     c = 2
     while(c<=sqrt(n)):
         if(n%c==0):
             primes.append(c)
             t = 0
             while(n%c==0):
                 n/=c
                 t+=1
             exponents.append(t)
         c+=1
     if(n>1):
         primes.append(n)
         exponents.append(1)
     return sorted(listFactorsGivenFactorization(primes, exponents))
 
 def listFactorsGivenFactorization(p,e):
     total = []
     if(len(p) >= 1):
         for x in range(e[0]+1):
             total.append(p[0]**x)
     else:
         return [1]
     previousTotal = listFactorsGivenFactorization(p[1:], e[1:])
     
     actualTotal = []
     for a in total:
         for b in previousTotal:
             actualTotal.append(a*b)
     
     return actualTotal
 
 def countPythagoreanTriples(n):
     if(n%2==1):
         return -1
     found = []
     possibleD = listFactors(n/2)
     n/=2
     for d in possibleD:
         newProduct = n/d
         lowerBound = int(sqrt(newProduct/2))
         upperBound = int(sqrt(newProduct))
         for m in range(lowerBound, upperBound+1):
             if(m>0 and newProduct%m == 0):
                 o = newProduct/m-m
                 if(0<o<m):
                     triple = sorted([d*(m*m-o*o), 2*d*m*o, d*(m*m+o*o)])
                     if triple not in found:
                         found.append(triple)
     
     return len(found)
 
 def projectEulerProblemThirtyNine(n):
     maximum = 1
     maxIndex = 12
     for c in range(13,n+1):
         v = countPythagoreanTriples(c)
         if(v>maximum):
             maxIndex = c
             maximum = v
     return maxIndex
 
 start = time.time()
 print projectEulerProblemThirtyNine(1000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 840
 --- 0.00754904747009 seconds ---
 
 for input of n = 1000
 '''

As shown above, many of the problems on Project Euler are nearly identical to earlier problems, and as a result you can solve new problems by using code written for earlier problems.

Thanks for reading!

Project Euler Problem #38:

Problem #38 is one of the many problems on Project Euler that requires permutations of the digits 1-9, also known as pandigitals. The question reads:

Project Euler Problem 38: Pandigital multiples
Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will 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 product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

You can probably guess that my solution to this problem will involve brute force. However, there is a way to make the brute force more efficient with information in the problem.

Solution #1: Brute Force Approach

Using the fact that 918273645 is a pandigital number with this property, we know that the largest pandigital number must be larger than 918273645. Thus, the number that generates the largest pandigital number should be greater than a prefix of 918273645. If it has 2 digits, it should be greater than or equal to 91. If it has 3 digits, it should be greater than or equal to 918. Continuing with this reasoning, we only have to check numbers between each prefix and the next smallest power of 10. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #38
 '''
 
 import time
 from collections import Counter
 
 def pandigital(n):
     a = str(n)
     c = 2
     while(len(a)<9):
         a+=str(n*c)
         c+=1
     if(len(a)!=9):
         return -1
     if Counter(a) == Counter("123456789"):
         return int(a)
     return -1
 
 def projectEulerProblemThirtyEight(maxKnown):
     c = 2
     temp = maxKnown
     while(c<=4):
         start = int(str(maxKnown)[0:c]) + 1
         while(start<10**c):
             v = pandigital(start)
             if(v>temp):
                 temp = v
             start+=1
         c+=1
     return temp
 
 start = time.time()
 print projectEulerProblemThirtyEight(918273645)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints
 
 932718654
 --- 0.00893306732178 seconds ---

 for input of n = 918273645
 '''

As shown above, brute force iteration can be fairly efficient if you put a bit of thought into using it.

Thanks for reading!

Design a site like this with WordPress.com
Get started