は（まだ良いかコードを！）私は、アルゴリズムを探しているため

Question

に数字（権力）のシーケンスを生成する力を生成するために、1より大きい奇数の指数と特異番号：第三の勢力、第五の力を、第7勢力、など。私の希望する出力は、

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

などです。

メモリに収まるようにあまりにも多くのメモリを作っているので、リストにその能力を格納しておきたいとは思っていません。メモリの所要量に相当する1程度です。 ≈1 TB。

私の基本的な考え方は、指数ごとに現在の数値（2から始まる）を保持し、3から始めて限界値のバイナリログに行くことです。各ステップで、指数配列をループして、最小のパワー（基底、指数）または可能性の高い指数* log（基底）のいずれかを見つけ、これらの値をおそらくメモする）を見つける。その時点で実際に数値で計算する「出力」関数を呼び出しますが、もちろんそのことについて心配する必要はありません。

もちろん、数字の範囲のために、bignumを使用する必要があります。つまり、言語、ライブラリ、またはセルフ・ロールに組み込む必要があります。関連するコードやコードスニペットはわかります：私はこのタスクがいくつかの古典的な問題に似ていると感じます（例えば、ハミングの数字を生成する問題は2 ^{x y z}です）効率的に私はかなり言語には無関係です。私の「出力」関数に必要なのは、配列、減算、ビッグ・ワード比較、ビギナン整数平方根関数です。 2で

Answer 1

あなたの例は、64 = 4^3、および729 = 9^3がありません。

すべての{n^m}の集合を数値順、m奇数、n積分、n> 1で欲しいと思います。n> 1の場合、n または mのいずれかが値は限られていますが、計算が不十分なため、それ以外の点では比較できません。

これを行うには2つの明白な「デュアル」方法があります。考慮する最高の基数nを考慮し、それより小さいすべての基底について考慮する次の指数mを追跡します。次に、最小のものを選んでn^3と比較します。あるいは、それ以外の方法では、最高指数mを追跡し、それより小さい各指数について、使用される最高基底を追跡し、最小指数を見つけてそれを2^mを加えることと比較する。

これらの番号を効率的に把握するには、priority queueに保管してください。今度は、一度に優先度キューのエントリ数を最小限に抑えたいので、これらの2つの方法のどちらが良いか分かります。それは与えられた点にそれを作るためにはるかに高い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にすることができます。

ランダム優先度キューがhackageから離れているHaskell実装です。

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 8分

Answer 2

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 

、番号が3で[2,8]

なり、番号は[2,9]、[3、27] なり... 8で 、数字になります[2,8]、[3,27] ..... [8,8^3]

最初のノードを離して印刷し、番号の真ん中に戻します値[2,32]

私はこれがうまくいくと思って、妥当なメモリ使用量を持っています。

1^Nは決して変更されないので、1の特殊なケースがあります。これは数字の重複値（例えば256）も表示しますが、それらを削除するアルゴリズムを少し変更する方法はかなり簡単です。

この解決策は、各数値をチェックするための一定時間ですが、かなりのRAMが必要です。

Answer 3

数字2 .. k+1の数字のリストをkと考えてください。各リストiは、番号i+1の累乗を表します。各リストは、あなたが必要とするものを達成するためにソートされた使用k-way merging with min heapです。

最小ヒープは、キーとして、リストの最初のインデックスで構成され、最小が抽出された後、我々は、キーとして、第二の要素を製造する最初の要素を削除して、次の最小値を取得するために、ヒープを再配置します。 この手順は、すべての数値が得られるまで繰り返されます。