次の数は、手計算で素因数分解できるものなのか？

N0=110001011
N1=11111111
N2=11112121
N3=133113133
N4=14141441
N5=15151515115
N6=11611661
N7=17171111
N8=1811811818
N9=191111911


（コメント）　以下のような結果になるのだが、とても手計算で出来る気がしない。

N0=110001011=311*577*613
N1=11111111=11*73*101*137
N2=11112121=101*269*409
N3=133113133=233*647*883
N4=14141441=107*149*887
N5=15151515115=5*11*17*107*269*563
N6=11611661=109*307*347
N7=17171111=101*197*863
N8=1811811818=2*103*193*199*229
N9=191111911=433*449*983


　DD++ さんからのコメントです。（令和４年６月２１日付け）

　とりあえず瞬殺できるものから。

N1 = 11111111 = 1111*10001 = 11*101*10001

さて、GAI さんがこれで終わるだけの面白みのない問題を出すとは思えないので、10001 は
合成数、それもそこそこ大きな素数の積だと信じることにします。

　10001 を 2 つの自然数の積で書くと考えると、その相乗平均は √10001 で 100 よりわず
かに大きい数です。

　また、10001 は 4 で割ると 1 余る数なので、これが 2 つの数の積であるならば、それは 4
で割ると 1 余る数同士の積か、あるいは 4 で割ると 3 余る数同士の積。

　つまり、その 2 つの数の和は 4 で割ると 2 余ります。

　これら 2 つの情報に、どちらもそこそこ大きな素因数という情報を追加すると、2 数の相
加平均は 100 より少し大きい奇数であるとわかります。

　ということで、これを 101+2k と書くことにします。

　すると 2 つの数を解に持つ二次方程式は、x^2 - 2(101+2k)x + 10001 = 0　となり、その判
別式は、

　D/4 = (101+2k)^2 - 10001 = 4k^2 + 404k + 200 = 4(k^2+101k+50)

　あとはこの括弧内が平方数になるような k の値を小さい順に試しながら探せばよく、

　k=1 のとき 152 は平方数ではない

　k=2 のとき 256 は平方数

とすぐにみつかります。

　2 数の相加平均が 105 ということは和は 210 で、積が 10001 なのですから、差は、

√(210^2-4*10001) = √4096 = 64

つまり、2 数は 105 + 32 = 137 と 105 - 32 = 73

　以上より、　N1 = 11111111 = 11*73*101*137


　同じやり方でもう 1 つ。

N2 = 11112121 = 11111111+1010

と考えると、N1 の結果と合わせてこれが 101 の倍数であることは明らかで、

N2 = 11112121 = 11*73*101*137 + 101*10 = 101*110011 + 101*10 = 101*110021

　開平法を使って頑張れば、 √110021≒331.7 で、ということは 2 数の相加平均は 331 よ
り少し大きい奇数なので、331+2k とおいて、同様に進めて、

　D/4 = (331+2k)^2 - 110021 = 4(k^2+331k-115)

　この括弧内が平方数になる k を探します。

　k=1 のとき 217 は平方数ではない

　k=2 のとき 551 は平方数ではない

　k=3 のとき 887 は平方数ではない

　k=4 のとき 1225 は平方数

　2 数の相加平均が 339 で、和が 678、積が 110021 なので、差は、

√(678^2-4*110021) = √19600 = 140

つまり 2 数は 339 + 70 = 409 と 339 - 70 = 269

　以上より、　N2 = 11112121 = 101*269*409

　一応 19 以下の素数で割ってみて、これが全部素数と確認して終了。


＃N7 もいけるかと思いましたが、170011 の処理がこの方法では無理そうですね。2 つの数
　がおそらく倍以上差があるようで、この方法ではちょっと厳しい。さあどうしようかな。


（コメント）　求め方が芸術的ですね！


　らすかるさんからのコメントです。（令和４年６月２２日付け）

　170011 の処理について、

　f(k)=(412+2k)^2-170011　とすると、　f(k)=4k^2+1648k-267

　k が偶数のとき、　f(k)≡5　(mod 8)　となるが、mod 8 での平方剰余は、0、1、4 だけなの
で、平方数にならない。

　k=2m-1 とすると、　f(k)=g(m)=16m^2+3280m-1911

　m≡0、1、2、3、4、5、6、7、8 に対して、　g(m)≡6、8、6、0、8、3、3、8、0　(mod 9)　だが
mod 9 での平方剰余は、0、1、4、7　だけなので、平方数になる可能性があるのは、

　m≡3、8　(mod 9)　のときのみ。

　m≡3　(mod 9)　のとき、m=9t-6　とおくと、　g(m)=h(t)=1296t^2+27792t-21015

　h(1)=8073、h(2)=39753 は、一の位が 3 なので、平方数ではない。

　h(3)=74025　が平方数ならば、　27^2=729、28^2=784　から、　h(3)=275^2　でなければな
らないが、275^2=75625　なので、h(3) は平方数ではない。

　h(4)=110889　が平方数ならば、　33^2=1089、34^2=1156　から、

　　　h(4)=333^2 または 337^2

でなければならないが、333^2=110889 なので、h(4) は平方数。
（たまたま見つかったのでm≡8(mod9)は考える必要がなくなった）

　t=4→m=30→k=59→412+2k=530　なので、　170011=530^2-333^2　とわかる。以下略。


（コメント）　上記より、　N7 = 17171111 = 101*170011 = 101*863*197


　ＧＡＩ さんからのコメントです。（令和４年６月２３日付け）

　27000001 の素因数分解で、　27000001 = 27000000 + 1 = 300^3 + 1^3

ここで、　a^3+b^3=(a+b)^3-3*a*b*(a+b)=(a+b)*((a+b)^2-3*a*b)　から、3*a*b の部分が平
方数となる場合で、この例でも

300^3 + 1^3 = 301*(301^2-3*300*1) = 301*(301^2-30^2) = 301*(271)*(331) = 7*43*271*331

　この様な3乗の和（N=a^3+b^3 しかも 3*a*b が平方数）で、上記のルートで素因数分解で
きるタイプの数Nを10^7台に限って調査してみました。(全部で89個)
(2*10^7台では27000001も当然現れる。)

N [a , b]=最終の因数分解形

　なお、大学入試に手計算で、次の数を素因数分解させるものが出題されていました。

　N=12345654321


（コメント）　福岡大学医学部（２０１９）の入試問題ですね！

　電卓で遊ばれた方は多分　N = 12345654321 = 111111^2　とすぐ気付き、さらに、

　3^2・7^2・11^2・13^2・37^2　と素因数分解されるんでしょう。（→　参考：「連綿と続く１」）

　2 〜 37 までの素数をくまなく調べれば、答えはすぐ見つかりますね！

（→　参考：「倍数の判定」）

実際に、111111 は 2 では割れない。1+1+1+1+1+1=6 なので、3 で割り切れる。よって、

　111111=3*37037 と分解できる。37037 は5 では割れない。37-037=0 なので、37037 は

7 で割り切れる。よって、37037=7*5291 と分解できる。5-2+9-1=11 なので、5291 は 11 で

割り切れる。よって、5291=11*481 と分解できる。481=1+48*10 と考えて、4*1+48=52 は 13

で割り切れる。よって、481=13*37 と分解できる。37 は素数であるので、以上から、

　111111=3*7*11*13*37 と分解できる。



　　以下、工事中！