10001st prime : Problem 7 Euler Project

10001st prime:Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

Python Code

import math
def countPrime():
    primeCount = 0
    prime = 1
    counter = 2
    def checkPrime(numb):
        prime = True
        for i in range(int(math.sqrt(numb))):
            i = i+2
            if numb%i == 0:
                prime = False
                break
        if numb == 2:
            return True
        else:           
            return prime
    while primeCount < 10001:
         if checkPrime(counter) == True:
             primeCount = primeCount+1
             prime = counter
         counter = counter + 1   
    print "10001 st Prime is",prime        
countPrime()

Largest palindrome product: Euler Project Problem 4

Largest palindrome product

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

Python Code

def largestPalindromeProduct():
    largestPalin = 1
    def checkPalin(strNumb):
        palin = True
        for i in range(len(strNumb)+1/2):
            if strNumb[i] == strNumb[len(strNumb)-1-i]:
                continue
            else:
                palin = False     
        if palin == False:
            return False
        else:
            return True
    for i in range(999-100+1):
        i = i+100
        for j in range(999-100+1):
            j = j+100
            numb = i*j
            strNumb = str(numb)
            if strNumb[0] != strNumb[len(strNumb)-1]:
                continue
            if checkPalin(strNumb) == True:
                if largestPalin < numb:
                    largestPalin = numb
                    a = i
                    b = j
    print "Largest Palindrome formed by the product of three digit numbers is:",largestPalin,"=",a,"x",b
largestPalindromeProduct()           

Multiples of 3 and 5 : Euler Project

Multiples of 3 and 5

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Project Euler.net

Python Code

def sumMultiples():
    sumTotal = 0
    lwrBnd = 1
    uprBnd = input("Enter the upper bound:")
    uprBnd = uprBnd-1
    print ("Enter the numbers sum of whose multiples are to be found:")
    a = input("First Number:")
    b = input("Second Number:")
    lcm = 2
    while lcm > 1:
        if lcm%a == 0 and lcm%b == 0:
            break
        else:
            lcm = lcm+1
    lastTerm = a*(uprBnd/a)   
    n = lastTerm/a
    sumTotal = sumTotal + a*(n*(n+1))/2
    lastTerm = b*(uprBnd/b)
    n = lastTerm/b
    sumTotal = sumTotal + b*(n*(n+1))/2
    lastTerm = lcm*(uprBnd/lcm)
    n = lastTerm/lcm
    sumTotal = sumTotal - lcm*(n*(n+1))/2
    print "Required Sum is",sumTotal
sumMultiples()   
   

Even Fibonacci numbers: Python Code

Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Euler Project Problem 2

Python Code

def sumEvenFiboNumbers():
    a = 1
    b = 2
    nextSum = 0
    totalSum = 2
    while True:
        nextSum = a+b
        a = b
        b = nextSum
        if nextSum <= 4000000:
            if nextSum%2 == 0:
                totalSum = totalSum+nextSum
        else:
            break
    print "Sum of even fibo terms less than 4 million is:"totalSum       
sumEvenFiboNumbers()   

Largest prime factor: Python Code : Problem 3

Largest prime factor : Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
http://projecteuler.net/problem=3 

Answer:  6857

Python Code

import math
def largestPrimeFactor():
    numb = input("Enter the number:")
    pf = 1
    def checkPrime(numb):
        prime = True
        for i in range(int(math.sqrt(numb))):
            i = i+2
            if numb%i == 0:
                prime = False
                break
        if numb == 2:
            return True
        else:           
            return prime
    for i in range(int(math.sqrt(numb))):
        i = i+2
        if checkPrime(i) == True and numb % i == 0:
            print i
            pf = i
    print "Largest Prime factor of",numb,"is:",pf
largestPrimeFactor()                        

Strong Achilles Numbers: Python Code

A positive integer n is powerful if p² is a divisor of n for every prime factor p in n.
A positive integer n is a perfect power if n can be expressed as a power of another positive integer.
A positive integer n is an Achilles number if n is powerful but not a perfect power. For example, 864 and 1800 are Achilles numbers: 864 = 2⁵·3³ and 1800 = 2³·3²·5².
We shall call a positive integer S a Strong Achilles number if both S and φ(S) are Achilles numbers.¹
For example, 864 is a Strong Achilles number: φ(864) = 288 = 2⁵·3². However, 1800 isn't a Strong Achilles number because: φ(1800) = 480 = 2⁵·3¹·5¹.
There are 7 Strong Achilles numbers below 10⁴
How many Strong Achilles numbers are there below 10⁸?
¹ φ denotes Euler's totient function.

Problem taken from Euler Project

Python Code:

# STRONG ACHILLIES NUMBER

def strongAchilliesNumber():
    strongAchilliescounter = 0
    a = input("Enter the lower limit (must be >= 1)")
    b = input("Enter the upper limit(must be <= 10^8)")
    def checkPrime(numb):
        prime = True
        for i in range(numb/2):
            i = i+2
            if numb%i == 0:
                prime = False
                break
        if numb == 2:
            return True
        else:           
            return prime
   
    def calculatePhiNumber(number):
        phiNumber = 1
        for i in range(number/2):
            i = i+2
            powr = 0
            if checkPrime(i) == True and number % i == 0:
                powr = powr+1
                numb = number/i 
                while numb % i == 0:
                    powr = powr+1
                    numb = numb/i
                phiNumber = phiNumber*(pow(i,powr)-pow(i,powr-1))
        return phiNumber
                            
    def checkPowerful(number):
        powerful = True   
        phiNumber = 1   
        powr = 0
        powersList = ()
        maxPower = 0
        for i in range(number/2):
            i = i+2
            powr = 0
            if checkPrime(i) == True and number % i == 0:
                #print i
                powr = powr+1
                numb = number/i 
                while numb % i == 0:
                    powr = powr+1
                    numb = numb/i
                if maxPower < powr:
                    maxPower = powr
                powersList = powersList+(powr,)
                if powr < 2:
                    powerful = False
                    break
        #print powersList,maxPower           
        if powerful == False:
            return False
        else:
            perfect  = True   
            for l in range(maxPower-1):
                l = l+2
                #print ">",l
                temp = True
                for p in powersList:
                    if p%l != 0:        
                        temp = False
                if temp == False:
                    perfect = False
                else:
                    perfect = True
                    break
            if perfect == False:
                return True
            else:
                return False
    for i in range(b):           
        number = i+a
        if checkPowerful(number) == True:
            if checkPowerful(calculatePhiNumber(number)) == True:
                strongAchilliescounter = strongAchilliescounter + 1
                print number,"is a Strong Achilles number:"
            else:
                print number,"is an Achilles number but not a Strong Achillies number:"
                continue   
        else:
            print number,"is not an Achilles number:"
            continue
    print "Total number of Strong Achilles number is:",strongAchilliescounter                           
strongAchilliesNumber()       

Longest Collatz sequence: Python Code

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

 

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?

Python Code:

def Collatz():
    lengthCollatz = 1
    count = 1
    numb = 0
    longestCnumb =1
    for i in range(1000000):
        count = 1
        numb = i+1
        while numb != 1:
            if numb%2 == 0:
                numb = numb/2
            else:
                numb = 3*numb+1
            count +=1
        if count > lengthCollatz:
                lengthCollatz = count;   
                longestCnumb = i+1;
    print "Longest length of Collatz Sequence is:",lengthCollatz,"and the number is",longestCnumb                 
Collatz()