No.294

SuperFizzBuzzな数値は5で割り切れるので, 1の位は5である.

桁の数値に SuperFizzBuzz がいくつあるかであるが, SuperFizzBuzz は3の倍数でもあるので, 各桁の合計が3の倍数でなければならず, そのためには5が3の倍数個含まれていなければならない.

以上のことから, 桁の数値に SuperFizzBuzz がいくつ含まれているかは以下の通りとなる.

$$ n $$ $$ SuperFizzBuzz の個数 $$
$$ 1 $$ $$ 0 $$
$$ 2 $$ $$ 0 $$
$$ 3 $$ $$ {}_2C_2 = 1 $$
$$ 4 $$ $$ {}_3C_2 = 3 $$
$$ 5 $$ $$ {}_4C_2 = 6 $$
$$ 6 $$ $$ {}_5C_2 + {}_5C_5 = 11 $$
$$ 7 $$ $$ {}_6C_2 + {}_6C_5 = 21 $$
$$ 8 $$ $$ {}_7C_2 + {}_7C_5 = 42 $$
$$ 9 $$ $$ {}_8C_2 + {}_8C_5 + {}_8C_8 = 85 $$
$$ 10 $$ $$ {}_9C_2 + {}_9C_5 + {}_9C_8 = 171 $$
$$ 11 $$ $$ {}_{10}C_2 + {}_{10}C_5 + {}_{10}C_8 = 342 $$
$$ 12 $$ $$ {}_{11}C_2 + {}_{11}C_5 + {}_{11}C_8 + {}_{11}C_{11} = 683 $$
$$ 13 $$ $$ {}_{12}C_2 + {}_{12}C_5 + {}_{12}C_8 + {}_{12}C_{11} = 1365 $$
$$ 14 $$ $$ {}_{13}C_2 + {}_{13}C_5 + {}_{13}C_8 + {}_{13}C_{11} = 2730 $$
$$ 15 $$ $$ {}_{14}C_2 + {}_{14}C_5 + {}_{14}C_8 + {}_{14}C_{11} + {}_{14}C_{14} = 5461 $$
$$ 16 $$ $$ {}_{15}C_2 + {}_{15}C_5 + {}_{15}C_8 + {}_{15}C_{11} + {}_{15}C_{14} = 10923 $$
$$ 17 $$ $$ {}_{16}C_2 + {}_{16}C_5 + {}_{16}C_8 + {}_{16}C_{11} + {}_{16}C_{14} = 21846 $$
$$ 18 $$ $$ {}_{17}C_2 + {}_{17}C_5 + {}_{17}C_8 + {}_{17}C_{11} + {}_{17}C_{14} + {}_{17}C_{17} = 43691 $$
$$ 19 $$ $$ {}_{18}C_2 + {}_{18}C_5 + {}_{18}C_8 + {}_{18}C_{11} + {}_{18}C_{14} + {}_{18}C_{17} = 87381 $$
$$ 20 $$ $$ {}_{19}C_2 + {}_{19}C_5 + {}_{19}C_8 + {}_{19}C_{11} + {}_{19}C_{14} + {}_{19}C_{17} = 174762 $$
$$ 21 $$ $$ {}_{20}C_2 + {}_{20}C_5 + {}_{20}C_8 + {}_{20}C_{11} + {}_{20}C_{14} + {}_{20}C_{17} + {}_{20}C_{20} = 349525 $$
$$ 22 $$ $$ {}_{21}C_2 + {}_{21}C_5 + {}_{21}C_8 + {}_{21}C_{11} + {}_{21}C_{14} + {}_{21}C_{17} + {}_{21}C_{20} = 699051 $$
$$ 23 $$ $$ {}_{22}C_2 + {}_{22}C_5 + {}_{22}C_8 + {}_{22}C_{11} + {}_{22}C_{14} + {}_{22}C_{17} + {}_{22}C_{20} = 1398102 $$
$$ 24 $$ $$ {}_{23}C_2 + {}_{23}C_5 + {}_{23}C_8 + {}_{23}C_{11} + {}_{23}C_{14} + {}_{23}C_{17} + {}_{23}C_{20} + {}_{23}C_{23} = 2796203 $$

この表をあらかじめ持っておくことで, 番目の SuperFizzBuzz の桁数 と, それが 桁の SuperFizzBuzz の中で何番目かを知ることができる.

あとは ビットの数値を順に探索し, 0 を3、1 を5として5の数が3で割って余りが2になる数でカウントアップするようにすれば, 桁の中で何番目の SuperFizzBuzz を求めることができる.