毎日のコーディング問題: 三角数と大約数

解決すべき別の問題がある皆さん、ようこそ!今日は三角数とその約数、特に巨大な数について話します。

自然界の三角数を表現した私の素晴らしい芸術的表現を賞賛することができますが、いつもの免責事項を述べておきます。

1. この問題は素晴らしいウェブサイトによって提供されていますプロジェクトオイラー.net 、購読できますここ！解決すべき数学とコーディングの問題は 800 を超え、それらに関する議論の膨大なアーカイブがあります。文字通り、頭をかき回して新しいことを学ぶのに最適なツールです。ぜひチェックして、あなたの課題も解決してみてください!

   
   

2. 私は専門プログラマーではありません。ただ、この種のことについて書くのが好きで、自分のショットを共有するのが好きな人です。これが最適な解決策ではないことは確かです。そのため、より良い解決策や、それを最適化する方法についてのアイデアがある場合は、共有していただければ大歓迎です。

話はこれくらいにして、今日の問題が何を提供するかを見てみましょう。

三角数列は自然数を加算することで生成されます。したがって、7 番目の三角形の数は 1+2+3+4+5+6+7=28 となります。最初の 10 項は次のようになります:1、3、6、10、15、21、28、36、45、55、…

最初の 7 つの三角形の数の因数をリストしてみましょう。

28 が、約数が 5 を超える最初の三角形の数であることがわかります。

約数が 500 を超える最初の三角形の数値はいくらですか?

問題は非常に単純です。約数が 500 を超える最初の三角数は何かを理解するように求められます。まず最初に、三角数とは何か、約数とは何かをよく見てみましょう。

三角数字

三角数は、特定の数までのすべての自然数の合計によって形成される数の特定のサブセットです。いつでも三角形として配置できるため、三角形と呼ばれます。ここではいくつかの例を示します。

上の画像では、3番目、4番目、5番目の三角数字です。したがって、たとえば、3 番目の数字は 1+2+3 = 6 として形成され、4 番目の数字は 1+2+3+4 = 10 として形成されます。一般的に言えば、nᵗʰ 三角数 Tₙ は次と等しいです。

もちろん、これは数学で最も有名な級数の 1 つであり、ガウスによっても提示され、連続する整数の合計は以下に等しいと述べました。

したがって、基本的に、たとえば 3 番目の三角数を計算したい場合は、単純に 3*4/2 = 6 を計算します。これは、解を書き始めるときに非常に役立ちます。

ディバイザーズ

数値nの約数(または因数) の定義を与えるのは非常に簡単です。数値jに別の整数kを乗算して、再びn を求めることができます。たとえば、3 と 6 を掛けて再び 18 を得ることができるため、3 は 18 の約数です。

ただし、5 と掛け算して 18 になる数k は存在しないため、5 は 18 の約数ではありません。

この定義により、重要な特性も得られます。j をkに乗算してnを取得できるため、 j が n の約数である場合、 jを乗算してnを取得できるため、 kもn の約数です。

このようにして、数値n には常に少なくとも 2 つの約数jとkがあることを確認できます(実際、 j は常に 1 であり、 kはnである可能性があります)。

また、別の言い方をすると、 n / jの余りが 0 に等しい場合、数値jは数値nの約数になります。したがって、たとえば、18/3 = 6 となり、余りは 0 になります。

n % j = 0の場合、 j はnの約数であるというモジュラー演算を使用して、この概念をより適切に形式化できます。つまり、この 2 番目のプロパティを取得します。

私たちが興味を持っている 3 番目で最後の特性は、 n自体ではなく、n/2より大きい数nの約数は存在できないということです。これは非常に簡単に理解できます。最初の特性から、因子が 1、…、n の範囲で何らかの形で「リンク」されていることがわかります。

これも、 j \ n の場合、 j * k = n であるためです。したがって、 k\n も同様です。もう一度 18 を例として取り上げ、その約数を見つけて、この特性を反映するように色を付けてみましょう。

したがって、たとえば、 j = 3、k = 6 の場合、およびその逆の場合、 j = 6、k = 3 の場合、これは、1 以外に使用できる最小のj は2 であることを意味し、これにより最大のkが得られます。可能、 n/2 (この場合は 9) 。これは機能します:

• 偶数の場合、最大の係数はn の半分に正確に等しくなります。

• 奇数の場合: nを 2 で割ることができない場合 (奇数であると有理数が得られるため)。これは、 j > 2 のみを使用できることを意味し、常にk < n/2 の結果が得られます。

  
  

最後に、 jとk が等しくなるケースは 1 つだけあり、それはnが平方数の場合です。たとえば、 n = 36 の場合、考えられる因数j = 6 は別の因数k = 6を生成します。このケースについては、後のコード部分で詳しく説明します。

もちろん、これらの概念は非常に些細なものですが、ソリューションでは非常に重要になります。

コード

コードはGoで書かれます。これは、非常に高速な言語でありながら、優れた可読性を維持しているためです。解を 2 つに分割します。まず、数値の約数を求める関数を作成し、次にそれを三角数に適用します。

まず関数を見てみましょう。

整数nを受け入れ、約数を含む整数の配列out返す関数を作成します。その後、自明な因数、つまり 1 とn自体をoutします。

次に、 j 2 からn/2までループし始めます (2 番目のプロパティから。n n偶数の場合、 k = n/2がj = 2によって約数に加算されるため、 n/2 /2 自体には興味がないことにも注意してください)。 j = 2反復: これが、 j≤ n/ j<n/2 j≤ n/2で停止する理由です)。

このようにして、 nの前半でのみ約数をチェックできるため、プロセスがかなり高速化されます。

各ループで 3 つのことをチェックします。

• 3 番目の if ステートメントは、実際にはn%j==0かどうか、つまり 0 ≡ n (mod j) かどうかをチェックします。そうであれば、因子が見つかったので、リストにjを追加します。 n/jを計算して次のjに進むことで、対応するkをリストに追加することもできます。

• 2 番目の if ステートメントは、 nが正方形であるかどうか、つまりjがnの根であるかどうかをチェックします。その場合、重複を避けるために、除数j 1 つだけoutに追加され、アルゴリズムは次に進みます。

  
  

  n = 36と仮定します。この小さなブロックが欠落している場合、3 番目の if ステートメントがトリガーされ、 outがj = 6およびk = n/j = 36/6 = 6を受け取ることになり、重複が作成されます。

• 最初の if ステートメントは最も複雑です。その目的は、 jkペアの繰り返しが始まっているかどうかを確認することです。そうであれば、因子はすべて in outにすでに存在するため、ループを即座に中断できます。

  
  

この 3 番目の点については、特にout[len(out)-1] == jまたはout[len(out)-2] == j 2 つのケースをチェックする必要があります。

最初のケースは古典的なケースです。たとえば、数値 T₇ = 28 を考えます。

j = 7の場合、最後に挿入された値と等しくなります。したがって、ループを断ち切ることができます。

2 番目のケースは、正方形n見つかった場合にのみ発生します。たとえば、36 を再度取り上げます。

j = 9の場合、これはnの平方根の前に追加される最後の値と等しくなります。この値は 1 回だけ現れます。したがって、この時点でループを解除できます。

最後に、単純に約数return outができます。

結果の適用

関数が完成したので、それをすべての三角数に適用できます。三角数のジェネレーターとして機能するカウンターcを作成します。ガウス方程式を使用して関連する三角数tnを計算し、その約数がいくつあるかを確認します。

500 を超える場合は、そのtnを結果として返します。

しかし…落とし穴があります！

ProjectEuler.net は本当に素晴らしいプロジェクトです。数学のなぞなぞや問題を提示することに加えて、その主な焦点は数学について学び、考え、推論するためのツールを提供することです。

そして、私はそれが気に入っています。彼らは非常に熱心なので、問題の結果やガイドを公開することは実際には禁止されています (これは最初の 100 の問題の 1 つなので、許可されているのは理解しています)。

このことを考えると、単にコピペで解決策を提示して実績を取得するのは公平ではないと思います。このため、私は実際の解決策を提供するつもりはありません。自分で試してみて、私のアルゴリズムよりも優れたアルゴリズムを考え出すようにしてください (アルゴリズムはたくさんあります)。ごめんなさい、みんな！ 😅

時間計算量

これはかなりひどいショットだと思うので、もっと良い解決策がたくさんあると私は確信しています。

FindDivisor関数は線形時間で実行されます。これは、インスタンスnのサイズに依存し、最大でもn/2ループも実行されるためです。それは O(n) であると考えることができます。

ただし、最初に各三角数を計算する必要があり、これにも O(tn) 時間がかかります。tn は結果 (実際に最後に計算したもの) です。これを考慮すると、アルゴリズム全体の時間計算量はおよそ O(tn*n) になるはずです。

tnが引数または関数となり、その中で最大n/2個のループを実行するため、時間計算量は O(tn*tn/2) = O(tn²/2) = O(tn²) として書き換えることができます。したがって、二次時間の解になりますが、残念ながら!

しかし、アルゴリズムがその程度の複雑さであるにもかかわらず、それにもかかわらず、かなり高速に実行されることに驚きました。私のマシン (AMD Ryzen 5、平均 2700 MHz) で結果を出すには、322.564227 ミリ秒かかりました。

ただし、約数 1000 を超える最初の三角数を見つけようとすると 3.827144472 秒かかったので、時間の消費が急速に増加していることがはっきりとわかります。

結論

ついに成功しました！この記事を楽しんでいただければ幸いです。また、そこから何か興味深いものを受け取っていただければ幸いです。もしそうなら、拍手を 1 ～ 2 回残して、このトピックに興味を持つ可能性のある誰かと記事を共有してください。

ProjectEuler の素晴らしい仕事に改めて感謝の意を表します。ぜひ行って、彼らが提供できるものをチェックしてみてください。きっととても面白いと思うでしょう！

そしていつものように、読んでいただきありがとうございます。

ニコラ