PWC 254 Task 1, Three Power

The tune you should be humming while working on this task is Blues Power

Task 1: Three Power

You are given a positive integer, $n.
Write a script to return true if the given integer
is a power of three otherwise return false.

• Example 1: Input: $n = 27, Output: true ( 27 = 3 ^ 3 )
• Example 2: Input: $n = 0, Output: true ( 0 = 0 ^ 3)
• Example 3: Input: $n = 6, Output: false

Thoughts

Quite a few early solutions seem to have interpreted this to mean "check if $n is a cube", and solve it by checking if the cube root of $n is 3. But that is not what "power of three" means. The powers of three are 3⁰, 3¹, 3², 3³, etc.

Example 2 seems to have led them astray. I'm going to assume that Example 2 is a mistake, both because it doesn't match the definition of powers of three and because the input is specified as a positive integer and therefore should exclude zero.

Digression on cube roots

On Facebook, this led to a discussion of finding the cube root of -8, which should be -2? The typical way of finding a cube root is to raise a number to the 1/3 power -- (-8)**(1/3). However, the ** operator (and the underlying C pow() function on which it's based) explicitly don't work for a negative base with a fractional exponent. Why? Because in general, the roots of negative numbers are complex numbers, which can't be represented with a single floating point return value.

Well. Perl has Math::Complex, which overloads the ** operator to work with complex numbers. So if we cleverly plop in use Math::Complex;, set up -8 as a complex number and let 'er rip, we will get -2, right?

$ perl -MMath::Complex -wE 'say cplx(-8,0) ** (1/3)'
1+1.73205080756888i

Urk. What happened? There are three cube roots in the complex plane, and the one that we got is 1+sqrt(3)i. To get all the roots, we have the root function, but it has some worrisome floating point rounding error.

$ perl -MMath::Complex -wE 'my @r = root(cplx(-8,0), 3); say "@r"'
1+1.73205080756888i -2+2.44929359829471e-16i 0.999999999999999-1.73205080756888

I'm going to take all this (complex arithmetic, numerical accuracy) as further evidence that this "easy" problem really isn't about cube roots.

On with it, then

So, the answer is to divide $n by three, and keep doing it until there's either a remainder or we reach 1. That's a one-liner if we're willing to be terse. Here it is checking for $n=9:

$ perl -wE 'my $n=shift; $n /= 3 while ( $n > 0 && $n % 3 == 0 ); say $n == 1' -- 9

Just to make something interesting of it, let's over-engineer it by using the recently-introduced class capability, and let's generalize to numbers other than 3. We want to end up with something that can be used like:

my $n = shift; # From command line arguments
if ( Power->new(base => 3)->isPowerOf($n) ) {
    say "true";
} else {
    say "false";
}

We'll create a class constructor that takes the base as an argument, and has a method to check a number for being a power of that base.

use v5.38;
use feature 'class'; no warnings "experimental::class";

class Power {
    field $base :param = 10;
    method isPowerOf($n) { ... }
}

The field keyword declares member variables, and tagging it with the :param trait means that it should be initialized via the constructor. We'll give it a default value of 10 if the constructor doesn't explicitly set it. The convention for a class constructor is to provide the fields as named parameters, using the variable name. So, to create a Power object that uses 3 as the base instead of 10:

my $p3 = Power->new(base => 3);
if ( $p3->isPowerOf(27) ) { ... }

The implementation of the isPowerOf method will be able to use $base as an in-scope variable, and it will refer to the member variable of the object. In traditional OO Perl, we would be using the more awkward $self->{base}.

    method isPowerOf($n) {
        if ( $n > 0  )    {
            $n /= $base  while ( $n % $base == 0 );
            return $n == 1;
        }
        elsif ( $n == 0 ) { return true }
        else              { return false; }
    }

Since we're across the over-engineering boundary, I added a bit of error checking, and I made Example 2 pass, just in case we are in an alternate universe where 0 is a power of 3.

And to complete the example, the testing code for using this class looks like:

sub runTest
{
    use Test2::V0;
    use builtin qw/true false/; no warnings "experimental::builtin";

    my $p3 = Power->new(base => 3);
    is( $p3->isPowerOf(27), true,  "Example 1 with class");
    is( $p3->isPowerOf( 0), true,  "Example 2 with class");
    is( $p3->isPowerOf( 6), false, "Example 3 with class");

    done_testing;
}