[I get the digest so forgive me if Jim has reported this already.] The smallest n where f(n) < n/2 is 5495. Here are the record-breakers for f(n)-n/2 that I've computed so far: n f(n)-n/2 T(n) (see below) 3 +0.5 2 4 +1.0 2 13 +1.5 4 40 +2.0 8 43 +2.5 8 124 +3.0 14 181 +3.5 16 622 +4.0 26 1435 +4.5 34 1882 +5.0 36 4225 +5.5 44 5495 -0.5 48 <-- 8992 +6.0 52 12343 +6.5 56 19108 +7.0 62 24632 -1.0 66 24713 -1.5 66 31891 +7.5 68 71968 +8.0 78 71971 +8.5 78 152990 -2.0 88 153017 -2.5 88 288568 +9.0 96 288577 +9.5 96 549512 -3.0 106 549513 -3.5 106 665470 +10.0 108 1575895 +10.5 120 1575898 +11.0 120 2850236 -4.0 128 2851713 -4.5 128 9440910 -5.0 146 10034029 +11.5 146 10038334 +12.0 146 16214491 +12.5 154

From: James Propp <jpropp@cs.uml.edu>

(1) How big can |f(n) - n/2| be? I suspect it's O(log n). (For n up through 500, f(n) - n/2 ranges between 0 and 7/2.)

It looks sort of log like, but if you graph those numbers above, there are very piecewise-linear features, which doesn't make me confident I know what it's doing. f(n)-n/2 is like a moving slice on the far tail of a growing, skewed bell curve.

(3) What's the best way to compute f(n)? It would be good to know ahead of time two numbers L(n) and T(n) such that if you replace the infinite one-dimensional lattice {1,2,3,...} by the finite interval {1,2,3,...,L(n)} and run the arithmetic rule for T(n) steps, with particles that leave 1 going leftward being absorbed at 0 and particles that leave L(n) going rightward being ignored, then f(n) is just n minus the number of particles that have been absorbed at 0 by time T(n).

T(n), the time step where you should stop, is easy to see as you compute. It's the point where the population at lattice point 1 reaches 1. Once initially colonized (& skipping every other time step), (I believe but haven't proven) a lattice point's population never increases again. So once point 1 reaches 1, it will never drop particles to the left again. The third column of numbers above shows T(n). It's log-like starting at n ~= 3000, but it might be line segments approximating log^2. L(n) is how wide to make the rows. Once you've cut back the number of rows drastically, making L(n) < T(n) doesn't help much, maybe a factor of two. But the best speedup is to keep the 2D table between calculations. The change between calculating f(n) and f(n+1) is to increment one entry on each row. Here's the inner loop in Python: i = 1 # Column 0 absorbs particles. for t in range( len(A) ): # for each row A[ t ][ i ] += 1 if i > 0: # Once in column 0, stay there. if A[ t ][ i ] % 3 == 2: i -= 1 else: i += 1 # Once at the bottom you occasionally need to add two rows. So successive visits to a 2D point go down to the right, next time left, next time right; right, left, right, etc. It's a rounder-router! Guess you can do the whole calculation by keeping each count mod 3. Might be nice to plot in color. --Steve