Как проверить, является ли целое число степенью 3?

Question

Я видел этот вопрос , и всплыла эта идея.

Answer 1

Вот общий алгоритм для определения, является ли число степенью другого числа:

bool IsPowerOf(int n,int b)
{
    if (n > 1)
    {
        while (n % b == 0)
        {
            n /= b;
        }
    }
    return n == 1;
}

Answer 2

Python-решение

from math import floor
from math import log

def IsPowerOf3(number):
  p = int(floor(log(number) / log(3)))
  power_floor = pow(3, p)
  power_ceil = power_floor * 3
  if power_floor == number or power_ceil == number:
    return True
  return False

Это намного быстрее, чем простое решение деления на 3.

Доказательство: 3 ^ p = число

p log (3) = log (число) (ведение журнала с обеих сторон)

p = log (число) / log (3)

Answer 3

Набор на основе решения ...

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

С SET STATISTICS TIME ON он записывает минимально возможную 1 миллисекунду.