Powers Of 3
March 1, 2016
The powers of 3 are 30 = 1, 31 = 3, 32 = 9, 33 = 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.
Programming Praxis 
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.
import math k = math.log(2)/math.log(3) def pow3(n): bits = n.bit_length() trits = int(k*bits) return n == 3**trits i = 0 while True: assert(pow3(3**i)) i += 1I 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.
(define-syntax let2 (syntax-rules () ((let2 ((x y exp)) body) (call-with-values (lambda () exp) (lambda (x y) body))))) (define (lesser? os ws) (or (and (null? os) (pair? ws)) (and (pair? os) (pair? ws) (lesser? (cdr os) (cdr ws))))) (define (after os ws) (if (null? ws) os (after (cdr os) (cdr ws)))) (define (divide os ws) (let loop ((p (list)) (os os)) (if (lesser? os ws) (values p os) (loop (cons (car os) p) (after os ws))))) (define (divides? ws os) (let2 ((q r (divide os ws))) (null? r))) (define (one? os) (and (pair? os) (null? (cdr os)))) (define (power-of? ws os) (cond ((null? os) (null? ws)) ((one? os) => values) (else (let2 ((q r (divide os ws))) (and (null? r) (power-of? ws q)))))) (define (power-of-ooo? os) (power-of? (list os os os) os)) (define (expected p obs) (write (length obs)) (write-char #\tab) (write (if (p obs) (quote pass) (quote FAIL))) (newline)) (define (surprise p obs) (write (length obs)) (write-char #\tab) (write (if (p obs) (quote FAIL) (quote pass))) (newline)) (let* ((zero (list)) (one (cons zero zero)) (two (cons zero one)) (three (cons zero two)) (four (cons zero three)) (five (cons zero four)) (six (cons zero five)) (seven (cons zero six)) (eight (cons zero seven)) (nine (cons zero eight))) (surprise power-of-ooo? zero) (expected power-of-ooo? one) (surprise power-of-ooo? two) (expected power-of-ooo? three) (surprise power-of-ooo? four) (surprise power-of-ooo? five) (surprise power-of-ooo? six) (surprise power-of-ooo? seven) (surprise power-of-ooo? eight) (expected power-of-ooo? nine) (surprise power-of-ooo? (append six six)) (surprise power-of-ooo? (append seven eight)) (surprise power-of-ooo? (append nine nine six)) (surprise power-of-ooo? (append nine nine seven)) (surprise power-of-ooo? (append nine nine eight)) (expected power-of-ooo? (append nine nine nine)) (surprise power-of-ooo? (append nine nine nine one)) (surprise power-of-ooo? (append nine nine nine two)) (surprise power-of-ooo? (append nine nine nine three)))@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):
sbc (a:s) (b:t) k = do x <- sbc s t (fromEnum(b+k>a)) Just((a+b+k)`mod`2 : x) sbc [] [] 0 = Just [] sbc [] t k = Nothing sbc (a:s) [] k = sbc (a:s) [0] k shift [] = [] shift s = 0:s pdiv [] t = Just [] pdiv (_:s) (0:t) = pdiv s t pdiv (0:s) (1:t) = do x <- pdiv s (1:t) Just(shift x) pdiv (1:s) (1:t) = do y <- sbc s t 0 x <- pdiv y (1:t) Just(1 : x) padic 0 = [] padic n = (n `mod` 2) : padic (n `div` 2) pow3 k [1] = Just k pow3 k n = do x <- pdiv n [1, 1] pow3 (k+1) x main = print (map (pow3 0 . padic) [1..30])Quick off-the-cuff pseudocode to check whether the input is a *power* of three (not a multiple of three):
power_of_three = 1; while (power_of_three < number_to_check) do { if (power_of_three == number_to_check) then return true; power_of_three = power_of_three * 3; } return false;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?