## Powers Of 3

### August 27, 2019

We extend the question to consider any modulus m, not just 3, and provide a recursive solution:

```(define (power-of? m n)
(if (zero? (modulo n m))
(power-of? m (/ n m))
(= n 1)))

> (power-of? 3 27)
#t
> (power-of? 3 36)
#f```

I could never be a teacher of beginning programmers. The discussion thread (I won’t link it, to preserve anonymity) indicated that the beginning programmer understood neither the mathematics of the problem nor the concept of looping in a programming language. You can run the program at https://ideone.com/hpSaFA.

Pages: 1 2

### 9 Responses to “Powers Of 3”

1. Zack said

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

``````return false
``````

end

Some testing:

is_power_of_3_new(100)
false

is_power_of_3_new(3^30)
true

is_power_of_3_new(1 + 3^30)
false

is_power_of_3_new(1)
true

is_power_of_3_new(0)
true

is_power_of_3_new(-1)
false

Cheers!

2. matthew said

@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))
```
3. matthew said

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 *= 3
```
4. John Cowan said

The 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.

5. matthew said

@John: David Turner’s advice here is possibly relevant: https://www.cs.kent.ac.uk/people/staff/dat/miranda/manual/30.html

6. matthew said

Some interesting solutions here: https://programmingpraxis.com/2016/03/01/powers-of-3/

Here’s a modification of one of them in Haskell:

```import Data.List.Ordered (member)
pow n = flip member powers where powers = 1 : map (n*) powers
main = print (filter (pow 3) [1..10000000])
```
7. Zack said

@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!

8. Daniel said

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, 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
```
9. Junaid Ali said

#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)