A Vivaldi's number is a number that can be factored by only 2, 3 and 5 ( V = 2^a * 3^b * 5^c, a, b, c = 0,1,...
; also known as Hamming number). The task is to find the Nth Vivaldi number.
The algorithm isn't too bad for small inputs, but N ranges from 0 to 9999. It took 2 minutes at 2000. I wrote the code with a pretty simple algorithm, but I'm curious (hopeful) to find another way. I tried to tackle this problem mathematically with logarithms but ended up nowhere. Is an efficient way even possible when it comes to large inputs?
#include <iostream>
#include <cstdlib>
#include <ctime>
bool vivaldi(unsigned long long d) {
while (d%2 == 0)
d = d/2;
while (d%3 == 0)
d = d/3;
while (d%5 == 0)
d = d/5;
if (d == 1)
return true;
return false;
}
int main() {
int count = 0, N;
unsigned long long number = 0;
std::cin >> N;
std::clock_t begin = clock();
if (N < 0 || N > 9999) {
std::fprintf(stderr, "Bad input\n");
std::exit(EXIT_FAILURE);
}
while (count <= N) {
number++;
if (vivaldi(number))
count++;
}
std::cout << number << std::endl;
std::clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
std::cout << "TIME: " << elapsed_secs << std::endl;
}