PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 346 / 強いレピュニット

7は特別な数である。2進数では111と表せ,6進数では11と表せる。
7(10) = 11(6) = 111(2)

別の言い方をすると,7は少なくとも二種類の1より大きい底の記数法でレピュニット(全ての桁が1である自然数)である。

上記の特徴を有する正の整数を「強いレピュニット」と呼ぶことにする。50未満には8つの強いレピュニットが存在する。
{1,7,13,15,21,31,40,43}

さらに,1000未満の強いレピュニットの和は15864になる。

10^12未満の強いレピュニットの和を求めよ。

Problem 346 - Project Euler


いろいろな底に対してレピュニット数を作って,重複しているものを抽出しました。例によって素直すぎる解法ではとても時間内(1分)に終わらないので,10^6 を境に集合を区切って数えています。

10^6+1 以上の底に対して3桁以上のレピュニット数は作れません。たとえば 10^7 進法で111となる数は

 1\cdot (10^7)^2+1\cdot 10^7+1=10^{14}+10^7+1

となって,10^12 を軽く超えます。2桁なら 10^7+1 でOKです。

底として使うのは 10^6 まで。10^6+1 以下の数は Tally で重複をしっかり調べましたが,10^6+2 以上の数は myList1 に1回でも出てくればOKとしました。これらの数は 10^6+1 以上の数を底に使うと出てくるからです。