PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 162 / 16進数

16進法では数は以下の16個の数字によって表される。

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

16進数の AF は10進法での 10x16 + 15 = 175 と等しい。

3桁の16進数 10A, 1A0, A10, A01 には, 0, 1, A のすべてがあらわれている。
10進数で書くときと同様に先頭の0は書かないことにする。

0, 1, A がそれぞれ少なくとも1回はあらわれるような16桁までの16進数はいくつ存在するか? 16進数で答えよ。

Problem 162 - Project Euler


これは手計算でも解ける問題です。n桁の場合を考えます。全体集合の要素数をN(Ω)であらわし,文字xを含むものの個数をN(x)のようにあらわします。

f:id:variee:20170402032643p:plain

第2項はばらして計算します。

f:id:variee:20170402032644p:plain

あとは n=3 から n=16 までの和をとって16進数に直せば終わりです。