How to check if an integer is power of 3?

Question

I saw this question,and pop up this idea.

Answer 1

Recursively divide by 3, check that the remainder is zero and re-apply to the quotient.

Note that 1 is a valid answer as 3 to the zero power is 1 is an edge case to beware.

Answer 2

If you are running Python, you can try using this (broken because of rounding error) code.

from math import log

def power_of(number, base):
    return log(number) / log(base) % 1 == 0

The test shown below that it is only reliable on the lower values of 3 ** X. Rounding can help, but starblue's answer is certainly superior to any other way of solving your question.

>>> from math import log
>>> def power_of(number, base):
    return log(number) / log(base) % 1 == 0

>>> for power in range(21):
    number = 3 ** power
    answer = '{} is{}a power of {}.'
    values = number, ' ' if power_of(number, 3) else ' not ', 3
    print(answer.format(*values))
    number += 1
    values = number, ' ' if power_of(number, 3) else ' not ', 3
    print(answer.format(*values))


1 is a power of 3.
2 is not a power of 3.
3 is a power of 3.
4 is not a power of 3.
9 is a power of 3.
10 is not a power of 3.
27 is a power of 3.
28 is not a power of 3.
81 is a power of 3.
82 is not a power of 3.
243 is not a power of 3.
244 is not a power of 3.
729 is a power of 3.
730 is not a power of 3.
2187 is a power of 3.
2188 is not a power of 3.
6561 is a power of 3.
6562 is not a power of 3.
19683 is a power of 3.
19684 is not a power of 3.
59049 is not a power of 3.
59050 is not a power of 3.
177147 is a power of 3.
177148 is not a power of 3.
531441 is a power of 3.
531442 is not a power of 3.
1594323 is not a power of 3.
1594324 is not a power of 3.
4782969 is a power of 3.
4782970 is not a power of 3.
14348907 is not a power of 3.
14348908 is not a power of 3.
43046721 is a power of 3.
43046722 is not a power of 3.
129140163 is not a power of 3.
129140164 is not a power of 3.
387420489 is a power of 3.
387420490 is not a power of 3.
1162261467 is a power of 3.
1162261468 is not a power of 3.
3486784401 is not a power of 3.
3486784402 is not a power of 3.
>>>

Answer 3

while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

Note that 1 is the zeroth power of three.

Edit: You also need to check for zero before the loop, as the loop will not terminate for n = 0 (thanks to Bruno Rothgiesser).

Answer 4

I find myself slightly thinking that if by 'integer' you mean 'signed 32-bit integer', then (pseudocode)

return (n == 1) 
    or (n == 3)
    or (n == 9)
    ... 
    or (n == 1162261467)

has a certain beautiful simplicity to it (the last number is 3^19, so there aren't an absurd number of cases). Even for an unsigned 64-bit integer there still be only 41 cases (thanks @Alexandru for pointing out my brain-slip). And of course would be impossible for arbitrary-precision arithmetic...

Answer 5

How large is your input? With O(log(N)) memory you can do faster, O(log(log(N)). Precompute the powers of 3 and then do a binary search on the precomputed values.

Answer 6

if (log n) / (log 3) is integral then n is a power of 3.

Answer 7

You can do better than repeated division, which takes O(lg(X) * |division|) time. Essentially you do a binary search on powers of 3. Really we will be doing a binary search on N, where 3^N = input value). Setting the Pth binary digit of N corresponds to multiplying by 3^(2^P), and values of the form 3^(2^P) can be computed by repeated squaring.

Algorithm

• Let the input value be X.
• Generate a list L of repeated squared values which ends once you pass X.
• Let your candidate value be T, initialized to 1.
• For each E in reversed L, if T*E <= X then let T *= E.
• Return T == X.

Complexity:

O(lg(lg(X)) * |multiplication|) - Generating and iterating over L takes lg(lg(X)) iterations, and multiplication is the most expensive operation in an iteration.

Answer 8

Set based solution...

DECLARE @LastExponent smallint, @SearchCase decimal(38,0)

SELECT
    @LastExponent = 79, -- 38 for bigint
    @SearchCase = 729

;WITH CTE AS
(
    SELECT
        POWER(CAST(3 AS decimal(38,0)), ROW_NUMBER() OVER (ORDER BY c1.object_id)) AS Result,
        ROW_NUMBER() OVER (ORDER BY c1.object_id) AS Exponent
    FROM
        sys.columns c1, sys.columns c2
)
SELECT
    Result, Exponent
FROM
    CTE
WHERE
    Exponent <= @LastExponent
    AND
    Result = @SearchCase

With SET STATISTICS TIME ON it record the lowest possible, 1 millisecond.

Answer 9

Very interesting question, I like the answer from starblue, and this is a variation of his algorithm which will converge little bit faster to the solution:

private bool IsPow3(int n)
{
 if (n == 0) return false;
 while (n % 9 == 0)
 {
  n /= 9;
 }
 return (n == 1 || n == 3);
}

Answer 10

I'm surprised at this. Everyone seems to have missed the fastest algorithm of all.

The following algorithm is faster on average - and dramatically faster in some cases - than a simple while(n%3==0) n/=3; loop:

bool IsPowerOfThree(uint n)
{
  // Optimizing lines to handle the most common cases extremely quickly
  if(n%3 != 0) return n==1;
  if(n%9 != 0) return n==3;

  // General algorithm - works for any uint
  uint r;
  n = Math.DivRem(n, 59049, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r, 243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;
}

The numeric constants in the code are 3^10, 3^5, and 3^3.

Performance calculations

In modern CPUs, DivRem is a often single instruction that takes a one cycle. On others it expands to a div followed by a mul and an add, which would takes more like three cycles altogether. Each step of the general algorithm looks long but it actually consists only of: DivRem, cmp, cmove, cmp, cand, cjmp, add. There is a lot of parallelism available, so on a typical two-way superscalar processor each step will likely execute in about 4 clock cycles, giving a guaranteed worst-case execution time of about 25 clock cycles.

If input values are evenly distributed over the range of UInt32, here are the probabilities associated with this algorithm:

• Return in or before the first optimizing line: 66% of the time
• Return in or before the second optimizing line: 89% of the time
• Return in or before the first general algorithm step: 99.998% of the time
• Return in or before the second general algorithm step: 99.99998% of the time
• Return in or before the third general algorithm step: 99.999997% of the time

This algorithm outperforms the simple while(n%3==0) n/=3 loop, which has the following probabilities:

• Return in the first iteration: 66% of the time
• Return in the first two iterations: 89% of the time
• Return in the first three iterations: 97% of the time
• Return in the first four iterations: 98.8% of the time
• Return in the first five iterations: 99.6% of the time ... and so on to ...
• Return in the first twelve iterations: 99.9998% of the time ... and beyond ...

What is perhaps even more important, this algorithm handles midsize and large powers of three (and multiples thereof) much more efficiently: In the worst case the simple algorithm will consume over 100 CPU cycles because it will loop 20 times (41 times for 64 bits). The algorithm I present here will never take more than about 25 cycles.

Extending to 64 bits

Extending the above algorithm to 64 bits is trivial - just add one more step. Here is a 64 bit version of the above algorithm optimized for processors without efficient 64 bit division:

bool IsPowerOfThree(ulong nL)
{
  // General algorithm only
  ulong rL;
  nL = Math.DivRem(nL, 3486784401, out rL); if(nL!=0 && rL!=0) return false;
  nL = Math.DivRem(nL+rL,   59049, out rL); if(nL!=0 && rL!=0) return false;
  uint n = (uint)nL + (uint)rL;
  n = Math.DivRem(n,   243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;

}

The new constant is 3^20. The optimization lines are omitted from the top of the method because under our assumption that 64 bit division is slow, they would actually be slow things down.

Why this technique works

Say I want to know if "100000000000000000" is a power of 10. I might follow these steps:

1. I divide by 10^10 and get a quotient of 10000000 and a remainder of 0. These add to 10000000.
2. I divide by 10^5 and get a quotient of 100 and a remainder of 0. These add to 100.
3. I divide by 10^3 and get a quotient of 0 and a remainderof 100. These add to 100.
4. I divide by 10^2 and get a quotient of 1 and a remainder of 0. These add to 1.

Because I started with a power of 10, every time I divided by a power of 10 I ended up with either a zero quotient or a zero remainder. Had I started out with anything except a power of 10 I would have sooner or later ended up with a nonzero quotient or remainder.

In this example I selected exponents of 10, 5, and 3 to match the code provided previously, and added 2 just for the heck of it. Other exponents would also work: There is a simple algorithm for selecting the ideal exponents given your maximum input value and the maximum power of 10 allowed in the output, but this margin does not have enough room to contain it.

NOTE: You may have been thinking in base ten throughout this explanation, but the entire explanation above can be read and understood identically if you're thinking in in base three, except the exponents would have been expressed differently (instead of "10", "5", "3" and "2" I would have to say "101", "12", "10" and "2").