The Inner Machinations of Walker

Project Euler Problem #57

Problem #57 is the first of several Project Euler problems to involve infinite continued fractions for irrational numbers, and it is the first of several problems that can b killed with Pell Equations. The problem reads:

Project Euler Problem 57: Square root convergents
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
 2–√=1+1/(2+1/(2+1/(2+…)))

By expanding this for the first four iterations, we get:
 1+1/2=3/2=1.5
 1+1/(2+1/2)=7/5=1.4
 1+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 eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than the denominator?

As it turns out, the process of determining the continued fraction approximations for a square root is closely related to the problem of solving a Pell Equation. Here’s my solution:

Solution #1: Pell Equation Approach

Let thee nth expansion for the square root of 2 be a/b. Then we would expect a^2 – 2b^2 to be roughly equal to 0. Of course, it can be shown that there are no integers a and b for which the expression is exactly equal to 0, but there are many for which a^2 – 2b^2 = 1 or -1. The first few are a/b = 3/2, 7/5, 17/12, 41/29, etc. These correspond precisely to the expansions for the continued fraction for the square root of 2. It is well known that from the initial solution of a Pell Equation, the rest can be generated recursively. In the case of the square root of 2, it can be shown that if (a,b) is a solution, then (a+2*b)/(a+b) is the next solution. By applying this recursion 1000 times on 3/2, the first 1000 expansions can be analyzed. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Pell Equation Approach to Project Euler Problem #57
 '''
 
 import time
 
 def projectEulerProblemFiftySeven(n):
     numerator = 1
     denominator = 1
     total = 0
     for x in range(n):
         numerator+=2*denominator
         denominator = numerator - denominator
         if(len(str(numerator))>len(str(denominator))):
             total+=1
     return total
 
 start = time.time()
 print projectEulerProblemFiftySeven(1000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 153
 --- 0.00200414657593 seconds ---
 
 for input of n = 1000.
 '''

As shown above, Pell Equation recursions can be very handy for evaluating the continued fraction expansions of square roots.

Thanks for reading! See you tomorrow.

Project Euler Problem #56

Problem #56 concerns the sum of the digits of various perfect powers. The question reads:

Project Euler Problem 56: Powerful digit sum
A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 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 is the maximum digital sum?

Unfortunately, there is no easy way to determine the sum of the digits of a power. It is possible to find the remainder when it is divided by 9, but determining the exact value requires expanding the power. Thus, my solution for this problem falls into the category of brute force. Here is my solution:

Solution #1: Brute Force Approach

We simply calculate every power in this range and store the maximum digital sum. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #56
 '''
 import time

 def sumDigits(x):
     a = str(x)
     total = 0
     for c in a:
         total+=int(c)
     return total

 def projectEulerProblemFiftySix(n):
     maximum = -1
     for a in range(1,n):
         p = 1
         for b in range(1,n):
             p*=a
             v = sumDigits(p)
             if(v>maximum):
                 maximum = v
     return maximum

 start = time.time()
 print projectEulerProblemFiftySix(100)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints
 972
 --- 0.279350042343 seconds ---
 for input of n = 100.
 '''

And with that, we’re done. I would like to find a more efficient method for solving this problem some day. However, brute force is plenty efficient for the inputs in this problem.

Thanks for reading! See you tomorrow.

Project Euler Problem #55

Problem #55 involves an obscure type of number called a Lychrel number. The question reads:

Project Euler Problem 55: Lychrel numbers
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 = 4213
4213 + 3124 = 7337
That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; 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 the theoretical nature of Lychrel numbers.

You can probably guess how a brute force solution to this problem would look. Here is my solution:

Solution #1: Brute Force Approach

We know that all numbers less than 10,000 either produce a palindrome within 50 iterations or are considered Lychrel numbers. Thus, it suffices to perform 50 iterations on all numbers less than 10,000 until a palindrome is found and add the numbers which do not produce a palindrome. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #55
 '''
 
 import time
 
 def isPalindrome(x):
     a = str(x)
     return a == a[::-1]
 
 def projectEulerProblemFiftyFive(n,m):
     final = 0
     for x in range(1,n+1):
         total = x
         found = False
         for a in range(m):
             total = total+int(str(total)[::-1])
             if(isPalindrome(total)):
                 found = True
                 break
         if not found:
             final+=1
     return final
 
 start = time.time()
 print projectEulerProblemFiftyFive(10000, 50)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 249
 --- 0.0513601303101 seconds ---
 
 for input of n = 10000, m = 50
 '''

As shown above, brute force can be quite effective at determining whether integers fall into certain classes of numbers.

Thanks for reading! See you tomorrow.

Project Euler Problem #54

Problem #54 is one of the many problems on Project Euler that is very annoying to implement by hand, but can be solved quickly with the right library. The question reads:

Project Euler Problem 54: Poker hands
In the card game poker, a hand consists of five cards and are ranked, from lowest 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 the highest 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 players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.
Consider the following five hands dealt to two players:
Hand
Player 1
Player 2
Winner
1
5H 5C 6S 7S KD
Pair of Fives
2C 3S 8S 8D TD
Pair of Eights
Player 2
2
5D 8C 9S JS AC
Highest card Ace
2C 5C 7D 8S QH
Highest card Queen
Player 1
3
2D 9C AS AH AC
Three Aces
3D 6D 7D TD QD
Flush with Diamonds
Player 2
4
4D 6S 9H QH QC
Pair of Queens
Highest card Nine
3D 6D 7H QD QS
Pair of Queens
Highest card Seven
Player 1
5
2H 2D 4C 4D 4S
Full House
With Three Fours
3C 3D 3S 9S 9D
Full House
with Three Threes
Player 1
The 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): the first five are Player 1's cards and the last five are Player 2's cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player's hand is in no specific order, and in each hand there is a clear winner.
How many hands does Player 1 win?

As you might imagine, implementing this by hand is extremely nasty. Luckily, there are already some libraries in common languages such as Python that can solve this for us. Here is my solution:

Solution #1: Library Approach

Luckily, the Python library eval7 can solve this exact problem for us by defining the Card library which can sort the various poker hands. By going through all of the hands that are listed in the file, we can simply use this library to compare the two hands in each line and count the number of times the first player wins. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Library Approach to Project Euler Problem #54
 '''
 
 import time
 import eval7
 
 f = open("PE54Hands.txt","r")
 
 if(f.mode == "r"):
     contents = f.readlines()
     realContents = []
     for x in contents:
         realContents.append(map(str,x.split()))
 else:
     raise ValueError("Cannot read from file")
 
 finalList = realContents
 
 def projectEulerProblemFiftyFour(myList):
     total = 0
     for x in myList:
         a = x[0:5]
         b = x[5:]
         oneHand = []
         for card in a:
             oneHand.append(eval7.Card(card[0]+card[1].lower()))
         twoHand = []
         for card in b:
             twoHand.append(eval7.Card(card[0]+card[1].lower()))
         if(eval7.evaluate(oneHand)>eval7.evaluate(twoHand)):
             total+=1
     return total
 
 start = time.time()
 print projectEulerProblemFiftyFour(finalList)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 376
 --- 0.00889301300049 seconds ---
 
 for input of finalList = given list of hands.
 '''

And with that, we’re done. Knowing the right libraries can save a lot of time when solving Project Euler problems.

Thanks for reading! See you tomorrow.

Project Euler Problem #53

Problem #53 is one of the many problems in Project Euler that involves binomial coefficients. The question reads:

Project Euler Problem 53: Combinatoric selections
There are exactly ten ways of selecting three from five, 12345:

 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, (5 choose 3)=10.
In general, (n choose r)=n!/(r!(n−r)!), where r≤n, n!=n×(n−1)×…×3×2×1, and 0!=1.

It is not until n=23, that a value exceeds one-million: (23 choose 10)=1144066.
How many, not necessarily distinct, values of (n choose r) for 1≤n≤100, are greater than one-million?

My solution for this problem involves a bit of brute force. Here is my solution:

Solution #1: Brute Force Approach

We can rewrite the formula for n choose r in the more efficient form n choose r = n*(n-1)*(n-2)*…*(n-r+1)/r! Using this method, we can easily calculate n choose r for any values of n and r. Now, using the fact that Pascal’s Triangle is symmetric, i.e. n choose r = n choose n-r, we only have to check values of r from 0 to n/2 to determine the values of n choose r which are greater than 1,000,000. Checking all values of n between 1 and 100 and all values of r between 1 and 100, we can calculate a running total of the number of binomial coefficients in this range which are greater than 1,000,000. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #53
 '''
 
 import time
 
 def combination(n,r):
     numerator = 1
     denominator = 1
     for x in range(r):
         numerator*=(n-x)
         denominator*=(x+1)
     return numerator/denominator
 
 def projectEulerProblemFiftyThree(n, m):
     total = 0
     for c in range(1,n+1):
         for x in range(0,c/2+1):
             if(combination(c,x)>m):
                 total+=(c-2*x+1)
                 break
     return total
 
 start = time.time()
 print projectEulerProblemFiftyThree(100, 1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 4075
 --- 0.000518083572388 seconds ---
 
 for input of n = 100, m = 1000000
 '''

And with that, we’re done. An alternative approach may use the fact that the sum of the numbers in the nth row is 2^n and instead find the sum of the numbers which are less than or equal to 1,000,000. This would probably be a more efficient approach for larger values of n. However, I am too lazy to implement it right now.

Thanks for reading!

Project Euler Problem #52

Problem #52 is one of the few problems on Project Euler where many people will already know the answer before solving the question. The question reads:

Project Euler Problem 52: Permuted multiples
It can be seen that the number, 125874, and its double, 251748, contain exactly 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.

As stated above, the number x with this property is incredibly well known and most people who make it to this question will probably know the answer by heart. Here is a programming solution just for completeness:

Solution #1: Brute Force Approach

We can observe that in order for the given property to be true, x, 2x, 3x, 4x, 5x, and 6x have to each have the same sum of digits. In order for this to be possible, x has to be a multiple of 9. From here we can simply iterate through all of the multiples of 9 until we find a value of x with the given property. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #52
 '''
 
 import time
 
 def enumerateString(a):
     aChars = []
     aNums = []
     for x in a:
         if x not in aChars:
             aChars.append(x)
             aNums.append([x,1])
         else:
             aNums[aChars.index(x)][1]+=1
     return aNums
 
 def isPermutation(a,b):
     return sorted(enumerateString(str(a))) == sorted(enumerateString(str(b)))
 
 def projectEulerProblemFiftyTwo(n):
     c = 9
     found = 0
     current = -1
     while(found<n):
         none = False
         for x in range(2,7):
             if(not isPermutation(c,x*c)):
                 none = True
                 break
         if not none:
             found+=1
             current = c
         c+=9
     return current
 
 start = time.time()
 print projectEulerProblemFiftyTwo(1)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 142857
 --- 0.100811958313 seconds ---
 
 for input of n = 1.
 '''

And with that, we’re done. The question would have been much better if it had asked for the nth smallest number x with this property. In case you’re curious, the first few numbers are 142857, 1428570, 1429857, 14285700, 14298570, 14299857, etc. Ignoring the multiples of 10 in this list, we see an interesting pattern where it seems that the number 14299…99857 has this property for an arbitrary number of 9’s. It would be interesting to prove whether all numbers in this list are of this form. Regardless, there is a much better solution that I imagine most people who solved this question used:

Solution #2: Mathematical Knowledge Approach

We can simply recall that the digits in the first period of each of the fractions 1/7, 2/7, 3/7, 4/7, 5/7, and 6/7 are all rearrangements of 142857. Thus, 142857 is a number with this property. Guessing that this is the smallest number with this property, we’re done.

This fact adds to the property we discussed earlier. Multiplying each number in our list which is not a multiple of 10 by 7, we get 999999, 10008999, 100098999, 1000998999, etc. With this fact, we can guess that for n>=2, the nth number in this list will be (1000*10^(n+2) + (10^(n-2)-1)*10^4 + 8999)/7. With this result, we have an explicit form for infinitely many numbers x with this property.

Thanks for reading! See you tomorrow.

Project Euler Problem #51

Problem #51 is one of the many problems that involves manipulating digits in prime numbers. The question reads:

Project Euler Problem 51: Prime digit replacements
By replacing the 1^st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

My solution for this problem definitely falls into the category of brute force. Here’s my solution:

Solution #1: Brute Force Approach

First, we can notice that the 10 different values which are formed by replacing sections of a prime number with the digits 0-9 should form an arithmetic sequence. If the common difference of this arithmetic sequence is not a multiple of 3, then we would expect at least 3 of the values to be multiples of 3, and thus, the family could have at most 7 primes. Thus, for a 8 prime value family to be found, the common difference should be a multiple of 3. Because the common difference for an arithmetic sequence created in this manner is the sum of powers of 10 representing which digits are being replaced, the common difference can only be a multiple of 3 if the number of digits that is being replaced is a multiple of 3. Thus, it suffices to investigate changing 3 of the digits in primes.

From this point, I proceed by brute force. I iterate through all of the prime numbers that could be the minimum number in the prime family. Then I create arrays representing the positions of the ‘0’, ‘1’, and ‘2’ digits in the prime. Then I list all subsets of each of these arrays with exactly 3 elements. For each subset, I list the possible numbers that can be found by increasing the respective digits in the positions in the subset. Finally, I count the number of primes in the set and check if it is greater than or equal to 8. Once a prime is found which generates at least 8 primes, the problem is solved. Here is an implementation of this long approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #51
 '''
 
 import time
 from math import sqrt
 
 def listSubsets(myList,n):
     l = len(myList)
     if(l<n):
         return []
     if(n==0):
         return [[]]
     a = myList[0]
     first = listSubsets(myList[1:],n)
     second = listSubsets(myList[1:],n-1)
     total = first[:]
     for b in second:
         c = b[:]
         c.append(a)
         total.append(sorted(c))
     return total
 
 def primePossibilities(x):
     a = str(x)
     l = len(a)
     possibilities = []
     twos = []
     ones = []
     zeros = []
     for y in range(l):
         v = int(a[y])
         if(v==2):
             twos.append(y)
         elif(v==1):
             ones.append(y)
         elif(v==0):
             zeros.append(y)
     zeroTriples = listSubsets(zeros, 3)
     oneTriples = listSubsets(ones, 3)
     twoTriples = listSubsets(twos, 3)
     for triple in zeroTriples:
         firstIndex = triple[0]
         secondIndex = triple[1]
         thirdIndex = triple[2]
         total = [x]
         for c in range(1,10):
             letter = str(c)
             total.append(int(a[0:firstIndex] + letter+ a[firstIndex+1:secondIndex]+letter + a[secondIndex+1:thirdIndex]+letter+a[thirdIndex+1:]))
         possibilities.append(total)
     for triple in oneTriples:
         firstIndex = triple[0]
         secondIndex = triple[1]
         thirdIndex = triple[2]
         total = [x]
         for c in range(2,10):
             letter = str(c)
             total.append(int(a[0:firstIndex] + letter+ a[firstIndex+1:secondIndex]+letter + a[secondIndex+1:thirdIndex]+letter+a[thirdIndex+1:]))
         possibilities.append(total)
     for triple in twoTriples:
         firstIndex = triple[0]
         secondIndex = triple[1]
         thirdIndex = triple[2]
         total = [x]
         for c in range(3,10):
             letter = str(c)
             total.append(int(a[0:firstIndex] + letter+ a[firstIndex+1:secondIndex]+letter + a[secondIndex+1:thirdIndex]+letter+a[thirdIndex+1:]))
         possibilities.append(total)
     return possibilities
 
 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 projectEulerProblemFiftyOne(n):
     found = 0
     possible = 3
     current = -1
     while(found<n):
         if(isPrime(possible)):
             a = primePossibilities(possible)
             for replaced in a:
                 total = 0
                 for x in replaced:
                     if isPrime(x):
                         total+=1
                 if(total>=8):
                     current = possible
                     found+=1
         possible+=2
     return current
 
 start = time.time()
 print projectEulerProblemFiftyOne(1)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 121313
 --- 0.314001083374 seconds ---
 
 for input of n=1
 '''

