Consider the set of numbers whose exponents of its prime factorization (in order by prime, not omitting zero exponents) are non-increasing.
In other words, write a number as its prime factorization, putting an exponent zero if a prime is not a factor:
x = 2^e2 * 3^e3 * 5^e5 * 7^e7 * 11^e11 * ...
We are interested in the set of numbers x for which the exponents ep are non-increasing (decreasing or equal): e2 >= e3 >= e5 >= e7 >= e11 >= ...
(We don't do strictly decreasing because every number ends with an infinite string of zero exponents for high primes.)
The sequence begins : 1 2 4 6 8 12 16 24 30 32 36 48 60 64 72 96 120 128 144 180 192 210 216 240 256 288 360 384 420 432 480 512 576 720 768 840 864 900 960 1024 .... (OEIS A025487)
What is an efficient algorithm to generate this sequence in order? What is the asymptotic growth rate of the sequence?
No comments :
Post a Comment