わさっきhb

大学（教育研究）とか ，親馬鹿とか，和歌山とか，とか，とか．

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

math

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

　以下の条件を満たす正整数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個でした．