## Thursday, July 3, 2014

### More Pretty Math Patterns: Spiral Fibonaci Strings

You may have heard of the Fibonacci numbers:
f0=0, f1=1 and fn=f(n-1) + f(n-2), so that the numbers are:

0,1,1,2,3,5,8....   (you add the last two numbers to get the next.  the next one will be 13)

There are tons of fun facts about these critters.

Today I saw something similar - Fibonacci strings:
f0='0', f1='1' and fn = f(n-1) concatenated with f(n-2), so the strings are:

'0', '1', '10', '101', '10110', '10110101',  ,...

(you tack the second to last string at the end of the last string to get the next.  the next one is '1011010110110'.   This can be extended as long as we like.

When i saw this I immediately decided I wanted to plot it in a spiral, don't ask me why...

So the spiral would start from a '1' at the center, then a '0' to the right and then up and counterclockwise:
011
110
01...

here is a plot for the Fibonacci string large enough to fill an 11x11 plot (I filled in the ones and zeros in the center where it starts)
That's weird... doesn't seem to be any pattern.  I didn't really expect one either!  lets try a bigger plot with more of the string:

Well, that's curious, more:

Seems to be two kinds of regions..
Now we see some kind of pattern
It's a metaspiral on the spiral, very weird.  Does it continue?

Apparently it does.  I have no clue why this happens, it will bear some careful observation and thinking!  The length of the Fibonacci string grows exponentially, the length of one trip around the spiral grows...

1
8=1+1+1+1+4
3+3+3+3+4=16
5+5+5+5+4=24

so it grows by 8 each time.  That's linear.  I don't see why they match up in such a curious fashion!

UPDATE:
i drew some lines and did some counting:

here is a smaller region:

Look at the metaspirals bands on the right.  focus on the ones made up of mostly horizontal rows of dots.  I will find out how far apart they are.  notice in some places the horizontal row of dots is only two long.  i will count how many spiral lines between these.

there are 18.  this is consistent in the bigger pic too.

now each spiral grows by 8 squares as it comes around.  so the first spiral of any metaspiral band is 8*18 squares longer than the first spiral of the previous band.  8*18=144 which is the 12th fibonacci number.

THIS is a CLUE.  though i'm still clueless about what is going on!

For those of you curious about my computer code, here it is in python:

` `

#first create the Fibonacci string:
fs=['0','1']
while len(fs[-1]) < 1000000:
fs.append(fs[-1]+fs[-2])
fs=fs[-1]  #choose the last string produced

#now create an image of the spiral with this string:
def make_fib_sp(N, px, fname, fibstr):
"""make_fib_sp(N, px, fname, fibstr) -- create an image file fname
(give it an extension like .jpg or .png...)
of a pattern of pixels based on starting from the
center of the image and working one pixel around in a
spiral based on the mapping with the fibonacci string fibstr:
f0='0',f1='1', fn+1=fn concat fn-1
look at a fibonacci string long enough to fill an NxN square
and around the spiral draw black if 1 and white if 0
uses Image library and spriral
px is the number of pixels in the image to make each square"""
from PIL import Image  #python image library
bkgr=(255,255,255); pts=(0,0,0)  #background is white, pts are black
img=Image.new('RGB',(N*px,N*px),bkgr) #create an Image object
pix=img.load()  # this is for fast construction of image
idx=0
ctr=N//2
#I iterate over the coordinates given by my spiral generator
for x,y in mf.spiral(ctr, ctr, lambda x,y,xs,ys:
abs(x-xs)>=ctr-1):
#because spiral stops sloppily...
if x<0 or="" x="">=N or y<0 or="" y="">=N:
break
if fibstr[idx]=='1': #draw a black pixel
xp=x*px; yp=y*px
for i in xrange(px):  #fill the square in as px X px pixels
for j in xrange(px):
pix[xp+i,yp+j]=pts
idx+=1
img.save(fname)

def spiral(x,y,exit_fun):
"""spiral(x,y, exit_fun) -
lazily return coordinates in a spiral path starting
from (x,y) then to (x+1,y), (x+1,y-1) etc...
counterclockwise until exit_fun(x,y,xs,ys) is true
xs,ys are the initial center coords
NOTE tests exit function only ONCE around the
spiral so exit_fun should use < or > rather than ==
as an exact value in each round might be missed.
since the spiral goes around with smaller and bigger
values, it's best to use some version of
abs(x-xs) for exit_fun getting it to stop where you
want is subtle"""
incs=2
xs,ys=x,y
if not exit_fun(x,y,xs,ys):
yield x,y
while not exit_fun(x,y,xs,ys):
x+=1; yield x,y
for i in range(incs-1):
y-=1; yield x,y
for i in range(incs):
x-=1; yield x,y
for i in range(incs):
y+=1; yield x,y
for i in range(incs):
x+=1; yield x,y
incs+=2