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

SelectLatticePtsInDiskCenteredAtO[radius_] := Module[{m},
  Flatten[Table[m = Ceiling[Sqrt[radius^2 - i^2]] - 1; 
    Table[{i,j}, {j,-m,m}], {i,-Floor[radius],Floor[radius]}], 1] ]

SelectLatticePtsInDiskCenteredAtij[{i_,j_}, radius_] := 
 addListToListOfLists[{i,j}, 
  SelectLatticePtsInDiskCenteredAtO[radius]]

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}] = 
  Module[{cntFromNewOrigin,radius},
  radius = Norm[{i,j}];
  cntFromNewOrigin[newOrigin_] := u[{i,j} - newOrigin];
  Apply[Plus, Map[cntFromNewOrigin, 
     SelectLatticePtsInDiskCenteredAtij[{i,j}, radius]]]]

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

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

 A: 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.
A: 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$
