Printing numbers of the form 2^i * 5^j in increasing order

Question

How do you print numbers of form 2^i * 5^j in increasing order.

For eg:
1, 2, 4, 5, 8, 10, 16, 20

Answer 1

This is actually a very interesting question, especially if you don't want this to be N^2 or NlogN complexity.

What I would do is the following:

• Define a data structure containing 2 values (i and j) and the result of the formula.
• Define a collection (e.g. std::vector) containing this data structures
• Initialize the collection with the value (0,0) (the result is 1 in this case)
• Now in a loop do the following:
  • Look in the collection and take the instance with the smallest value
  • Remove it from the collection
  • Print this out
  • Create 2 new instances based on the instance you just processed
    • In the first instance increment i
    • In the second instance increment j
  • Add both instances to the collection (if they aren't in the collection yet)
• Loop until you had enough of it

The performance can be easily tweaked by choosing the right data structure and collection. E.g. in C++, you could use an std::map, where the key is the result of the formula, and the value is the pair (i,j). Taking the smallest value is then just taking the first instance in the map (*map.begin()).

I quickly wrote the following application to illustrate it (it works!, but contains no further comments, sorry):

#include <math.h>
#include <map>
#include <iostream>

typedef __int64 Integer;

typedef std::pair<Integer,Integer> MyPair;
typedef std::map<Integer,MyPair> MyMap;

Integer result(const MyPair &myPair)
{
return pow((double)2,(double)myPair.first) * pow((double)5,(double)myPair.second);
}

int main()
{
MyMap myMap;
MyPair firstValue(0,0);

myMap[result(firstValue)] = firstValue;

while (true)
   {
   auto it=myMap.begin();
   if (it->first < 0) break;        // overflow

   MyPair myPair = it->second;
   std::cout << it->first << "= 2^" << myPair.first << "*5^" << myPair.second << std::endl;

   myMap.erase(it);

   MyPair pair1 = myPair;
   ++pair1.first;
   myMap[result(pair1)] = pair1;

   MyPair pair2 = myPair;
   ++pair2.second;
   myMap[result(pair2)] = pair2;
   }
}

Answer 2

This is well suited to a functional programming style. In F#:

let min (a,b)= if(a<b)then a else b;;
type stream (current, next)=
    member this.current = current
    member this.next():stream = next();;
let rec merge(a:stream,b:stream)=
    if(a.current<b.current) then new stream(a.current, fun()->merge(a.next(),b))
    else new stream(b.current, fun()->merge(a,b.next()));;

let rec Squares(start) = new stream(start,fun()->Squares(start*2));;

let rec AllPowers(start) = new stream(start,fun()->merge(Squares(start*2),AllPowers(start*5)));;
let Results = AllPowers(1);;

Works well with Results then being a stream type with current value and a next method.

Walking through it:

1. I define min for completenes.
2. I define a stream type to have a current value and a method to return a new string, essentially head and tail of a stream of numbers.
3. I define the function merge, which takes the smaller of the current values of two streams and then increments that stream. It then recurses to provide the rest of the stream. Essentially, given two streams which are in order, it will produce a new stream which is in order.
4. I define squares to be a stream increasing in powers of 2.
5. AllPowers takes the start value and merges the stream resulting from all squares at this number of powers of 5. it with the stream resulting from multiplying it by 5, since these are your only two options. You effectively are left with a tree of results

The result is merging more and more streams, so you merge the following streams

1, 2, 4, 8, 16, 32...

5, 10, 20, 40, 80, 160...

25, 50, 100, 200, 400...

.

.

. Merging all of these turns out to be fairly efficient with tail recursio and compiler optimisations etc.

These could be printed to the console like this:

let rec PrintAll(s:stream)=
    if (s.current > 0) then
        do System.Console.WriteLine(s.current)
        PrintAll(s.next());;

PrintAll(Results);

let v = System.Console.ReadLine();

Similar things could be done in any language which allows for recursion and passing functions as values (it's only a little more complex if you can't pass functions as variables).

Answer 3

For an O(N) solution, you can use a list of numbers found so far and two indexes: one representing the next number to be multiplied by 2, and the other the next number to be multiplied by 5. Then in each iteration you have two candidate values to choose the smaller one from.

In Python:

 numbers = [1]
 next_2 = 0
 next_5 = 0

 for i in xrange(100):
     mult_2 = numbers[next_2]*2
     mult_5 = numbers[next_5]*5

     if mult_2 < mult_5:
        next = mult_2
        next_2 += 1
     else:
        next = mult_5
        next_5 += 1

     # The comparison here is to avoid appending duplicates
     if next > numbers[-1]:
        numbers.append(next)

 print numbers