Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Golden Strings and the Rabbit Constant

DZone's Guide to

Golden Strings and the Rabbit Constant

· Big Data Zone ·
Free Resource

Hortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.

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.


Hortonworks Community Connection (HCC) is an online collaboration destination for developers, DevOps, customers and partners to get answers to questions, collaborate on technical articles and share code examples from GitHub.  Join the discussion.

Topics:

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}