Richard Matthew McCutchen's Guest post
he challenged the readers to figure out a certain sum.
And I challenged them to help me do a better pi in html.
- KKMD (comment 3) is correct, it is the largest prime that divides n. The formal proof is here.
- pi: I originally used an & followed by pi which yields &pi
- pi: I was supposed to use & followed by pi and then a semicolon which yields π
- pi: Lance says to use < span style=" font-family:times" > & pi;</span> which yields π
Some of the comments from the posting on
ith largest of n inspire some random
thoughts from me:
- Why on earth would anyone be doing a computer search for such algorithms? (for algorithms to find ith largest of n with as few comparisons as possible). One hope is that with enough empiricial evidence we may get EXACT values for how many comparisons it takes. Also, for the challenge! But YES, limited practical value. But see next point.
- Why do you think your conjecture is true? The known algorithms for finding ith largest of n take n+(i-1)log n + O(1) and begin by making comparisons pairwise. For i small this is optimal up to the O(1). So in this realm it seems likely. But what is `i small'? When finding the 10th largest out of 40 is that more like i small or like you are finding the n/4th largest element? Don't know- want to find out. Another reason to do this- when is small small?
- A commenter says there is interesting info in a Tech Report that may be hard to find. The notion of a Tech Report that is hard to find may be unfamiliar to young people. With the web it may be easier to find some unpublished papers then some published ones, depending on who the authors are and the journals are. (If someone knows where the Journal version of Barrington's paper on Bounded Width BP containing NC1 is online please let me know. Barrington does not have it on his website or know where it is online.)
- Lance recently recommended a certain wallet in this blog. On his advice I bought it and its great. What I wonder is, how big a mover and shaker is Lance? Should they have given him a free wallet since he influences others? How many others have bought it based on his recommendation? At Maryland Theory Day there was a talk about how sellers should give people of influence discounts since they will influence others to buy their product. This is not a new idea, but with modern technology it can be better targeted.