The Inner Machinations of Walker

Project Euler Problem #115

Problem #115 concerns separating rows of blocks into red sections and black sections. The question reads:

Project Euler Problem 115: Counting block combinations II
NOTE: This is a more difficult version of Problem 114.
A row measuring n units in length has red blocks with a minimum length of m units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.
Let the fill-count function, F(m, n), represent the number of ways that a row 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 for which the fill-count function first exceeds one million.
In the same way, for m = 10, it can be verified that F(10, 56) = 880711 and F(10, 57) = 1148904, so n = 57 is the least value for which the fill-count function first exceeds one million.
For m = 50, find the least value of n for which the fill-count function first exceeds one million.

My solution is almost identical to my solution for Problem #114. Therefore, I will not repeat the details for the recursions that I used. Here’s my solution:

Solution #1: Dynamic Programming Approach

As I did in Problem #114, we separate the recursion into tilings that end in a red square and tilings that end in a grey square. The recursions are nearly identical to the ones in Problem #114, and the initial conditions can easily be extended to account for the larger minimal red tilings. From this point, it is only a matter of applying the recursion repeatedly until a value with over 1000000 different tilings is obtained. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Dynamic Approach to Project Euler Problem #115
 '''
 
 import time
 
 def projectEulerProblemOneHundredFifteen(m,n):
     rTotals = [0]*m
     rTotals.append(1)
     gTotals = [1]*(m+1)
     sumG = sum(gTotals)
     l = len(gTotals)
     v = rTotals[l-1]+gTotals[l-1]
     while(v<=n):
         rValue = sumG
         for x in range(1,m):
             rValue-=gTotals[l-x]
         gValue = v
         rTotals.append(rValue)
         gTotals.append(gValue)
         sumG+=gValue
         l+=1
         v = rTotals[l-1]+gTotals[l-1]
     return l-1
 
 start = time.time()
 print projectEulerProblemOneHundredFifteen(50, 1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 168
 --- 0.000357866287231 seconds ---
 
 for input of m = 50, n = 1000000.
 '''

And with that, we’re done. Once again, dynamic programming proves to be invaluable at solving recursive problems.

Thanks for reading! See you tomorrow.

Project Euler Problem #114

Problem #114 concerns partitioning a row of blocks with contiguous red sections and contiguous grey sections. The question reads:

My solution for this problem involves dynamic programming. Here’s my solution:

Solution #1: Dynamic Programming Approach

It suffices to recursively find the number of ways a row of n units can be filled such that the last square is red and the number of ways a row of n units can be filled such that the last square is grey. If the number of ways ending in a red square is a_n and the number of ways ending in a grey square is b_n, then a_n = b_(n-3)+b_(n-2) + … + b_0 and b_n = a_(n-1) + b_(n-1). Thus, with these recursions, the values of a_50 and b_50 can be determined, and the answer is simply a_50+b_50. Giving initial values of a_0, a_1, a_2, a_3, b_0, b_1, b_2, and b_3, it is easy to dynamically find the answer. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Dynamic Approach to Project Euler Problem #114
 '''
 
 import time
 
 def projectEulerProblemOneHundredFourteen(n):
     rTotals = [0,0,0,1]
     gTotals = [1,1,1,1]
     sumG = sum(gTotals)
     l = len(gTotals)
     while(l<=n+1):
         rValue = sumG - gTotals[l-1]-gTotals[l-2]
         gValue = rTotals[l-1]+gTotals[l-1]
         rTotals.append(rValue)
         gTotals.append(gValue)
         sumG+=gValue
         l+=1
     return rTotals[n]+gTotals[n]
 start = time.time()
 print projectEulerProblemOneHundredFourteen(50)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 16475640049
 --- 3.40938568115e-05 seconds ---
 
 for input of n = 50.
 '''

And with that, we’re done. This is a great example of the powers of dynamic programing. Over 16 billion cases could be counted in under a tenth of a millisecond.

Thanks for reading! See you tomorrow.

Project Euler Problem #113

Problem #113 concerns numbers whose digits are neither increasing nor decreasing. The question reads:

Project Euler Problem 113: Non-bouncy numbers
Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.
Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.
We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.
As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below 10¹⁰.
How many numbers below a googol (10¹⁰⁰) are not bouncy?

This problem can be solved very efficiently with some mathematical knowledge. Here’s my solution:

Solution #1: Combinatorial Approach

We proceed by counting the number of increasing numbers below a googol and the number of decreasing numbers below a googol and finding the sum of these results. To form an increasing number below a googol, it suffices to arrange 100 arbitrary digits in increasing order. The distinguishing factor between the increasing numbers is the number of each digit 0, 1, 2, …, 9 within the increasing number. The number of choices for each digit can be found with Stars and Bars: the number of distinct ordered sums with k elements and a total of n is equal to (n+k-1) choose (k-1). Thus, the number of increasing numbers is 109 choose 9. This includes the case where all digits are 0, so 1 must be subtracted. Similarly, to generate a decreasing number below a googol, it suffices to arrange 100 arbitrary digits in decreasing order. However, in this case, some of the digits can be leading zeros, so there are 11 choices for each digit. Thus, the number of decreasing numbers is 110 choose 10. Once again, this includes the case where all digits are 0 so 1 must be subtracted. Thus, the running total is (109 choose 9) + (110 choose 10) – 2. However, this total double counts numbers of the form xxx…xxx with an arbitrary number of equal digits, and it includes numbers which only contain leading zeros and ending zeros. Thus, 100*2 = 200 must be subtracted from the total. Thus, the answer is (109 choose 9) + (110 choose 10) – 202. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Combinatorial Approach to Project Euler Problem #113
 '''
 
 import time
 
 def nChooseR(n,r):
     value = 1
     for x in range(r):
         value*=(n-x)
         value/=(x+1)
     return value
 
 def projectEulerProblemOneHundredThirteen(n):
     increasing = nChooseR(n+9,9)-1
     decreasing = nChooseR(n+10,10)-1
     return increasing+decreasing-10*n
 
 start = time.time()
 print projectEulerProblemOneHundredThirteen(100)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 51161058134250
 --- 1.4066696167e-05 seconds ---
 
 for input of n = 100.
 '''

And with that, we’re done. This approach finishes the problem in under a millisecond, so it is more than efficient enough for our purposes. This is a great example of the power of discrete math.

Thanks for reading! See you tomorrow.

Project Euler Problem #112

Problem #112 concerns numbers which are neither increasing nor decreasing. The question reads:

Project Euler Problem 112: Bouncy numbers
Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.
Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.
We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.
Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.
Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.
Find the least number for which the proportion of bouncy numbers is exactly 99%.

My solution for this question can be summarized as a brute force approach that relies on the percentage being an integer. Here’s my solution:

Solution #1: Brute Force Approach

