# Get numbers that have only 2,3 and 5 as prime factors

I am given an integer N. I have to find first N elements that are divisible by 2,3 or 5, but not by any other prime number.

N = 3
Results: 2,3,5
N = 5
Results: 2,3,5,6,8


Mistake number = 55.. 55/5 = 11.. 11 is prime number.. so means that it divides by any other prime number and doesn't counts in..

I guess there is need of recursive function,but I cant imagine what would algorithm look like

I was sent here from stackoverflow.

They gave me advice.. 2^i*3^j*5^k , for i,j,k = 0,1,2... , but it won't give an ordered array, because 2*2 < 2*3 .. and so on

I am trying to get this work in C++

The algorithm in this answer, in the end, is the same as the one in Bill Dubuque's answer, but I hope to be more elaborate and describe how one could arrive at the algorithm. Let's frame the problem as that of building the list of all such numbers in ascending order, i.e., each time adding to the list the smallest number that is not already in it.

First, note that all the numbers you want are of the form $2^i3^j5^k$, where $i, j, k$ are nonnegative integers. This means that after the first number $1$ (corresponding to $i = j = k = 0$), each "next" number can be obtained by multiplying some number already generated in the list, by either $2$, or $3$ or $5$.

So you start the list with the first number, $1$. To find the next number, you have three choices: multiply the number $1$ by either $2$, or $3$, or $5$. Since you want the smallest result, you pick $2$, and your list becomes $[1, 2]$.

Now you can no longer multiply $1$ by $2$ to get a new number, it is "used up". Your three choices now are: multiplying $1$ by $3$, multiplying $1$ by $5$, or multiplying $\color{red}{2}$ by $2$. The smallest result is from multiplying $1$ by $3$, so you add the result to the list, which becomes $[1, 2, 3]$.

Now you can no longer multiply $1$ by $3$, it is "used up" for multiplication by $3$. The smallest number you can multiply by $3$ is the next number, $2$. Your three choices now are: multiplying $\color{red}{2}$ by $2$, multiplying $\color{red}2$ by $3$, and multiplying $1$ by $5$. You pick the smallest result, which corresponds to multiplying $2$ by $2$ and gives you $4$ which you add to the list, and now $2$ is also used up for multiplication by $2$ and for multiplication by $2$ you have to go to the next number in the list, namely $3$.

In general, you always have three choices: one number that you can multiply by $2$, another that you can multiply by $3$, and another that you can multiply by $5$. You pick whichever of these three choices gives the smallest result, and update the choice ("advance the pointer") for 2 or 3 or 5, whichever you chose.

The first few steps worked out explicitly:

List is $[1]$. Choice for 2 is $1$, choice for 3 is $1$, choice for 5 is $1$. (Choose multiplication by 2.)

List is $[1, 2]$. Choice for 2 is $2$, choice for 3 is $1$, choice for 5 is $1$. (Choose multiplication by 3.)

List is $[1, 2, 3]$. Choice for 2 is $2$, choice for 3 is $2$, choice for 5 is $1$. (Choose multiplication by 2.)

List $[1, 2, 3, 4]$. Choice for 2 is $3$, for 3 is $2$, choice for 5 is $1$. (Choose multiplication by 5.)

List is $[1, 2, 3, 4, 5]$. Choice for 2 is $3$, for 3 is $2$, for 5 is $2$. (Choose multiplication by 2.)

List is $[1, 2, 3, 4, 5, 6]$. Choice for 2 is $4$, for 3 is $3$ (note that we updated this also), for 5 is $2$. (Choose multiplication by 2.)

List is $[1, 2, 3, 4, 5, 6, 8]$. Choice for 2 is $5$, for 3 is $3$, for 5 is $2$. (Choose multiplication by $3$.)

List is $[1, 2, 3, 4, 5, 6, 8, 9]$. Choice for 2 is $5$, for 3 is $4$, for 5 is $2$.

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10]$. Choice for 2 is $6$, for 3 is $4$, for 5 is $3$.

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]$. Choice for 2 is $8$, for 3 is $5$, for $5$ is $3$.

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15]$. Choice for 2 is $8$, for 3 is $6$, for $5$ is $4$.

In code, you could implement it as a growing array, with three array indices pointing to the choices for 2, 3, and 5. Here is a complete working Python program (time.sleep is to keep it slow enough to see the output):

import time
num = [1]
c2 = c3 = c5 = 0

while True:
next = min(2*num[c2], 3*num[c3], 5*num[c5])
num.append(next)
print num
if next == 2*num[c2]: c2 += 1
if next == 3*num[c3]: c3 += 1
if next == 5*num[c5]: c5 += 1
time.sleep(0.5)

• I've got solution.. @binn, too simple and effective – waplet Sep 17 '12 at 22:00
• @waplet: That is not at all efficient, plus it's the obvious boring solution. :-) And this one is about the same (or fewer) number of lines of code as that, so it isn't really harder to code. Anyway, whatever works for you. – ShreevatsaR Sep 18 '12 at 1:57
• Yeah, i found it easy to implement .. too :) Thank you also.. I guess this one is more faster , though? – waplet Sep 18 '12 at 16:06

Hint $\$ There is a very simple recursive algorithm, e.g. the final $\color{#C00}\to$ below is calculated as follows.

$\ \ 1_{2,3,5}\to 1_{3,5} 2_2\to 1_5 2_{2,3} 3\to 1_5 2_{3} 3_2 4\to 1\, 2_{3,5} 3_2 4\, 5\to 1 2_{5} 3_3 4_2 5\,6\color{#C00}\to 1 2_{5} 3_3 4\, 5_2 6\,8\to\, \cdots$

The term $\:1 2_{5} 3_3 4_2 5\,6\:$ on the left of the $\color{#C00}\to$ means that we have computed the initial sequence $\:1\,2\,3\,4\,5\,6,\:$ where the subscript $5$ on $2$ means that $2\cdot 5$ is the next multiple of $5$ to insert, similarly $3\cdot 3$ and $4\cdot 2$ are the next multiples of $3$ and $2$ to be inserted. Therefore the next term must be $\rm\:min(2\cdot 5, 3\cdot 3, 4\cdot 2) = 8.\:$ Since $8$ is not already at the end, we append it, then we bump the subscript $2$ from $4$ to the next term $5$, indicating that $2\cdot 5$ is the next multiple of $5$. Then recurse.

This can be implemented elegantly in a functional programming language using (lazy) streams for the multiples of $2,3,5$.

• Quite hard to understand, for me who don't have english as native language :S – waplet Sep 17 '12 at 12:18
• @waplet What is not clear? – Bill Dubuque Sep 17 '12 at 13:01

I'd build it up from the prime factorization. You're looking for numbers with a prime factorization of the form $2^a3^b5^c$. Thus, you can simply start with an a, b, and c of zero, and work along the following pseudocode algorithm:

do
{
if(2^(a+1) > 3^(b+1))
if(3^(b+1) > 5^(c+1))
{
increment c
b = 0
a = 0
}
else
{
increment b
a = 0
}
else
increment a

}
while(results.count < N) //should loop exactly N times

• Didn't work out.. Dunno what i have done wrong – waplet Sep 17 '12 at 16:17

I solve this kind of situation with this:

 function getIdealNums($$l,$$r) { $$numbers = []; for ($$x=0; $$x <= 2*pow(10, 5);$$x++) { for ($$y=0;$$y <= 2*pow(10, 5); $$y++) { number = pow(3, x)*pow(5, y); if (l <= number) { if (number <= r) { array_push(numbers, number); } else { break; } } } } return count($$numbers); } 

Make a loop over numbers i. Check the numbers one at a time, it doesn't need to be recursive.

If you want, you can use a nice recursive algorithm f(i) which is true or false depending on whether the number i should be allowed into the list.
f(i):
if i == 1: return true
else if i % 2 == 0: return f(i/2)
else if i % 3 == 0: return f(i/3)
else if i % 5 == 0: return f(i/5)
else: return false

• This algorithm may function, but it will run in exponential time; by the very definition of the problem, you'll need to loop through $2^a3^b5^c$ numbers, where $a+b+c = N$ and $2^a\leq3^b\leq5^c$, to return the required N results. You will additionally need to recurse deeply through all numbers of factorization $2^a3^b5^cq$ where $q$ is some other prime or product of primes. As a computational strategy, this is the worst possible thing I can think of to recommend. – KeithS Sep 17 '12 at 15:07