Let $S(r)$ be the surface of the origin-centered sphere in $\mathbb{R}^3$. A point is an *integer point* if all its coordinates are integers. > What is the smallest radius $r_n$ such that $S(r_n)$ includes $\ge n$ integer points? What is the growth rate of $r_n$ with respect to $n$? Is there an algorithm that could compute $r_n$ for a specific given $n$? It is known that rational points (all coordinates rational) are dense on $S(1)$: see, e.g., the MO question [Rational points on a sphere in $\mathbb{R}^d$](https://mathoverflow.net/q/125224/6094). One possible approach is via rational points of bounded height. The height of a rational $a/b$ in lowest terms is max$(|a|,|b|)$, and the height of a rational point is the max of the heights of its coordinates. <hr /> [![SphereRationalHeights][1]][1] <br /> <sup> Rationals of height $\le 2048$ on sphere. Image due to Stefan Kohl in [this answer](https://mathoverflow.net/a/125391/6094). </sup> <hr /> Choose an appropriate $h_\max$, perhaps using an [estimate](https://mathoverflow.net/a/125750/6094) of the number of rational points of height at most $h_\max$ on $S(1)$. Then scale all coordinates by the LCM of the points' denominators. For example, for $h_\max=10$, scaling by $2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$ would suffice to clear all denominators, so that $S(2520)$ includes all those points at integer coordinates. But this would not necessarily result in the minimum $r_n$ for a given $n$. It would likely be better to use rational points that result in a small LCM. Exact calculations on a sphere (for example, computing [Voronoi diagrams on a sphere](https://mathoverflow.net/a/135338/6094)) often need integer points of bounded size. [1]: https://i.sstatic.net/tByOX.jpg