[seqfan] Re: Products of primorials

[hv at crypt.org]

Charles Greathouse <charles.greathouse at case.edu> wrote:
:There are many sequences which are naturally subsequences of A025487,
:numbers with prime exponents in nonincreasing order (and no missing
:primes).  Is there a good way to iterate through these numbers (not
:necessarily in order) up to a fixed limit?  Alternately, a version
:that iterated them in order in an unbounded fashion would be
:interesting (but probably would not be as fast).
:
:Any thoughts?  I'm sure this has been done already...

I think an efficient approach is:
- start with the exponent sequence [ 1 ]; create a structure with that
  sequence and its value, and use it to initialize a binary heap
- while the least value in the heap is inside your limit
[
  - remove the least value from the heap
  - append a 1 to the sequence, insert the corresponding structure in the heap
  - increment the last element of the sequence, if it does not exceed the
    previous element (or if there is no previous element), insert the
    corresponding structure on the heap
  - process this value
]

See http://stackoverflow.com/questions/2508406/ for some additional detail.

Since for each element removed from the heap you insert either 1 or 2 new
elements, after processing n elements the heap will contain no more than n
new elements. It is interesting to consider also the asymptotic behaviour
of the heap size as n increases.

Hugo