Python,C,C++ and JAVA programs for CBSE, ISC and MCA students

The Programming Project

Thursday, August 28, 2014

Smallest multiple : Euler Project

Smallest multiple : Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The answer to this problem is to find the l.c.m of the numbers 1,2,3,.......,18,19,20

Python Code

def smallestMultiple():
    lcm = 2
    tup = [0 for i in range(20)]
    for i in range(20):
        tup[i] = i+1
    while lcm > 1:
        count = 0
        for i in range(20):
            if lcm%tup[i] == 0:
                count = count+1
            else:
                break   
        if count != 20:
            lcm = lcm+1       
        else:
            break
    print lcm
smallestMultiple()           
           

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

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()                        


Wednesday, August 27, 2014

Strong Achilles Numbers: Python Code

A positive integer n is powerful if p2 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 = 25·33 and 1800 = 23·32·52.
We shall call a positive integer S a Strong Achilles number if both S and φ(S) are Achilles numbers.1
For example, 864 is a Strong Achilles number: φ(864) = 288 = 25·32. However, 1800 isn't a Strong Achilles number because: φ(1800) = 480 = 25·31·51.
There are 7 Strong Achilles numbers below 104
How many Strong Achilles numbers are there below 108?
1 φ 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()