問題タブ [factorization]

重複の可能性:
n 番目の醜い数
式 (2^x)*(3^y)*(5^z) の K 番目に小さい数を見つける

この問題を迅速かつエレガントな方法で解決する方法を考えています。

2^x * 3^y * 5^z; の形式で記述できるすべての数値nを「醜い」と定義します。ここで、x、y、z は自然数です。1500 番目の醜い数を見つけます。

たとえば、最初の「醜い」数字は次のとおりです。

この方法で、ブルートフォースを使用してこの問題を解決しようとしました。

しかし、それにはかなりの時間がかかるため、より迅速でより良い解決策を見つけたいと考えています。

醜い数の素因数は知っていますが、これらの数を正しい順序で生成する方法が思いつきません。

すべての数字をチェックすることなく、これらの数字を生成する方法が必要だと思います。問題は、素因数の指数が非常にランダムに分布しているように見えることです。

この表を見てください：

ご覧のとおり、x、y、z の値は規則に従っていないようです。

あなたの誰かがこの問題の解決策を見つけることができますか?

問題をさまざまな部分に分割しようと考えています。問題は指数のランダム性によって決定されるため、2s、3s、5s の累乗を個別に生成してから、2^x*3^y、2^x*5^z などの形式の数値を生成することができます。最終的にそれらをまとめましたが、これで問題が解決するかどうかはわかりません。

私は最近、ポラードの Rho アルゴリズムの並列化に関する論文を偶然見つけました。私の特定のアプリケーションを考えると、必要なレベルの数学に達していないという事実に加えて、この特定の並列化方法が私の特定のケースに役立つかどうか疑問に思っています。 .

非常に大きな数の 2 つの因数 (半素数) を見つけようとしています。この論文について私が理解できることはほとんどないが、この並列化は 2 つの非常に大きな因数ではなく、多数の小さな因数を含む数に対してうまく機能するというのが私の推測である。

これは本当ですか？この並列化を使用するか、他のものを使用する必要がありますか? ポラードのローを使用する必要がありますか、それとも別の因数分解アルゴリズムのより良い並列化がありますか?

私はアセンブリにかなり慣れていないので、特定の数値の素因数分解を出力しようとしています。ネットを何時間も探し回った結果、DIV 命令に関する役立つ情報をいくつか見つけましたが、自分のコードで自分のやりたいことを実行することができません。

私はひどく間違ったことをしましたが、それを見つけることはできません。誰か親切な人が私にそれを見つけてくれませんか？

実際、N a (おそらく非常に大きい) 偶数整数が与えられた場合、gcd(F,R) = 1、F>R、および F が可能な限り小さい N = F * R を見つけたいと思います (完全にファクタリング F)。問題の核心は、R < sqrt(N) となる最大の除数 R を見つけることです。

たとえば、N=36 の場合、F=9 と R=4 になります。R は必ずしも素数または素数ベキではないことに注意してください。N を因数分解していないことに注意してください。F と R の唯一の制限は、それらが互いに素であることです。

これは私の簡単で素朴なバージョンで、動作しています:

私が想像するもう 1 つの方法は、除数を昇順で見つけ、途中で非除数の倍数を削除することです。何かのようなもの：

これは遅く、メモリを大量に消費すると思いますが、i代わりにジェネレーターを使用すると効率的になる可能性があります。発電機はあまり使っていません。

最初のバージョンを改善できますか? 2 番目のバージョンは実行可能ですか (どうすればよいですか)? より良い完全に異なる方法はありますか？

Python、C、または疑似コードで答えを探しています。

これは、数論のクラスのプロジェクトです。Pocklingtonに基づく素数性テストを実装しています。因数分解アルゴリズムが必要ですが、私たちは何も研究していません。おそらく、クラスの範囲外にある二次ふるいなどを使用するつもりはありません。提起された質問に関する具体的なヘルプを探しています。

ウィキペディアの車輪の因数分解の手順に従っていると、2-3-5-7 の車輪を作ろうとすると、素数 331 が合成数として扱われるという問題に遭遇したようです。

2-3-5-7 ホイールの場合、2*3*5*7=210。そこで、210 スロットのサークルをセットアップし、手順 1 ～ 7 を問題なく実行しました。次に、ステップ 8 に進み、素数のすべての倍数のスポークを削除します。最終的には、素数である 11 の倍数である 121 に根ざしたスポークを削除します。121 を根とするスポークの場合、121 + 210 = 331 です。残念ながら、331 は素数です。

ウィキペディアの手順は間違っていますか？

それとも手順を誤解していたので、2、3、5、および 7 の倍数であるスポークのみを削除し、210 未満の他の素数は削除すべきではなかったのでしょうか?

Haskell の学習を支援するために、Project Euler の問題に取り組んでいます。各問題を解決した後、Haskell wiki と照らし合わせて解決策を確認し、より良いコーディング プラクティスを学びます。問題3の解決策は次のとおりです。

これについての私の単純な解釈は、primesは で定義され、primeFactorsは で定義されているということですprimes。したがって、評価primeFactors 9は次のプロセスに従います。

1. 評価しfactor 9 primesます。
2. 最初primesの要素である 2 を求めます。
3. 次primesの要素を求めます。
4. このプロセスの一環として、評価しprimeFactors 3ます。
5. 最初primesの要素である 2 を求めます。
6. 次primesの要素を求めます。
7. このプロセスの一環として、評価しprimeFactors 3ます。
8. ...

つまり、手順 2 ～ 4 が無限に繰り返されます。アルゴリズムが終了するので、明らかに私は間違っています。私はここでどんな間違いを犯していますか？

Python（numpy）でCholesky分解で低ランクの更新を実行できるようにするライブラリ/コードを教えてもらえますか？Matlab は、この機能を「cholupdate」と呼ばれる関数として提供しています。LINPACKにもこの機能がありますが、（私の知る限り）まだLAPACKに移植されていないため、scipyなどでは利用できません。

scikits.sparse が CHOLMOD に基づいて同様の機能を提供することがわかりましたが、私の行列は密です。

numpy と互換性のある「cholupdate」の機能を備えた Python で使用できるコードはありますか?

ありがとう！

たとえば、整数を因数分解したい

41748850938502584251

これをブルートフォースで因数分解したい。この数の短い長さを考えると、これは可能であるはずです。

任意の長さの整数データ型をサポートする適切なプログラミング言語は何ですか?

よし、それで私は膨大な数を持っているf。この数字は、実際には 100 桁を少し超えています。因子はほぼ同じサイズであることがわかっています。

リソースと時間が限られている場合、どの言語とアルゴリズムを使用すればよいですか? 限られた時間にアルゴリズムをコーディングする時間の長さを含めています。

考え？

編集: 制限付きとは、可能な限り短い時間を意味します。

有界係数。

数 n が与えられたとき、k より小さい適切な因数があるかどうかを判断します。

これはco-Npの問題ですか？