Python,C,C++ and JAVA programs for CBSE, ISC, B.Tech and I.T Computer Science and MCA students

The Programming Project: Strong Achilles Numbers: Python Code

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


No comments:

Post a Comment