# Why are the numbers counting "ever-closer" lattice paths so round?

Let $$u(i,j)$$ denote the number of lattice paths from the origin to a fixed terminal point $$(i,j)$$ subject only to the condition that each successive lattice point on the path is closer to $$(i,j)$$ than its predecessor. For example, $$u(1,1) = 5$$ counts the one-step path $$(0,0) \to (1,1)$$ and the 4 two-step paths with lone interior point (1,0), (0,1), (2,1), and (1,2) respectively, each of which points is just 1 unit from (1,1) while the origin is at distance $$\sqrt{2}$$. By symmetry, $$u(i,j)=u(j,i)$$ and $$u(i,j)=u(\pm i, \pm j)$$. So we may assume $$0\le j \le i$$.

The numbers $$u(i,j)$$ grow rapidly but have only small prime factors. For example, $$u(15,4)=269124680144389687575008665117965469864474632630636414714548567937\\ 47381916046142578125 =3^{114}\ 5^{19}\ 13^6\ 17^9.$$

Any explanations? Have these paths been considered in the literature?

Here is Mathematica code to generate $$u(i,j)$$.

addListToListOfLists[ls_,lol_] := (ls + #1 &) /@ lol

Flatten[Table[m = Ceiling[Sqrt[radius^2 - i^2]] - 1;

u[i_,j_] := u[{i,j}];
u[{0,0}] = 1;
u[{i_,j_}] /; j > i := u[{i,j}] = u[{j,i}];
u[{i_,j_}] /; i < 0 := u[{i,j}] = u[{-i,j}];
u[{i_,j_}] /; j < 0 := u[{i,j}] = u[{i,-j}];
u[{i_,j_}] /; 0 <= j <= i := u[{i,j}] =
cntFromNewOrigin[newOrigin_] := u[{i,j} - newOrigin];
Apply[Plus, Map[cntFromNewOrigin,

In[918]:= Table[ u[{i,j}],{i,0,3},{j,0,i}]

Out[918]= {{1}, {1, 5}, {25, 125, 1125}, {5625, 28125, 253125,
102515625}}

• "closer" in what metric? Taxicab? Euclidean? Nov 12 at 21:29
• @Wojowu: if you read the $u(1,1)$ example you will see Euclidean distance is intended. Nov 12 at 21:33
• @SamHopkins Good catch. I didn't read it thoroughly, and apart from the mention of the distance this example works in either metric. Nov 12 at 21:44

For any $$k\in\mathbb N$$ let $$a_k$$ be the number of points on the circle of radius $$\sqrt{k}$$ (this number may be zero). For any path as in question and for any $$k$$ between $$1$$ and $$i^2+j^2-1$$, there is going to be either none or exactly one of the points on the circle of radius $$\sqrt{k}$$ around $$(i,j)$$. As the sequence of points determines the path, this tells us that the number of possible such paths is $$\prod_{k=1}^{i^2+j^2-1}(1+a_k).$$ This is a product of comparatively large number of factors, each of which is small: we easily see $$a_k<4k$$, but in fact we have tighter bounds, for instance $$a_k\leq 4d(k)$$ where $$d$$ is the divisor counting function (follows e.g. from this result), which is $$O(k^c)$$ for all $$c>0$$. As all these factors are small, they can only have small prime factors, explaining your observation.

In fact the numbers $$a_k$$ in the various factors $$1+a_k$$ are multiples of $$4$$ and typically small ones.

$$a_k=0$$ unless every prime of the form $$4m-1$$ dividing $$k$$ occurs to an even power. If so, $$a_k=4(s_1+1)(s_2+1)\cdots (s_i+1)$$ where the $$s_j$$ are the exponents of the prime divisors of the form $$4m+1$$.

The number given $$3^{114}\ 5^{19}\ 13^6\ 17^9$$ involves the $$a_k$$ for $$2 \le k <241=5^2+14^2.$$ It arises as $$(1+4)^{19}(1+8)^{57}(1+12)^6(1+16)^9$$ So it uses the primes $$3,5,13,17$$ but misses $$7$$ and $$11$$ . Those show up later, but rarely. For $$k=625=5^4$$ we have $$1+a_k=21$$ and that is the first time we get a multiple of $$7.$$ For $$k=1105=5\cdot 13 \cdot 17$$ we will have $$1+a_k=33$$ and that is the first time we get $$11$$. And not until $$k=5^6$$ do we get $$1+28$$

On the other hand, for the $$k$$ below as well as their multiples by powers of $$2$$ and/or even powers of primes from $$\{3,7,11,19,\cdots \}$$

• $$k=1$$ gives $$1+4.$$
• $$k=5,13,17,29\dots$$ give $$1+8.$$
• $$k=5^2,13^2,17^2$$ give $$1+12$$
• $$k=5^113^1,5^117^1,5^3$$ give $$1+16$$
• $$k=5^213,5^5,5^113^2$$ give $$1+24$$