We consider a long-range percolation graph on $\mathbb Z^d$ where, in addition to the nearest-neighbor edges of $\mathbb Z^d$, distinct $x,y\in\mathbb Z^d$ are connected by an edge independently with probability asymptotic to $β|x-y|^{-s}$, for $s\in(d,2d)$, $β>0$ and $|\cdot|$ a norm on $\mathbb R^d$. We first show that, for all but a countably many $β>0$, the graph-theoretical (a.k.a. chemical) distance between typical vertices at $|\cdot|$-distance $r$ is, with high probability as $r\to\infty$, asymptotic to $φ_β(r)(\log r)^Δ$, where $Δ^{-1}:=\log_2(2d/s)$ and $φ_β$ is a positive, bounded and continuous function subject to $φ_β(r^γ)=φ_β(r)$ for $γ:=s/(2d)$. The proof parallels that in a continuum version of the model where a similar scaling was shown earlier by the first author and J. Lin. This work also conjectured that $φ_β$ is constant which we show to be false by proving that $(\logβ)^Δφ_β$ tends, as $β\to\infty$, to a non-constant limit which is independent of the specifics of the model. The proof reveals arithmetic rigidity of the shortest paths that maintain a hierarchical (dyadic) structure all the way to unit scales.