Representation of Integers in Golden Mean Number System
Jump to navigation
Jump to search
Theorem
The positive integers $n$ are represented in the golden mean number system in their simplest form $S_n$ as follows:
$n$ $S_n$ $1$ $1$ $2$ $10 \cdotp 01$ $3$ $100 \cdotp 01$ $4$ $101 \cdotp 01$ $5$ $1000 \cdotp 1001$ $6$ $1010 \cdotp 0001$ $7$ $10000 \cdotp 0001$ $8$ $10001 \cdotp 0001$ $9$ $10010 \cdotp 0101$ $10$ $10100 \cdotp 0101$ $11$ $10101 \cdotp 0101$ $12$ $100000 \cdotp 101001$ $13$ $100010 \cdotp 001001$ $14$ $100100 \cdotp 001001$ $15$ $100101 \cdotp 001001$ $16$ $101000 \cdotp 100001$
Proof
- $1$ is represented by $\left[{1}\right]_\phi = \phi^0$.
From there, the algorithm for Addition of 1 in Golden Mean Number System is run.
\(\text {(2)}: \quad\) | \(\ds 1 + \left[{1}\right]_\phi\) | \(=\) | \(\ds 1 + \left[{0 \cdotp 11}\right]_\phi\) | Expansion | ||||||||||
\(\ds \) | \(=\) | \(\ds \left[{1 \cdotp 11}\right]_\phi\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \left[{10 \cdotp 01}\right]_\phi\) | Simplification |
\(\text {(3)}: \quad\) | \(\ds 1 + \left[{10 \cdotp 01}\right]_\phi\) | \(=\) | \(\ds \left[{11 \cdotp 01}\right]_\phi\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{100 \cdotp 01}\right]_\phi\) | Simplification |
\(\text {(4)}: \quad\) | \(\ds 1 + \left[{100 \cdotp 01}\right]_\phi\) | \(=\) | \(\ds \left[{101 \cdotp 01}\right]_\phi\) |
\(\text {(5)}: \quad\) | \(\ds 1 + \left[{101 \cdotp 01}\right]_\phi\) | \(=\) | \(\ds 1 + \left[{101 \cdotp 0011}\right]_\phi\) | Expansion | ||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \left[{100 \cdotp 1111}\right]_\phi\) | Expansion | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{101 \cdotp 1111}\right]_\phi\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \left[{110 \cdotp 0111}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{1000 \cdotp 0111}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{1000 \cdotp 1001}\right]_\phi\) | Simplification |
\(\text {(6)}: \quad\) | \(\ds 1 + \left[{1000 \cdotp 1001}\right]_\phi\) | \(=\) | \(\ds \left[{1001 \cdotp 1001}\right]_\phi\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{1010 \cdotp 0001}\right]_\phi\) | Simplification |
\(\text {(7)}: \quad\) | \(\ds 1 + \left[{1010 \cdotp 0001}\right]_\phi\) | \(=\) | \(\ds \left[{1011 \cdotp 0001}\right]_\phi\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{1100 \cdotp 0001}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{10000 \cdotp 0001}\right]_\phi\) | Simplification |
\(\text {(8)}: \quad\) | \(\ds 1 + \left[{10000 \cdotp 0001}\right]_\phi\) | \(=\) | \(\ds \left[{10001 \cdotp 0001}\right]_\phi\) |
\(\text {(9)}: \quad\) | \(\ds 1 + \left[{10001 \cdotp 0001}\right]_\phi\) | \(=\) | \(\ds 1 + \left[{10000 \cdotp 1101}\right]_\phi\) | Expansion | ||||||||||
\(\ds \) | \(=\) | \(\ds \left[{10001 \cdotp 1101}\right]_\phi\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \left[{10010 \cdotp 0101}\right]_\phi\) | Simplification |
\(\text {(10)}: \quad\) | \(\ds 1 + \left[{10010 \cdotp 0101}\right]_\phi\) | \(=\) | \(\ds \left[{10011 \cdotp 0101}\right]_\phi\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{10100 \cdotp 0101}\right]_\phi\) | Simplification |
\(\text {(11)}: \quad\) | \(\ds 1 + \left[{10100 \cdotp 0101}\right]_\phi\) | \(=\) | \(\ds \left[{10101 \cdotp 0101}\right]_\phi\) |
\(\text {(12)}: \quad\) | \(\ds 1 + \left[{10101 \cdotp 0101}\right]_\phi\) | \(=\) | \(\ds 1 + \left[{10101 \cdotp 010011}\right]_\phi\) | Expansion | ||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \left[{10101 \cdotp 001111}\right]_\phi\) | Expansion | |||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \left[{10100 \cdotp 111111}\right]_\phi\) | Expansion | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{10101 \cdotp 111111}\right]_\phi\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \left[{10110 \cdotp 011111}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{11000 \cdotp 011111}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{100000 \cdotp 011111}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{100000 \cdotp 100111}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{100000 \cdotp 101001}\right]_\phi\) | Simplification |
\(\text {(13)}: \quad\) | \(\ds 1 + \left[{100000 \cdotp 101001}\right]_\phi\) | \(=\) | \(\ds \left[{100001 \cdotp 101001}\right]_\phi\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{100010 \cdotp 001001}\right]_\phi\) | Simplification |
\(\text {(14)}: \quad\) | \(\ds 1 + \left[{100010 \cdotp 001001}\right]_\phi\) | \(=\) | \(\ds \left[{100011 \cdotp 001001}\right]_\phi\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{100100 \cdotp 001001}\right]_\phi\) | Simplification |
\(\text {(15)}: \quad\) | \(\ds 1 + \left[{100100 \cdotp 001001}\right]_\phi\) | \(=\) | \(\ds \left[{100101 \cdotp 001001}\right]_\phi\) |
\(\text {(16)}: \quad\) | \(\ds 1 + \left[{100101 \cdotp 001001}\right]_\phi\) | \(=\) | \(\ds 1 + \left[{100100 \cdotp 111001}\right]_\phi\) | Expansion | ||||||||||
\(\ds \) | \(=\) | \(\ds \left[{100101 \cdotp 111001}\right]_\phi\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \left[{100110 \cdotp 011001}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{101000 \cdotp 011001}\right]_\phi\) | Simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \left[{101000 \cdotp 100001}\right]_\phi\) | Simplification |
$\blacksquare$
Sources
- 1957: George Bergman: Number System with an Irrational Base (Math. Mag. Vol. 31, no. 2: pp. 98 – 110) www.jstor.org/stable/3029218
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $35$