Devise an algorithm for writing any positive base ten integer in base φ number system.
**** φ, called the Golden Ratio is a positive real number equal to (1+√5)/2
The base is less than 2. We can use only digits 0 and 1, otherwise there'd be two or more ways of writing some numbers. As phi is irrational, even integers, beyond 1, will usually have infinite sequences of digits.
1 of course is 1.
We'll find the base-phi digits one by one from left to right, which is the opposite of what we do with integers, where we divide by the base and keep track of the remainders. In the case of phi, this would get messy.
Take the floor of the base-phi logarithm of the integer under consideration. Call this floor of the logarithm q. Then subtract phi^q from the original number; this difference will always be 1, the first digit of the base-phi representation. The phi^q tells you how much of the original number remains to be accounted for.
Then successively apply the above portion of the algorithm to the successive remainders. The logarithms will always be 1, but there will be occasions when the next q (base-phi log) will not be the next lower integer, but will skip a few. In this case append as many zeros as integers skipped between the old q and the new q. (I call it q as its the quotient between the base-10 or base-e log of the number and that same base log of phi, to do the base conversion on the log.)
At the point where you are inserting a 1 for q=0, or the zero that represents what q would have been zero for one of the skipped q's, insert a radix point immediately after that 1 or 0.
Take an example of conversion of 3 to base-phi, which terminates, as do all integers 4 or less:
Base-phi log of 3 = 2.28301182858928
q is 2
phi^2 = 2.618033988749895
3 - phi^2 = .3819660112501051 1
base-phi log(.3819660112501051) = -2
add zeros for q=1 and zero 100
add radix point 100.
add zero for q = -1 100.0
add the 1 for q = -2 100.01
check:
1*phi^2 + 1/phi^2 = 3
In practice:
phi=(1+sqrt(5))/2;
limDig=72;
for n=1:11
rep='';
num=n;
q=log(num)/log(phi);
if abs(round(q)-q)<.000000000001
q=round(q);
else
q=floor(q);
end
d=floor(num/phi^q);
num=num-d*phi^q;
rep=[rep char(string(d)) ];
prevq=q;
for i=1:limDig
if num==0
break
end
q=floor(log(num)/log(phi));
d=floor(num/phi^q);
rep=[rep char(string(d)) ];
if q==0
rep=[rep '.'];
end
num=num-d*phi^q;
if num==0
break
end
prevq=q;
if length(rep)>limDig
break
end
end
disp([char(string(n)) ' ' ' ' rep])
end
1 1
2 10.0011
3 100.0011
4 101.0011
5 1000.100010101010101010101010101010101010101010101010101010101010101010101
6 1010.000010101010101010101010101010101010101010101010101010101010101010101
7 10000.0000101010101010101010101010101010101010101010101010101010101010101
8 10001.0000101010101010101010101010101010101010101010101010101010101010101
9 10010.0100101010101010101010101010101010101010101010101010101010101010101
10 10100.0100101010101010101010101010101010101010101010101010101010101010101
11 10101.0100101010101010101010101010101010101010101010101010101010101010101
Notice for decimal 3 it shows 100.0011, rather than the 100.01 we had found and confirmed.
The difference was a slight rounding error in determining whether floor(base-phi log(.3819660112501051)) is -2 or -3. When we did it manually we saw it as exactly -2 without the need to adjust to the floor. The internal calculation had it slightly lower so the mechanical floor was considered -3. But this was a rounding error. The figure should have been exactly -2; the slight rounding error made it seem its floor would be -3, upsetting the whole calculation.
The fix was to change both occurrences of
q=floor(log(num)/log(phi));
to
q=log(num)/log(phi);
if abs(round(q)-q)<.0000000000000001
q=round(q);
else
q=floor(q);
end
Now, for the first 50 positive integers:
1 1
2 10.0011
3 100.0011
4 101.0011
5 1000.100010101010101010101010101010101010101010101010101010101010101010101
6 1010.000010101010101010101010101010101010101010101010101010101010101010101
7 10000.0000101010101010101010101010101010101010101010101010101010101010101
8 10001.0000101010101010101010101010101010101010101010101010101010101010101
9 10010.0100101010101010101010101010101010101010101010101010101010101010101
10 10100.0100101010101010101010101010101010101010101010101010101010101010101
11 10101.0100101010101010101010101010101010101010101010101010101010101010101
12 100000.1010001010101010101010101010101010101010101010101010101010101010101
13 100010.0010001010101010101010101010101010101010101010101010101010101010101
14 100100.0010001010101010101010101010101010101010101010101010101010101010101
15 100101.0010001010101010101010101010101010101010101010101010101010101010101
16 101000.1000001010101010101010101010101010101010101010101010101010101010101
17 101010.0000001010101010101010101010101010101010101010101010101010101010101
18 1000000.00000010101010101010101010101010101010101010101010101010101010101
19 1000001.00000010101010101010101010101010101010101010101010101010101010101
20 1000010.01000010101010101010101010101010101010101010101010101010101010101
21 1000100.01000010101010101010101010101010101010101010101010101010101010101
22 1000101.01000010101010101010101010101010101010101010101010101010101010101
23 1001000.10010010101010101010101010101010101010101010101010101010101010101
24 1001010.00010010101010101010101010101010101010101010101010101010101010101
25 1010000.00010010101010101010101010101010101010101010101010101010101010101
26 1010001.00010010101010101010101010101010101010101010101010101010101010101
27 1010010.01010010101010101010101010101010101010101010101010101010101010101
28 1010100.01010010101010101010101010101010101010101010101010101010101010101
29 1010101.01010010101010101010101010101010101010101010101010101010101010101
30 10000000.10101000101010101010101010101010101010101010101010101010101010101
31 10000010.00101000101010101010101010101010101010101010101010101010101010101
32 10000100.00101000101010101010101010101010101010101010101010101010101010101
33 10000101.00101000101010101010101010101010101010101010101010101010101010101
34 10001000.10001000101010101010101010101010101010101010101010101010101010101
35 10001010.00001000101010101010101010101010101010101010101010101010101010101
36 10010000.00001000101010101010101010101010101010101010101010101010101010101
37 10010001.00001000101010101010101010101010101010101010101010101010101010101
38 10010010.01001000101010101010101010101010101010101010101010101010101010101
39 10010100.01001000101010101010101010101010101010101010101010101010101010101
40 10010101.01001000101010101010101010101010101010101010101010101010101010101
41 10100000.10100000101010101010101010101010101010101010101010101010101010101
42 10100010.00100000101010101010101010101010101010101010101010101010101010101
43 10100100.00100000101010101010101010101010101010101010101010101010101010101
44 10100101.00100000101010101010101010101010101010101010101010101010101010101
45 10101000.10000000101010101010101010101010101010101010101010101010101010101
46 10101010.00000000101010101010101010101010101010101010101010101010101010101
47 100000000.000000001010101010101010101010101010101010101010101010101010101
48 100000001.000000001010101010101010101010101010101010101010101010101010101
49 100000010.010000001010101010101010101010101010101010101010101010101010101
50 100000100.010000001010101010101010101010101010101010101010101010101010101
...
194 10101001010.0001010100101010101010101010101010101010101010101010101010101
Take 4 as an example:
Base-phi, it's 101.01.
1*phi^2 + 1*phi^0 + 1/phi^2 = 4
numbers above are carried out to 72 places, as decimal accuracy of double precision numbers is 15+ decimial digits, and 15*log(10)/log(phi) is 71.77....
and, for example 194, using the positional values of the 1's:
>> phi^10+phi^8+phi^6+phi^3+phi
ans =
193.768957021241
>> ans+1/phi^4+1/phi^6+1/phi^8+1/phi^10+1/phi^12+1/phi^14+1/phi^16
ans =
194.004744965159
>> phi^10+phi^8+phi^6+phi^3+phi
ans =
193.768957021241
>> ans+1/phi^4+1/phi^6+1/phi^8+1/phi^10+1/phi^12+1/phi^14+1/phi^16
ans =
194.004744965159
>> phi^10+phi^8+phi^6+phi^3+phi
ans =
193.768957021241
>> ans+1/phi^4+1/phi^6+1/phi^8+1/phi^11+1/phi^13+1/phi^15+1/phi^17
ans =
193.999826929728
>> ans+1/phi^19+1/phi^21+1/phi^23+1/phi^25+1/phi^27+1/phi^29
ans =
193.99999946251
>> ans+1/phi^31+1/phi^33+1/phi^35+1/phi^37+1/phi^39+1/phi^41
ans =
193.999999998331
It does seem that most, after 46, settle down to an infinite stream of alternating 1's and 0's.
Later:
Googling base phi leads to a Wikipedia article indicating that the beginning of 10101... can be replaced by a 1 in the previous position, just like 99999... in decimal can do the same. That's just what appears in the case of 194 above, but using extended precision: 194 as 10101001010.0001010101 would be exact:
phi^10+phi^8+phi^6+phi^3+phi^1+phi^-4+phi^-6+phi^-8+phi^-10 = 194
1 1
2 10.01
3 100.01
4 101.01
5 1000.1001
6 1010.0001
7 10000.0001
8 10001.0001
9 10010.0101
10 10100.0101
11 10101.0101
12 100000.101001
13 100010.001001
14 100100.001001
15 100101.001001
16 101000.100001
17 101010.000001
18 1000000.000001
19 1000001.000001
20 1000010.010001
21 1000100.010001
22 1000101.010001
23 1001000.100101
24 1001010.000101
25 1010000.000101
26 1010001.000101
27 1010010.010101
28 1010100.010101
29 1010101.010101
30 10000000.10101001
31 10000010.00101001
32 10000100.00101001
33 10000101.00101001
34 10001000.10001001
35 10001010.00001001
36 10010000.00001001
37 10010001.00001001
38 10010010.01001001
39 10010100.01001001
40 10010101.01001001
41 10100000.10100001
42 10100010.00100001
43 10100100.00100001
44 10100101.00100001
45 10101000.10000001
46 10101010.00000001
47 100000000.00000001
48 100000001.00000001
49 100000010.01000001
50 100000100.01000001
51 100000101.01000001
52 100001000.10010001
53 100001010.00010001
54 100010000.00010001
55 100010001.00010001
56 100010010.01010001
57 100010100.01010001
58 100010101.01010001
59 100100000.10100101
60 100100010.00100101
61 100100100.00100101
62 100100101.00100101
63 100101000.10000101
64 100101010.00000101
65 101000000.00000101
66 101000001.00000101
67 101000010.01000101
68 101000100.01000101
69 101000101.01000101
70 101001000.10010101
71 101001010.00010101
72 101010000.00010101
73 101010001.00010101
74 101010010.01010101
75 101010100.01010101
76 101010101.01010101
77 1000000000.1010101001
78 1000000010.0010101001
79 1000000100.0010101001
80 1000000101.0010101001
81 1000001000.1000101001
82 1000001010.0000101001
83 1000010000.0000101001
84 1000010001.0000101001
85 1000010010.0100101001
86 1000010100.0100101001
87 1000010101.0100101001
88 1000100000.1010001001
89 1000100010.0010001001
90 1000100100.0010001001
91 1000100101.0010001001
92 1000101000.1000001001
93 1000101010.0000001001
94 1001000000.0000001001
95 1001000001.0000001001
96 1001000010.0100001001
97 1001000100.0100001001
98 1001000101.0100001001
99 1001001000.1001001001
100 1001001010.0001001001
101 1001010000.0001001001
102 1001010001.0001001001
103 1001010010.0101001001
104 1001010100.0101001001
105 1001010101.0101001001
106 1010000000.1010100001
107 1010000010.0010100001
108 1010000100.0010100001
109 1010000101.0010100001
110 1010001000.1000100001
111 1010001010.0000100001
112 1010010000.0000100001
113 1010010001.0000100001
114 1010010010.0100100001
115 1010010100.0100100001
116 1010010101.0100100001
117 1010100000.1010000001
118 1010100010.0010000001
119 1010100100.0010000001
120 1010100101.0010000001
121 1010101000.1000000001
122 1010101010.0000000001
123 10000000000.0000000001
124 10000000001.0000000001
125 10000000010.0100000001
126 10000000100.0100000001
127 10000000101.0100000001
128 10000001000.1001000001
129 10000001010.0001000001
130 10000010000.0001000001
131 10000010001.0001000001
132 10000010010.0101000001
133 10000010100.0101000001
134 10000010101.0101000001
135 10000100000.1010010001
136 10000100010.0010010001
137 10000100100.0010010001
138 10000100101.0010010001
139 10000101000.1000010001
140 10000101010.0000010001
141 10001000000.0000010001
142 10001000001.0000010001
143 10001000010.0100010001
144 10001000100.0100010001
145 10001000101.0100010001
146 10001001000.1001010001
147 10001001010.0001010001
148 10001010000.0001010001
149 10001010001.0001010001
150 10001010010.0101010001
151 10001010100.0101010001
152 10001010101.0101010001
153 10010000000.1010100101
154 10010000010.0010100101
155 10010000100.0010100101
156 10010000101.0010100101
157 10010001000.1000100101
158 10010001010.0000100101
159 10010010000.0000100101
160 10010010001.0000100101
161 10010010010.0100100101
162 10010010100.0100100101
163 10010010101.0100100101
164 10010100000.1010000101
165 10010100010.0010000101
166 10010100100.0010000101
167 10010100101.0010000101
168 10010101000.1000000101
169 10010101010.0000000101
170 10100000000.0000000101
171 10100000001.0000000101
172 10100000010.0100000101
173 10100000100.0100000101
174 10100000101.0100000101
175 10100001000.1001000101
176 10100001010.0001000101
177 10100010000.0001000101
178 10100010001.0001000101
179 10100010010.0101000101
180 10100010100.0101000101
181 10100010101.0101000101
182 10100100000.1010010101
183 10100100010.0010010101
184 10100100100.0010010101
185 10100100101.0010010101
186 10100101000.1000010101
187 10100101010.0000010101
188 10101000000.0000010101
189 10101000001.0000010101
190 10101000010.0100010101
191 10101000100.0100010101
192 10101000101.0100010101
193 10101001000.1001010101
194 10101001010.0001010101
195 10101010000.0001010101
196 10101010001.0001010101
197 10101010010.0101010101
198 10101010100.0101010101
199 10101010101.0101010101
200 100000000000.101010101001
Those 10101's sound like the beginnings of an infinite set but they are not.
|
|
Posted by Charlie
on 2022-01-27 11:42:35 |
my take on it
