I have a mathematical problem about prime power. A number \$x\$ can be considered a prime power if \$x = p^k\$ where \$p\$ is a prime and \$k\$ is a non-negative integer. For example, \$81\$ is a prime power because \$81 = 3^4\$. Now, form a sequence of numbers in the following way. Start by taking a random number.
- If the number is a prime power, end the sequence.
- If the number is not a prime power, minus that number with the biggest prime power that's not more than the number itself. Do it over and over again until a prime power is met, then stop.
For example, 34 is not a prime power. Hence we minus it with the highest prime power that's not more than it which is \$32\$, hence \$34-32=2\$. \$2\$ is a prime power, so we stop. In this case, the length of the operation is 2 (because 34 -> 2).
Another example is \$95\$. \$95\$ isn't a prime power, so \$95-89=6\$. \$6\$ is also not a prime power, so we minus it again with the highest prime power, \$6-5=1\$. \$1\$ is a prime power (because \$2^0 = 1\$), so we stop. In this case, the length of the operation is 3 (because 95 -> 6 -> 1).
Known that:
- 1 is the smallest initial number that can be formed with a length of 1 operation.
- 6 is the smallest initial number that can be formed with a length of 2 operations.
- 95 is the smallest initial number that can be formed with a length of 3 operations.
- 360748 is the smallest initial number that can be formed with a length of 4 operations.
I made an application using Python to find the smallest initial number that can be formed with a length of 5, 6 and 7 operations. It is using looping to solve the problem. However, to find the smallest initial number that can be formed with a length of 4 or more operations, the program takes a very very long time to run.
Is there any way I could improve my code to make the program to run much faster? I just want to focus on getting the number with 5, 6 and 7 operations.
from sympy.ntheory import factorint
def pp(q): #to check whether it is a prime power
fact=factorint(q)
p=int(list(fact.keys())[0])
n=int(list(fact.values())[0])
if q!=p**n:
return False
else:
return True
a=[1,6][-1]
b=a*2
d=1
while d!=0:
c=b-a
if pp(b)==False and pp(c)==True:
for i in range(b-1,c-1,-1):
if i==c:
d=0
elif pp(i)==True:
b=i+a
break
elif pp(b)==False:
for i in range(b-1,c-1,-1):
if i==c:
b=b+a+1
elif pp(i)==True:
b=i+a
break
elif pp(b)==True:
b=b+a
b