## Powers Of 3

### March 1, 2016

The powers of 3 are 3^{0} = 1, 3^{1} = 3, 3^{2} = 9, 3^{3} = 27, and so on.

Your task is to write a program that determines if a number is a power of 3; you must give more than one solution. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

In R7RS, your “divrem” operator is available in the base module as “floor/”, which is a much more descriptive name, and “modulo” is also provided as “floor-remainder”. These systematic names for integer division were devised by Taylor Campbell, and were adopted by the R7RS-small working group for floor and truncate; the R7RS-large working group will consider adding similar names for ceiling, quotient, Euclidean, and balanced (R6RS div0/mod0) division operators

First way: return not(n % 3).

Second solution: Any integer n is divisible by 3, if the sum of its digits is divisible by 3. Therefor we get the following recursive algorithm.

Recursion amount is actually pretty low, for 12157665459056928801 we get 2 recursions (first sums up to 90, then 9, then returns True).

The modulo 3 function would be the obvious approach but this feels like cheating. A couple of alternatives (in Julia) are:

function is_power_of_3(x::Int64, th::Float64 = 0.001)

if x <= 0

return false

end

z = log(3,x)

return abs(z – round(z)) < th

end

function is_power_of_3_alternative(x::Int64)

if x <= 0

return false

elseif x == 0

return true

else

z = 1

while z < x

z *= 3

if z == x

return true

end

end

return false

end

end

Here are my two solutions, first one in Haskell, build a lazy list of powers of 3 (I expect the compiler can optimize this to a shift and add itself, but just in case not, we do it explicitly), then just do a linear lookup (with the ‘member’ function that expects a sorted list):

Second is Python: use the bit length of the input number to guess the closest power of 3 – this seems to work exactly, at least up to 3**100000 or so but I expect rounding errors will eventually cause problems. The test is just that all powers of 3 are correctly identified – clearly pow3 will only return true when n really is a power of 3, so not so much point in checking that.

I meant, “not much point in checking that pow3 returns false for non-powers of 3” there.

Another possible method: https://programmingpraxis.com/2014/08/05/minimal-palindromic-base/#comment-26372 has a function for converting from a radix-n representation to a radix-n+1, so we can use this to directly convert from binary to base-3 (where it’s easy to see if we have an exact power).

For unary numbers aka lengths of lists represented by lists of corresponding lengths.

@Jussi: nice, looks like a subsystem of Peano arithmetic. I dusted off an old implementation of p-adic arithmetic in Haskell and came up with this. Numbers are lists of bits, least significant first, and division is done in the opposite order to usual, we use the Maybe type to indicate division has failed (we could just extend the number out to the ‘left’ in a lazy list, but here we are only interested in exact division):

Quick off-the-cuff pseudocode to check whether the input is a *power* of three (not a multiple of three):

Basically it checks whether the number_to_check is the first power of three (ie 1). If not, it increases the power_of_three to the next power of three (by multiplying it by three) and checks again, and keeps doing so until it either matches the number_to_check or the power of three is too high – in which case it returns ‘false’.

Hello, I’m new around here. I’m a Software Devolopment Student and I wrote my algorithm in java.

First way:

public static void main(String[] args) {

String entrada = “”;

int num, result = 1;

entrada = JOptionPane.showInputDialog(“Type a number:”);

num = Integer.parseInt(entrada);

for (int i = 1; i < num; i++) {

result = result * 3;

if (result == num) {

System.out.println("This is power of 3!");

break;

}

}

System.out.println(num == 1 ? "This is power of 3!" : "");

}

Second way:

public static void main(String[] args) {

String entrada = "";

int num, result = 1;

entrada = JOptionPane.showInputDialog("Type a number:");

num = Integer.parseInt(entrada);

while (result < num) {

result = result * 3;

if (result == num)

System.out.println("This is power of 3!");

}

System.out.println(num == 1 ? "This is power of 3!" : "");

}

With the exception of zero, the digits of multiples of 3 always sum to 3.

Similarly, with the exception of 1 and 3, the digits of powers of 3 sum to 9.

So maybe, if we were testing extremely large numbers, this rule (along with the number being odd) could be used as a fast-fail. Hmmm, makes we wonder, how many numbers less than n have digits that sum to 9?