Find perfect powers

[sabbyiqbal]

I hope it is OK to post problems that I am having on other sites. The only reason I switched from FCC was to beef up on JS practice before I continued on with FCC curriculum.

I have been trying to solve this for nearly 2 days and I think I am spinning my wheels at this point.

Problem: Trying to solve this codewars problem. In case the link is blocked for any reason, this is description of the problem:

A perfect power is a classification of positive integers:

In mathematics, a perfect power is a positive integer that can be expressed as an integer power of another positive integer. More formally, n is a perfect power if there exist natural numbers m > 1, and k > 1 such that mk = n.

Your task is to check wheter a given integer is a perfect power. If it is a perfect power, return a pair m and k with mk = n as a proof. Otherwise return Nothing , Nil , null , NULL , None or your language’s equivalent.

Note: For a perfect power, there might be several pairs. For example 81 = 3^4 = 9^2 , so (3,4) and (9,2) are valid solutions. However, the tests take care of this, so if a number is a perfect power, return any pair that proves it.

And this is my code:

// alert ("is this mike on?");

function perfectpower(n){
//Get square root of n;
  var sqrtn = Math.sqrt(n);
  // console.log(sqrtn);
//Get list of x: x >> sqr rt of n;
  var x = Array.apply(null, Array(sqrtn+1)).map(function (_, i) {return i;});
  var y = [...Array(10).keys()];

  // console.log("This is x: " + x);
  // console.log("This is the length of x: " + x.length);
  //
  // console.log("This is y: " + y);
  // console.log("This is the length of y: " + y.length);

// Calc each x^2,3,4 etc
var perfects = [];
var message = null;

for(var i = 2; i<x.length; i++){
    for(var j = 2; j<y.length; j++){
        var xtothey = (Math.pow(x[i],y[j]));
        // console.log("i is: " + i);
        // console.log("j is: " + j);
        // console.log("xtothey is: " + xtothey);


        if(xtothey === n){
          perfects.push(x[i],y[j]);
          message = "";
        }else if (xtothey !== n){
          //do nothing
        }
    }
}

return perfects;

}

The testcase that is failing right now is:

perfectpower(5)

This is the error I am getting:

RangeError: Invalid array length

It should return null or nothing but I also need to keep looping through to find perfect power pairs that might come later in the loop.

Part of the problem could be that I had never heard of perfect powers before today and so have the most minimal grasp of exactly how to solve for them. This was a little helpful: link in so far as it helped me develop the basic steps that I needed to code for.

Thank you.

[kevinSmith]

You are getting the “RangeError: Invalid array length” message because of this: Array(sqrtn+1). That function expects integer (I assume).

But I’m not sure why you need an array. You don’t need to store anything.

First of all, if it helps, a perfect power is just a power where the two numbers are integers. There is nothing magical about it - it is what we think of when you think a number is a power of something. They just make the distinction because technically every number is a power of something, if you allow decimals and irrational and imaginary numbers. They just mean numbers that are “normal” powers.

But the algorithm.

First, I like that you are limiting the range to the square root.

Then you have two loops - good. You can loop those to your square root.

Inside those loops, if your power is equal to n, then return those two numbers in an array - you’re done!

Then, if you make it to the end of the loops, have a return null as the last thing you do - it will only get there if no pair was found.

I also might put an if at the end to the inner loop to break out of it if the power is greater than n - no need to keep checking.

That should do it.

The only other thing I’d add is that in ES6, you don’t need to do Math.pow(i, j) - you can just do i**j.

[kevinSmith]

Oh yeah, and definitely nothing wrong with talking about non-FCC material.

[sabbyiqbal]

Thanks @kevinSmith for all the feedback. There are so many moving parts to this problem. Trying to keep it all straight in my head (the math part and the code part) is tough so bear with me while I go through your response.

First off - after making a bunch of updates, I went from failing 32 (out of 33) testcases to only failing 1 so yay! And thanks!

However, I still have some questions (and obviously one more error):

That function expects integer (I assume).

Thanks. I rounded this number instead.

But I’m not sure why you need an array. You don’t need to store anything

But how would I run 2 loops without both x and y being stored as arrays?

First, I like that you are limiting the range to the square root.

I actually don’t have any idea why I am doing this; just following the instructions as per the link. If I want all x,y pairs that give me n (such that x^y = n) then why stop limit range of x such that x^2 = n…?

Inside those loops, if your power is equal to n , then return those two numbers in an array - you’re done!

Then, if you make it to the end of the loops, have a return null as the last thing you do - it will only get there if no pair was found.

So I changed the code around to do exactly that (I think). But please let me know if you think there was a more elegant way to do it.

Finally - the testcase that I am failing is set up as:

  Test.it("should work for random perfect powers", function(){
    var k, m, i, r, l;
    for(i = 0; i < 100; ++i){
      m = 2 + (Math.random() * 0xff)|0,
      k = 2 + (Math.random() * Math.log(0x0fffffff) / Math.log(m))|0;
      l = Math.pow(m,k);
      r = isPP(l);
      if(r === null) {
        Test.expect(r !== null, l + " is a perfect power");
        break;
      } else if(Math.pow(r[0],r[1]) !== l){
        Test.assertEquals(
          Math.pow(r[0],r[1]), l, "your pair (" + r[0] + ", "+ r[1]+ ") doesn't work for "+ l);
        break;
      }
    }      
  });

And the error I am getting is:

Maximum call stack size exceeded

But after looking it up, it looks like this might be a problem b/c of the way the testcase is set up, i.e. calling a function which calls a function. Is there anything I can do to get around this…?

Here is my new code:

var isPP = // alert ("is this mike on?");

function perfectpower(n){
//Get square root of n;
  var sqrtn = Math.sqrt(n);
  // console.log(sqrtn);
//Get list of x: x >> sqr rt of n;
  var x = Array.apply(null, Array(Math.round(sqrtn+1))).map(function (_, i) {return i;});
  var y = [...Array(10).keys()];

  // console.log("This is x: " + x);
  // console.log("This is the length of x: " + x.length);
  //
  // console.log("This is y: " + y);
  // console.log("This is the length of y: " + y.length);

// Calc each x^2,3,4 etc
var perfects = [];
// console.log("This is the length of perfects array: " + perfects.length);

for(var i = 2; i<x.length; i++){
    for(var j = 2; j<y.length; j++){
        var xtothey = (Math.pow(x[i],y[j]));
        // console.log("i is: " + i);
        // console.log("j is: " + j);
        // console.log("xtothey is: " + xtothey);


        if(xtothey === n){
          perfects.push(x[i],y[j]);
          return perfects;
        }
    }
}

if(perfects.length == 0){
  return null;
  }
}

[kevinSmith]

@sabbyiqbal

But how would I run 2 loops without both x and y being stored as arrays?

Running loops and storing values in arrays are two completely different things. Sometimes you want to. But there is no need here.

Look at it this way - you are checking if a pair works. If you find a pair that works, you return that and you’re done. You don’t need a list of failed pairs. If it was asking you to keep track of all the pairs that failed or passed, then that would be different. But they’re not asking that. All they want is the first (any) pair that works or return null. Trust me, you don’t need those arrays.

If I want all x,y pairs that give me n (such that x^y = n) then why stop limit range of x such that x^2 = n…?

Because not of the other numbers are possible. Imagine that n is 81. Then 9 is the biggest number that can be raised in a power to that number. If 2 is the lowest exponent, then the square root of n is the largest possible base. If the problem was defined such that 3 was the lowest possible exponent, then the cube root of n.

It’s a math thing. But learning to think mathematically is useful for these kinds of things. If it doesn’t make sense, don’t worry about it. Just keep working on it and it will gradually make more sense. You could ignore this and run the loops up to n (instead of the square root of n) and it would work but you’d be testing numbers that couldn’t possibly pass. You’d still get to the right answer, you’d just take longer. But part of learning to do algorithms is learning to optimize them. But again, you get better at this as you go along.

Your second code works, if you eliminate the line var isPP = // alert ("is this mike on?"); I don’t know what it is trying to do. Plus it screw up the code.

It works, but it is messy as hell. It’s like if someone asked you to screw in a light bulb and instead of getting a ladder and doing it, you’ve trained a monkey in a clown suit to balance on beach ball while Gavin McLeod films it in betamax. True, you solved the problem, but it’s not the ideal way.

Don’t let me get you down. Trust me, you’re doing great, I’m just trying to help you get better.

Repeat after me - I don’t need those arrays for this problem!

Go through your code.

1. Get rid of the line:

var isPP = // alert ("is this mike on?");

It does nothing.

2. Get rid of these lines - they do nothing:

  var x = Array.apply(null, Array(Math.round(sqrtn + 1))).map(function(_, i) {
    return i;
  });
  var y = [...Array(10).keys()];

  var perfects = [];

