PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 112 / はずみ数

左から右までどの桁もその左の桁を下回らない数を増加数と呼ぶ。
例 134468

同様に, どの桁もその右の桁を下回らない数を減少数と呼ぶ。
例 66420

増加数でも減少数でもない正の整数を「はずみ数」と呼ぶことにする。
例 155349

100以下にはずみ数がないのは明らかだが,1000未満では半数を少し上回る525個がはずみ数である。

はずみ数の割合が50%に達する最少の数は538である。驚くべきことに,はずみ数の割合はますます増え,21780では90%に達する。はずみ数の割合がちょうど99%になる最小の数を求めよ。

Problem 112 - Project Euler


昨日解いた第113問の類題です。こちらは重複組合せを使って一気に数えるようなことはできないので,はずみ数かどうか1つ1つチェックしていかないといけません。

variee.hatenadiary.com

IntegerDigits で各数を桁ごとに区切ったものを並べ替えて,はずみ数の判定をします。g[n]/n と 99/100 の分母をはらった形に直すだけでかなりスピードが変わりました。