Power Number

general
,
1

A power number is a number of the form A^B (A, B ≥ 2). The list of Power Passwords starts with 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100…

how to check for a number if it is on this form.

1 Like
2

You may discover the smallest (or any) prime factor of the number. It can obviously be found in sqrt(N) time . Let the factor be p and the given number be N.

Check if p | (N/p).

The algorithm runs in O(sqrt(N)).

If you find any error in this ans tell me.

And obviously the algorithm is not efficient for numbers of the order 10^10 & up.

3

It is based on the observation that the difference between ab and (a+1)b where a > b may not be constant, but if you take the difference of successive differences, b times, there is a constant b! factor. For example, 94 = 6561, and 104 is 10000. the difference is 3439. The difference between 84 and 94 is 2465, meaning the difference of differences is 974. A step further and you have 204. One step further, and you have 24, which is equal to 4!.

4

Anyone of you read the editorial? -.-

5

Let N be the given number. Find the prime factors of N and their respective powers. i.e. find out P’s and A’s in N = (P1 ^ A1) * (P2 ^ A2) * … * (PK ^ AK). Now if gcd of all A’s is 2 or more, its a power number.

6

Please find the following Python code:
Here I am trying to check log value of the input number with the base as numbers upto num-1 and checking if any value is an integer.

import math

def pow_num():

flg=0

num=int(raw_input("Enter a number to know if it is a power number or not:"))

for i in range(2,num):

	if math.log(num,i)-math.ceil(math.log(num,i))==0:

		flg=1

		print "%d is a power number!!!"%num

		break

if flg==0:

	print "%d is not a power number :("%num