Project Euler

I chose to do math in my spare time once..

Thu, 01 Oct 2015

Intro

This article is where I will put up a few of my Project Eulers Solutions. They arent particularly special but I really enjoyed solving the problems so I thought Id share a few of the problems that I had fun with.


36 - Double-Base Palindromes

At this point I have solved a few of the Eulers problems but I chose this one to share over the similar problem 4 because I felt this one was a little more fun since you have got to convert the number to base 2 from base 10 and also check it. The only hitch in this really was the leading zeros but that didnt take much doing to get around. Below is the code and the problem.

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

#! usr/bin/python
#Find check to see if its a palindrome
#Add palindromes that pass the check to total
def findPals(i):
    total=0
    for i in range(0, 1000000):
        if(str(i)==str(i)[::-1] and (str(toBin(i))==str(toBin(i))[::-1])):
            total+=i
            i+=1    
        i+=1    
    return(total)
#Convert base 10 to base 2
def toBin(n):
    return("{0:b}".format(n))

def main():
    i=0
    print(findPals(i))
    
if __name__ == '__main__': main()

8 - Largest Product in series

This one also isnt particularly challenging but it was fun and it got me comfortable with lists. All I really did was take that large number, drop it into a list so I could iterate through it and then just made a list of the products of the 13 adjact numbers. After that it was just a quick call to max() and there you go. The number is a bit large being a 1000 digits and all so I threw it into a tab.

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

#! usr/bin/python 

def main(): 
    #Convert int to list
    number= "See tab above"
    j = [int(i) for i in str(number)]
    k=0
    #create second list to store products
    products=[]
    while(k<988):
        #multiply 13 ints at a time from list 1
        product = j[k]*j[k+1]*j[k+2]*j[k+3]*j[k+4]*j[k+5]*j[k+6]*j[k+7]*j[k+8]*j[k+9]*j[k+10]*j[k+11]*j[k+12]
        
        if(product==0):
            k+=1
        else:#if product isnt zero add to list
            products.append(product)
            k+=1
        
    #Find largest product of consecutive ints
    print(max(products))
    
if __name__ == '__main__': main()

25 - 1000 Digit Fibonacci Number

The Fibonacci problems for me represented an interesting problem. I could go about it recursively but that o(n) becomes far too large on this problem. I could use floating point arithmetic as well, which I tried to do on problem 2. Theres two things about that, one is that floating point arithmetic becomes inaccurate due to rounding errors the higher you go, and two is that at F(34) it breaks. So I knew when I had to pass F(34)r that I would need a new approach. So Ive got a simple generator going and a counter to stop at the right index0. It worked like a charm. Another approach I couldve considered is implementing some form of caching ge so instead of calculating up the chain to find the next number, I only need to work with the previous two Ive found.

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1. Hence the first 12 terms will be:

F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144 The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

#! usr/bin/python
#Digit Counter
def digits(n):
    n=[int(i) for i in str(n)]
    if len(n)==1000:
        return True
    return False

#Fibonnaci Generator
def fib():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a + b


def main():
    stop = False
    a = fib()
    i=-1
    #Stop when N is a length of 1000
    while stop!=True:
        i+=1 #Use I to track where in the sequence we are
        n=a.next()
        stop=digits(n)
        
    
    print(i)

if __name__ == '__main__': main()
Loading...
Anthony Laiuppa

If you have any feedback feel free to @ me on twitter, Im always looking to learn. -AL