m進記数法とn進記数法の両方で0と1だけで表記される非負整数。特にm=10について。

ある数Nを10進数で表しても8進数で表しても各桁が0と1だけになることはあるか？(自明な0と1以外でね)
— るふぁ(ノンリニアは一日目西れ59a) (@lpha_z) 2017年1月2日

これを見て、備忘録を作ろうと思った。

めんどくさいからこの記事では、二進記数法を「2進」と省略して書くことにしよう。

そして、(2進)11010というように、(2進)をつけたら続く数が2進に従うとしよう。

もちろん、2以外の基数に対してもこのルールを同様に適用して書くことにしよう。

10進と2進

2進では、全ての数が0と1だけで表記される。

だから、全ての非負整数は2進において0と1だけで表記される。

10進で0と1だけで表記される数は容易に列挙可能である。

10進と3進

3進では、0と1以外に2を使って数を表記する。

だから、「10進と3進の両方で0と1だけで表記される整数」の自明な列挙が困難である。

困難とはいえ、総当たりで計算すれば小さい数を確かめることは可能だ。

11110101010011