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.

Advertisements

Pages: 1 2

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

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: