上の問題で、表計算ソフトの列番号によくある A, B, … , Z, AA, … といった文字列が何番目を指すのかを問われた。
何となく A → 1, B → 2, … , Z → 26 と「ゼロを抜いて各文字に番号を振った」うえで「普通の26進法と同じ計算をした」ところ正答できた（試していたらできそうに見えただけで、何も証明していない）。しかし、普通は十進法なら 0 ～ 9 というようにゼロを入れて N は入れないはずで、この解き方はN進法のルールを破ってしまっている気がする。
convert.rb
def str2num(str) # str = "BRUTMHYHIIZP"
digits = str.bytes.map { |b| b - 0x40 } #=> [2, 18, 21, 20, 13, 8, 25, 8, 9, 9, 26, 16]
digits.inject(0) { |s, d| s * 26 + d } #=> 10000000000000000
end
# おまけ：逆方向の変換
def num2str(num) # num = 10000000000000000
digits = []
while num > 0
num, d = (num - 1).divmod(26)
digits << d + 1
end
digits = digits.reverse #=> [2, 18, 21, 20, 13, 8, 25, 8, 9, 9, 26, 16]
digits.map { |d| d + 0x40 }.pack("C*") #=> "BRUTMHYHIIZP"
end
調べたところ、各桁で 0 を使わず 1 ～ N を割り当てるようなN進法（位取り記数法）は "bijective base-N numeration" としてきちんとあるらしい。
- 任意の自然数と文字列とが1対1対応する。（だから名前に「全単射」とある）
- それに対して通常のN進法だと、ゼロ埋めしても同じ数値になるため1対1でない。
- 同じ最大桁数であれば通常のN進法より多くの数値を表せる。
- 空文字列を認めれば、数値のゼロも文字列で表せる。
-
文字列から数値への変換は、通常のN進法と同じ式。
- したがって表記中に 0 や N を含まない数は、通常版でも全単射版でも同じ数値を表す。
- 数値から文字列への変換も、通常版の方法を僅かに変更すればできる。
- 加算や乗算も、通常のN進法と同じ要領で筆算できる。（繰り上がりの処理でゼロの桁を作らないようにだけ注意）
証明にはならないが、十進法で実際に試してみれば妥当な雰囲気が掴める。
冒頭の問題が26進法でいけそうに見えたのは、 Z を含んでいないものは本当に通常の26進法と数値が一致するからかもしれない。