« 「デスコロC #2」の高度じゃないコード | トップページ | 『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード »

2016年3月 8日 (火)

「平方コピペ数問題」の高度じゃないコード

「高度じゃないコード」シリーズその7は「平方コピペ数問題」です。

桁数が偶数の自然数であって、前半分と後ろ半分の桁の数字の並びが同じである数を「コピペ数」と定義します。

例えば、11、100100、123123、666666 はコピペ数です。
12、333、1001、124421、202020 はコピペ数ではありません。

また、整数の二乗で表される数(16、25、49 など)を平方数と呼びます。

コピペ数かつ平方数である、最も小さい数を求めて下さい。

(下記の問題ページよりコピペさせていただきました)


【平方コピペ数問題】

今日の午前中になって問題を初めて知りましたが、今朝の朝8時にブログ等での解答などの発表が解禁になったということであわてて考え、お昼過ぎに何とか解けて足跡を残しましたが、その時点で既に解答を公開している人もおられたようです。ですが、カンニングはしておりませんので念のため・・・。

数字の前半と後半が等しいということは、その数字は、11・101・1001・10001・・・という最上位と最下位の桁が1で後は0の数字(これ以降は101数字と書きます)の倍数です。101数字に掛ける数字はそれより1桁小さな数字でなくてはならないので、全体が自然数の二乗であるためには、101数字自身が2以上の自然数の二乗で割り切れなくてはなりません。

これを式として考えてみます。求める答えが3つの自然数 i, j, k を掛けたものの二乗だとします。
(i*j*k)2 = i*i * j*j * k*k = (i*i*j) * (j*k*k)
今回の問題の条件を満たすためには、この積となっている2つの括弧の中身のどちらかが101数字、もう片方がコピペされる数字でなければなりません。ここでは前者が101数字だとします。

さて、101数字は奇数なので2で割り切れません。また、全ての桁を足すと2となることから3でも割り切れません。1の桁が1なので5でも割り切れません。ということで、最初の候補は上の式の i = 7 の場合となり、i*i = 49 となります。

そこで、まずは、101数字で49で割り切れるものを探してみました。そうして、1000000000000000000001 = 7*7*20408163265306122449 を見つけました。j = 20408163265306122449 ということになりますが、このままだと1桁足りなくてコピペ数字にならないので、k*k を掛けて1桁増える最小値の k = 3 を適用させ 9倍します。ということで、(7*7*20408163265306122449)*(20408163265306122449*3*3) = 183673469387755102041183673469387755102041 という答えが出ました。

ところが、その答えを入力しても、Not Found となります。どうやら、条件を満たす数字でもっと小さいものがあるようです。そこで、i = 7 以外の、i = 11 や i = 13 や i = 17 や i = 19 などの各二乗で、上記より小さい101数字が割り切れないかを調べてみました。そしたら、i = 11 で 100000000001 = 11*11*826446281 となりました。上の例と比べてむっちゃ小さいですね。で、上と同じ方法で答えを出しました。(11*11*826446281)*(826446281*4*4) = 1322314049613223140496 となり、今度は、ちゃんと正解のページに飛ぶことができました。

色々とコードをいじりまくりながら正解にたどり着いたので、以下に示すソースは結果がわかった後で組んだものになります。また、上の i (コード中では x となります)の値については、万一、例外があった時に見つけることができるように、可能性がある奇数値を全て調べるようにしています。そのため、値を見つけても処理を終了せずに値を探し続けるように変更すると、最初に見つけた 183673469387755102041183673469387755102041 に行き着く(21.times のループの最後)前にタイムオーバーとなってしまいます。

|

« 「デスコロC #2」の高度じゃないコード | トップページ | 『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63317040

この記事へのトラックバック一覧です: 「平方コピペ数問題」の高度じゃないコード:

« 「デスコロC #2」の高度じゃないコード | トップページ | 『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード »