Генерация последовательности чисел (степеней) по порядку

Question

Я ищу алгоритм (или, еще лучше, код!) Для генерации степеней, в частности чисел с нечетным показателем степени больше 1: третьи степени, пятые степени, седьмые степени и так далее.Тогда мой желаемый результат -

8, 27, 32, 125, 128, 216, 243, 343, 512, 1000

и т. Д. До указанного предела.

Я не хочу хранить полномочия в списке и сортировать их, потому что я делаюслишком много, чтобы поместиться в памяти - надеюсь, предел будет 10 ³⁰ или около того, что соответствует требованию к памяти ≈ 1 ТБ.

Моя основная идея - иметь массив, содержащий текущийчисло (начиная с 2) для каждого показателя степени, начиная с 3 и доходя до двоичного журнала предела.На каждом шаге я перебираю массив экспонент, находя тот, который дает наименьшую мощность (находя либо Pow (основание, экспонента), либо более вероятный показатель * log (основание), вероятно запоминая эти значения).В этот момент вызовите функцию «output», которая фактически выполнит вычисления с числом, но, конечно, вам не нужно об этом беспокоиться.

Конечно, из-за диапазона используемых чисел, bignums должныбыть использованным - встроенным в язык, в библиотеку или самостоятельно развернутым.Приветствуется соответствующий код или фрагменты кода: я чувствую, что эта задача похожа на некоторые классические проблемы (например, проблема Хэмминга по генерации чисел в форме 2 ^x 3 ^y 5 ^z ) и может быть эффективно решена.Я довольно независим от языка: все, что мне понадобится для моей функции «вывода», это массивы, вычитание, сравнение слова bignum и функция квадратного корня bignum integer.

Answer 1

В вашем примере отсутствует 64 = 4 ^ 3, а 729 = 9 ^ 3.

Вы хотите, чтобы множество всех {n ^ m}, пройденных в числовом порядке, m нечетное, n целое и n> 1. Мы знаем, что (для n> 1) это увеличение или n или m увеличит это значение, но если не считать вычислений, мы не можем сравнивать многое другое.

Существует два очевидных «двойных» способа сделать это: отслеживать самую высокую базу n, которую вы рассматриваете, и для всех баз, меньших этой, следующий показатель m, который нужно рассмотреть. Затем выберите самый маленький и сравните его с n ^ 3. Или наоборот - отслеживайте наивысший показатель m и для каждого показателя, меньшего этого, отслеживайте наивысшее используемое основание, найдите наименьшее и сравните его с добавлением 2 ^ m.

Для эффективного отслеживания этих номеров вам нужно сохранить их в очереди с приоритетами . Теперь вы все еще хотите свести к минимуму количество записей в очереди приоритетов за раз, поэтому мы хотим выяснить, какой из этих двух методов лучше справляется с этой задачей. Оказывается, что для достижения заданной точки требуются гораздо более высокие значения n. При числе k наибольшее увиденное значение m будет log_2 из k, а наибольшее увиденное значение n будет k ^ (1/3).

Итак, у нас есть очередь приоритетов с элементами (v, n, m), где значение v = n ^ m.

add_priority_queue(2^3, 2, 3)
for m in 5, 7, ....
    v = 2^m
    while value(peek(queue)) <= v:
        (v1, n1, m1) = pop(queue)
        if v1 != v print v1
        add_priority_queue((n1+1)^m1, n1+1, m1)
    add_priority_queue(2^m, 2, m)

Обратите внимание, что нам нужно проверить v1 = v: у нас может быть 2 ^ 9 = 512 = 8 ^ 3, и только один должен быть распечатан, верно?

Реализация на Haskell со случайной очередью приоритетов, захваченной hackage .

import Data.MeldableHeap

dropMin q = maybe empty snd (extractMin q)

numbers = generate_values (insert (2^3, 2, 3) empty) 5

generate_values q m = case findMin q of
    Nothing -> []
    Just (v1, n1, m1) -> case compare v1 (2^m) of
        EQ -> generate_values (insert ((n1+1)^m1, n1+1, m1) (dropMin q)) m
        LT -> v1 : generate_values (insert ((n1+1)^m1, n1+1, m1) (dropMin q)) m
        GT -> 2^m : generate_values (insert (3^m, 3, m) q) (m + 2)

main = sequence_ (map print numbers)

У меня в данный момент пробег 177403008736354688547625 (это 23 цифры) и вывод открытого текста 1,3 ГБ через 8 минут

Answer 2

Рассмотрим k списки для чисел 2 .. k+1 чисел.Каждый список i представляет полномочия числа i+1.Поскольку каждый список отсортирован, используйте k-way merging with min heap для достижения того, что вам нужно.

Мин-куча создается с первыми индексами списков в качестве ключа, а после извлечения минимума мы удаляем первый элемент, составляющий второй элемент, как ключ и переставляем кучу, чтобы получить следующий минимум.Эта процедура повторяется, пока мы не получим все числа.

Answer 3

deque numbers // stores a list of tuples - base number, and current odd power value - sorted by the current odd power value

for i = 2 .. infinity
  numbers.push_back (i,i^3) // has to be the highest possible number so far
  while numbers.peek_front[1] == i // front always has the lowest next value
    print i
    node = numbers.pop_front
    node[1]=node[1]*(node[0]^2)
    // put the node back into the numbers deque sorted by the second value in it - will end up being somewhere in the middle

в 2, цифры будут [2,8]

на 3, цифры будут [2,9], [3, 27] ... в 8 числа будут [2,8], [3,27] ..... [8,8 ^ 3]

Вы снимаете первый узел, распечатываете его, затем помещаете его обратно в середину чисел со значениями [2,32]

Я думаю, что это будет работать и разумно использовать память.

Есть особый случай для 1, так как 1 ^ N никогда не меняется. Это также выведет дубликаты значений для чисел - например, 256 - и есть довольно простые способы немного изменить алгоритм их удаления.

Это решение является постоянным временем для проверки каждого числа, но требует довольно много оперативной памяти.