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