# Detecting if n is of the form a^b

5 replies to this topic

### #1Reedbeta

DevMaster Staff

• 5310 posts
• LocationSanta Clara, CA

Posted 03 November 2004 - 11:03 PM

I'm trying (just for fun) to implement the Agrawal-Kayal-Saxena primality testing algorithm. The majority of the algorithm seems fairly straightforward, but the first line is tripping me up.

It asks to determine, for a given natural number n, if n = a^b for some natural numbers a and b > 1. I've thought of taking the logarithm of n; this gives log n = b log a, but doesn't seem to help the determination if a and b are natural numbers (obviously, if one allows a and b to be real numbers, there are infinitely many solutions to n = a^.

This isn't an essential part of the algorithm as it's basically an early-out, but I'm curious anyways.

How do you tell whether n is of the form a^b?
reedbeta.com - developer blog, OpenGL demos, and other projects

### #2cristic

New Member

• Members
• 7 posts

Posted 04 November 2004 - 07:13 AM

hmmm, you could use the brute force method until you come up with a better idea...

And, honestly I don't know of a better idea, because you want to find the values of two constants, but you only have one equation. :sad:

Edited for length.

### #3Reedbeta

DevMaster Staff

• 5310 posts
• LocationSanta Clara, CA

Posted 04 November 2004 - 07:36 AM

Yes, if we were dealing with real numbers, the system would be underdetermined. But since n, a, and b are all constrained to be natural numbers, it should be easier. There will still be multiple solutions in some cases, but all that is required is to discover that one exists (I don't care what the a and b are, only that they exist) or to prove that none exist.

Brute force would work, though I was hoping for something better =D
reedbeta.com - developer blog, OpenGL demos, and other projects

### #4FarooqMela

New Member

• Members
• 3 posts

Posted 04 November 2004 - 07:45 AM

There is a paper by DJ Bernstein which addresses this very problem. Off the top of my head I think it's titled "Detecting perfect powers in essentially linear time." Google it

### #5cristic

New Member

• Members
• 7 posts

Posted 04 November 2004 - 07:50 AM

If you could think of one more dependency between a,b it could work. But to my knowledge, if you have only one equation and two unknown constants it can not be done, without expressing one constant as a function of the other. Whether we are dealing with real or natural number the nature of the problem is the same, only thing that changes is that with natural numbers the problem has a finite number of possible solutions and thus the correct one can be computed with brute force.

Although looking closer at the problem, I think it is safe to say that if n=a^b then this means that n can be divided by a exactly b times, so it would make sense to furhter investigate only those values of a that divide n. This doesn't give an exact solution but further narrows the interval for valid values of a and b. For instance if n is 9, there is no need to check for values of a like 2, 4, 5,...

What do you mean by multiple solutions in this context ?

DevMaster Staff

• Members
• 1057 posts

Posted 04 November 2004 - 01:20 PM

FarooqMela said:

There is a paper by DJ Bernstein which addresses this very problem. Off the top of my head I think it's titled "Detecting perfect powers in essentially linear time." Google it

Scroll to the Other arithmetic operations section

Some really nice and seemingly interesting papers here

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users