We simply check every interval of 100 consecutive positive integers until the cumulative total of bouncy numbers is 99% of the cumulative total of the number of integers in all of the intervals. Here is an implementation of this approach in Python 2.7:

 '''
 Author: ArrGeeStee
 Brute Force Approach to Project Euler Problem #112
 '''
 
 import time
 
 def isBouncy(n):
     a = str(n)
     curr = int(a[0])
     increasing = True
     decreasing = True
     for c in range(1,len(a)):
         v = int(a[c])
         if(v>curr):
             decreasing = False
         if(v<curr):
             increasing = False
         if not decreasing and not increasing:
             return True
         curr = v
     return False

 def projectEulerProblemOneHundredTwelve(n):
     complement = 100-n
     notBouncy = 100
     total = 100
     while(complement*total!=notBouncy*100):
         total+=100
         for x in range(100):
             if not isBouncy(total-x):
                 notBouncy+=1
     return total
 
 start = time.time()
 print projectEulerProblemOneHundredTwelve(99)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 1587000
 --- 2.88207697868 seconds ---
 
 for input of n = 99.
 '''

And with that, we’re done. This brute force approach wasn’t very efficient as it took nearly 3 seconds to run. I may come back to this problem at some point to search for a more efficient solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #111

Problem #111 concerns 10-digit primes with lots of repeated digits. The question reads:

My solution to this problem can best be described as a brute force approach. Here’s my solution:

Solution #1: Brute Force Approach

We simply search for primes with each digit. Through brute force it is possible to check every possible position of the repeated digits. Once the largest number of possible repeated digits is verified, brute force can be used to find every prime with those repeated digits. Here’s an implementation of this approach in Python 2.7:

'''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #111
 '''
 
 import time
 from math import sqrt
 
 def isPrime(n):
     if(n%2==0):
         return False
     c = 3
     upper = sqrt(n)
     while(c<=upper):
         if(n%c==0):
             return False
         c+=2
     return True
 
 def convertNDigits(n,x):
     a = str(x)
     while len(a)<n:
         a = "0" + a
     return a
 
 def allPermutations(myList):
     l = len(myList)
     if l==0:
         return [[]]
     if(l==1):
         return [myList]
     a = myList[0]
     b = allPermutations(myList[1:])
     total = []
     for x in b:
         for z in range(l):
             new = x[0:z]
             new.append(a)
             new.extend(x[z:])
             if new not in total:
                 total.append(new)
     return total
 
 def projectEulerProblemOneHundredEleven(n):
     final = 0
     for d in range(0,10):
         for m in range(n,-1,-1):
             total = 0
             order = []
             for x in range(m):
                 order.append(1)
             for x in range(m,n):
                 order.append(0)
             v = allPermutations(order)
             for x in range(0,10**(n-m)):
                 a = convertNDigits(n-m, x)
                 possible = True
                 for q in a:
                     if q == str(d):
                         possible = False
                         break
                 if possible:
                     for z in v:        
                         s = ""
                         b = 0
                         for y in z:
                             if y==1:
                                 s+=str(d)
                             else:
                                 s+=a[b]
                                 b+=1
                         if int(s[0])>0 and isPrime(int(s)):
                             total+=int(s)
             if total>0:
                 final+=total
                 break
     return final
 
 start = time.time()
 print projectEulerProblemOneHundredEleven(10)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 612407567715
 --- 0.370451927185 seconds ---
 
 for input of n = 10.
 '''

And with that, we’re done. The main problems here were implementing casework based on potential leading zeroes. This solution was more than efficient enough for this problem, so I probably will not return to this problem.

Thanks for reading! See you tomorrow.

Project Euler Problem #109

Problem #109 concerns checking out in a game of darts. The question reads:

My solution for this problem is another example of the powers of brute force. Here’s my solution:

Solution #1: Brute Force Approach

We simply check every combination of dart scores that end in a double and count the ones with a total less than 100. There are 62 possibilities for each of the three darts, so at most there are 62^3 = 238328 possibilities to consider. Here’s an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #109
 '''
 
 import time
 
 def checkout(n):
     possible = [25,50]
     for x in range(1,21):
         possible.append(x)
         possible.append(2*x)
         possible.append(3*x)
     possible = sorted(possible)
     total = 0
     for a in possible:
         v = n-a
         for b in possible:
             if(b>a):
                 break
             else:
                 w = v-b
                 if(w%2==0 and (w<=40 or w==50)):
                     total+=1
     return total
 
 def projectEulerProblemOneHundredNine(n):
     possible = [25,50]
     doubles = []
     for x in range(1,21):
         possible.append(x)
         possible.append(2*x)
         possible.append(3*x)
         doubles.append(2*x)
     possible = sorted(possible)
     doubles.append(50)
     total = 0
     l = len(possible)
     for i in range(l):
         for j in range(i,l):
             v = possible[i]+possible[j]
             for d in doubles:
                 if v+d<n:
                     total+=1
                 else:
                     break
             if v>=n:
                 break
     for i in range(l):
         v = possible[i]
         for d in doubles:
             if v+d<n:
                 total+=1
             else:
                 break
         if v>=n:
             break
     for d in doubles:
         if d<n:
             total+=1
         else:
             break
     return total
 
 start = time.time()
 print projectEulerProblemOneHundredNine(100)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 38182
 --- 0.00199699401855 seconds ---
 
 for input of n = 100.
 '''

And with that, we’re done. While this may have been a brute force solution, it was more than efficient enough for this problem. I may come back to this problem eventually to look for a different approach.

Thanks for reading! See you tomorrow.

Project Euler Problem #108

Problem #108 concerns the Diophantine equation 1/x + 1/y = 1/n for arbitrary integers n. The question reads:

Project Euler Problem 108: Diophantine reciprocals I
In the following equation x, y, and n are positive integers.
1/x + 1/y = 1/n
For n = 4 there are exactly three distinct solutions:
1/5 + 1/20 = 1/4
1/6 + 1/12 = 1/4
1/8 + 1/8 = 1/4
What is the least value of n for which the number of distinct solutions exceeds one-thousand?
NOTE: This problem is an easier version of Problem 110; it is strongly advised that you solve this one first.

I believe the most natural approach to solving this problem with knowledge of math is Simon’s Favorite Factoring Trick. Here’s my solution:

Solution #1: SFFT Approach

We can rearrange the given equation to xy = nx+ny. By Simon’s Favorite Factoring Trick, this equation can be factored as (x-n)(y-n) = n^2. It follows that the number of ordered solutions (x,y) is the number of factors of n^2. Thus, it suffices to find the smallest value of n such that n^2 has at least 1999 factors. I did this by using the Sieve of Eratosthenes to find all primes less than an arbitrary upper bound and then using this list of primes to check each potential value of n until a sufficient value was found. Here’s an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Factoring Approach to Project Euler Problem #108
 '''
 
 import time
 
 from math import sqrt
 
 def countFactorSquare(n):
     a = n*n
     t = 0
     for x in range(1,n):
         if(a%x==0):
             t+=1
     return t+1
 
 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 projectEulerProblemOneHundredEight(n,m):
     myPrimes = sieveEratosthenes(n)
     primes = []
     exponents = []
     for a in range(n+1):
         primes.append([])
         exponents.append([])
     for x in myPrimes:
         for y in range(x,n+1,x):
             primes[y].append(x)
             exponents[y].append(1)
         power = x*x
         while(power<=n):
             for y in range(power,n+1,power):
                 l = len(exponents[y])
                 exponents[y][l-1]+=1
             power*=x
     totals = []
     for x in range(n+1):
         myProd = 1
         for a in exponents[x]:
             myProd*=(2*a+1)
         myProd = (myProd+1)/2
         totals.append(myProd)
     for x in range(n+1):
         if(totals[x]>m):
             return x
     return -1
 
 start = time.time()
 print projectEulerProblemOneHundredEight(1000000,1000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 180180
 --- 3.04166793823 seconds ---
 
 for input of n = 1000000, m = 1000.
 '''

And with that, we’re done. Even with an arbitrary upper bound for primes, this solution took over 3 seconds to run. I may come back to this problem eventually to look for a more efficient approach.

Thanks for reading! See you tomorrow.

Project Euler Problem #107

Problem #107 concerns determining the Minimum Spanning Tree for a weighted graph. The question reads:

As it turns out, the formal term for this type of minimal network is the Minimum Spanning Tree of the graph. There are many well known algorithms for finding the minimum spanning tree of an arbitrary graph. I used Prim’s Algorithm because I thought it would be the easiest to implement. Here’s my solution:

Solution #1: Prim’s Algorithm Approach

Prim’s Algorithm involves choosing an arbitrary starting point and growing the Minimum Spanning Tree one vertex at a time by choosing the potential edge with the lowest weight. I recommend checking the wikipedia article linked above for a clearer description of this algorithm. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #107
 '''
 
 import time
 
 f = open("PE107Grid.txt","r")
 
 if f.mode=="r":
     contents = f.readlines()
     realContents = []
     for x in contents:
         coords = x.split(",")
         new = []
         for x in coords:
             if x=="-" or x=="-\n":
                 new.append(0)
             else:
                 new.append(int(x))
         realContents.append(new)
 else:
     raise ValueError("Cannot read from file")
 
 def minimumSpanningTree(myList):
     l = len(myList)
     vertices = [0]
     edges = []
     while(len(vertices)<l):
         newV = []
         newW = []
         newC = []
         for x in vertices:
             for i in range(l):
                 if(x!=i):
                     v = myList[x][i]
                     if(v>0 and i not in vertices):
                         if i in newV:
                             a = newV.index(i)
                             w = newW[a]
                             if(v<w):
                                 newW[a] = v
                                 newC[a] = x
                         else:
                             newV.append(i)
                             newW.append(v)
                             newC.append(x)
         lw = len(newW)
         if(lw==0):
             return -1
         else:
             myMin = newW[0]
             minIndex = 0
             for i in range(lw):
                 if(newW[i]<myMin):
                     myMin = newW[i]
                     minIndex = i
             vertices.append(newV[minIndex])
             edges.append(sorted([newC[minIndex],newV[minIndex]]))
     return edges
 
 def projectEulerProblemOneHundredSeven(myList):
     mySum = 0
     for x in myList:
         mySum+=sum(x)
     mySum/=2
     a = minimumSpanningTree(myList)
     total = 0
     for x in a:
         total+=myList[x[0]][x[1]]
     return mySum-total
     
 start = time.time()
 print projectEulerProblemOneHundredSeven(realContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 259679
 --- 0.0105230808258 seconds ---
 
 for input of given grid of weights.
 '''

And with that, we’re done. Prim’s Algorithm was more than efficient enough for a graph of degree 40. I may come back to this problem at some point to investigate the other well known algorithms for this problem. I apologize for skipping Project Euler Problem #106. Unfortunately, I have not solved it yet.

Thanks for reading! See you tomorrow.

Project Euler Problem #105

Problem #105 concerns sets with ordered sums of all of their subsets. The question reads:

Project Euler Problem 105: Special subset sums: testing
Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:
S(B) ≠ S(C); that is, sums of subsets cannot be equal.
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 set because 65 + 87 + 88 = 75 + 81 + 84, whereas {157, 150, 164, 119, 79, 159, 161, 139, 158} satisfies both rules for all possible subset pair combinations and S(A) = 1286.
Using sets.txt (right click and "Save Link/Target As..."), a 4K text file with one-hundred sets containing seven to twelve elements (the two examples given above are the first two sets in the file), identify all the special sum sets, A₁, A₂, ..., A_k, and find the value of S(A₁) + S(A₂) + ... + S(A_k).
NOTE: This problem is related to Problem 103 and Problem 106.

My solution for this problem can most concisely be called brute force. Here’s my solution:

Solution #1: Brute Force Approach

We first eliminate obvious non-special subsets by comparing the largest subset of size n-1 with the smallest subset of size n for each n from 1 to the length of the potential special set. To check that no two subset sums are equal, brute force is used. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #105
 '''
 
 import time
 f = open("PE105Sets.txt","r")
 
 if f.mode=="r":
     contents = f.readlines()
     realContents = []
     for x in contents:
         coords = map(int, x.split(","))
         realContents.append(coords)
 else:
     raise ValueError("Cannot read from file")
 
 def testOrder(a):
     a = sorted(a)
     first = []
     total = 0
     for x in a:
         first.append(total)
         total+=x
     first.append(total)
     back = []
     total = 0
     for x in a[::-1]:
         back.append(total)
         total+=x
     back.append(total)
     l = len(a)
     for x in range(1,l):
         if first[x+1]<back[x]:
             return False
     return True
 
 def subset(myList,n):
     if n==0:
         return [[]]
     l = len(myList)
     if l<n:
         return []
     a = myList[0]
     b = subset(myList[1:],n)
     c = subset(myList[1:], n-1)
     for x in c:
         x.append(a)
         b.append(sorted(x))
     return b
 
 def testNoneEqual(a):
     l = len(a)
     allSums = []
     for x in range(1,l+1):
         v = subset(a,x)
         for y in v:
             value = sum(y)
             if value in allSums:
                 return False
             allSums.append(value)
     return True
 
 def isSpecialSet(myList):
     if testOrder(myList):
         if testNoneEqual(myList):
             return True
     return False
 
 def projectEulerProblemOneHundredFive(myList):
     total = 0
     for x in myList:
         if isSpecialSet(x):
             total+=sum(x)
     return total
 
 print isSpecialSet([20,31,38,39,40,42,45])
 
 start = time.time()
 print projectEulerProblemOneHundredFive(realContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 73702
 --- 0.487046003342 seconds ---
 
 for input of given list of sets.
 '''

And with that, we’re done. Even with the obvious brute force approach, this program ran in well under a second. I may come back to this problem at some point to look for a more efficient means of checking that no two subsets have the same sum.

Thanks for reading! See you tomorrow.

Project Euler Problem #104

Problem #104 concerns Fibonacci numbers which contain each of the digits 1-9 in their leftmost and their rightmost digits. The question reads:

Project Euler Problem 104: Pandigital Fibonacci ends
The Fibonacci sequence is defined by the recurrence relation:
F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.
It turns out that F₅₄₁, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F₂₇₄₉, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.
Given that F_k is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

My solution for this question is not rigorous, and it probably wouldn’t get the correct answer if the question asked for the nth index with this property. However, it was efficient enough to solve this problem within a reasonable amount of time. Here’s my solution:

Solution #1: Arbitrary Precision of Leftmost Digits Approach

It is easy to determine the rightmost 9 digits of the nth Fibonacci number by simply storing the number mod 10^9. The difficulty comes in investigating the leftmost 9 digits. To do this, I arbitrarily stored the leftmost 15 digits and recursively updated them to get approximate leftmost 15 digits for each Fibonacci number. My hope is that the leftmost 9 digits of this recursive result will have the correct leftmost 9 digits for successive Fibonacci numbers. By checking the leftmost and rightmost 9 digits for the pandigital property, it is possible to find the first index 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 #104
 '''
 
 import time
 
 def isPandigital(x):
     return sorted(x) == ["1","2","3","4","5","6","7","8","9"]
 
 def projectEulerProblemOneHundredFour(n):
     firstL = 1
     secondL = 1
     firstF = 1
     secondF = 1
     i = 3
     while(True):
         temp = firstL+secondL
         secondL = firstL
         firstL = temp%(10**9)
         temp = firstF + secondF
         secondF = firstF
         if(temp>10**n):
             temp = int(str(temp)[0:n])
             secondF/=10
         firstF = temp
         if isPandigital(str(firstL)):
             if isPandigital(str(firstF)[0:9]):
                 return i
         i+=1
 
 start = time.time()
 print projectEulerProblemOneHundredFour(15)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 329468
 --- 0.478230953217 seconds ---
 
 for input of given problem.
 '''

And with that, we’re done. It is very likely that for successive indices with this property, a larger amount of precision is necessary. I may come back to this problem eventually to find a more rigorous solution. Regardless, this solution did solve the problem within a second.

Thanks for reading! See you tomorrow.