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)
> (power-of? 3 36)

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

8 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
    while x > 1
    x /= 3
    if x == 1; return true; end

    return false


    Some testing:



    is_power_of_3_new(1 + 3^30)





  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
  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(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[1], NULL, 10);
      printf("%d\n", is_power3(x));
      return EXIT_SUCCESS;


    $ ./a.out 9
    $ ./a.out 8
    $ for i in {0..20000}; do            \
        if [ "$(./a.out $i)" = 1 ]; then \
          echo $i;                       \
        fi;                              \

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: