わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

2乗では変わるけど3乗で帰ってくるやつ

 いきなりですが問題です.

 以下の条件を満たす正整数nを,小さい数から順に求めなさい.dはnの桁数とする.

  • n^2の下d桁は,nと異なるが,n^3の下d桁は,nと等しい.

 元ネタです.


 総当たりで計算する,ワンライナーを作成しました.桁数を変えて求められるようにしています.2~4桁について,手元のシェルで実行してみました.

$ ruby -e 'def q(a,b,m)a%m==b%m end;def r(m)(m/10).upto(m-1){|i|i2=i*i;i3=i2*i;puts"%d→%d→%d"%[i,i2,i3]if !q(i,i2,m)&&q(i,i3,m)}end;r(100);r(1000);r(10000)'

 実行結果の前にコードの解説です.冒頭の問題では「正整数n」と「桁数d」と表記しましたが,これらから処理をはじめると,「下d桁」の計算が少し複雑になるので,d桁の全ての値をとるための変数mを用意し,関数rの引数としました.この値は,2桁なら100,3桁なら1000,とします.こうすることで,d桁の最小値はm/10,最大値はm-1となり(m=1000のときそれぞれ100と999です),RubyのInteger#uptoメソッドで1ずつとって処理していきます.また「下d桁」は,関数qの中の「%m」演算が対応します.
 実行結果です.

24→576→13824
49→2401→117649
51→2601→132651
75→5625→421875
99→9801→970299
125→15625→1953125
249→62001→15438249
251→63001→15813251
375→140625→52734375
499→249001→124251499
501→251001→125751501
624→389376→242970624
749→561001→420189749
751→564001→423564751
875→765625→669921875
999→998001→997002999
1249→1560001→1948441249
3751→14070001→52776573751
4375→19140625→83740234375
4999→24990001→124925014999
5001→25010001→125075015001
5625→31640625→177978515625
6249→39050001→244023456249
8751→76580001→670151588751
9375→87890625→823974609375
9999→99980001→999700029999

 2桁について,ツイートと同じ個数そして計算結果です.3桁で該当する個数は11個,4桁で10個と分かりました.
 5~7桁も,試してみます.リプライのツイートでは「4桁以降は10個」と書きましたが「各桁」が抜けていますし,「6桁の場合には11個」となっていることも,見落としていました.

$ ruby -e 'def q(a,b,m)a%m==b%m end;def r(m)(m/10).upto(m-1){|i|i2=i*i;i3=i2*i;puts"%d→%d→%d"%[i,i2,i3]if !q(i,i2,m)&&q(i,i3,m)}end;5.upto(7){|t|r(10**t)}'
18751→351600001→6592851618751
31249→976500001→30514648531249
40625→1650390625→67047119140625
49999→2499900001→124992500149999
50001→2500100001→125007500150001
59375→3525390625→209320068359375
68751→4726700001→324965351768751
81249→6601400001→536357148681249
90624→8212709376→744268574490624
99999→9999800001→999970000299999
109375→11962890625→1308441162109375
218751→47852000001→10467672852218751
281249→79101000001→22247077149281249
390625→152587890625→59604644775390625
499999→249999000001→124999250001499999
500001→250001000001→125000750001500001
609375→371337890625→226284027099609375
718751→516603000001→371308922853718751
781249→610350000001→476835327150781249
890624→793211109376→706452851076890624
999999→999998000001→999997000002999999
2109375→4449462890625→9385585784912109375
2890624→8355707109376→24153207507332890624
4218751→17797860000001→75084739672864218751
4999999→24999990000001→124999925000014999999
5000001→25000010000001→125000075000015000001
5781249→33422840000001→193225760327165781249
7109375→50543212890625→359330654144287109375
7890625→62261962890625→491285800933837890625
9218751→84985370000001→783458964672879218751
9999999→99999980000001→999999700000029999999

 nが1桁のときも求めることができ,4(→16→64)と9(→81→729)です.
 ここまでを表にまとめます.冒頭の問題について,9999999までに限定したときの答えとなります.

桁数
1 4,9 (2個)
2 24,49,51,75,99 (5個)
3 125,249,251,375,499,501,624,749,751,875,999 (11個)
4 1249,3751,4375,4999,5001,5625,6249,8751,9375,9999 (10個)
5 18751,31249,40625,49999,50001,59375,68751,81249,90624,99999 (10個)
6 109375,218751,281249,390625,499999,500001,609375,718751,781249,890624,999999 (11個)
7 2109375,2890624,4218751,4999999,5000001,5781249,7109375,7890625,9218751,9999999 (10個)

 これ以上大きな値も計算できますが,1桁増えるごとに,ループ回数が10倍になる点には,気をつけないといけません.規則性*1も見えてきたので,数学的に(紙と鉛筆で)一般化できそうにも思います.
 さて,ワンライナーの第三者検証や拡張を容易にするために,コード実行ができるWebサービスを使うことにしました.codinggroundにアクセスしてRubyを選択し,「def」から「r(10000)」までをコピーして左側に貼り付けて,Executeのボタンを押すと,手元のシェルと同じ結果になりました.日本語文字が入っていても,大丈夫です.
 次にShareのボタンを押すと,短縮URLを得ることができましたが,ツイートに入れる前に,他のブラウザで動作確認すると,実行できずにエラーが表示されました.プログラムコードには「"」や「&」が入っています.
 エスケープされてしまった「"」「&」(それと日本語文字)を,Rubyスクリプトに入れないように書き換えたのが,次のコードです.

def q(a,b,m)(a%m==b%m)?1:0 end;def r(m)(m/10).upto(m-1){|i|i2=i*i;i3=i2*i;puts %q(%d,%d,%d)%[i,i2,i3]if q(i,i3,m)-q(i,i2,m)==1}end;r(100);r(1000);r(10000)

 関数qは,true/falseではなく1/0を返すように変更することで,「n^2の下d桁は,nと異なるが,n^3の下d桁は,nと等しい.」の条件式を「q(i,i3,m)-q(i,i2,m)==1」に書き換えました.「"..."」は,%記法のうち%qを使用しました.

*1:3桁と6桁がともに11個なら,9桁も11個になるのかなと思って,値を増やして試すと,9桁については10個でした.かわりに8桁が11個でした.