3

I'm trying to write an algorithm that can return the set of positive integers that is less than an instance n and can be factorised as 2^p5^q. My maths is not the best, so I have no idea how I can determine whether a number can be factorised in this specific form...

Any help would be much appreciated :)

Andy
  • 61
  • 6

3 Answers3

5

I have no idea how I can determine whether a number can be factorised in this specific form

Instead of testing whether a given number can be factorised and running through all numbers less than n, why not just generate them, e.g:

void findNumbers(int n)
{
    int p = 0;
    int power2 = 1; 
    while(power2 < n)
    {
        int q = 0;
        int power5 = 1;
        while(power5 * power2 < n)
        {
            printf("%d p = %d q = %d\n", power5 * power2, p, q);
            power5 *= 5;
            q++;
        }
        power2 *= 2;
        p++;
    }
}

Output for n = 500:

1 p = 0 q = 0
5 p = 0 q = 1
25 p = 0 q = 2
125 p = 0 q = 3
2 p = 1 q = 0
10 p = 1 q = 1
50 p = 1 q = 2
250 p = 1 q = 3
4 p = 2 q = 0
20 p = 2 q = 1
100 p = 2 q = 2
8 p = 3 q = 0
40 p = 3 q = 1
200 p = 3 q = 2
16 p = 4 q = 0
80 p = 4 q = 1
400 p = 4 q = 2
32 p = 5 q = 0
160 p = 5 q = 1
64 p = 6 q = 0
320 p = 6 q = 1
128 p = 7 q = 0
256 p = 8 q = 0

It just loops through every combination of p and q up to n.

If you want to exclude p = 0 and q = 0, just start the loops at 1 and set power2 = 2 and power5 = 5.

samgak
  • 23,944
  • 4
  • 60
  • 82
  • It's safer to avoid testing that a number is less than the limit. The multiplication here potentially overflows. Better to divide the limit by 5 and 2, and compare the number against those reduced limits. – Potatoswatter Apr 11 '15 at 07:55
  • 1
    @Potatoswatter that's a good point and worth taking into consideration as an implementation detail but let's just pretend the above is just pseudocode for explaining the algorithm, even if it does look suspiciously like compilable C code :) – samgak Apr 11 '15 at 08:02
  • @NiklasB. Don't you need `<=` there? Else your statement is false - take `a = 2`, `b = 2`, `c = 5`, for example. (Assuming that `/` is integer division here.) – Mark Dickinson Apr 11 '15 at 08:07
  • @Mark Yeah actually it should be (a * b < c) <=> (a <= (c - 1) / b). – Niklas B. Apr 11 '15 at 08:36
2

Use two queues: q1, q2.

Start with q1,q2 empty.

(In the following, define q.head() == 1 if q is empty, it is needed only for first iterations)

Repeat while `min{q1.head(), q2.head()} <n`:
    let x = min{q1.head(), q2.head()}
    yield x
    remove x from relevant queue
    q1.add(x*2)
    q2.add(x*5)

The idea is, if x1 was processed before x2, then it means x1<x2, and thus x1*2 < x2*2 and x1*5 < x2*5 - so the queues are maintained order, and all you have to do at each point is check which of the queues should be polled at each step, which is fairly simple.


Note that you can easily trim duplicates as well this way, because the numbers are produced in order, and you just need to skip numbers if it is identical to the last number that was processed.

Pros of this solution:

  1. Complexity of this solution is linear in the number of elements produced.
  2. Produced list is already sorted, if you need it to be.
  3. If you need k first elements, this solution is pretty efficient, as it runs in O(k), and you just break after producing the kth element.
amit
  • 175,853
  • 27
  • 231
  • 333
  • So at the end you get what? A list of numbers 2^n and a list of numbers 5^m? – Niklas B. Apr 11 '15 at 07:56
  • @NiklasB. No, for example when you process `5`, you add 2*5 and 5*5. – amit Apr 11 '15 at 07:57
  • @Potatoswatter I specifically defined `x` for this reason, you think it's still unclear? I'll try to clarify a bit more. thanks for the feed back. – amit Apr 11 '15 at 07:58
  • I still don't understand. If your goal is to enumerate all the numbers 2^n * q^m, you can just loop over the exponents, like the other answer suggests. There are no collisions 2^a * 5^b = 2^c * 5^d with (a,b) != (c,d). What's the improvement here? – Niklas B. Apr 11 '15 at 07:58
  • 1
    If 5 and 2 belong to the set, then 1 does too, and you should just start with x = 1 and empty queues. – Potatoswatter Apr 11 '15 at 07:58
  • Sorry, I looked again and saw the definition before the pseudocode. It would be clearer to just substitute the definition for the line `produce x`, in my opinion. – Potatoswatter Apr 11 '15 at 07:59
  • 1
    @NiklasB. (1) It's producing them already sorted, which saves some extra time if you need it. (2) Easy to produce the `k`th element in the set (just stop after k elements). – amit Apr 11 '15 at 08:09
1

It’s likely that you will want a better algorithm than "generate all numbers and then test that they are 2^p 5^q". But to answer your question of how to determine whether a positive number is of the form 2^p 5^q, you divide out all the possible 2s and 5s. If anything is left, the original number didn’t have that factorization:

while ( n % 5 == 0 ) {
    n /= 5;
}
while ( n % 2 == 0 ) {
    n /= 2;
}
return n==1;

There are faster ways to test if a number is 2^p, but I find them less readable than the last four lines.

Community
  • 1
  • 1
Teepeemm
  • 4,331
  • 5
  • 35
  • 58