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
My first step was to simplify the calculation of powers of Phi, which can all be written in the form (a + b*sqrt(5))/2, or represented as a list [a,b]. I first put these into a dictionary so that powers of Phi can be looked up if they have already been calculated. Here is a sample of the dictionary:
{
-5: [-11, 5],
-4: [7, -3],
-3: [-4, 2],
-2: [3, -1],
-1: [-1, 1],
0: [2, 0], (Phi^0 = (2+0*sqrt(5))/2 )
1: [1, 1],
2: [3, 1],
3: [4, 2],
4: [7, 3], (Phi^4 = (7+3*sqrt(5))/2 )
5: [11, 5]
}
Notice that the 'a' values and 'b' values follow a Fibonacci pattern, the b's being actual Fibonacci sequence and the a's starting with different initial seed values. What I didn't expect was that this pattern continues into the negative powers of Phi.
Function powerPhi(n) (code below) returns the n-th power of Phi.
Function basePhi(n) returns a string of 1's and 0's representing decimal number n as it would appear in base Phi. In general, for larger numbers, this will have an further continuation to the right after the decimal point, which I have defaulted to 10 places.
Some examples:
0 0
1 1.0000000000
2 10.0100000000
3 100.0100000000
4 101.0100000000
5 1000.1001000000
6 1010.0001000000
7 10000.0001000000
8 10001.0001000000
9 10010.0101000000
10 10100.0101000000
11 010101.0101000000
12 100000.1010010000
13 100010.0010010000
14 100100.0010010000
15 100101.0010010000
16 101000.1000010000
17 0101010.0000010000
18 1000000.0000010000
19 1000001.0000010000
20 1000010.0100010000
21 1000100.0100010000
22 1000101.0100010000
23 1001000.1001010000
24 1001010.0001010000
100 1001001010.0001001001
1000 100010010001000.1000100101
10000 10000010010000010000.0001000000
100000 0101010001010100000100000.1010001010
But n need not be an integer, and further precision can be calculated, for example here is the square root of 2, to 30 places in base Phi:
basePhi(2**.5,precision = 30)
'1.010000010100101001000000010100'
------ Python code ------
p = (1+5**.5)/2
import math
phi_power_dictionary = {0:[2,0],1:[1,1],-1:[-1,1]} # just to start
def powerPhi(n):
""" return the n-th power of Phi, use a dictionary
but first, build Phi Power Dictionary up to key = n if needed """
largest_key = max(phi_power_dictionary.keys())
if largest_key < abs(n):
if n < 0:
powerPhi(-n)
for i in range(largest_key+1, n+1):
a=phi_power_dictionary[i-2][0] + phi_power_dictionary[i-1][0]
b=phi_power_dictionary[i-2][1] + phi_power_dictionary[i-1][1]
phi_power_dictionary[i] = [a,b]
phi_power_dictionary[-i] = [a*(-1)**i,b*(-1)**(i+1)]
x = phi_power_dictionary[n]
return (x[0] + x[1]*5**.5)/2
def basePhi(n, p = (1+5**.5)/2, precision = 10):
""" n is a base 10 integer; output it in base Phi """
if n == 0:
return 0
less_than_p = int(p*10)/10 # e.g. 1.6 if p = Phi
upper_bound = int(math.log(n,less_than_p)) + 1
ans = ''
for i in reversed(range(-precision, upper_bound)):
digit = int(n//powerPhi(i))
n = n - digit * powerPhi(i)
ans += str(digit)
if i == 0:
ans += '.'
return (ans)
|
|
Posted by Larry
on 2022-01-27 10:35:10 |
Solution
