記数法のさまざまな拡張
～2進数からButchi数まで～

面白法人カヤック岩淵勇樹

自己紹介

岩淵勇樹
金沢大学大学院自然科学研究科電子情報科学専攻博士後期課程修了
博士（工学）
2012年4月面白法人カヤックに入社

10進法(decimal)

既知

人間が普段使っている記数法

base: 10
digit: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

例: 1984=1×10³+9×10²+8×10¹+4×10⁰

用語説明

base: radix、基数、底。仮数に掛け合わせる数（重みの倍率）
digit: 仮数。その位に記される数

16進法(Hexadecimal)

既知

コンピューターでよく使われている

HTMLのカラーコードは16進数を3つ並べて表記する（#ffffffなど）

base: 16
digit: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f

例: 2d=2×16¹+13×16⁰=45

2進法(binary)

既知

base: 2
digit: 0, 1

例: 1011=1×2³+0×2²+1×2¹+1×2⁰=13

8	4	2	1
0	0	0	0	0
0	0	0	1	1
0	0	1	0	2
0	0	1	1	3
0	1	0	0	4
0	1	0	1	5
0	1	1	0	6
0	1	1	1	7

8	4	2	1
1	0	0	0	8
1	0	0	1	9
1	0	1	0	10
1	0	1	1	11
1	1	0	0	12
1	1	0	1	13
1	1	1	0	14
1	1	1	1	15

3進法(ternary)

既知

base: 3
digit: 0, 1, 2

9	3	1
0	0	0	0
0	0	1	1
0	0	2	2
0	1	0	3
0	1	1	4
0	1	2	5

9	3	1
0	2	0	6
0	2	1	7
0	2	2	8
1	0	0	9
1	0	1	10
1	0	2	11

N進法（まとめ）

既知

base: N
digit: 0～N-1

\sum_{k = 1}^{n} a_{k} N^{k}

黄金進法（φ進法）(phinary, golden ratio base)

既知

base: $\frac{1}{2} (1 + \sqrt{5})$ (=φ)
digit: 0, 1

自然数全体に加えて一部の無理数も表現できる（10=φなど）

黄金進法（φ進法）(phinary, golden ratio base)

既知

φ⁴	φ³	φ²	φ¹	φ⁰	φ^-1	φ^-2	φ^-3	φ^-4
0	0	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	1
0	0	0	1	0	0	1	0	0	2
0	0	1	0	0	0	1	0	0	3
0	0	1	0	1	0	1	0	0	4
0	1	0	0	0	1	0	0	1	5
0	1	0	1	0	0	0	0	1	6
1	0	0	0	0	0	0	0	1	7
1	0	0	0	1	0	0	0	1	8
1	0	0	1	0	0	1	0	1	9
1	0	1	0	0	0	1	0	1	10

フィボナッチ記数法（フィボナッチ符号）

既知

base: フィボナッチ数
digit: 0, 1

自然数全体を表現できる

フィボナッチ記数法（フィボナッチ符号）

既知

8	5	3	2	1
0	0	0	0	0	0
0	0	0	0	1	1
0	0	0	1	0	2
0	0	1	0	0	3
0	0	1	0	1	4
0	1	0	0	0	5
0	1	0	0	1	6
0	1	0	1	0	7
1	0	0	0	0	8
1	0	0	0	1	9
1	0	0	1	0	10

ゼッケンドルフの定理

既知

自然数は隣り合わないフィボナッチ数の和で表せる

二五進法

既知

そろばんで用いられる

十進数	二五進法	二進数
0	0 000	0000
1	0 001	0001
2	0 010	0010
3	0 011	0011
4	0 100	0100
5	1 000	0101
6	1 001	0110
7	1 010	0111
8	1 011	1000
9	1 100	1001

グレイコード

既知

0	0	0	0	0
0	0	0	1	1
0	0	1	1	2
0	0	1	0	3
0	1	1	0	4
0	1	1	1	5
0	1	0	1	6
0	1	0	0	7
1	1	0	0	8
1	1	0	1	9
1	1	1	1	10
1	1	1	0	11
1	0	1	0	12
1	0	1	1	13
1	0	0	1	14
1	0	0	0	15

（蛇足）グレイコードの歌

独自

グレイコードカウンタの歌

符号付き2進法

既知

base: 2
digit: -1, 0, 1

NAF表記（0でないdigitが連続しない）によって一意性が保たれる

符号付き2進法

既知

8	4	2	1
0	-1	0	-1	-5
0	-1	0	0	-4
0	-1	0	1	-3
0	0	-1	0	-2
0	0	0	-1	-1
0	0	0	0	0
0	0	0	1	1
0	0	1	0	2
0	1	0	-1	3
0	1	0	0	4
0	1	0	1	5
1	0	-1	0	6
1	0	0	-1	7
1	0	0	0	8
1	0	0	1	9
1	0	1	0	10

平衡3進法

既知

base: 3
digit: -1, 0, 1

コンピューターで計算がしやすい

平衡3進法

既知

9	3	1
0	0	0	0
0	0	1	1
0	1	-1	2
0	1	0	3
0	1	1	4
1	-1	-1	5
1	-1	0	6
1	-1	1	7
1	0	-1	8
1	0	0	9
1	0	1	10

Bijective numeration

既知

k-adicの場合:

base: k
digit: 1～k

0を使わない記数法

Bijective numeration (1-adic)

既知

1	1	1	1	1
				ε
				1
			1	1
		1	1	1
	1	1	1	1
1	1	1	1	1

Bijective numeration (2-adic)

既知

4	2	1
		ε	0
		1	1
		2	2
	1	1	3
	1	2	4
	2	1	5
	2	2	6
1	1	1	7
1	1	2	8
1	2	1	9
1	2	2	10

-2進法(negabinary)

既知

base: -2
digit: 0, 1

整数全体を表せる記数法

-2進法(negabinary)

既知

16	-8	4	-2	1
0	1	1	1	1	-5
0	1	1	0	0	-4
0	1	1	0	1	-3
0	0	0	1	0	-2
0	0	0	1	1	-1
0	0	0	0	0	0
0	0	0	0	1	1
0	0	1	1	0	2
0	0	1	1	1	3
0	0	1	0	0	4
0	0	1	0	1	5
1	1	0	1	0	6
1	1	0	1	1	7
1	1	0	0	0	8
1	1	0	0	1	9
1	1	1	1	0	10

-1+i進法

既知

base: -1+i
digit: 0, 1

D. Knuthが考案

有限桁でガウス整数を記述可能

1+i進法

独自

base: 1+i
digit: 0, 1

有限桁ではガウス整数全体は記述不可

2i進法

既知

base: 2i
digit: 0, 1, 2, 3

D. Knuthが考案

黄金進法の負への拡張

未知

(-φ)⁴	(-φ)³	(-φ)²	(-φ)¹	(-φ)⁰	(-φ)^-1	(-φ)^-2	(-φ)^-4
0	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	1
0	0	0	1	0	0	1	0	2
0	0	1	0	0	0	1	0	3
0	0	1	0	1	0	1	0	4
0	1	0	0	0	1	0	1	5
0	1	0	1	0	0	0	1	6
1	0	0	0	0	0	0	1	7
1	0	0	0	1	0	0	1	8
1	0	0	1	0	0	1	1	9
1	0	1	0	0	0	1	1	10

フィボナッチ記数法の負への拡張

未知

13	-8	5	-3	2	-1	1
0	1	0	0	1	0	1	-5
0	0	0	1	0	1	0	-4
0	0	0	1	0	0	0	-3
0	0	0	1	0	0	1	-2
0	0	0	0	0	1	0	-1
0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	1
0	0	0	0	1	0	0	2
0	0	0	0	1	0	1	3
0	0	1	0	0	1	0	4
0	0	1	0	0	0	0	5
0	0	1	0	0	0	1	6
0	0	1	0	1	0	0	7
0	0	1	0	1	0	1	8
1	0	0	1	0	1	0	9

factorial based radix

既知

base: n!
digit: 0～n

3!	2!	1!
0	0	1	1
0	1	0	2
0	1	1	3
0	2	0	4
0	2	1	5
1	0	0	6
1	0	1	7
1	1	0	8
1	1	1	9
1	2	0	10

p-進法

既知

無限桁で負の数を含む有理数を表せる

-1=…111111

-1/3=…010101

（蛇足）3足さん！

http://butchi.jp/documents/program/santasan/

（蛇足）

Googleで「16進数」を検索すると…

繰り上がり則

2進法では、左に繰り上がる

繰り上がり則

黄金進法では左に1繰り上がり、右に2繰り下がる

繰り上がり則

では、上にも繰り上がってはどうか？

Butchi数

独自

Butchi数解説ページ

卒業論文「2進数の平面的表現に関する考察」

余談

このスライドはHTML 5の技術を用いて作りました。

数式はMathematicaを用いてMathMLで記述しています。

Firefox 14で動作確認済みです。

8	5	3	2	1
0	0	0	0	0	0
0	0	0	0	1	1
0	0	0	1	0	2
0	0	1	0	0	3
0	0	1	0	1	4
0	1	0	0	0	5
0	1	0	0	1	6
0	1	0	1	0	7
1	0	0	0	0	8
1	0	0	0	1	9
1	0	0	1	0	10

