Question

Is there an efficient way to generate these numbers?

Answer 1

So you want all n=2·3^(a)·5^(b)·7^(c)·... where a,b,c,...∈{0,1} and n<N.

I'd suggest: Start with S[1]={2}, and iterate with

S[n+1] = S[n] ∪ {p[n]·x : x∈S[n] ∧ p[n]·x < N}

where the p[i] are the primes between 3 and √N inclusive.

IOW, given the set of numbers which are even, square-free, and have only prime factors less than or equal to p[k], multiply each number in the set (in increasing order) by p[k+1], terminating if you reach a value greater than or equal to N. Repeat until you run out of primes.

Initially, the set will double in size at each step: {2}, {2,6}, {2,6,10,30}, {2,6,10,14,30,42,70,210}, etc. Eventually you'll start getting numbers greater than or equal to N and the growth will slow down.

Answer 2

I can propose the following method but I'm not sure about the quick part...

So you start with 1 and iterate through the primes 3 <= p <= sqrt(n): for all products already computed, you add in the term p \* product if p \* product <= n / 2. You can sort the products after each iteration so you can stop early. Finally you multiply all the terms by 2 to make them even.

Answer 3

depending on the size of your numbers it would take the longest to calculate the square roots of the numbers, but it could also take a long time to multiply the primes as you go higher and higher it kinda looks like a bastardized factorial.

luckily there arent a whole lot of primes, so i guess you could make a database of them up to maybe 10^10 as i’m sure they are probably all found? that would speed up things significantly as you could iterate through those to multiply instead of having to calculate in real time each one lower than n for every input of n

edit: I believe i forgot how massive 10^10 is. this could not work depending on how many primes there are. the computational power needed would be quite huge