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

Subcontract

I think usercccd means 1 = 2^0 * 5^0, 2 = 2^1 * 5^0, 4 = 2^2 * 5^0, 5 = 2^0 * 5^1. The problem is to know what the next smallest value is. Interesting... – Pump

What do you know about iand j? Also, are these ints? You need to start by establishing an upper bound on i and j, or equivalently, on the range of the produced values. Without that, it gets tricky. – Lollis

I can think of an algorithm that will find all such numbers up to n in O(n^2) time and O(n) space. It doesn't require knowing n ahead of time so it can be used to generate the numbers incrementally. However, it's very messy... – Ramburt

Very related (Hamming numbers): https://mcmap.net/q/144879/-nᵗʰ-ugly-number – Sidedress

@JohnL the implication is that he wants a representation of the infinite list, which is quite common in lots of programming languages (IEnumerable in .net, Current+Function(Next) in functional programming etc. etc.) – Timeworn

@Tuskan360 - I agree that's a perfectly reasonable thing to want (note I specified tricky, not impossible). However, when I wrote that I thought it was easier with known boundaries (restricted to C, and I didn't think of Patrick's solution). – Lollis

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;
   }
}

Catanddog

Some additional info: there are 838 of these numbers that fit in a signed 64-bit. The largest is 2^5*5^24 (1907348632812499968). – Catanddog

This is O(nlogn), in contrast to your statement if you don't want this to be N^2 or NlogN complexity. Insertion in map is O(nlogn) – Nonfeasance

Shazbaz, you are right ... partially. The map does not contain N elements, but only the possible next combinations, which is more like log(log(N)), so the final complexity is something like Nlog(log(N)). So substantially faster than N^2 or Nlog(N). – Catanddog

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

Timeworn

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

Qualifier

Answer 4

So we have two loops, one incrementing i and second one incrementing j starting both from zero, right? (multiply symbol is confusing in the title of the question)

You can do something very straightforward:

1. Add all items in an array
2. Sort the array

Or you need an other solution with more math analysys?

EDIT: More smart solution by leveraging similarity with Merge Sort problem

If we imagine infinite set of numbers of 2^i and 5^j as two independent streams/lists this problem looks very the same as well known Merge Sort problem.

So solution steps are:

• Get two numbers one from the each of streams (of 2 and of 5)
• Compare
• Return smallest
• get next number from the stream of the previously returned smallest

and that's it! ;)

PS: Complexity of Merge Sort always is O(n*log(n))

Selfsuggestion

What's the expected computation time for sorting two infinite arrays out of interest? ;-) I guess it could be optimised if you had an algorithm that would put them in the right order for you without direct comparisons... ;-) – Groove

@Groove : yep absolutely this is why I'm asking whether OP need an more smart algorithm ;) thanks for your note anyway, at least now I see that someone has some insights regarding this interesting questions :) – Selfsuggestion

Yeah. I'm finding it quite interesting too. My current thoughts are whether it is easiest to use logarithms to turn it into a linear equation I've not got a full answer yet but I'll stick my thoughts into an answer to show my thinking... – Groove

@Groove : looking forward to see your solutions because I've no ideas except my straightforward "solution" ;) Will read Cormen tonight perhaps I'll got some insights – Selfsuggestion

@sil: Assuming you want such numbers from 1 to 1000000, waht will be the upper limit for i and j? I mean to iterate from 0 up to what? – Shimkus

@Michał Šrajer: the upper limits of i and j can be worked out just by finding the biggest integer less than log(1000000)/log(2)and log(1000000)/log(5). In this case i can be 19 or less and j can be 8 or less. – Groove

@sll: Looking at your second solution your two stream method doesn't seem to take into account things like 10 unless I've missed something. Once you have taken the smallest from your stream you then need to add two more numbers into the mix, two times your value and 5 times your value. Or something. Its complicated... ;-) Oh, and I've not got too far in my head with my system using logarithms. I think you should be able to do something with the ratio of log5/log2 to work out what operations to perform to get the next value but I'm not sure quite how that works yet. too busy at work sadly. :) – Groove

@Chris: If I got it right add two more numbers into the mix - I assumed that i and j could be incremented independently, so if smallest number is gotten from 2^i stream then I just get next number from thsi 2^i stream which assuming incremetning only i, would it work? – Selfsuggestion

@sll: It looked to me like you were only considering numbers of the form 2^i or 5^j. your two streams just have these numbers on but after taking the first number (2) then you will have a stream of 2.2^i, 2.5^j or 5^k. In theory any of these could be the smallest number, etc. I may be jsut misreading your solution though. P.S. My solution is now up. Runs pretty damn quick. :) – Groove

I think that each next number would be greater than previous because degree is incrementing (in scope of each stream, so 2^i < 2^(i+1) ... ) – Selfsuggestion

Answer 5

I visualize this problem as a matrix M where M(i,j) = 2^i * 5^j. This means that both the rows and columns are increasing.

Think about drawing a line through the entries in increasing order, clearly beginning at entry (1,1). As you visit entries, the row and column increasing conditions ensure that the shape formed by those cells will always be an integer partition (in English notation). Keep track of this partition (mu = (m1, m2, m3, ...) where mi is the number of smaller entries in row i -- hence m1 >= m2 >= ...). Then the only entries that you need to compare are those entries which can be added to the partition.

Here's a crude example. Suppose you've visited all the xs (mu = (5,3,3,1)), then you need only check the @s:

x x x x x @
x x x @
x x x 
x @
@

Therefore the number of checks is the number of addable cells (equivalently the number of ways to go up in Bruhat order if you're of a mind to think in terms of posets).

Given a partition mu, it's easy to determine what the addable states are. Image an infinite string of 0s following the last positive entry. Then you can increase mi by 1 if and only if m(i-1) > mi.

Back to the example, for mu = (5,3,3,1) we can increase m1 (6,3,3,1) or m2 (5,4,3,1) or m4 (5,3,3,2) or m5 (5,3,3,1,1).

The solution to the problem then finds the correct sequence of partitions (saturated chain). In pseudocode:

mu = [1,0,0,...,0];
while (/* some terminate condition or go on forever */) {
    minNext = 0;
    nextCell = [];
    // look through all addable cells
    for (int i=0; i<mu.length; ++i) {
        if (i==0 or mu[i-1]>mu[i]) {
            // check for new minimum value
            if (minNext == 0 or 2^i * 5^(mu[i]+1) < minNext) {
                nextCell = i;
                minNext = 2^i * 5^(mu[i]+1)
            }
        }
    }
    // print next largest entry and update mu
    print(minNext);
    mu[i]++;
}

I wrote this in Maple stopping after 12 iterations:

1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50

and the outputted sequence of cells added and got this:

1  2  3  5  7 10
4  6  8  11 
9  12

corresponding to this matrix representation:

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

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

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

Handler

Answer 6

First of all, (as others mentioned already) this question is very vague!!!

Nevertheless, I am going to give a shot based on your vague equation and the pattern as your expected result. So I am not sure the following will be true for what you are trying to do, however it may give you some idea about java collections!

import java.util.List;
import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;


public class IncreasingNumbers {

    private static List<Integer> findIncreasingNumbers(int maxIteration) {
        SortedSet<Integer> numbers = new TreeSet<Integer>();
        SortedSet<Integer> numbers2 = new TreeSet<Integer>();

        for (int i=0;i < maxIteration;i++) {
            int n1 = (int)Math.pow(2, i);
            numbers.add(n1);

            for (int j=0;j < maxIteration;j++) {
                int n2 = (int)Math.pow(5, i);
                numbers.add(n2);

                for (Integer n: numbers) {
                    int n3 = n*n1;
                    numbers2.add(n3);
                }
            }
        }

        numbers.addAll(numbers2);

        return new ArrayList<Integer>(numbers);
    }

    /**
     * Based on the following fuzzy question @ StackOverflow
     * https://mcmap.net/q/738968/-printing-numbers-of-the-form-2-i-5-j-in-increasing-order
     * 
     * 
     * Result:
     * 1 2 4 5 8 10 16 20 25 32 40 64 80 100 125 128 200 256 400 625 1000 2000 10000 
     */
    public static void main(String[] args) {
        List<Integer> numbers = findIncreasingNumbers(5);

        for (Integer i: numbers) {
            System.out.print(i + " ");
        }
    }
}

Zumstein

Answer 7

If you can do it in O(nlogn), here's a simple solution:

Get an empty min-heap
Put 1 in the heap
while (you want to continue)
    Get num from heap
    print num
    put num*2 and num*5 in the heap

There you have it. By min-heap, I mean min-heap

Nonfeasance

Answer 8

As a mathematician the first thing I always think about when looking at something like this is "will logarithms help?".

In this case it might.

If our series A is increasing then the series log(A) is also increasing. Since all terms of A are of the form 2^i.5^j then all members of the series log(A) are of the form i.log(2) + j.log(5)

We can then look at the series log(A)/log(2) which is also increasing and its elements are of the form i+j.(log(5)/log(2))

If we work out the i and j that generates the full ordered list for this last series (call it B) then that i and j will also generate the series A correctly.

This is just changing the nature of the problem but hopefully to one where it becomes easier to solve. At each step you can either increase i and decrease j or vice versa.

Looking at a few of the early changes you can make (which I will possibly refer to as transforms of i,j or just transorms) gives us some clues of where we are going.

Clearly increasing i by 1 will increase B by 1. However, given that log(5)/log(2) is approx 2.3 then increasing j by 1 while decreasing i by 2 will given an increase of just 0.3 . The problem then is at each stage finding the minimum possible increase in B for changes of i and j.

To do this I just kept a record as I increased of the most efficient transforms of i and j (ie what to add and subtract from each) to get the smallest possible increase in the series. Then applied whichever one was valid (ie making sure i and j don't go negative).

Since at each stage you can either decrease i or decrease j there are effectively two classes of transforms that can be checked individually. A new transform doesn't have to have the best overall score to be included in our future checks, just better than any other in its class.

To test my thougths I wrote a sort of program in LinqPad. Key things to note are that the Dump() method just outputs the object to screen and that the syntax/structure isn't valid for a real c# file. Converting it if you want to run it should be easy though.

Hopefully anything not explicitly explained will be understandable from the code.

void Main()
{
    double C = Math.Log(5)/Math.Log(2);
    int i = 0;
    int j = 0;
    int maxi = i;
    int maxj = j;

    List<int> outputList = new List<int>();
    List<Transform> transforms = new List<Transform>();
    outputList.Add(1);
    while (outputList.Count<500)
    {
    Transform tr;
        if (i==maxi)
        {
            //We haven't considered i this big before. Lets see if we can find an efficient transform by getting this many i and taking away some j.
            maxi++;
            tr = new Transform(maxi, (int)(-(maxi-maxi%C)/C), maxi%C);
            AddIfWorthwhile(transforms, tr);
        }
        if (j==maxj)
        {
            //We haven't considered j this big before. Lets see if we can find an efficient transform by getting this many j and taking away some i.
            maxj++;
            tr = new Transform((int)(-(maxj*C)), maxj, (maxj*C)%1);
            AddIfWorthwhile(transforms, tr);
        }
        //We have a set of transforms. We first find ones that are valid then order them by score and take the first (smallest) one.
        Transform bestTransform = transforms.Where(x=>x.I>=-i && x.J >=-j).OrderBy(x=>x.Score).First();
        //Apply transform
        i+=bestTransform.I;
        j+=bestTransform.J;
        //output the next number in out list.
        int value = GetValue(i,j);
        //This line just gets it to stop when it overflows. I would have expected an exception but maybe LinqPad does magic with them?
        if (value<0) break;
        outputList.Add(value);
    }
    outputList.Dump();

}

public int GetValue(int i, int j)
{
    return (int)(Math.Pow(2,i)*Math.Pow(5,j));
}

public void AddIfWorthwhile(List<Transform> list, Transform tr)
{
    if (list.Where(x=>(x.Score<tr.Score && x.IncreaseI == tr.IncreaseI)).Count()==0)
    {
        list.Add(tr);
    }
}

// Define other methods and classes here
    public class Transform
    {
        public int I;
        public int J;
        public double Score;
        public bool IncreaseI
        {
            get {return I>0;}
        }

        public Transform(int i, int j, double score)
        {
            I=i;
            J=j;
            Score=score;
        }
    }

I've not bothered looking at the efficiency of this but I strongly suspect its better than some other solutions because at each stage all I need to do is check my set of transforms - working out how many of these there are compared to "n" is non-trivial. It is clearly related since the further you go the more transforms there are but the number of new transforms becomes vanishingly small at higher numbers so maybe its just O(1). This O stuff always confused me though. ;-)

One advantage over other solutions is that it allows you to calculate i,j without needing to calculate the product allowing me to work out what the sequence would be without needing to calculate the actual number itself.

For what its worth after the first 230 nunmbers (when int runs out of space) I had 9 transforms to check each time. And given its only my total that overflowed I ran if for the first million results and got to i=5191 and j=354. The number of transforms was 23. The size of this number in the list is approximately 10^1810. Runtime to get to this level was approx 5 seconds.

P.S. If you like this answer please feel free to tell your friends since I spent ages on this and a few +1s would be nice compensation. Or in fact just comment to tell me what you think. :)

Groove

Answer 9

I'm sure everyone one's might have got the answer by now, but just wanted to give a direction to this solution..

It's a Ctrl C + Ctrl V from http://www.careercup.com/question?id=16378662

 void print(int N)
  {
     int arr[N];
     arr[0] = 1;
     int i = 0, j = 0, k = 1;
     int numJ, numI;
     int num;
       for(int count = 1; count < N; )
        {
          numI = arr[i] * 2;
          numJ = arr[j] * 5;

            if(numI < numJ)
             {
               num = numI;
               i++;
             }

           else
            {
              num = numJ;
              j++;
            }

            if(num > arr[k-1])
            {
             arr[k] = num;
             k++;
             count++;
            }

       }

     for(int counter = 0; counter < N; counter++)
     {
      printf("%d ", arr[counter]);
     }
}

Tremolo

Answer 10

The question as put to me was to return an infinite set of solutions. I pondered the use of trees, but felt there was a problem with figuring out when to harvest and prune the tree, given an infinite number of values for i & j. I realized that a sieve algorithm could be used. Starting from zero, determine whether each positive integer had values for i and j. This was facilitated by turning answer = (2^i)*(2^j) around and solving for i instead. That gave me i = log2 (answer/ (5^j)). Here is the code:

class Program
{
static void Main(string[] args)
{
    var startTime = DateTime.Now;

    int potential = 0;

    do
    {
        if (ExistsIandJ(potential))
            Console.WriteLine("{0}", potential);
            potential++;
    } while (potential < 100000);

    Console.WriteLine("Took {0} seconds", DateTime.Now.Subtract(startTime).TotalSeconds);

}

private static bool ExistsIandJ(int potential)
{
    // potential = (2^i)*(5^j)
    // 1 = (2^i)*(5^j)/potential
    // 1/(2^1) = (5^j)/potential or (2^i) = potential / (5^j)
    // i = log2 (potential / (5^j))

    for (var j = 0; Math.Pow(5,j) <= potential; j++)
    {
        var i = Math.Log(potential / Math.Pow(5, j), 2);
        if (i == Math.Truncate(i))
            return true;
    }
    return false;
}
}

Venditti