Peter
Peter Campbell Smith

Triumvirate and Treamviruti?

Weekly challenge 254 — 29 January 2024

Week 254: 29 Jan 2024

Task 1

Task — 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.

Examples


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

Analysis

We have a little problem here. The statement of the task seems clear: we are to determine whether $n is a power of 3. The powers of 3 are
3 ^ 0 = 1, 3 ^ 1 = 3, 3 ^ 2 = 9 and so on, up to 3 ^ 32 = 1853020188851841 which is getting close to the largest integer Perl can handle on my machine.

But wait! The examples suggest that we are not looking for 3 ^ $a = $n - whether $n is a power of 3 - but instead for $a ^ 3 = $n - whether $n is a perfect cube.

Frustratingly, example 1 works either way because 27 is both a power of 3 and a perfect cube. But example 2 is only correct if what we are asking is whether 0 is a perfect cube, which it is, but it isn't a (finite) power of 3 as stated in the task. (Moreover, one could argue that 0 isn't a positive integer!)

So does example 3 help? 6 is neither a power of 3 nor a perfect cube, so 'false' is the answer either way - so no, that doesn't help.

What I have done, therefore is to provide two answers: whether $n is a power of 3 and whether $n is a perfect cube.

To determine whether $n is a power of 3 I calculate successively all the powers of 3 from 0 to 32 (because 3 ^ 32 is the largest power of 3 that my Perl can handle as an integer). If the power equals $n, then the criterion is true, if the power exceeds $n then the criterion is false, and if the power is less then $n then I try the next power, and so on.

I considered a different approach, which is to divide $n by 3 repeatedly until arriving at a quotient <= 1. If it is 1 then $n is power of 3, if it is < 1 then $n isn't a power of 3. But division is dangerous because of the rounding of floating point numbers, and I think my original solution is safer.

So how about the other interpretation? Again I think the simplest way is simply to generate all the cubes (0, 1, 8, 27, 64 ...) and similarly compare them to $n. If there is a match then the criterion is true, if the cube exceeds $n then the criterion is false and if the cube is less then $n I try the next cube.

Both of these algorithms execute in negligible time up to $n = 1853020188851841 = 3 ** 32 and $n = 2197000000000000 = 130000 ** 3, beyond which we reach numbers which Perl cannot represent as integers.

Try it 

Try running the script with any input:



example: 12345

Script


#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-01-29
use utf8;     # Week 254 task 1 - Three power
use strict;   # Peter Campbell Smith
use warnings; 
binmode STDOUT, ':utf8';

three_power(27);
three_power(0);
three_power(6);
three_power(1);
three_power(1853020188851840);
three_power(1853020188851841);
three_power(2197000000000000);
three_power(205891132094649);


sub three_power {
    
    # initialise
    my ($n, $j, $try, $limit);
    $n = shift;
    say qq[\nInput:  $n];
    if ($n > 2197000000000000) {
        say qq[-- too big (max is 2197000000000000)];
        return;
    }
    
    # powers of 3
    $try = 1;
    for $j (0 .. 33) {
        if ($try == $n) {
            say qq[Output: true,  $n is 3 ** $j];
            last;
        } elsif ($try > $n) {
            say qq[Output: false, $n is not a power of 3];
            last;
        }
        $try *= 3;
    }
    
    # cubes
    for $j (0 .. 130000) {
        $try = $j ** 3;
        if ($try == $n) {
            say qq[        true,  $n is $j ** 3];
            last;
        } elsif ($try > $n) {
            say qq[        false, $n is not a perfect cube];
            last;
        }
    }
}

Output


Input:  27
Output: true,  27 is 3 ** 3
        true,  27 is 3 ** 3

Input:  0
Output: false, 0 is not a power of 3
        true,  0 is 0 ** 3

Input:  6
Output: false, 6 is not a power of 3
        false, 6 is not a perfect cube

Input:  1
Output: true,  1 is 3 ** 0
        true,  1 is 1 ** 3

Input:  1853020188851840
Output: false, 1853020188851840 is not a power of 3
        false, 1853020188851840 is not a perfect cube

Input:  1853020188851841
Output: true,  1853020188851841 is 3 ** 32
        false, 1853020188851841 is not a perfect cube

Input:  2197000000000000
Output: false, 2197000000000000 is not a power of 3
        true,  2197000000000000 is 130000 ** 3

Input:  205891132094649
Output: true,  205891132094649 is 3 ** 30
        true,  205891132094649 is 59049 ** 3

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain