#!/usr/bin/env python
### wander6 -- more about Jim Propp's 2008.04.09 question
# Follow the rounding rule.
# a[t][0] accumulates stuff that falls off the left.
# This one saves the whole table from computing each f(n)
# and then just increments one element per row for f( n + 1 ).
# (Occasionally expand by two rows.)
#
# n   round( n/3 )   round( 2n/3 )
# 1         0            * 1 *
# 2       * 1 *            1
# 3         1            * 2 *
# 4         1            * 3 *
# 5       * 2 *            3
# 6         2            * 4 *
# etc.          

from math import log, ceil

def pr_row( a, fmt ):
    print fmt % a[0],
    for x in a[ 1: ]:
        if x == 0: print "",
        else:      print str( x ),
    print

def pr_table( a ):
    nd = int( ceil( log( a[0][1] ) / log(10) ) )
    fmt = "%" + str(nd) + "d|"
    for row in a:
        pr_row( row, fmt )


a = [ [ 0, 1 ] ]  # Finished state for n = 1


def f( n ):
    global a

    danger = -1
    i = 1
    for t in range( len( a ) ):
        a[ t ][ i ] += 1
        if i > 0:
            if a[ t ][ i ] % 3 == 2:
                i -= 1
            else:
                i += 1
    while a[ t ][ 1 ] > 1:
        for t in range( t + 1, t + 3 ):
            a.append( [ a[t-1][0] ] + [0] * len( a[t-1] ) )
            for j in range( 1, len( a[t-1] ) ):
                a[t][ j-1 ] += int( round( a[t-1][j] * 1.0 / 3.0 ) )
                a[t][ j+1 ] += int( round( a[t-1][j] * 2.0 / 3.0 ) )

    if danger > 0  and  danger < len(a):
        increased( dt, di )

    return n - a[ t ][ 0 ],  t


mn = mx = 0
nlt, neq, ngt = 0, 0, 1
print "         n  f(n)-n/2  T(n)  f(n)<n/2   f(n)==n/2    f(n)>n/2  % < n/2",
sn, sfn, sfnon = 0.0, 0.0, 0.0
print "  sum(f(n))/sum(n)"
# "   sum(f) - sum(n)/2"
for n in xrange( 2, 200000000 ):
    y, time = f(n)
    y = float( y )
    sn += n
    sfn += y
    sfnon += ( y / n )
    x = y - ( n * .5 )
    if x > 0:    ngt += 1
    elif x == 0: neq += 1
    else:        nlt += 1
    if x < mn  or  x > mx:
        print "%10d" % n, "%+7.1f  " % x, "%4d" % time, 
        print "%10d" % nlt, "%10d" % neq, "%10d" % ngt, 
        print "%9.3f%%" % (100.0*nlt/n),
        # "%18.16f" % (sfnon/n),
        print "%18.16f" % (sfn/sn)
        # "%+13.1f" % (sfn - sn*.5)
    if x < mn:
        mn = x
    elif x > mx:
        mx = x