Golden Ratio Base

Number Theory Level 4

The golden ratio $\phi$ is the larger positive root to $x^2 = x + 1$ .

We can calculate that

$\begin{array} { l l } \phi^0 = 1, & \\ \phi^1 = \phi, &\phi^{-1} = \phi - 1, \\ \phi^2 = \phi + 1, & \phi^{-2} = -\phi + 2, \\ \phi^3 = 2\phi + 1, & \phi^{-3} = 2\phi -3 . \\ \end{array}$

This allows us to write numbers in base $\phi$ , where each place value is a non-negative integer less than $\phi$ . For example,
$\begin{array} { l l l l l l } 1 & = & 1 & = & 1 _\phi \\ 2 & = & \phi + (-\phi + 2) & = & 10.01_\phi \\ 3 & = & (\phi+1) + (-\phi + 2) & = & 100.01 _\phi. \end{array}$

Give the finite decimal representation of 5 in base $\phi$ that doesn't use a consecutive pair of 1's.

(You may assume the fact that a finite decimal representation with no consecutive pair of 1's is unique. This is known as the standard form for base $\phi$ .)

The answer is 1000.1001.

4 solutions

Chung Kevin
Jan 20, 2017

Here's a way to calculate each number inductively.

Add 1 to the units place.
If there is a 2, replace it with $10.01$ .
If there is a 11, replace it with $100$ .
Eventually, the 1's are spread out sufficiently, so that there isn't a 2 or a 11 in the sequence, and so we're done.

In the case of 4, we're just doing the first step $3 + 1 = 100.01_\phi + 1 _\phi = 101.01_\phi$ , which is why I didn't ask about 4.

In the case of 5, we get $4 + 1 = 101.01_\phi + 1_\phi = 102.01_\phi = 110.02_\phi = 110.1001_\phi = 1000.1001_\phi$ .

We could also use multiplication to calculate larger values, and then do the removal of 2's and 11's. For example, with 2 and 3, we get

$6 = 2 \times 3 = 10.01_\phi \times 100.01 _\phi = 1001.1001_ \phi = 1010.0001_\phi$

The great thing about multiplication in base $\phi$ (and also in base 2), is that it works just like multiplication in base 10! We then have to deal with the non-0's or 1's by reducing them term by term.

Moderator note:

As it turns out, there is a unique way to represent every positive integer as a finite decimal in base $\phi$ with no consecutive 11. These 2 requirements are known as standard form in base $\phi$ . The requirement of finite is needed because $1 = 0.101010\ldots _ \phi$ . The requirement of "no consecutive 1's" is needed since $11_\phi = 100 \phi$ .

The existence of a standard form for integers follows from Chung's argument of "eventually the 1's are spread out". In particular, we can conclude that the number of 1's is at most $n$ .

Uniqueness in standard form for integers follows from this argument:
Suppose that $N = \sum f_i \phi ^i = \sum g_i \phi ^ i$ are 2 different standard form representations of $N$ . Let $k$ be the largest power in which the coefficients differ, and without loss of generality, $f_k = 1, g_k = 0$ .
Claim: $\displaystyle \sum_{i < k} g_i \phi^i < \sum_{j=0}^{\infty} \phi^{k-1-2j} = \phi^k \leq \sum_{i \leq k } f_i \phi ^i$ .
The first inequality follows because no two consecutive ones appear, and the inequality is strict because of the finiteness condition.
This leads a contradiction, since $n = \sum g_i \phi^i < \sum f_i \phi^i = n$ .

Brian Charlesworth
Jan 20, 2017

We first note that, since $\phi \lt 2$ , we can only have a string of $0$ 's and $1$ 's for any number base $\phi$ . So we can only add at most one of each $\phi^{n}$ as calculated above. As $\phi^{-2}$ is the only such term that results in a subtraction of $\phi$ , we will not be able to add any combination of the presently calculated $\phi^{n}$ in order to get the desired "numeric" component of $5$ . So we will need to calculate further values of $\phi^{n}$ :

$\phi^{4} = (\phi^{2})^{2} = (\phi + 1)^{2} = \phi^{2} + 2\phi + 1 = 3\phi + 1$ ;
$\phi^{-4} = (\phi^{-2})^{2} = (-\phi + 2)^{2} = \phi^{2} - 4\phi + 4 = -3\phi + 5$ .

Now we can find a suitable combination, namely

$5 = (2\phi + 1) + (\phi - 1) + (-3\phi + 5) = \phi^{3} + \phi^{-1} + \phi^{-4} = \boxed{1000.1001}$ base $\phi$ .

@Chung Kevin This is an interesting question. I'm wondering about uniqueness, though, as we could also have, say,

$1 = (\phi - 1) + (2\phi - 3) + (-3\phi + 5) = \phi^{-1} + \phi^{-3} + \phi^{-4} = 0.1011$ ,

$2 = (\phi) + (2\phi - 3) + (-3\phi + 5) = \phi^{1} + \phi^{-3} + \phi^{-4} = 10.0011$ and

$3 = (\phi + 1) + (2\phi - 3) + (-3\phi + 5) = \phi^{2} + \phi^{-3} + \phi^{-4} = 100.0011$ .

which makes me wonder if we can't find other ways of expressing $5$ if we look at further $\phi^{n}$ . The posted answer may be unique, but I'm just not sure.

Brian Charlesworth - 4 years, 4 months ago

I have to add the condition that no consecutive 1's is allowed, because $11_\phi = 100 \phi$ .

With that, it becomes unique (according to Wikipedia ).

Chung Kevin - 4 years, 4 months ago

$4 = 101.01_\phi = \phi^2 + \phi^0 + \phi^{-2}$ .

The "trick" that I do to calculate each subsequent number, is to

Add 1 to the unit place.
If there is a 2, replace it with $10.01$ .
If there is a 11, replace it with $100$ .

Eventually, the 1's are spread out sufficiently, so that there isn't a 2 or a 11 in the sequence, and so we're done.

In the case of 4, we're just doing the first step $3 + 1 = 100.01_\phi + 1 _\phi = 101.01_\phi$ , which is why I didn't ask about 4.
In the case of 5, we get $4 + 1 = 101.01_\phi + 1_\phi = 102.01_\phi = 110.02_\phi = 110.1001_\phi = 1000.1001_\phi$ .

Chung Kevin - 4 years, 4 months ago

Great to know that there's a method. I was going at it rather haphazardly. I hadn't realized that all non-negative real numbers can be written in base $\phi$ using just $0$ 's and $1$ 's, (with no $11$ subsequences to guarantee uniqueness).

Brian Charlesworth - 4 years, 4 months ago

The requirement of finite is needed because $1 = 0.101010\ldots _ \phi$ . The requirement of "no consecutive 1's" is needed since $11_\phi = 100 \phi$ . These are the 2 requriements of standard form .

The existence of a standard form for integers follows from Chung's argument of "eventually the 1's are spread out".

Uniqueness in standard form for integers follows from this argument:
Suppose that $N = \sum f_i \phi ^i = \sum g_i \phi ^ i$ are 2 different standard form representations of $N$ . Let $k$ be the largest power in which the coefficients differ, and without loss of generality, $f_k = 1, g_k = 0$ .
Claim: $\sum_{i < k} g_i \phi^i < \sum_{j=0}^{\infty} \phi^{k-1-2j} = \phi^k \leq \sum_{i \leq k } f_i \phi ^i$ .
The first inequality follows from no two consecutive ones appear, and the inequality is strict because of the finiteness condition. This leads a contradiction, since these representations are not equal.

Calvin Lin Staff - 4 years, 4 months ago

I typed in answer as 1000.1001, it corrected itself to 1000.1, this question requires precision.

Siva Bathula - 4 years, 4 months ago

Anirudh Sreekumar
Jan 20, 2017

we have, $\phi^{3}+2\phi^{-2}=5$

also we know that, $\phi^{1}+\phi^{-2}=2$ (given)

substituting for 2 we get,

$\phi^{3}+(\phi^{1}+\phi^{-2})\phi^{-2}=5$

thus we get $\phi^{3}+\phi^{-1}+\phi^{-4}=5=\boxed{1000.1001}_\phi$

Your first line. Is it true? Where do you get this from?

Aviel Livay - 4 years, 3 months ago

The information that $\phi^{3}=2\phi+1$ and $\phi^{-2}=-\phi+2$ is provided in the question

multiplying the second equation by 2 and adding to the first we get

$\phi^{3}+2\phi^{-2}=5$

Anirudh Sreekumar - 4 years, 3 months ago

Aviel Livay
Mar 6, 2017

$2=10.01_\phi$ actually means $2=\phi+\frac{1}{\phi^2}$
$3=100.01_\phi$ actually means $3={\phi}^2+\frac{1}{\phi^2}$
Let's multiply these two
$6=(\phi+\frac{1}{\phi^2})(\phi^2+\frac{1}{\phi^2})=\phi^3+\frac{1}{\phi}+1+\frac{1}{\phi^4}$
So
$5=\phi^3+\frac{1}{\phi}+\frac{1}{\phi^4}$
Which means
$\boxed{1000.1001_\phi}$

Golden Ratio Base

The answer is 1000.1001.

4 solutions

Moderator note:

0 pending reports