Raul Miller wrote: > On Mon, Jun 8, 2009 at 2:40 AM, <[email protected]> wrote: > >> A positive integer n is said to be a perfect power >> if there exist two positive integers a and >> b ≥ 2 such that n = ab . >> > ... > >> I did a search at jsoftware.com on "perfect power" and did >> not find anything. >> >> any suggestions would be appreciated. >> > > I could not understand your post, so I used the definition at > http://mathworld.wolfram.com/PerfectPower.html > > Here's an implementation: > > pp=: *./@(=/@#...@~.@#, 2&<:, 0&<@#)@(#/....@q: ::0:"0) > (#~ pp) i. 100 > 4 8 9 16 25 27 32 36 49 64 72 81 > > Breaking it down... > > Fundamentally, perfect power is a set of constraints on the > number of factors which a number has. #/....@q: will give us > the number of each of the prime factors which a number has. > > However, some numbers can not be factored, because they are out > of the domain of q:, thus the ::0:"0 (I need an explicit rank zero > because the rank of verbs formed with :: is not zero). If you > limit your use of pp to positive integers (for example, if you > never try numbers like 0), you can eliminate ::0:"0 from the > definition of pp. > > Once you have the count of prime factors for a number, the > wolfram page specifies three constraints. > > First, n is of the form m^k, m > 1 and k >: 2 > > These test correspond roughly to the comma separated tests > in PP (except I have expressed my tests in terms of the number > of prime factors the number has). If all three tests are true (*./) > then the number is a prime power. > > Does this help? > > Thanks to Raul, I looked at the Wolfram definition and noted that n = */p^e is a perfect power iff 1 < GCD (e0 e1... ) , and so came up with the somewhat slimmer expression
NB. I'm adding extra line-throws ... pp1 =: (1 < +./@(0 -.~ _&q:)) :: 0:"0 ... and then I timed it and to my horror: 1 ts'pp1 q'[q =: i.100000 3.17794 1.5193e7 1 ts'pp q' 0.764443 1.0496e6 ... so it's far worse in time & in space. ... and then I checked the equivalence of these functions: (pp1 -: pp) i.100 0 ... so where was I going wrong? I."1 (pp,:pp1) i.100 4 8 9 16 25 27 32 36 49 64 72 81 4 8 9 16 25 27 32 36 49 64 81 0 But 72 isn't a perfect power. So it looks as if Raul's function needs a bit of extra filtering to be both fast and correct. My function is ok if you're not worried about performance on reasonable sized arrays. Mike ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
