I ran into an interesting problem the other day, someone asked for all positive integers of i & j, provide an ordered list of the solutions to (2^i)(5^j). After wracking my brains for quite a couple hours, I finally came up with the following solution. It work by finding integers for which there is an i and j in a sieve fashion. This works by solving for i, such that i = log2 (potential / (5^j)). This will allow the program to output as many values as the representation can support. I limit the number of values of j that I test for by limiting it to 5^j < potential. This gives the program O(n).
class Program
{
static void Main()
{
int potential = 0;
do
{
if (ExistsIandJ(potential))
Console.WriteLine("{0}", potential);
potential++;
} while (potential <= int.MaxValue)
}
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;
}
}
I was expecting this to be fairly easy to begin with, the realized that wasn't going to be true. I then thought there must be a pattern to the values to i & j, but after a while realized there was not. Trees might be the answer, but only for a finite number of values, since you would have to determine when to prune the tree. Would you miss an answer. It was later that I realized that if I tested every answer for an i & j that it could be done infinitely. I pondered how to determine i & j, then decided to solve for i. The pieces fell into place.
