Author |
Topic: Perfect powers (Read 2639 times) |
|
TimMann
Senior Riddler
Gender: 
Posts: 330
|
 |
Perfect powers
« on: Oct 22nd, 2002, 1:48am » |
 Quote  Modify
|
Write a fast program that prints perfect powers (integers of the form mn, with m, n > 1) in increasing numerical order. So the first few outputs should be 4, 8, 9, 16, 25, 27, 32, ...
This was a contest problem that I worked on when I was in high school back in 1977 or so. I didn't have access to a computer at the time, so I desk-checked the program and sent it in. It worked and took third place!
"Fast" in the above is pretty fuzzy. I'm leaving it that way intentionally. The original contest rules were that the programs had to be in a standard dialect of Basic and fit on one page, and the contest organizers would type them in and time them on their system, with the winner being the fastest one to print all perfect powers less than N = 10,000,000. A different rule might be that your algorithm has to work for unlimited N, and the algorithm that has the least time complexity (in the O(f(N)) sense) wins. Can you think of an algorithm that would win under the original rules but would be disqualified under the later rules?
|
| « Last Edit: Nov 7th, 2002, 10:21am by TimMann » |
 IP Logged |
http://tim-mann.org/
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: New problem: perfect powers
« Reply #1 on: Oct 31st, 2002, 10:25pm » |
Quote Modify
|
With regard to the last question, I guess if we made a list of all the perfect powers from 1 to 10 million beforehand, and have the algorithm just print out that list, it would win under the first set of rules, but lose under the second. 
I'm almost afraid to try to solve this one, as it has gone so long without a reply... but that's not in the spirit of the site, so let's give it a shot. 
The way I see it, this puzzle has two interpretations: in one of them you know the value of N from the start, and in the other you just have to keep printing out perfect powers until someone tells you to stop. They require different approaches, I think.
For the fixed-N interpretation, the first way I thought of was not very efficient memory-wise, but it sure does seem quick, at least in this initial stage. It is analogous to Erastothenes's sieve, as you shall see. It is as follows:
1. Initialize a vector A[1..N] of N single bits with all zeroes at first;
2. Print 1;
3. Set A[1] := 1;
4. Set i := 2;
5. If A[i] = 1, go to step 14
6. Set j := i;
7. Set A[i] := 1;
8. If i*j > N go to step 14
9. If A[i*j] = 1, go to step 15;
10. Set A[i*j] := 1;
11. Print i*j;
12. Set j := i*j;
13. Go to step 8;
14. If j = i, halt.
15. Set i := i + 1;
16. If i > N, halt.
17. Go to step 5;
In the above algorithm, I am pressuposing that N > 1. The idea behind it is really simple: take a number i and repeatedly find its powers, i2, ... , ik, marking them off, until ik+1 is greater than N. Then, go on to the next i. If some number i we encounter while running the algorithm is already crossed off, then i = jk for some j, k, which means any powers of i will be powers of j also, and have already been printed - so it is pointless to continue.
From number-theoretic considerations, it is clear that any number will be checked at most twice by the algorithm, which therefore runs linearly in N. The considerations are:
- a number x is a power yk iff the greatest common divisor of the exponents of the primes in its factorization is greater than 1;
- if a number x = yk, let G = GCD(exponents); then x = uG for some integer u;
- the number u is the smallest integer of which x is a power;
- if we have am = bn, then the factorization of these numbers coincide, and they have the same G. Further, G divides both m and n;
- hence, a = uG/m and b = uG/n, so that at least one of them would already have been crossed out
ah, it's getting late. If anyone reads this before I have a chance to fix it up tomorrow, please excuse me, but I DEFINITELY need to sleep now. I can't think straight anymore.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: jRe: New problem: perfect powers
« Reply #2 on: Nov 1st, 2002, 12:06am » |
Quote Modify
|
on Oct 31st, 2002, 10:25pm, Pietro K.C. wrote: With regard to the last question, I guess if we made a list of all the perfect powers from 1 to 10 million beforehand, and have the
|
|
32
print 8
[32,24]
print 9
[24,33]
print 16
[52, 33, 25]
print 25
[33, 25, 62, 53]
etc
It's based on a datastructure that combines a queue with a binary tree structure.. I'm too lazy to actually implement it and see how it works.. But I'm pretty sure it can do it in O(n log(n)) time
Basicly you start with the first square (22), then for every iteration pop the front, insert the next power (mn => mn+1), and if it's a square also insert the next square into the datastructure (m2n => (mn+1)2).
You have to make some effort to keep the tree balanced of course.. (else you'll get O(n2) )
// modified by Wiliam Wu on 2008-05-27. corruption from last forum crash caused thread to be unreadable. recovered most of it, but some of it was lost, precisely at this point in the thread.
|
| « Last Edit: May 27th, 2008, 12:55am by william wu » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New problem: perfect powers
« Reply #3 on: Nov 1st, 2002, 9:02am » |
Quote Modify
|
Towr,
I think the data structure you want is a heap. It allows you to add items quickly, and remove the smallest one easily. It also has no balancing issues!
I'm trying to understand exactly what your program does, but maybe this is a simpler way to do things (or maybe it's the same as yours?):
1) Fundamentally, what we're doing is searching through this two-dimensional array:
22 23 24 25 26 27 ...
32 33 34 35 36 37 ...
42 43 44 45 46 47 ...
52 53 54 55 56 57 ...
etc...
2) What I propose is that we effectively perform a "merge" of all the columns. We keep track of the top number in each column, and each step, we select the smallest out of those top values.
3) Luckily, you don't have to search all the columns at once. In fact, you only have to start searching column n after you start using the numbers in column n-1.
4) Just keep the top value from each column you're currently searching in sorted order in a data structure. Note that you have to remember which column a value came from.
5) Each step, you print out the smallest number (or don't print it, if it's a duplicate). Then you replace it in the data structure, with either one or two new values. Always add the next value down the column, and if you printed out the value at the top of a column, then add the top of the next column over.
6) The data structure grows to a size O(log(n)), obvious from looking at the first row.
7) Adding one element to the data structure is pretty quick, since it's in sorted order. I would recommend a heap (thanks, towr!), with O( log n ) insertions and O( log n ) removals.
 Since you print out fewer than O(sqrt(n)*log n) numbers, and to add each one takes at most O(log n) time, I would say you're looking at O(sqrt(n)*log2 n) time for the whole operation--definitely less than O(n)!
Of course, making this fast is another question entirely. I think the most important thing is to notice that the vast majority of the numbers are squares, so we should make sure that when we're squaring something, we multiply it by itself, rather than exponentiating. Probably this would be better for cubes too. Also, since most of the numbers are squares, we should make sure that our algorithm just leaves the first column at the top of the heap if it doesn't need sorting again. That will save some time. I'm sure you can think of a bunch more optimizations.
Okay, here's another optimization: ignore rows that have perfect squares as their base (row 4n, 8n, 9n, etc.). Implementing this might slow things down, however, and increase the code size to more than a page.
|
| « Last Edit: Nov 1st, 2002, 9:57am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New problem: perfect powers
« Reply #4 on: Nov 1st, 2002, 9:51am » |
Quote Modify
|
You guys are on the right track. You've missed one important optimization, though. Spoiler:
Every perfect power >1 can be represented in at least one way as ab where b is prime. Therefore you need only use the prime-numbered columns.
You're being much more clever in your choice of data structure to keep track of the next not-yet-printed number in each column than I and the other mid-1970's high school students were in the original contest. But I think we'd still beat you if you leave out the optimization above!
By the way, the difference between the two sets of rules is important in deciding how to implement this optimization. I'll explain that later if no one guesses it first.
Edit: fixed the error noted by James Fingas below
|
| « Last Edit: Nov 1st, 2002, 10:57am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New problem: perfect powers
« Reply #5 on: Nov 1st, 2002, 9:58am » |
Quote Modify
|
Correction to my reply to Pietro:
on Nov 1st, 2002, 12:49am, TimMann wrote:| However, a sieve approach would of course still work if you used two passes... |
|
Oops, actually, two passes aren't needed. It's a fairly simple modification to Pietro's algorithm to get it to print the powers in order. Do you see it?
|
| « Last Edit: Nov 1st, 2002, 9:59am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New problem: perfect powers
« Reply #6 on: Nov 1st, 2002, 10:50am » |
Quote Modify
|
Ahh! I see the light! That could help a fair bit...
It may be a better optimization than the one I just added to my solution (look at the bottom of my post now!)  ... or is it the same, just in another guise . Of course, yours might be easier to compute, because you use fewer columns than you do rows.
I disagree that all perfect powers have a unique representation in the way you say. Consider 46, which is 163, and also 642. Maybe my optimization is better after all
In terms of actual speed, however, since sqrt(N) of the numbers are from the first column, and sqrt(sqrt(N)) numbers are from the third column (the first non-prime column), it is probably more important how you compute the square of a number than whether or not you search the third column...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New problem: perfect powers
« Reply #7 on: Nov 1st, 2002, 10:57am » |
Quote Modify
|
Oops, you caught me before I edited that. Yes, the representation isn't unique, of course. That was a thinko. It's still an important optimization, I think.
Hmm, or does using a heap help so much that it doesn't matter a lot that you keep track of columns that are redundant? The high school students didn't know about heaps; if I remember right, we kept the head of each column in an array and used linear search each time to find the smallest. So eliminating redundant columns was important.
|
| « Last Edit: Nov 1st, 2002, 11:04am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New problem: perfect powers
« Reply #8 on: Nov 1st, 2002, 11:06am » |
Quote Modify
|
No, I would say that it's still important to get rid of the extra columns (or rows, or whatever). Even with the heap, you still have to delete the duplicates and sort them. But with the heap it's an additive factor, whereas with the linear search, it seems to be a multiplicative factor...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New problem: perfect powers
« Reply #9 on: Nov 1st, 2002, 6:59pm » |
Quote Modify
|
By the way, it looks to me like eliminating redundant columns is vastly better than eliminating redundant rows. (You can't do both at once, of course.)
- You need one entry in your heap for each active column, so eliminating redundant columns makes this structure smaller, while eliminating redundant rows doesn't.
- Redundant columns are those headed by composites, while redundant rows are those headed by perfect powers. Composites are a lot more frequent than perfect powers, so you eliminate much more of the table by eliminating columns.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Difference between rules
« Reply #10 on: Nov 1st, 2002, 7:13pm » |
Quote Modify
|
I'll tell this part of the story now. It doesn't look like anyone is going to guess it, and it's not that interesting to guess anyway.
To eliminate redundant columns, you need to be able to tell which columns are headed by composite numbers. How to do that? The winning entry in the original contest had a hard-coded list of the primes up to 71. This was fine for any N the judges were at all likely to test it up to -- they probably had a 32- or 36-bit machine. But it breaks the stricter rules, because the program would fail at 272.
So you need a decent algorithm for generating primes on the fly to adhere to the stricter rules. I don't know the state of the art on that.
In my original contest entry, it didn't occur to me to "cheat" and put in a list of primes, and I didn't know a good algorithm for generating them on the fly, so instead I used 2, 3, and all numbers of the form 6n-1 or 6n+1. This was good enough to get third place in the contest, but my program took 1.53 times as long to reach 100,000 as the one with the list of primes.
I didn't get to see the second place program, which took 1.43 times as long as the winner. In hindsight, I wonder what it did. The fourth place program was way slower (4.97x running time), and the rest were far worse than that.
Edit: Found the original contest results and corrected the running time data.
|
| « Last Edit: Nov 2nd, 2002, 1:27am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New problem: perfect powers
« Reply #11 on: Nov 4th, 2002, 12:03pm » |
Quote Modify
|
I really don't think that the method of finding the primes is important. You only use that method about 23 times up to 10,000,000. On the other hand, there are at least 3000 perfect powers below 10,000,000. I find it hard to believe that the prime-finding could take more than 10% of the program execution time.
Therefore, improvements in the inner loop would have much larger benefits than improvements in the prime-finding algorithm. Probably the winner just had a more optimized loop. Not that I could guess what the optimizations would have been ... actually, one killer optimization would have been to eliminate excessive use of the 'print' statement, and print off the perfect powers 10 at a time or so. Maybe things like this are a little too tricky ...
You are probably right that eliminating rows is useless--it would take so much extra time to eliminate a row that it would be faster just to notice duplicates after-the-fact. Plus eliminating a row involves finding perfect numbers, and if we could do that fast
|
| « Last Edit: Nov 4th, 2002, 12:06pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New problem: perfect powers
« Reply #12 on: Nov 4th, 2002, 2:11pm » |
Quote Modify
|
Note that I wasn't just finding primes a different way; I was being sloppy and not using only primes. However, I guess that shouldn't have made any difference for running only up to 100,000! The first composite I'd fail to eliminate would have been 25, and 225 is already beyond where the judges tested up to.
So perhaps it had to be a difference in the inner loop. If I can find both programs somewhere in my files, I'll take a look. It's funny to realize this after all these years! I bet the judges didn't realize it either.
(By the way: Eliminating a row involves eliminating perfect powers, of course, not perfect numbers. It involves eliminating perfect powers that we've already printed, so that part's OK, but it does take extra memory to save them around instead of forgetting about them as soon as they're printed.)
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Perfect powers 
(attachment deleted)
« Reply #13 on: May 30th, 2004, 11:34am » |
Quote Modify
|
I had a look at this interesting problem and I came to the following conclusion:
As Tim mentionned, it is only necessary to consider ab where b is prime.
Now consider 511 = 4882815. It is already >10000000. So, you just need to consider ab where a<5 or b<11. That means a=2,3,4 and b=2,3,5,7.
It is easy to track the next power for the 3 rows and the 4 columns. You just have to make a big loop, find the smallest of 7 numbers, print it, and compute the next value for the rows/columns that equal the minimum. With this method, I could generate the whole list in ~one millisecond on a 450 Mhz PC and a modern C compiler. Without printing. I just generate it and compare the result with a list calculated previously using a sieve.
Now, If for the general case you have to find m such that mm>N. m is o(log(N)). Then, compute the primes <m one time, and loop as many times as there are numbers to print. Inside the loop, there are <2m comparisons. There are exponent calculations, as many as there are ab below N. These are O(sqrt(N)).
So the total execution time would be O(output size*m) which is better than O(sqrt(N)*log(N)).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print