• Jack Applegame (50/50) May 09 2020 I recently came across an interesting exercise.

Jack Applegame <japplegame gmail.com> writes:

I recently came across an interesting exercise.

Given a series of positive numbers, each of which belongs to the 
set

{ 2^^i * 3^^j * 5^^k | i, j, k ≥ 0 }.

The series is ordered in ascending order. The beginning looks 
like this:

{ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ... }

The goal is to get the Nth element of the series. For example, 
for N = 10, the answer is 12.

On the Internet, I found an elegant and incredibly fast solution 
in Haskell:

```
mergeUniq :: Ord a => [a] -> [a] -> [a]
mergeUniq (x:xs) (y:ys) = case x `compare` y of
                                EQ -> x : mergeUniq xs ys
                                LT -> x : mergeUniq xs (y:ys)
                                GT -> y : mergeUniq (x:xs) ys

powers :: [Integer]
powers = 1 : expand 2 `mergeUniq` expand 3 `mergeUniq` expand 5
   where
     expand factor = (factor *) <$> powers

main = print $ powers!!999999
```
On my machine, the 1000000th element is found in 0.215s. OMG!


After that, I spent almost the entire day searching for at least 
the same fast solution in D.

My first attempt was simple and quite pretty, but awfully slow:

```
import std.stdio;
import std.array;
import std.bigint;
import std.algorithm;

auto generate(int n) {
     BigInt[] nums = [BigInt("1")];
     foreach(i; 0..n) {
         nums = merge(nums, [nums[i] * 2, nums[i] * 3, nums[i] * 
5]).uniq().array();
     }
     return nums[n - 1];
}

void main() {
   writeln(generate(5000));
}
```

0.275s for 5000th element.

At the end of the day, I managed to catch up and even overtake 
Haskell by emulating its lazyness with ranges and a funny trick.

Victory! :)

If you find this interesting, I will publish my latest version.
And feel free to find your own solution. ;)