# How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$?

I've googled around a bit and found the sequence in OEIS, but I don't really see a simple way of generating it.

• These are called "Hamming numbers" (or "regular numbers" by non-computer scientists). Look that up, and you'll find lots and lots of hits. – Pseudonym Feb 23 '15 at 0:56
• I disagree with closing as "not computer science": the request is for an efficient algorithm to perform a particular task. – David Richerby Feb 23 '15 at 8:09

Here I assume $0\in \mathbb N$. If you disagree start with $105$.

Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order. Apart from $1$ each number added is of the form $3\cdot x$, $5\cdot y$ or $7\cdot z$ where $x,y,z$ are previous numbers in the sequence. We can generate $S$ by shifting $x,y,z$ along the sequence.

So, first put $1$ into $S$, and set $x,y,z$ equal to $1$.

Now repeat: Take the minimum value $m$ of $3\cdot x$, $5\cdot y$ and $7\cdot z$, and add $m$ to the sequence $S$. The $x,y,z$ for which the minimum was taken are shifted to the next element of $S$. This might be more than one, or even all three.

$\newcommand{\ul}{\underline{#1}}$ $\begin{array}{r|rr|rr|rr} S & x & {}*3 & y & {}*5 & z & {}*7 & \\\hline 1 & 1 & \ul{3} & 1 & 5 & 1 & 7 \\ 3 & 3 & 9 & & \ul{5} & & 7 \\ 5 & & 9 & 3 & 15 & & \ul{7} \\ 7 & & \ul{9} & & 15 & 3 & 21 \\ 9 & 5 & \ul{15} & & \ul{15} & & 21 \\ 15 & 7 & \ul{21} & 5 & 25 & & \ul{21} \\ 21 & 9 & 27 & & \ul{25} & 5 & 35 \\ 25 & & \ul{27} & 7 & 35 & & 35 \\ 27 & 15 & 45 & & \ul{35} & & \ul{35} \\ 35 & & \ul{45} & 9 & \ul{45} & 7 & 49 \\ 45 & 21 & 63 & 15 & 75 & & 49 \end{array}$

Works in linear time, as we need to take the minimum of three numbers in each step.

Consider a weighted, directed graph, with a vertex $v_i$ for $i\in\mathbb{N}$. There is an edge with weight $j-i$ from $v_i$ to $v_j$ if $j\in\{3i,5i,7i\}$.

Now run Dijkstra's shortest path algorithm. It will expand exactly the nodes from your sequence and do so in order. This gives an $n\log n$ algorithm to enumerate the first $n$ elements, since the graph has maximum out-degree $3$.

• Given $N$, what is the exact (finite?) graph you create? How many nodes do you need to cover the first $N$ sequence elements? – Raphael Feb 23 '15 at 11:38
• @Raphael Every element you extract results in at most $3$ new elements getting created, so you generate at most $3N$ nodes. The graph is really just an analogy to show the similarity with Dijkstra's algorithm, all you are really doing is pushing 1 on to a priority queue, and then repeatedly extracting the minimum from the priority queue (let this number be $x$) and pushing $3x,5x$ and $7x$ back on to the queue. – Tom van der Zanden Feb 23 '15 at 11:41

Let $n(m)$ be the number of members of $\{ 3^a5^b7^c \mid a,b,c \in \mathbb{N}\}$ which are less than $m$. Using the principle of inclusion/exclusion we have: $$n(m) = 1 + \lfloor\frac{m}{3}\rfloor + \lfloor\frac{m}{5}\rfloor + \lfloor\frac{m}{7}\rfloor - \lfloor\frac{m}{15}\rfloor - \lfloor\frac{m}{21}\rfloor - \lfloor\frac{m}{35}\rfloor + \lfloor\frac{m}{105}\rfloor$$

Now what we are given $n$ and want to compute is the inverse$^\dagger$ of the function $m \mapsto n(m)$. One easy way to do this is to search for the smallest $m$ such that $n(m) \geq n$. Start with $m=1$ and double it until $n(m) \geq n$. Then do a binary search between $1$ and that number for the smallest number such that $n(m) \geq n$.

The running time is polynomial in $\lg n$.

$\dagger$: strictly speaking function is 1-1 so it doesn't have an inverse without some modification.