And with that, we’re done. The solution surprisingly ran in only a third of a second. I expected the answer to be at least a few orders of magnitude higher. I may come back to this question eventually to look for a more efficient approach.

Thanks for reading! See you tomorrow.

Project Euler Problem #50

Problem #50 involves sums of consecutive primes. The question reads:

Project Euler Problem 50: Consecutive prime sum
The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?

If you’ve seen my solutions to other Project Euler problems that involve primes, you can probably guess that my solution involves the Sieve of Eratosthenes. Here is my solution:

Solution #1: Brute Force Sieve Approach

We simply iterate through the sums of different numbers of consecutive primes until the minimum sum of the given number of consecutive primes is greater than 1,000,000. We can use a sieve to list all of the primes less than 1,000,000, and we can use binary search to check if a given sum is in the list of primes. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Sieve Approach to Project Euler Problem #50
 '''
 
 import time
 
 def sieveEratosthenes(n):
     myPrimes = []
     
     primePossible = [True]*(n+1)
     primePossible[0] = False
     primePossible[1] = False
     
     for (i,possible) in enumerate(primePossible):
         if possible:
             for x in range(i*i, (n+1), i):
                 primePossible[x] = False
             myPrimes.append(i)
 
     return myPrimes
 
 def binarySearch(myList,v):
     lower = 0
     upper = len(myList)-1
     while(lower<upper-1):
         middle = (lower+upper)/2
         a = myList[middle]
         if a<v:
             lower = middle
         elif a>v:
             upper = middle
         else:
             return middle
     if myList[lower] == v:
         return lower
     if myList[upper] == v:
         return upper
     return -1
 
 def projectEulerProblemFifty(n):
     allPrimes = sieveEratosthenes(n)
     maxPrime = 41
     c = 7
     while(c<=n):
         total = 0
         for x in range(c):
             total+=allPrimes[x]
         if(total>n):
             return maxPrime
         if(total in allPrimes):
             maxPrime = total
         a = c
         while(a<n):
             total+=allPrimes[a]
             total-=allPrimes[a-c]
             if(total > n):
                 break
             x = binarySearch(allPrimes, total)
             if(x>=0):
                 maxPrime = total
             a+=1
         c+=1
     return maxPrime
 
 start = time.time()
 print projectEulerProblemFifty(1000000)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints
 
 997651
 --- 1.33064293861 seconds ---
 
 for input of n = 1000000.
 '''

And with that, we’re done. While writing this, I realized that the solution can probably be greatly improved if the number of consecutive primes were to count down from the smallest number n such that the sum of the first n primes is greater than 1,000,000. Unfortunately, I am too lazy to implement this right now. I may come back to this problem eventually.

Thanks for reading! See you tomorrow.

Project Euler Problem #49

Problem #49 involves arithmetic sequences where the elements of the sequences are rearrangements of the digits in the other terms of the sequence. The problem reads:

Project Euler Problem 49: Prime permutations
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?

My solution for this problem probably falls into the category of brute force, and unfortunately, it does not run in under a second in Python 2.7. Here is my solution:

Solution #1: Brute Force Approach

We begin by using a sieve to get a list of all the four digit primes. Next, we run through the list and do casework on the first and third terms in the arithmetic sequence. The second term can be found by averaging the others, and once it is verified that the second term is in the list of primes and that each prime is a rearrangement of the digits in the other primes, the problem is solved. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Sieve Approach to Project Euler Problem #49
 '''
 
 import time
 
 def sieveEratosthenes(n):
     myPrimes = []
     
     primePossible = [True]*(n+1)
     primePossible[0] = False
     primePossible[1] = False
     
     for (i,possible) in enumerate(primePossible):
         if possible:
             for x in range(i*i, (n+1), i):
                 primePossible[x] = False
             myPrimes.append(i)
 
     return myPrimes
 
 def equivalentString(a,b):
     aList = []
     bList = []
     a = str(a)
     b = str(b)
     for x in a:
         aList.append(x)
     for x in b:
         bList.append(x)
     return sorted(aList) == sorted(bList)
 
 def projectEulerProblemFortyNine():
     allPrimes = sieveEratosthenes(10000)
     fourDigit = []
     for x in allPrimes:
         if x>1000:
             fourDigit.append(x)
     
     allTriples = []
     
     l = len(fourDigit)
     for a in range(l):
         for b in range(a+1, l):
             v1 = fourDigit[a]
             v2 = fourDigit[b]
             v3 = (v1+v2)/2
             if v3 in fourDigit:
                 if equivalentString(v1, v2) and equivalentString(v1, v3):
                     allTriples.append(sorted([v1,v2,v3]))
     
     final = []
     for x in allTriples:
         s = ""
         for y in x:
             s+=str(y)
         final.append(s)
     
     return final
 
 start = time.time()
 print projectEulerProblemFortyNine()
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 ['148748178147', '296962999629']
 --- 5.9415140152 seconds ---
 
 for no input
 '''

And with that, we’re done. It took 5.94 seconds to run through all the 4-digit primes… yikes. I may come back to this problem to look for a more efficient solution eventually.

Thanks for reading! See you tomorrow.

Project Euler Problem #48

Problem #48 is one of the many problems on Project Euler that involves modular arithmetic. The question reads:

Project Euler Problem 48: Self powers
The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.
Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

My solution involves a common technique for finding the remainder when a large power is divided by a large mod known as Exponentiation by Squaring. Here’s my solution:

Solution #1: Exponentiation by Squaring Approach

We simply use the exponentiation by squaring approach to find the remainder when each power is divided by 10^10. The remainder when a number is divided by 10^n is the same as the last n digits of the number. Thus, by converting each exponent in the list to binary and then finding the remainder when each square power of the base is divided by 10^10, the Exponentiation by Squaring approach can be used to quickly get an answer. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Exponentiation by Squaring Approach to Project Euler Problem #48
 '''
 
 import time
 
 def lastDigitsPower(a,b,n):
     myMod = 10**n
     total = a
     powers = [a]
     e = 1
     while(e<b):
         total*=total
         total%=myMod
         powers.append(total)
         e*=2
     myBinary = (bin(b)[2:])[::-1]
     final = 1
     for c in range(len(myBinary)):
         if(int(myBinary[c])):
             final*=powers[c]
             final%=myMod
     return final
 
 def projectEulerProblemFortyEight(i,n):
     total = 0
     myMod = 10**n
     for c in range(1,i+1):
         total+=lastDigitsPower(c, c, n)
         total%=myMod
     return total
 
 start = time.time()
 print projectEulerProblemFortyEight(1000, 10)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 9110846700
 --- 0.00864911079407 seconds ---
 
 for input of i = 1000, n = 10
 '''

As shown above, the Exponentiation by Squaring method can be very effective for dealing with modular arithmetic for large powers. An alternate method may use Euler’s Totient Theorem, but because this question was relatively simple, I decided not to use it for this solution.

Thanks for reading! See you tomorrow.