import math

class Circle:
    def __init__(self, radius):
        self.radius = radius
        self.contents = []  # [Placement]

    def add(self, circle, pos):
        self.contents.append(Placement(circle, pos))

class Placement:
    def __init__(self, circle, pos):
        self.circle = circle
        self.pos = pos

# make 0 and 1
cache = {0: Circle(.5), 1: Circle(1.)}
cache[1].add(cache[0], (-.5, 0))

def make(n):
    if n in cache:
        return cache[n]

    a = make(n - 1)
    b = make(n - 2)
    z = Circle(a.radius + b.radius)
    z.add(a, (-b.radius, 0))
    z.add(b, (a.radius, 0))

    if n - 3 >= 0:
        c = make(n - 3)
        p = getnestpos(a, b, c)
        z.add(c, p)

        nest(z, n - 4, b, a)

    cache[n] = z
    return z

def nest(z, n, a, b, recurse=True):
    if n >= 0:
        ap = bp = None
        for q in z.contents:
            if q.circle is a:
                ap = q
            if q.circle is b:
                bp = q
        assert ap and bp, 'failed to find ap and bp'

        c = make(n)
        p = getnestpos(a, b, c, ap, bp)
        z.add(c, p)

        if recurse:
            nest(z, n - 1, a, c, recurse=False)
            nest(z, n - 2, c, b)

def getnestpos(a, b, c, ap=None, bp=None):
    # use law of cosines to get angle between a->b and a->c
    p = a.radius ** 2 + a.radius * b.radius + a.radius * c.radius
    angle = math.acos((p - b.radius * c.radius) / (p + b.radius * c.radius))
    # find the vector a->c
    x = (a.radius + c.radius) * math.cos(angle) - b.radius
    y = (a.radius + c.radius) * math.sin(angle)

    if ap and bp:
        # place the vector correctly
        vx = bp.pos[0] - ap.pos[0]
        vy = bp.pos[1] - ap.pos[1]
        angle = math.atan2(vy, vx)
        vmag = math.hypot(vx, vy)
        vx -= a.radius * vx / vmag
        vy -= a.radius * vy / vmag

        x, y = (
            ap.pos[0] + vx + x * math.cos(angle) - y * math.sin(angle),
            ap.pos[1] + vy + x * math.sin(angle) + y * math.cos(angle)
        )

    return (x, y)

def getcolor(v,t):
    p = float(v)/float(t)
    i = int(p*150)+50
    return "rgb(%d,%d,%d)" % (i,i,i)

def printsvg(c, pos,m):
    print '<circle cx="%f" cy="%f" r="%f" fill="%s" />' % (zoom * pos[0], zoom * pos[1], zoom * c.radius, getcolor(len(c.contents),m))
    for p in c.contents:
        printsvg(p.circle, (pos[0] + p.pos[0], pos[1] + p.pos[1]),m)

zoom = 5
total = 15
c = make(total)

size = zoom * c.radius * 2
print '<svg xmlns="http://www.w3.org/2000/svg" width="%f" height="%f">' % (size, size)
printsvg(c, (c.radius, c.radius),total)
print '</svg>'