20
$\begingroup$

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}}
$\endgroup$
3
  • $\begingroup$ "closer" in what metric? Taxicab? Euclidean? $\endgroup$
    – Wojowu
    Nov 12 at 21:29
  • 4
    $\begingroup$ @Wojowu: if you read the $u(1,1)$ example you will see Euclidean distance is intended. $\endgroup$ Nov 12 at 21:33
  • $\begingroup$ @SamHopkins Good catch. I didn't read it thoroughly, and apart from the mention of the distance this example works in either metric. $\endgroup$
    – Wojowu
    Nov 12 at 21:44
39
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.