3. Now, here replace both the ....length parts with sqrtn - they are same thing.

  for (var i = 2; i < x.length; i++) {
    for (var j = 2; j < y.length; j++) {

4. Here,

      var xtothey = Math.pow(x[i], y[j]);

just do i and j. And, as I said, i**j is the more modern way (ES6) to do it.

5. Get rid of this line.:

        perfects.push(x[i], y[j]);

If we find a successful pair, you’re going to return that pair immediately. There is no need to store it or continue whatsoever.

6. Here

        return perfects;

just return the pair, [i, j].

7. Here:

  if (perfects.length == 0) {
    return null;
  }

Just return null, there is no need to check anything. If your code ever gets here, it’s because no pairs exist.

That is pretty much it to a much more sensible code. There are further optimizations. For example, I think the j loop only needs to go to the i root of n (for similar reasons we found the square root before.) But this is much more logical code than you had before.

Don’t get frustrated. This stuff is tough. Every algorithm you learn makes the next one easier.

Let us know if any of this doesn’t make sense.

[sabbyiqbal]

The problem with this website (codewars) is that it sets up the beginning of the code so that they can more easily control the testing. So the testcases looks for the value of a variable isPP in order to Pass or Fail. If I get rid of isPP, then the testcases will fail because: ReferenceError: isPP is not defined. I can modify the unit tests to not look for it, but not the final tests required to submit my solution. But this might just be something I take up with admin for codewars…?

In the meantime…I am testing my code via Atom + console on local web page instead:

Still mulling over the math parts. I think I am getting closer to understanding it but gonna put it aside to get through the rest of my problems for now.

This is what my code looks like now:

function perfectpower(n){
//Get square root of n;
  var sqrtn = Math.sqrt(n);
  console.log("This is sqrt of n: " + sqrtn);
  // Calc each x^2,3,4 etc

for(var i = 2; i<sqrtn; i++){
    for(var j = 2; j<sqrtn; j++){
        console.log("This is i: " + i);
        console.log("This is j: " + j);
        var xtothey = i**j;
        console.log("This is i**j: " + xtothey);

        if(xtothey === n){
          return [i,j];
        }
    }
}
return null;
}

I tested with perfectpower(9) and am getting a Null value. Expected: [2,3].

After putting in my handy console-logs, I see why.

1. It goes through the first loop with i = 2 and j = 2
2. i**j = 4
3. Fails IF statement so goes to second loop.
4. But now (inner loop first) j is 3 which is not less than sqrtn (3) so code kicks out of this loop.
5. Same thing happens with outer loop. So kicks out of loops completely.
6. Then the only thing left is to return null. Which it does.

As a final test, I ran perfectpower(81) and that worked, i.e returned [3,4]. But only because the i and j loops could keep running and get to a perfect power pair before they hit the limit of sqrtn (9, in this case).

So the question for me is, how to get the loops to keep running for perfectpower(9) long enough to get a perfect power pair. Since I don’t quite understand why I am limiting my i and j to be less than sqrtn, I feel ill-equipped to debug and get to that answer.

So I guess I’m asking for more help.

Thank you.

[kevinSmith]

@sabbyiqbal

The problem with this website (codewars) is that it sets up the beginning of the code so that they can more easily control the testing.

Well, then leave it in, but it just isn’t part of the algorithm so it isn’t something we need to consider.

I tested with perfectpower(9) and am getting a Null value. Expected: [2,3] .
No, you expect [3, 2] or 3**2. 2**3 would be 8.

But you basically have it, you’re only making one little mistake. In your loops, you want to test up to and including the square root of n. If the square root is and integer (like for 9) your loops will stop just short of it.

How do you keep it going? Instead of

for(var i = 2; i<sqrtn; i++){

what about

for(var i = 2; i<=sqrtn; i++){

It’s a subtle difference, but it makes all the difference if n is a square with only one solution (like 9). In the case of 81, there is an earlier solution so you don’t realize that your code couldn’t reach the final one.

So you’ve basically have the solution I came up with.

The only other enhancement that I can think that might make it slightly better is to have the j loop only go up to the i root of n. It’s mathematically impossible to have a j that is bigger than the i root of j. If n is 81, and i is 9, then any j bigger than 9 will fail (for this i). Is this an important improvement? Probably not. It might have an affect on very big numbers and it is the kind of thing that might impress and interviewer. As a computer formula, that would be (n ** (1 / i)).

But that code you have now works and is logical.

Since I don’t quite understand why I am limiting my i and j to be less than sqrtn, I feel ill-equipped to debug and get to that answer.

I’ll try again. Since the lowest possible power you can have is 2, the biggest possible base is the square root of n. Since we know that 92 is 81, would 102 work? No, that will be bigger than 81. If n is 121, then 11*2 will work, but 12**2 won’t work. The biggest possible i will always be the square root. Because the square or the square root of n is n. Anything bigger than the square root of n will be be bigger than n when we square it, by definition. If you don’t believe me, try out some numbers. I use similar logic on the “the i root of n” idea above.

What happens if you let the loops go up to n? You’ll still get the same answers, but your loops will test a bunch of combinations that can’t possibly work. Your code would still work but might loose some points in an interview.

Don’t worry if this doesn’t come naturally. There is more to being a web dev than math. It is just one piece of the puzzle. Maybe you’re better at something else. For example, I’m pretty good at the math, but suck at aesthetic design. But the math can be important so spend some time on it. If you struggle with basic math, maybe pick up a basic algebra and geometry text book and get some basic concepts. Or just do lots of problems and ask a lot of questions. The more you do, the easier they get.

[sabbyiqbal]

OK, believe it or not some part of my brain that vaguely understood the loops changed the logical operator. But instead of <= I changed it to =. Anyways, I made the correct update now and passed all the unit tests.

However, now the final tests was failing b/c of this error: Execution Timed Out (12000 ms). It came with a recommendation to: optimize your code further.

So, I tried your suggestion to take the j loop only up to the i root of n. I had to draw a table of i**j in order to fully understand. (See excel snippet below). Based on this, and using n = 81, this is my understanding:

1 - For each value of i, I calc’ed i**j.
2 - For i = 2, I see that after j = 6, it makes no sense to continue looping upto 9 (which is sqrtn) b/c we’re already past 81.
3 - For i = 3, the j limit is 4 and so on for each i up to i = 9.
4 - I greyed out the numbers greater than 81 to show clearly how j can be limited.
5 - And I see that each of those j limits corresponds to the value of (n ** (1/i)) - which is the ith root of n. I am not sure I would have made that connection but I do see the connection.
6 - So, I’m sold on limiting j to (n ** (1/i)).

This is my new code:

function perfectpower(n){
//Get square root of n;
  var sqrtn = Math.round(Math.sqrt(n));
  console.log("This is sqrt of n: " + sqrtn);

  // Calc each x^2,3,4 etc

for(var i = 2; i<=sqrtn; i++){
    var jlimit = Math.round(n ** (1 / i));
    for(var j = 2; j<=jlimit; j++){
        console.log("This is i: " + i);
        console.log("This is j: " + j);
        console.log("This is jlimit: " + jlimit);
           var xtothey = i**j;
        console.log("This is i**j: " + xtothey);

        if(xtothey === n){
          return [i,j];
        }
    }
}
return null;
}

Now I am back to failing a bunch of unit test-cases. A couple of them I was able to fix by rounding up jlimit.

But the next one I am failing is perfectpower(169). After adding in a bunch of console.log statements, I see that my i is not getting to 13…?? Which is the problem I used to have before I changed the logical operators in loops to <=.

So I’m stuck at this point now. sqrtn is 13 and i is supposed to go up till i = 13. I don’t see why it’s not.

Thank you again.

[kevinSmith]

First of all, I hate sites like codewars because it’s a bunch of guys making these up, trying to trip you up, trying to show off that they know some arcane math principle. And more than once I’ve found a problem that faultily applied a math principle (trying to be clever) and refused to correct it because they didn’t want to admit they didn’t know what they were talking about.

That being said, they can be good training for code challenges for interviews. Some interview questions are written by the same kind of idiots. And the ones that aren’t, they will be easy after wading through a few hundred of these.

Also, I went to the site and saw that that isPP is actually what the function is called and your code should be inside that. This is a little odd to me because to me, a function that starts with is traditionally returns a boolean. But OK.

So, we need to optimize. I still think the math of my optimization is correct, but it fails for some reason. Maybe there is an issue with the math. Floating point numbers are inherently sloppy on computers and JavaScript is not made for high precision math so there may be an error when we do something like using an exponent of a fraction. Keep in mind that sometimes these katas are written in other languages where the rules may be a little different.

OK, let’s do it the same way. We want to make sure the j loop doesn’t check unnecessary numbers.

This is our almost working code, that basically works but times out for large numbers:

const isPP = function(n){
  const max = Math.ceil(Math.sqrt(n));
  for (let i = 2; i <= max; i++) {
  	for (let j = 2; j <= max; j++) {
  		if (n === i ** j) {
  			return [i, j];
  		} 
  	}
  }
  return null;
}

We tried to limit the j loop by changing it to:

    const jLim = Math.ceil((n ** (1 / i)))
  	for (let j = 2; j <= jLim; j++) {

I still think that math is basically sound but for whatever reason, it’s not working. We can test that an easier way, by seeing in the j loop if our current power is greater than n. If it is, all the others will be even greater so must fail. At that point we can break, and that will exit us out of the j loop and continue with the next i loop. So, at the end of the j loop, we put:

When I do that, it passes. We basically did the same thing (I think) but for whatever reason, the limits of JavaScript math was failing. Anytime you’re dealing with floating numbers in JS, things can get a little hinky. Don’t believe me? Try console.log(.1 + .2); some time and try not to fall off your chair. There are ways to deal with it - you can google it. For now, just accept that JS is not ideal for high precision math.

So, we end up with this passing code:

const isPP = function(n){
  const max = Math.ceil(Math.sqrt(n));
  for (let i = 2; i <= max; i++) {
    for (let j = 2; j <= max; j++) {
      if (n === i ** j) {
        return [i, j];
      } 
      if (n < i ** j) {
        break;
      }
    }
  }
  return null;
}

Just for kicks, another way to handle it would be to check in the j loop, like:

  	for (let j = 2; (i ** j) <= n; j++) {
  		if (n === i ** j) {
  			return [i, j];
  		} 
  	}

We are doing the same thing, just doing it in the definition of the for loop. Is it better? It’s more compact but less readable. It might be the tiniest of a fraction faster, but not by much.

Like I said, some of these things are hard and sometimes they’re trying to trick you. I consider myself pretty good at these and there are some that just bust my balls. After you finish it, it’s interesting to see other people’s solutions and read the discussions.

[alhazen1]

I’ve been watching this unfold for the past few days. I’m fascinated with the algorithm problems. It was very good of @kevinSmith to offer up so much of his time.

I came up with a possible solution. Here’s my logic

check 2nd root, is it an integer? if yes, return [root, index] if no continue to next index
check 3rd root ....
keep going until root is integer or root < 2 (no possible answers below 2)
if no solution , return null

I’m not real sure about the math terminology - root and index may not be the correct terms or I may just have the two terms mixed up - been a long time since I’ve been in school. The guard against floating point errors is a little hacky but as n gets larger 1/index would require me add yet more zeros to the number I use for the Math.round trick to compensate for floating point errors - this seemed the only fail-safe way around that.

Also the for loop should probably be rewritten as a while loop since end condition has nothing to do with the counting variable.

var isPP = function(n){
  let root = 2;
  for(let index = 2; root >= 2; index++){

    root = Math.round((n ** (1/index))*1000)/1000;
    // && is a check for any floating point errors
    if(root%1 === 0 && root ** index === n) return [root,index];
  }
  return null;
}

Did a little testing - nothing exhaustinve. Seems to solve with very few iterations.

[kevinSmith]

Yes, I was thinking about this the other night, kind of doing it “backwards”, checking roots instead of powers. I would think that it would run into the same problem with n ** (1/index), running it the limits of precision. I see that you round it, which may help, but could also fail in some edge cases. But I just plugged it into the site and it passed. Good job.

In terms of big O analysis, this is a slightly better solution, although the original doesn’t run full loops either.

Still, it seems to work, good job.

[sabbyiqbal]

Thank you @kevinSmith for all your time helping me with this. And good to know your take on codewars. I do like the practice but nothing beats the level of support I get from FCC. Thanks again!

And in case you are curious, this was the highest-ranking solution:

function isPP(n) {
  for (var m = 2; m * m <= n; ++ m)
    for (var k = 2; Math.pow(m, k) <= n; ++ k)
      if (Math.pow(m, k) == n) return [m, k];
  return null;
}

[kevinSmith]

That’s basically what we did.

Another thing to think about with sites like codewars is that solutions get high scores if they’re “sexy”. The more code you can pile into one line the better. [rolls eyes] Unfortunately that often leads to unreadable code. This isn’t terrible but I like ours better. Instead of calculating the square root, he just tests for m * m <= n, basically the same thing - seeing is the square of m is less than or equal to n is the same as seeing if m is less than or equal to the square root of n.

The inner loop just does the limiting check in the for loop, something we discussed. And then they do the if statement in one line.

One thing I don’t like is he used == instead of ===. Since there is no doubt about the type, === is better - a little faster. Another thing I don’t like is putting that much logic inside the for loops. Those lines are already cluttered enough without burying formulas inside them. But that’s a stylistic preference.

This isn’t any better than ours (same exact algorithm) but stylistically, it’s “sexier” according to the kind of people that dominate sites like this. Again, this one isn’t too bad, but I’ve seen a lot of highest rated solutions on this site that were just ridiculously unreadable - they crammed everything onto one line.

Readability is very important. Eventually some is going to have to come and read your code. And trust me, after a few months of not looking at it, you can be just as bewildered looking at your own code.