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.
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
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).
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
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):
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 += 1I meant, “not much point in checking that pow3 returns false for non-powers of 3” there.
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).
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)))@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])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’.
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!" : "");
}
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?