From: Marc LeBrun <mlb@fxpt.com>

Subject: Re: [math-fun] Re: math-fun Digest, Vol 17, Issue 8

...

=Phil Carmody Surely the easiest algorithm would be Dijkstra's?

I'm not sure; which algorithm of Dijkstra's do you refer to?

Pretend your unit and your radical sqrt(t) are logs of some numbers n1 and n2. You want therefore to enumerate in order what you consider a.log(n1)+b.log(n2). Or log(n1^a.n2^b). This is easy to do if enumerating n1^a.n2^b in order is easy to do. Now /if/ {n1,n2} were {2,3} then you'd be enumerating 3-smooth numbers. Which is where Dijkstra comes in, as he has an algorithm for enumerating smooth numbers in order. Best of all, it really doesn't care what the 'primes' are, and therefore it works equally well with {2,3} as it does with {e,exp(sqrt(t))}. And it also doesn't care whether you calculate the smooth numbers by multiplication, or their logs by addition. So you can fall back into {1,sqrt(t)}-space, where you were originally looking. The algorithm is to assume you have a list in order, and have 2 pointers back into the list which tell you which are the least terms that when 1 and sqrt(t) are added to them yield numbers larger than the head of the list. Chose the one that yields the smaller result. Insert that result at the head, and step the pointer forward by one. Your assumption is preserved. Repeat. Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________ Do you Yahoo!? Yahoo! Mail - 50x more storage than other providers! http://promotions.yahoo.com/new_mail