0	0	0	0	0
0	0	0	1	1
0	0	1	1	2
0	0	1	0	3
0	1	1	0	4
0	1	1	1	5
0	1	0	1	6
0	1	0	0	7
1	1	0	0	8
1	1	0	1	9
1	1	1	1	10
1	1	1	0	11
1	0	1	0	12
1	0	1	1	13
1	0	0	1	14
1	0	0	0	15

8	4	2	1
0	-1	0	-1	-5
0	-1	0	0	-4
0	-1	0	1	-3
0	0	-1	0	-2
0	0	0	-1	-1
0	0	0	0	0
0	0	0	1	1
0	0	1	0	2
0	1	0	-1	3
0	1	0	0	4
0	1	0	1	5
1	0	-1	0	6
1	0	0	-1	7
1	0	0	0	8
1	0	0	1	9
1	0	1	0	10

16	-8	4	-2	1
0	1	1	1	1	-5
0	1	1	0	0	-4
0	1	1	0	1	-3
0	0	0	1	0	-2
0	0	0	1	1	-1
0	0	0	0	0	0
0	0	0	0	1	1
0	0	1	1	0	2
0	0	1	1	1	3
0	0	1	0	0	4
0	0	1	0	1	5
1	1	0	1	0	6
1	1	0	1	1	7
1	1	0	0	0	8
1	1	0	0	1	9
1	1	1	1	0	10

(-φ)⁴	(-φ)³	(-φ)²	(-φ)¹	(-φ)⁰	(-φ)^-1	(-φ)^-2	(-φ)^-4
0	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	1
0	0	0	1	0	0	1	0	2
0	0	1	0	0	0	1	0	3
0	0	1	0	1	0	1	0	4
0	1	0	0	0	1	0	1	5
0	1	0	1	0	0	0	1	6
1	0	0	0	0	0	0	1	7
1	0	0	0	1	0	0	1	8
1	0	0	1	0	0	1	1	9
1	0	1	0	0	0	1	1	10

13	-8	5	-3	2	-1	1
0	1	0	0	1	0	1	-5
0	0	0	1	0	1	0	-4
0	0	0	1	0	0	0	-3
0	0	0	1	0	0	1	-2
0	0	0	0	0	1	0	-1
0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	1
0	0	0	0	1	0	0	2
0	0	0	0	1	0	1	3
0	0	1	0	0	1	0	4
0	0	1	0	0	0	0	5
0	0	1	0	0	0	1	6
0	0	1	0	1	0	0	7
0	0	1	0	1	0	1	8
1	0	0	1	0	1	0	9

8	5	3	2	1
0	0	0	0	0	0
0	0	0	0	1	1
0	0	0	1	0	2
0	0	1	0	0	3
0	0	1	0	1	4
0	1	0	0	0	5
0	1	0	0	1	6
0	1	0	1	0	7
1	0	0	0	0	8
1	0	0	0	1	9
1	0	0	1	0	10

0	0	0	0	0
0	0	0	1	1
0	0	1	1	2
0	0	1	0	3
0	1	1	0	4
0	1	1	1	5
0	1	0	1	6
0	1	0	0	7
1	1	0	0	8
1	1	0	1	9
1	1	1	1	10
1	1	1	0	11
1	0	1	0	12
1	0	1	1	13
1	0	0	1	14
1	0	0	0	15

8	4	2	1
0	-1	0	-1	-5
0	-1	0	0	-4
0	-1	0	1	-3
0	0	-1	0	-2
0	0	0	-1	-1
0	0	0	0	0
0	0	0	1	1
0	0	1	0	2
0	1	0	-1	3
0	1	0	0	4
0	1	0	1	5
1	0	-1	0	6
1	0	0	-1	7
1	0	0	0	8
1	0	0	1	9
1	0	1	0	10

16	-8	4	-2	1
0	1	1	1	1	-5
0	1	1	0	0	-4
0	1	1	0	1	-3
0	0	0	1	0	-2
0	0	0	1	1	-1
0	0	0	0	0	0
0	0	0	0	1	1
0	0	1	1	0	2
0	0	1	1	1	3
0	0	1	0	0	4
0	0	1	0	1	5
1	1	0	1	0	6
1	1	0	1	1	7
1	1	0	0	0	8
1	1	0	0	1	9
1	1	1	1	0	10

(-φ)⁴	(-φ)³	(-φ)²	(-φ)¹	(-φ)⁰	(-φ)^-1	(-φ)^-2	(-φ)^-4
0	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	1
0	0	0	1	0	0	1	0	2
0	0	1	0	0	0	1	0	3
0	0	1	0	1	0	1	0	4
0	1	0	0	0	1	0	1	5
0	1	0	1	0	0	0	1	6
1	0	0	0	0	0	0	1	7
1	0	0	0	1	0	0	1	8
1	0	0	1	0	0	1	1	9
1	0	1	0	0	0	1	1	10

