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 />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
[![SphereRationalHeights][1]][1]
<br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
<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