PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 113 / 非はずみ数

ある数の桁を左から右へと順に見たとき,任意の桁の数が自身の左にある桁の数以上であるとき,その数を増加数(increasing number)と呼ぶ。たとえば134468は増加数である。

同様に,任意の桁の数が自身の右にある桁の数以上であるとき,その数を減少数(decreasing number)と呼ぶ。たとえば66420がそうである。

増加数でも減少数でもない正の整数を「はずみ数」(bouncy number)と呼ぶ。155349がそうである。

n が大きくなるにつれ,n 以下のはずみ数の割合は大きくなる。たとえば100万未満でははずみ数でない数は12951個しかない。同様に10^10未満では277032個しかない。

googol数(10^100)未満ではずみ数でないものの数を答えよ。

https://projecteuler.net/problem=113


n 桁の増加数を作るには 1〜9 の 9 個の数字から重複をゆるして n 個選べばよい。

H(9, n)=C(n+8, n)

n 桁の減少数を作るには 0〜9 の 10 個の数字から重複をゆるして n 個選べばよい。ただし,全部 0 の場合は不可。

H(10, n)-1=C(n+9, n)-1

これが原則ですが,同じ数字が n 個並んだ数は増加数かつ減少数としてダブルカウントされています。この 9 個は除外しないといけません。