6
$\begingroup$

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.

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

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}[1]{\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.

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Given $N$, what is the exact (finite?) graph you create? How many nodes do you need to cover the first $N$ sequence elements? $\endgroup$ – Raphael Feb 23 '15 at 11:38
  • 1
    $\begingroup$ @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. $\endgroup$ – Tom van der Zanden Feb 23 '15 at 11:41
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.