問題タブ [diophantine]

私は最近 Project Euler にはまっているので、次はこれをやろうとしています! 私はそれについていくつかの分析を開始し、すでに問題を大幅に削減しています。これが私の仕事です：

A = pqr および

1/A = 1/p + 1/q + 1/r だから pqr/A = pq + pr + qr

そして、最初の方程式のために：

pq+pr+qr = 1

p、q、r の 2 つだけが負でなければならないため、式を次のように単純化できます。

ab = ac+bc+1 の abc

c について解くと、次のようになります。

ab-1 = (a+b)c

c = (ab-1)/(a+b)

---

これは、次の a と b を見つける必要があることを意味します。

ab = 1 (mod a+b)

そして、これらの a と b の A 値は次のとおりです。

A = abc = ab(ab-1)/(a+b)

それが多くの数学である場合は申し訳ありません！しかし、ここで取り扱わなければならないのは、1 つの条件と 2 つの方程式だけです。ab = 1（mod a + b）でab（ab-1）/（a + b）として記述された150,000番目に小さい整数を見つける必要があるため、理想的には、Aができるだけ小さく。

簡単にするために、a < b と仮定し、gcd(a, b) = 1 であることにも気付きました。

私の最初の実装は単純明快で、150,000 の解を十分に速く見つけることさえできます。ただし、150,000 個の最小解を見つけるには時間がかかりすぎます。とにかくコードは次のとおりです。

私の次の考えは、Stern-Brocot ツリーを使用することでしたが、解決策を見つけるには遅すぎます。私の最終的なアルゴリズムは、中国の剰余定理を使用して、a+b の異なる値が解をもたらすかどうかを確認することでした。そのコードは複雑で、高速ではありますが、十分に高速ではありません...

だから私は絶対にアイデアがありません！誰でもアイデアはありますか？

次にプロジェクトオイラーの問題233に取り組むことにしましたが、いくつかの大きな問題があります。私はいくつかの分析を行い、かなり良い進歩を遂げましたが、今は行き詰まっています。これが私の仕事です：

補題1：円は4つのコーナーポイントを通過するため、任意のnに対して少なくとも4つの解があります。しかし、円周上の各ポイントには、反射で見つかった他の7つのポイントがあります。したがって、常に8k+4の格子点があります。

補題2：円は半径（√2）nと中心（n / 2、n / 2）を持っているので、その方程式は（xn / 2）^ 2 +（yn / 2）^ 2 =[n/√​​2]^です。 2.2。これは、x ^ 2 + y ^ 2 = n（x + y）に減少します。

補題3：x ^ 2 + y ^ 2 = n（x + y）の解が（x、y、z）と書かれている場合、別の解は（kx、ky、kz）です。その証拠は次のとおりです。

これは私がその考えでしたのと同じくらいでした-私はそこから行くところをどこにも見ることができませんでしたが、それはよく役立つかもしれないので含まれています。

次の考えは、円の中心を動かすことでした。整数全体を任意の次元で動かす同じ数の解があります。したがって、n / 2が整数の場合、n = 2k、x ^ 2 + y ^ 2 = 2 * k^2となります。また、この方程式には、方程式x ^ 2 + y ^ 2 = k ^ 2と同じくらい多くの解があることがわかります（Sloane A046109を参照）。

これにより、 A046080を介して任意のnの解の数を計算する簡単な方法も得られます。4k+1の形式のnの素数の累乗がf[0]... f [m]の場合、解の数は4 * product（2f [i] +1 | i in [0. .. .m]）。

これにより、逆方向に作業することができました。4.product（2f [i] +1 | i in [0 ... m]）= 420なので、product（2f [i] +1 | i in [0 ... m] ）= 105 = 3 * 5*7。私はこのプログラムを思いつくことができました。これは、420個の円格子点を持つ2kおよび10^11未満の形式ですべてのnの合計を見つけると思います。答え（私は願っています！）は257199853438240692です。

これがCプログラムです：

420個の円格子点を持ち2k+1の形式のnの値を追加する必要があります！しかし、それはn = 2kの場合よりも難しいようで、私はそれに対する方法を見つけることができません。方法がかなり複雑なので、nでも私の答えが正しいかどうかも少しわかりません...誰かがそれを確認できますか？異なるnを異なる方法で処理することなく、きちんとした方法はありますか？

私はすべてアイデアがありません！

ジョン・フェミネラが示唆しているように、N = 2kのときはできるので、私は主にN = 2k+1をどのように扱うかに興味があります。

