問題タブ [number-theory]

数学/アルゴリズムの問​​題について考えていたので、解決方法についてご意見をいただければ幸いです。

数字 (たとえば 479) がある場合、その数字またはそれらの組み合わせを元の数字と一致する数式に再結合したいと考えています。すべての数字は元の順序で使用する必要がありますが、数字に組み合わせることができます (したがって、479 は 4、7、9、47、79 を許可します)。ただし、各数字は一度しか使用できないため、4x47x9 のようなものは使用できません。現在、数字の 4 は 2 回使用されています。

今、私がそれをどのように考えているかを示すための例です。実際に機能する良い例を思い付くことができなかったため、この例は数学的に正しくありませんが、入力と期待される出力を示しています。

入力例:29485235

出力例:2x9+48/523^5

私が言ったように、私の例は合計されません(2x9+48/523^5 は 29485235 にはなりません)。計算すると元の数が得られる元の順序。

使用される数学の種類については、括弧 () と Add/Sub/Mul/Div/Pow/Sqrt と言えます。

これを行う方法についてのアイデアはありますか？私の考えは、数字をランダムに切り刻み、一致する結果を期待して計算を行うことで、単純にブルートフォースすることでした。でももっと良い方法があるはずですよね？

編集：元の順序ではない方が簡単な場合、または上記の「条件」のいくつかを無視してこれを解決するアイデアがある場合でも、そのような問題を解決する方法を理解することは非常に役立ちます.

3n1 + 4n2 + 5n3 = 456のような方程式の解があるかどうかを判断する方法を探してい ます。ここで、n1、n2、n3は正の整数です。

またはより一般的に：方程式k1n1 + k2n2 + k3n3 ... = mを解くゼロまたは正の整数n1、n2、n3 ...があります。ここで、k1、k2、k3 ...およびmは既知の正の整数です。

解決策を見つける必要はありません。解決策が存在するかどうかを判断するためだけです。

編集：

このアルゴリズムの実用化について：

通信ライブラリでは、メッセージを処理する前に、特定のメッセージがそのサイズに応じて有効かどうかを判断したいと思います。例：メッセージに0個以上の3バイト要素、0個以上の4バイト要素、および0個以上の5バイト要素が含まれていることを知っています。456バイトのメッセージを受信しましたが、内容をさらに調べる前に、その有効性を確認したいと思います。もちろん、メッセージのヘッダーには各タイプの要素の数が含まれていますが、.のようなものを渡すことによって、通信ライブラリレベルで最初の検査を行いたいと思いpair<MsgType,vector<3,4,5>>ます。

1 つの方法は、 gcdを計算し、それが 1 かどうかを確認することです。

もっと速い方法はありますか？

私はシリーズを持っています

和を求めたい。結果に分母があり、存在しない可能性のある剰余逆数を見つける必要があるため、幾何学的累進 (GP) 式を適用できません (分母と m が互いに素でない場合)。

そこで私は、これらの累乗が k よりもはるかに短い長さのサイクルを作るという仮定を立てて、別のアルゴリズムを作成しました (これは剰余方程式であり、2,7,9,1,2,7,9 のようなものが得られるためです)。 1....) そして、そのサイクルが上記のシリーズで繰り返されます。したがって、0 から k まで反復する代わりに、サイクル内の数値の合計を見つけてから、上記の系列のサイクル数を計算して乗算します。そのため、最初にこの数を見つけi^m (mod m)てから、最初の要素に再び到達するまで、各ステップでモジュロを取りながら何度も乗算しました。

しかし、実際にアルゴリズムをコーディングすると、i の値によっては、非常に大きなサイズのサイクルが得られました。そのため、終了するまでに長い時間がかかったため、私の仮定は正しくありません。

では、私たちが見つけることができる他のパターンはありますか? (基本的に、k を反復処理したくありません。) 合計を求める効率的なアルゴリズムのアイデアを教えてください。

プログラミング チャレンジの一環として、特定の範囲内で完全数を見つけるプログラムを C# でコーディングしました。ただし、10000 以上の完全数を計算すると非常に遅いことに気付きました。完全数を見つけるための最適化の方法はありますか? 私のコードは次のとおりです。

いくつかの非負の数があります。最大公約数のペアを見つけたいと思います。実際、この最大値はペアよりも重要です。たとえば、次の場合：

2 4 5 15

gcd（2,4）= 2

gcd（2,5）= 1

gcd（2,15）= 1

gcd（4,5）= 1

gcd（4,15）= 1

gcd（5,15）= 5

答えは5です。

私はHaskellでいくつかの古典的な問題を解決して機能スキルを開発していますが、この「プログラミング実践」サイトで提案されている最適化を実装するのに問題があります。

この問題には3つの解決策があり、3番目の解決策は2番目の解決策に比べて遅すぎます。誰かが私のコードの改善を提案できますか？

私の実装は次のとおりです。

古いint x = 54897数字のインデックス (0 ベース) と、その数字の新しい値があるとします。新しい値を取得する最速の方法は何ですか?

例

編集：最速とは、間違いなくより高速なパフォーマンスを意味します。文字列処理はありません。

すべて友好的なペア (n、m)、n < m、2 <= n <= 6500 万であると私が信じているものを見つけるために使用したコードを参照してください。私のコード: http://tutoree7.pastebin.com/wKvMAWpT。見つかったペア: http://tutoree7.pastebin.com/dpEc0RbZ。

私のラップトップでは、100 万件の追加ごとに 24 分かかっていることがわかりました。事前に除外できる n の数がかなりあることを願っています。これは近いですが、葉巻はありません。「5」で終わらない奇数の n. これまでのところ、反例のペアは 1 つしかありませんが、多すぎます: (34765731、36939357)。フィルターとして、すべての n の 40% を除外します。

必ずしもそれらを実装するための Python コードではなく、いくつかのアイデアを期待しています。

私は計算したい：

a ^{b c d . . .} mod m

この数値は大きすぎますが、 a 、 b 、 c 、 ... および m は単純な 32 ビット int に収まるため、効率的な方法をご存知ですか。

何か案は？

警告:この質問は、 ^b mod mを見つけることとは異なります。

^{また、 a b cは (a b} ) ^cと同じではないことに注意してください。^{後者は a bc}と同じです。べき乗は右結合です。