十六進表記が十進法でも読めると嬉しい
十六進法で表記されたハッシュ値を扱っていると、たまに十進法でも有効な文字列になっていることがある。
つまり、十六進表記だがどの桁も0から9のいずれかで、aからfを含まないということ。実例として、
など。反対に、
は 桁目に それぞれ
を含むため十進法で読めない。
このような性質を満たす数のことを 偽十進法整数 と呼ぶことにする。すなわち、 が偽十進法整数であるとは、
以上
以下の整数の列
が存在して、
を満たすということ。
7桁程度の偽十六進整数ならさして珍しくないことは、の数のうち、割合として
がこの性質を満たすことから分かる。gitのログで表示されるコミットハッシュの短縮形のデフォルト桁数がこの7桁*1なので、目にする機会も多い。
さて、偽十進法整数は具体的にどれくらい存在するだろうか。非負整数 以下の非負の偽十進法整数の個数を
で表すことにする。なお、特に進数表記をしていない限り以下では十進法。
が
で
に漸近することはほぼ明らか。では、
以下の偽十進法非負整数とそうでない数が同数になるのはいつだろうか。すなわち、
となるのはいつか。計算すると、 ただひとつがこの性質を満たすことが分かる。
少し一般化して、
を満たすような整数 が存在する
を探そう。
が上で調べた場合にあたる。
以下での結果が下表。
は十進で下位に9が並ぶ傾向があるが、完全ではない。実際、
等で一の位が
で一の位が
となっていることが観察できる。
この「傾向」はどう説明付けられるだろうか。 の振る舞いを見よう。
じっと見ると、 を簡単に計算する方法が分かる。
たとえば、
以下の偽十進非負整数は、
の関係が成り立つから、
の 個である。
言葉で説明しよう。 を 十六進表記で上の位から見て、最初に見つかる
より大きい文字（aからf）とそれ以下の桁の文字を全て
で置き換えると、それが
を超えない最大の偽十進法整数である（十六進法で読む）。その文字列を十進法で読み替えて1を加えれば
を得る。
という具合に。
を満たす
の下位の桁に9が並びがちな傾向はこのことから理解できる。そもそも
は
の大きな冪を約数に持ちやすく、そのため
は下位の桁に多くの9が並ぶ。非常に粗いヒューリスティックな議論ではあるが。
さて、未解決の問題がある。 を満たす
が、10で割って
以外の剰余を持つことはあるだろうか？（たぶん存在すると思う）
*1:`--abbrev` オプションで変更できる。