線形ディオファントス不等式のシステムを解くための適度に高速なアルゴリズムはありますか？

これで、条件 x^3+y^3=1+z^3 & x を満たす xyz 値の 23 セットの検索が完了しました。

しかし、私が持っているコードは非常に非効率的です。誰かがこれを修正するのを手伝ってくれますか?

だから私は平面上の線を指定する一連の有界ディオファントス方程式を持っています。これらの方程式の2つの共通部分を数学でプロットして、それらがどのように見えるかを確認したいと思います。

これまでのところ、私は次のようなものを持っています：

Solve [0 <x --y <3 && -1 <2 x --y <2、{x、y}、整数]

これは次のような構造を返します：

{{x-> -2、y-> -4}、{x-> -1、y-> -3}、{x-> -1、y-> -2}、{x-> 0、y -> -1}}

しかし、どうすればこれを数学でプロットして、結果の形状を見ることができますか？できれば、プロットですべての「点」を1x1の正方形と見なしたいと思います。

また、そのようなことをするためのより良い方法があるのだろうかと思います。ありがとう。

私の研究では、線形ディオファントス方程式のシステムに直面しています。

このトピックに関するいくつかの研究論文を見つけましたが、自分でソルバーを作成する前に、そのようなシステムを解く (軽量) C++ 数学ライブラリを知っているかどうか知りたいです。

私は数学的にもプログラム的にもこれらの問題に慣れていません。次の問題を解決できる C++ ライブラリを使用することを誰かが提案できれば、本当に感謝しています。

与えられた定数:

{x_1, ..., x_n}, {y_1, ..., y_n}, {z_1, ..., z_n}, C, & variables {q_1, ..., q_n}

最大化:sum(i = 1..n} q_i*x_i

対象:C - sum(i = 1..n){ sum(j = 1..q_i) [y_i + (j-1)*z_i ] } >= 0 AND q_i >= 0

すべての定数はゼロより大きい整数です。q_i'sも整数です。

だから私は解決しようとしています{q_1, ..., q_n}

与えられたHについて、次の方程式のすべての解を生成しようとしています。

H = 4の場合：

私の問題では、（他の方程式とは独立して）解くべき方程式が常に4つあります。合計2^（H-1）のソリューションがあります。前のものについては、ここに解決策があります：

これが問題を解決するRアルゴリズムです。

ただし、このアルゴリズムは必要以上の計算を行います。もっと速く行くことは可能だと確信しています。つまり、合計が>Hである順列を生成しないことを意味します

与えられたHのためのより良いアルゴリズムのアイデアはありますか？

私はPythonの初心者で、MIT 6.00を試してみましたが、提供されているページは割り当てページです。

私はディオファントス方程式の解を見つけなければならない課題2にいますが、数学はそれほど得意ではないので、できる限りそれが何をするのかを理解し、その解を考えようとしました。

これが私が得たものです：

割り当てには、の解決策があると記載されています50, 51, 52, 53, 54, and 55が、残念ながら、スクリプトはの解決策しか取得しません50, 53 and 55。

誰かが私のコードの何が悪いのかを説明してくれたら、またはディオファントス方程式をまったく理解していない場合は、割り当てを取得できないので、それが何であるか、そしてその解決策を見つける方法を教えてください。私の頭の中に説明。

ありがとう。

基本的にA^5 + B ^ 5 + C ^ 5 + D ^ 5 + E ^ 5 = F^5である5-1の5次ディオファントス方程式を解くコードを書くプログラムがあります。ここで0<A< = B <= C <= D <= E <= F <=N。これを実装する方法は、指定されたN値の値を事前に計算してから、配列に格納することです。したがって、たとえばNが100の場合、1から100までの値が配列に格納されます。

次に、最初のグループA ^ 5 + B ^ 5 + C^5と2番目のグループF^5-（D ^ 5 + E ^ 5）の値を計算し、最初のグループの値を比較します。それらが一致するかどうかを確認するために秒に。一致する場合、解決策が見つかります。

私の質問は、1からNまでの値の配列を使用して、2つのグループのすべての可能な値をどのように計算するのかということです。私は考えを理解していますが、それをコーディングすると、どのようにアプローチするかわかりません。誰かが私にいくつかのヒントを教えてもらえますか？私はそれをコーディングする方法についての解決策を求めているのではなく、コーディングプロセスをもう少しよく理解するのに役立ついくつかのヒント/ヒントが欲しいだけです。ありがとう！