2007-01-29 19:08:00 · 9 answers · asked by Anonymous in Entertainment & Music ➔ Jokes & Riddles
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, ...
"Fast" is intentionally fuzzy. 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?
Note: From a 1977 high school programming contest (Tim Mann).
2007-01-29 19:26:36 · answer #1 · answered by Anonymous · 1⤊ 2⤋
A perfect power is a number of the form , where is a positive integer and . If the prime factorization of is , then is a perfect power iff .
Including duplications (i.e., taking all numbers up to some cutoff and taking all their powers) and taking , the first few are 4, 8, 9, 16, 16, 25, 27, 32, 36, 49, 64, 64, 64, ... (Sloane's A072103). Here, 16 is duplicated since
(1)
As shown by Goldbach, the sum of reciprocals of perfect powers (excluding 1) with duplications converges,
(2)
The first few numbers that are perfect powers in more than one way are 16, 64, 81, 256, 512, 625, 729, 1024, 1296, 2401, 4096, ... (Sloane's A117453).
The first few perfect powers without duplications are 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 125, 128, ... (Sloane's A001597). Even more amazingly, the sum of the reciprocals of these numbers (excluding 1) is given by
(3)
(Sloane's A072102), where is the Möbius function and is the Riemann zeta function.
The numbers of perfect powers without duplications less than 10, , , ... are 4, 13, 41, 125, 367, ... (Sloane's A070428).
2007-01-30 03:41:05 · answer #2 · answered by annite 2 · 0⤊ 0⤋
I think that the perfect powers would have to be to have power over the 4 elements
earth
wind
fire
water
Wouldn't it just be Fantastic!!
2007-01-30 03:38:34 · answer #3 · answered by Noir.... 6 · 0⤊ 0⤋
I think perfect powers are those powers which every mother has, she could sense everything in our mind before we could say anything. I think mothers are the best example anyone could give for "Perfect Powers".
If you want more,
You've always got:
India's first superhero,
i.e.
Krrish for savour!!
2007-01-30 03:28:34 · answer #4 · answered by Diya 3 · 0⤊ 0⤋
will powers is the perfect powers .
2007-01-30 04:05:59 · answer #5 · answered by silu 1 · 0⤊ 0⤋
Would have perfect powers if were a genie
2007-01-30 03:18:32 · answer #6 · answered by flower_from_the_heavens 4 · 0⤊ 0⤋
power that turns everything around...but doesn't move...i believe...;-)
2007-01-30 03:23:36 · answer #7 · answered by Anonymous · 0⤊ 0⤋
yur wierd
2007-01-30 03:11:24 · answer #8 · answered by te quiero tanto 3 · 0⤊ 0⤋
wha?
2007-01-30 03:13:53 · answer #9 · answered by dre777 3 · 0⤊ 0⤋