13	-8	5	-3	2	-1	1
0	1	0	0	1	0	1	-5
0	0	0	1	0	1	0	-4
0	0	0	1	0	0	0	-3
0	0	0	1	0	0	1	-2
0	0	0	0	0	1	0	-1
0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	1
0	0	0	0	1	0	0	2
0	0	0	0	1	0	1	3
0	0	1	0	0	1	0	4
0	0	1	0	0	0	0	5
0	0	1	0	0	0	1	6
0	0	1	0	1	0	0	7
0	0	1	0	1	0	1	8
1	0	0	1	0	1	0	9

記数法のさまざまな拡張～2進数からButchi数まで～

自己紹介

10進法(decimal)

用語説明

16進法(Hexadecimal)

2進法(binary)

3進法(ternary)

N進法（まとめ）

黄金進法（φ進法）(phinary, golden ratio base)

黄金進法（φ進法）(phinary, golden ratio base)

フィボナッチ記数法（フィボナッチ符号）

フィボナッチ記数法（フィボナッチ符号）

ゼッケンドルフの定理

二五進法

グレイコード

（蛇足）グレイコードの歌

符号付き2進法

符号付き2進法

平衡3進法

平衡3進法

Bijective numeration

Bijective numeration (1-adic)

Bijective numeration (2-adic)

-2進法(negabinary)

-2進法(negabinary)

-1+i進法

1+i進法

i+1進法

Twindragon

2i進法

黄金進法の負への拡張

フィボナッチ記数法の負への拡張

factorial based radix

p-進法

（蛇足）3足さん！

（蛇足）

繰り上がり則

繰り上がり則

繰り上がり則

Butchi数

余談

記数法のさまざまな拡張
～2進数からButchi数まで～

8	5	3	2	1
0	0	0	0	0	0
0	0	0	0	1	1
0	0	0	1	0	2
0	0	1	0	0	3
0	0	1	0	1	4
0	1	0	0	0	5
0	1	0	0	1	6
0	1	0	1	0	7
1	0	0	0	0	8
1	0	0	0	1	9
1	0	0	1	0	10

0	0	0	0	0
0	0	0	1	1
0	0	1	1	2
0	0	1	0	3
0	1	1	0	4
0	1	1	1	5
0	1	0	1	6
0	1	0	0	7
1	1	0	0	8
1	1	0	1	9
1	1	1	1	10
1	1	1	0	11
1	0	1	0	12
1	0	1	1	13
1	0	0	1	14
1	0	0	0	15

8	4	2	1
0	-1	0	-1	-5
0	-1	0	0	-4
0	-1	0	1	-3
0	0	-1	0	-2
0	0	0	-1	-1
0	0	0	0	0
0	0	0	1	1
0	0	1	0	2
0	1	0	-1	3
0	1	0	0	4
0	1	0	1	5
1	0	-1	0	6
1	0	0	-1	7
1	0	0	0	8
1	0	0	1	9
1	0	1	0	10

16	-8	4	-2	1
0	1	1	1	1	-5
0	1	1	0	0	-4
0	1	1	0	1	-3
0	0	0	1	0	-2
0	0	0	1	1	-1
0	0	0	0	0	0
0	0	0	0	1	1
0	0	1	1	0	2
0	0	1	1	1	3
0	0	1	0	0	4
0	0	1	0	1	5
1	1	0	1	0	6
1	1	0	1	1	7
1	1	0	0	0	8
1	1	0	0	1	9
1	1	1	1	0	10

(-φ)⁴	(-φ)³	(-φ)²	(-φ)¹	(-φ)⁰	(-φ)^-1	(-φ)^-2	(-φ)^-4
0	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	1
0	0	0	1	0	0	1	0	2
0	0	1	0	0	0	1	0	3
0	0	1	0	1	0	1	0	4
0	1	0	0	0	1	0	1	5
0	1	0	1	0	0	0	1	6
1	0	0	0	0	0	0	1	7
1	0	0	0	1	0	0	1	8
1	0	0	1	0	0	1	1	9
1	0	1	0	0	0	1	1	10

13	-8	5	-3	2	-1	1
0	1	0	0	1	0	1	-5
0	0	0	1	0	1	0	-4
0	0	0	1	0	0	0	-3
0	0	0	1	0	0	1	-2
0	0	0	0	0	1	0	-1
0	0	0	0	0	0	0	0
0	0	0	0	0	0	1	1
0	0	0	0	1	0	0	2
0	0	0	0	1	0	1	3
0	0	1	0	0	1	0	4
0	0	1	0	0	0	0	5
0	0	1	0	0	0	1	6
0	0	1	0	1	0	0	7
0	0	1	0	1	0	1	8
1	0	0	1	0	1	0	9