Triumvirate and Treamviruti?

Weekly challenge 254 — 29 January 2024

Week 254 - 29 Jan 2024

Task 1

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 1Input: $n = 27 Output: true 27 = 3 ^ 3Example 2Input: $n = 0 Output: true 0 = 0 ^ 3Example 3Input: $n = 6 Output: false

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.

#!/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; } } }

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

Peter Campbell Smith is hereby placed in the public domain