Powers Of 3
August 27, 2019
This problem appeared on a beginning-programmers discussion list:
How can I determine if a number n is a power of 3?
Your task is to write a program to determine if a number is a power of 3. 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 
Cool drill, though not original. Actually, I’ve found a previously coded solution to it in my archive. Here is a new approach, using Julia 1.1:
function is_power_of_3_new(x::Int64)
if x < 0
return false
elseif (x == 0) || (x == 1)
return true
else
while x > 1
x /= 3
if x == 1; return true; end
end
end
end
Some testing:
Cheers!
@Zack – your code is very difficult to read & understand as the indentation has been lost – you really should try using the code formatting features described here: https://en.support.wordpress.com/wordpress-editor/blocks/syntax-highlighter-code-block/2/ – just leave out the “lang=..” bit for Julia or use “text” or find something else (“css”?) that looks OK.
Anyway, repeatedly dividing by three is slow for very large powers. Using Elric’s answer from https://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-a-power-of-3, we can do this: find the largest power of 3 greater or equal to input, then check remainder is 0. Of course, this will generally be slower for most numbers that aren’t powers of 3:
def ispower3(n): k = int(math.log(n)/math.log(3)) p = 3**k while p < n: p *= 3 return p % n == 0 n = 3**1234567 print(ispower3(n))Doing that final % operation is pointless – we can just look for the closest power of 3 – need to be a little careful because of rounding problems with the logs:
def ispower3(n): k = int(math.log(n)/math.log(3)) p = 3**k while p > n: p //= 3 while p < n: p *= 3 return p == n n = 3 while True: assert(not ispower3(n-1)) assert(ispower3(n)) assert(not ispower3(n+1)) n *= 3The given solution neatly exposes the power of Scheme: it is written recursively, which makes it easy to reason about. But because it’s tail recursion, Scheme will execute it iteratively.
While I’m at it, the next application for tail recursion beyond looping is state machines. A state machine in a typical
programming language is a big while-loop with a mutable state variable and a big case statement branching on that variable. In Scheme, it’s just a bunch of procedure definitions, one per state. Each one transitions to the appropriate next state by tail-calling its successor, possibly passing some useful arguments. Alternatively, the definitions can be wrapped in a let-block to maintain any needed shared state. Proper tail calls guarantee that this is more efficient than the while loop, being just a bunch of register-to-register moves and gotos after the Scheme compiler is done with it.
@John: David Turner’s advice here is possibly relevant: https://www.cs.kent.ac.uk/people/staff/dat/miranda/manual/30.html
Some interesting solutions here: https://programmingpraxis.com/2016/03/01/powers-of-3/
Here’s a modification of one of them in Haskell:
@matthew. Thank you for the tip. I’ll check it out next time. Also, the algo your implemented is definitely better and it the same I used in my original solution, the previous time this exercise was mentioned. This time, however, I wanted to try out something new as a creativity exercise. Cheers!
Here’s a solution in C.
#include <stdbool.h> #include <stdint.h> #include <stdlib.h> #include <stdio.h> bool is_power3(uint64_t x) { return 12157665459056928801ull % x == 0; } int main(int argc, char* argv[]) { if (argc != 2) return EXIT_FAILURE; uint64_t x = strtoull(argv[1], NULL, 10); printf("%d\n", is_power3(x)); return EXIT_SUCCESS; }Example:
$ ./a.out 9 1 $ ./a.out 8 0 $ for i in {0..20000}; do \ if [ "$(./a.out $i)" = 1 ]; then \ echo $i; \ fi; \ done 1 3 9 27 81 243 729 2187 6561 19683#How can I determine if a number n is a power of 3?
n=int(input(“Enter Number : “))
r=list(range(1,n))
print(r,end=” “)
print()
for i in r:
if n==i**3:
print(“Power of 3″,”and it is is the cube of”,i)