Graph solution: kth smallest num with n prime factors

Ok, here's my attempt at explaining my solution:

You have a graph. The nodes are prime factorizations, e.g.:
- 2^n
- 2^(n-1) * 3^1
- 2^(n-2) * 3^1 * 5^1

The starting node is 2^n. The starting node is connected to nodes with the following prime factorizations:
- 2^(n-1) * 3^1
- 2^(n-1) * 5^1
- 2^(n-1) * 7^1
...

Essentially, any prime factorization that can be formed by decrementing the exponent of one prime factor to increment the exponent of another prime factor.

Our goal is to use this graph in a Dijkstra-esque way: we keep a set of "solved" nodes, which initially contains only the start node. As we add "solved" nodes to the set, we make sure that when we add the ith node, it is in fact the factorization of the i smallest number made up of n primes. If we can successfully do this k times, the last node we add will be our solution.

Picking the second node - and as such, the second-smallest number made up of n primes - is pretty trivial. The only factorization that it could be is obviously 2^(n-1) * 3^1. Note: there's a long list of nodes we _could_ consider:
- 2^(n-1) * 3^1
- 2^(n-1) * 5^1
- 2^(n-1) * 7^1
But it's trivial to see that only the first one could possibly be the next smallest number. This is an important optimization: the only nodes we should seriously consider adding to the solved set should be optained by decrementing the exponent one prime factor (in this case, that prime factor is 2) and incrementing the exponent of the next prime factor (in this case, "the next prime factor" is 3, so we're incrementing its exponent).

Moving on: now our solved set is:
- 2^n (our starting node, I'll call this Node A)
- 2^(n-1) * 3^1 (I'll call this Node B)

What nodes do we want to consider to find the 3rd node to add to the set? First, let's consider nodes connected to Node B:
- 2^(n-1) * 5^1
- 2^(n-1) * 7^1
- 2^(n-1) * 11^1
...
- 2^(n-2) * 3^2
- 2^(n-2) * 3^1 * 5^1
- 2^(n-2) * 3^1 * 7^1
- 2^(n-2) * 3^1 * 11^1
...

I've divided the possibilities into 2 groups: the first group is obtained by decrementing the exponent of 3 and incrementing exponent on larger primes; the second group is obtained by decrementing the exponent of 2 and incrementing the exponent on larger primes. Due to the optimization I stated earlier, we only need to seriously consider the first possibility in each of these groups:
- 2^(n-1) * 5^1
- 2^(n-2) * 3^2

So we have 2 nodes that we are seriously considering as possibilities to be our 3rd node in the solved set. But, we must also go back and look at Node A again:
X 2^(n-1) * 3^1   <-- Already in the solved set, so we're not seriously considering it anymore
- 2^(n-1) * 5^1   <-- Now that the factorization 1 line above this is in the solved set, we need to seriously consider this factorization.
- 2^(n-1) * 7^1

So if we hadn't already been seriously considering 2^(n-1) * 5^1, we would need to. As it happens, no extra work is necessary. So the nodes we are seriously considering are:
- 2^(n-1) * 5^1
- 2^(n-2) * 3^2

I'll rewrite these, respectively, as:
- 2^(n-2) * 2*5
- 2^(n-2) * 3*3

So it's clear that the second option is the one we want to add to our solved set as Node C. The solved set is now:
- 2^n (Node A)
- 2^(n-1) * 3^1 (Node B)
- 2^(n-2) * 3^2 (Node C)



(Side note, completely optional reading:
There's a way to evaluate the nodes being seriously considered that doesn't involve multiplying out all their factors, or trying to simplify them like I wrote them out. It also more closely resembles Dijkstra's algorithm. We assign the weight of an edge from X -> Y to be ratio between Y's product and X's product. More specifically, the weight from X to Y = (total product of Y's factors) / (total product of X's factors). This can be easily computed because our edges always only decrement one exponent and increment another one. For example:
- Going from Node A -> Node B: Here we decremented the exponent of 2 and incremented the exponent of 3. The weight on the edge would then be 3/2 = 1.5
- Going from Node A -> Node C: Here again, we changed a 2 into a 3, and the weight is also 3/2 = 1.5
- Going from Node B -> 2^(n-1) * 5^1: Here we decremented the exponent of 3 and incremented the exponent of 5. The weight on the edge would be 5/3 = 1.66
To pick the node to add to the solved set, we pick the node X such that the path from Node A to Node X has the smallest _product_ (not sum) of edge weights. So in our previous step, we were deciding between:
- 2^(n-1) * 5^1 (I'll call this Node O)
- 2^(n-2) * 3^2 (I'll call this Node P)

The path from Node A to Node O is: A -> B -> O
Weight(A, B) = 1.5
Weight(B, O) = 5/3 = 1.66
Weight_of_path(A, O) = 1.5 * 1.66 = 2.5

The path from Node A to Node P is: A -> B -> P
Weight(A, B) = 1.5
Weight(B, P) = 1.5
Weight_of_path(A, P) = 1.5 * 1.5 = 2.25

Node P ends up having the shortest path, and so that's why we chose it to add to the solved set.

End side note)



I'll breeze through one more step. Again, our solved set is:
- 2^n (Node A)
- 2^(n-1) * 3^1 (Node B)
- 2^(n-2) * 3^2 (Node C)

Nodes connected to Node C that we want to seriously consider:
- 2^(n-2) * 3^1 * 5^1 (decrementing 3, incrementing 5)
- 2^(n-3) * 3^3 (decrementing 2, incrementing 3)

Nodes connected to Node B that we want to seriously consider:
- 2^(n-1) * 5^1 (decrementing 3, incrementing 5)
- 2^(n-2) * 3^1 * 5^1 (decrementing 2; normally we would increment 3, but since that's already in the solved set, we increment 5)

Nodes connected to Node C that we want to seriously consider:
- 2^(n-1) * 5^1

All nodes we want to seriously consider:
- 2^(n-2) * 3^1 * 5^1 (I'll call this Node R)
- 2^(n-3) * 3^3 (I'll call this Node S)
- 2^(n-1) * 5^1 (I'll call this Node T)

Rewrite them (respectively) as:
- 2^(n-3) * 2*3*5
- 2^(n-3) * 3*3*3
- 2^(n-3) * 2*2*5

Node T is the one we want.