Big Data/Analytics Zone is brought to you in partnership with:

John Cook is an applied mathematician working in Houston, Texas. His career has been a blend of research, software development, consulting, and management. John is a DZone MVB and is not an employee of DZone and has posted 172 posts at DZone. You can read more from them at their website. View Full User Profile

Golden Strings and the Rabbit Constant

07.24.2013
| 2265 views |
  • submit to reddit

Golden strings are analogous to Fibonacci numbers, except one uses concatenation rather than addition.

Start with s1 = “1″ and s2 = “10″. Then define sn = sn-1 + sn-2 where “+” means string concatenation.

The first few golden strings are

  • “1″
  • “10″
  • “101″
  • “10110″
  • “10110101″

The length of sn is Fn+1, the n+1st Fibonacci number. Also, sn contains Fn-1 1′s and Fn-2 0′s. (Source: The Glorious Golden Ratio).

If we interpret the sn as the fractional part of a binary number, the sequence converges to the rabbit constant R = 0.7098034428612913…

It turns out that R is related to the golden ratio φ by

R = \sum_{i=1}^\infty 2^{-\lfloor i \phi \rfloor}

where ⌊i φ⌋ is the largest integer no greater than iφ.

Here’s a little Python code to print out the first few golden strings and an approximation to the rabbit constant.

from sympy.mpmath import mp, fraction
 
a = "1"
b = "10"
for i in range(10):
    b, a = b+a, b
    print(b)
 
n = len(b)
mp.dps = n
denom = 2**n
num = int(b, 2)
 
rabbit = fraction(num, denom)
print(rabbit)

Note that the code sets the number of decimal places, mp.dps, to the length of the string b. That’s because it takes up to n decimal places to exactly represent a rational number with denominator 2n.


Published at DZone with permission of John Cook, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)