Вычисление различных членов для данной пары возведения в степень с одинаковым результатом

Question

Чтобы понять проблему, давайте сначала рассмотрим эти примеры:

4 ⁶ = (2 ² ) ⁶ = 2 ¹² = (2 ³ ) ⁴ = 8 ⁴ = 16 ³ = 4096 .

Таким образом, можно сказать, что 4 ⁶ , 2 ¹² , 8 ⁴ и 16 ³ одинаковы.

27 ³ = 3 ⁹ = 19683

так что 27 ³ и 3 ⁹ идентичны.

Теперь проблема для любой данной пары a ^b , как вычислить все другие возможные (если есть) x ^y где a ^b = x ^y . Меня интересует алгоритм , который может быть эффективно реализован в C / C ++.

Например:

Если входы такие:

4,6 желаемый результат: (2,12),(8,4)

8,4 желаемый вывод: (2,12),(2,6)

27,3 желаемый результат: (3,9)

12,6 желаемый результат: (144,3),(1728,2)

7,5 желаемый результат: No duplicate possible

Answer 1

Это в основном математическая задача. Вы можете извлечь все простые множители числа, и вы получите список простых чисел и их показателей, т. Е. 216000 = 2 ⁶ * 3 ³ * 5 ³ . Затем возьмите GCD из показателей: GCD (6,3,3) = 3. Разделите показатели по GCD, чтобы получить наименьший корень из числа, 2 ² * 3 ¹ * 5 ¹ = 60. Тогда множитель GCD - множители 3 равны 1 и 3. Существует один способ выразить число как интегральную степень для каждого множителя GCD. Вы можете выразить это как (60 ³ ) ¹ или (60 ¹ ) ³ .

РЕДАКТИРОВАТЬ: исправлена ​​математическая ошибка.

Answer 2

Если вам интересны только целые числа, вы можете просто начать извлекать целочисленные корни из целевого числа и проверять, является ли результат целым числом.

У вас даже есть удобное условие остановки - всякий раз, когда корень ниже 2, вы можете остановиться.То есть алгоритм:

• Дан результат
• N <- 2 </li>
• Вычислить N-й корень.
• • Если это целое число: добавить к ответам
• • Если это <2, выйти из цикла </li>
• N + = 1, назад к предыдущему шагу

Этот алгоритм всегда завершается.

Answer 3

Я считаю, что эта проблема эквивалентна Целочисленная факторизация .

Я сказал это, потому что мы можем преобразовать любое составное число в уникальный продукт простых чисел
(см. Основная теорема арифметики ), а затем начинайте создавать комбинации с факторами и степенями.

Обновление: например: 4 ⁶

мы преобразуем его в степень простого множителя, поэтому имеем 2 ¹² .
Теперь мы увеличиваем базу экспоненциально и имеем: 4 ⁶ , 8 ⁴ ... пока показатель не станет равным 1.

Answer 4

Я наконец-то решил это сам. Используя наивный алгоритм целочисленной факторизации, мое решение выглядит как this . Его можно оптимизировать дальше, используя алгоритм Полларда

РЕДАКТИРОВАТЬ: Код обновлен, теперь он может обрабатывать составные базы. Укажите, если у него есть и другие ошибки:)

Answer 5

Наименьшее основание, которое имеет смысл, равно 2. Кроме того, наименьшее значение, которое имеет смысл, равно 2.

Учитывая результат, вы можете определить максимально возможный показатель.

Пример: 4096 = 2 ^ 12, наибольшая экспонента 12.

Это также работает с результатами, которые не имеют степеней 2: 19683 немного больше, чем 2 ^ 14, поэтому вы не увидите никаких показателей больше 14.

Теперь вы можете взять свой номер и пройти путь от верхнего показателя к 2 (наименьший показатель). Для каждого пробного показателя exp возьмите exp-th корень результата; если это чистое целое число, значит, вы нашли одно решение.

Вы можете использовать логарифмы для вычисления log2 результата и для получения n-го корня числа. Но вам нужно остерегаться ошибок округления.

Преимущество этого подхода состоит в том, что, как только вы все настроите, вы можете просто запустить простой цикл, и после этого у вас будут все ваши результаты.