# Algorithm to generate all vectors of integers with magnitude between $n\pm \delta$

I am working on an program to compute the structure factor of a given configuration of particles, and I need an efficient algorithm to generate all the possible vectors with integer coordinates and magnitude between $n-\delta$ and $n+\delta$, where $\delta$ is small compared to $n$. This is equivalent to finding all the solutions to

$$(n-\delta)^2<\| \vec v \|^2<(n+\delta)^2$$

with $\vec v \in \mathbf{Z}^3$.

Of course, I only need to find half of the solutions because the other half will be given by

$$\vec v'=-\vec v$$

What is the best algorithm to solve this problem?

PS This is my first time posting here so any help with the tags would be really appreciated.

• Welcome to SciComp.SE! Your question isn't off-topic here, but might actually get better answers at the Computer Science SE. (After all, Knuth's Art of Computer Programming has a whole volume (4) devoted to such combinatorial generation problems.) – Christian Clason Jun 28 '16 at 13:45
• @ChristianClason Thank you, I didn't know of the existence of this SE. I will post this question on Computer Science SE too. – valerio Jun 28 '16 at 13:53
• You might wish to wait for a bit first, and at least mention (i.e., link to) the other version of the question. Cross-posting is discouraged on the StackExchange network in general. – Christian Clason Jun 28 '16 at 13:57
• @ChristianClason Ok, then I will wait. Thank you. – valerio Jun 28 '16 at 14:08
• You have an eight-fold symmetry, not just two-fold. Also: there are $O(n^2\delta)$ solutions, so if $\delta=\Omega(1)$, you can't do asymptotically better than just the straightforward iteration as in Jannis's answer. – Kirill Jun 28 '16 at 23:11

$i$ from 0 to $d+n$
$j$ from 0 to $\sqrt{(d+n)^2-i^2}$
$k$ from $\sqrt{(d-n)^2-i^2-j^2}$ to $\sqrt{(d+n)^2-i^2-j^2}$, where the minimum bound is 0 if $i^2+j^2 > (d-n)^2$.