Bash
ProjectEuler
数学
@tea63

Project Euler Q55 【Lychrel数】

BashProjectEuler数学

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

$47$とその反転を足し合わせると, $47 + 74 = 121$となり, 回文数になる.

全ての数が素早く回文数になるわけではない. $349$を考えよう,

  1. $349 + 943 = 1292$
  2. $1292 + 2921 = 4213$
  3. $4213 + 3124 = 7337$

$349$は, $3$回の操作を経て回文数になる.

まだ証明はされていないが, $196$のようないくつかの数字は回文数にならないと考えられている. 反転したものを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数で無いと証明されていない数はLychrel数だと仮定する.

更に, $10000$未満の数については，常に以下のどちらか一方が成り立つと仮定してよい.

  1. $50$回未満の操作で回文数になる
  2. まだ誰も回文数まで到達していない

実際, $10677$が$50$回以上の操作を必要とする最初の数である: $4668731596684224866951378664$ ($53$回の操作で$28$桁のこの回文数になる).

驚くべきことに, 回文数かつLychrel数であるものが存在する. 最初の数は$4994$である.

$10000$未満のLychrel数の個数を答えよ.

注: $2007/04/24$にLychrel数の理論的な性質を強調するために文面が修正された.

解答

time seq 9999 |
awk '{n[NR,0]=$1;printf $1" ";for(i=1;i<=49;i++){for(j=length(n[NR,i-1]);0<j;j--){t[NR,i]=(t[NR,i] substr(n[NR,i-1],j,1))};n[NR,i]=n[NR,i-1]+t[NR,i];printf n[NR,i]" "};print ""}' |
awk '{for(i=2;i<=NF;i++){for(j=length($i);0<j;j--){t[NR,i]=(t[NR,i] substr($i,j,1))};if($i==t[NR,i]){next}};print $1}' |
wc -l
249

real    0m7.781s
user    0m8.348s
sys     0m0.190s

他サイトを見る限り、「反転したものを加算する操作」を$0$回おこなったもの(つまり元の数字)が回文になっているものは回文とカウントしない様子。
よって$2$個目のawkのループでは$2$から始めた。

ところでawkでごりごりやるやり方は横に長くなるのであまり好きではないのですが、反転なので他のコマンドではやりにくいです。
revは行全体を反転させるので、工夫が必要。
perlのreverseもやってみたのですが途中で桁が足りなくなるようでした($20$桁までの整数しか対応していないっぽい)。
何かモジュールを入れればできるのかもしれないですけど、よく分からなかったです。

答え合わせ

こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/055.html

Edit request
0