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.

Pages: 1 2

11 Responses to “Powers Of 3”

  1. John Cowan said

    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

  2. Rutger said

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

    def divisible_by_3(n):
    	if n == 3 or n ==6 or n == 9:
    		return True
    	if n < 10:
    		return False
    	else:
    		reduction = sum(int(i) for i in str(n))
    		return divisible_by_3(reduction)
    
    for v in range(200):
    	print v, divisible_by_3(v)
    
    
  3. Zack said

    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

  4. matthew said

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

    import Data.Bits (shift)
    import Control.Monad (join)
    import Data.List.Ordered (member)
    
    powers3 = iterate (join ((+).(`shift`1))) 1 :: [Integer]
    pow3 = flip member powers3
    main =
      print (take 15 powers3) >>
      print (filter pow3 [1..10000000])
    

    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 += 1
    
  5. matthew said

    I meant, “not much point in checking that pow3 returns false for non-powers of 3” there.

  6. matthew said

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

  7. Jussi Piitulainen said

    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)))
    
  8. matthew said

    @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])
    
  9. Brendan said

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

  10. 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!" : "");
    }

  11. Chris Judge said

    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?

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: