Powers Of 3

March 1, 2016

The most straight forward solution is to repeatedly divide by 3 as long as the remainder of the division is 0; the original number n is divisible by 3 only if the repeated divisions reduce n to 1:

(define (power3? n)
  (cond ((= n 1) #t)
        ((positive? (modulo n 3)) #f)
        (else (power3? (/ n 3)))))

Non-powers of 3 are quickly identifed; powers of 3 take the longest. Beware this fails if n = 0, which causes an infinite loop. It’s easy to double the speed of that program:

(define (power3? n)
  (cond ((or (= n 1) (= n 3)) #t)
        ((positive? (modulo n 3)) #f)
        (else (power3? (/ n 9)))))

You could, of course, extend that to larger powers of 3, but we won’t. You can double the speed a different way if your division operator returns both the quotient and remainder:

(define (divrem n d)
  (let ((q (quotient n d)))
    (values q (- n (* d q)))))
(define (power3? n)
  (if (= n 1) #t
    (call-with-values
      (lambda () (divrem n 3))
      (lambda (q r)
        (if (positive? r) #f
          (power3? q))))))

If n has limited precision (say, you know it is a 16-bit integer), you could simply list all the possibilities:

(define (power3? n)
  (or (= n (expt 3  0))   ; 1
      (= n (expt 3  1))   ; 3
      (= n (expt 3  2))   ; 9
      (= n (expt 3  3))   ; 27
      (= n (expt 3  4))   ; 81
      (= n (expt 3  5))   ; 243
      (= n (expt 3  6))   ; 729
      (= n (expt 3  7))   ; 2187
      (= n (expt 3  8))   ; 6561
      (= n (expt 3  9))   ; 19683
      (= n (expt 3 10)))) ; 59049

With a larger range, you could speed this up by using binary search over the possibilities; here we handle 64-bit unsigned integers:

(define threes
  (let loop ((t 1) (ts (list)))
    (if (< (expt 2 64) t)
        (list->vector (reverse ts))
        (loop (* t 3) (cons t ts)))))
> threes
#(1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441
  1594323 4782969 14348907 43046721 129140163 387420489
  1162261467 3486784401 10460353203 31381059609 94143178827
  282429536481 847288609443 2541865828329 7625597484987
  22876792454961 68630377364883 205891132094649
  617673396283947 1853020188851841 5559060566555523
  16677181699666569 50031545098999707 150094635296999121
  450283905890997363 1350851717672992089 4052555153018976267
  12157665459056928801)
(define (power3? n)
  (let ((hi (- (vector-length threes) 1)))
    (if (or (< n 1) (< (vector-ref threes hi) n)) #f
      (let loop ((lo 0) (hi hi))
        (let ((mid (quotient (+ lo hi) 2)))
          (cond ((< hi lo) #f)
                ((< (vector-ref threes mid) n)
                  (loop (+ mid 1) hi))
                ((< n (vector-ref threes mid))
                  (loop lo (- mid 1)))
                (else #t)))))))

Another approach with limited-precision integers uses the largest power of 3 that fits in the allowed range:

(define (power3? n)
  (zero? (modulo 59049 n)))

For 31-bit integers, the constant is 319 = 1162261467, for 32-bit integers the constant is 320 = 3486784401, and for 63-bit integers the constant is 339 = 4052555153018976267.

If you have a way to compute integer logarithms, they provide another way to determine if a number is a power of 3:

(define (power3? n)
  (= (expt 3 (ilog 3 n)) n))
This is a mathematical truism, but probably won't work if you use the normal floating-point library to compute the logarithm, due to rounding error.

A general-purpose function that determines if a given number n is a power of a base b is shown below:
(define (power? n b)
  (when (< 1 n)
    (while (zero? (modulo n b))
      (set! n (quotient n b))))
  (= n 1))

You can run all these programs at http://ideone.com/FkrqlG, where you will also see contributions from the Standard Prelude.

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 )

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: