MC: 4th power with no small digits
in [HP48]
|
Prev: (Sorry for the non french speaking peoples) Un logiciel de géométrie dynamique pour HP
Next: Dust inside 50g. How to clean? How to prevent?
From: Veli-Pekka.Nousiainen on 25 Mar 2010 15:32 Han wrote: >> So how much logic is too much? >> > > In terms of pure speed, I think you would have to simply compare the > runtime of computing N^4 and determining if it has small digits with > the runtime of actually producing the possible values of N to check. > This is all up in my head, but what I was thinking was the following > algorithm. > > Let L be a list of all the valid last d digits. (1) Check if the last > d digits of N belongs to the list L. If so, then (2) test N^4. > > As our list gets larger, could (1) possibly take more time than just > doing (2), for a given N? Me thinks th list is cheating unless you construct the list using an algorithm...
From: Dave Hayden on 25 Mar 2010 17:22 One can also eliminate possibilities by considering the first digit also. If X^4 has N+1 digits, then the answer must lie between 5x10^N and 10^(N+1). You can then work backwards ranges of possible values of X: N minimum X maximum X 1 3 3 2 5 5 3 9 10 4 15 17 5 27 31 6 48 56 7 85 100 8 150 177 9 266 316 .... 12 1496 1778 13 2660 3162 Combining this with the techniques to eliminate the lower digits, you'd probably arrive at an answer very quickly indeed! Thanks for the MC!
From: John H Meyers on 25 Mar 2010 17:48 On 3/25/2010 12:17 PM, Han wrote: > On other thing I thought I should mention: the HP49G+ and HP50G take > more time to do number crunching when the inputs are integers as > opposed to real numbers. I was able to chop off a huge chunk of time > simply by changing " 1 - " to " 1. - " (I believe integer operations > take twice as long as real number operations) Is the result then raised to the 4th power? Is there a quick way to get all digits of a 4th power of N > 999 using "reals"? "User binary" can do 4th powers exactly, up to N < 2^16, then it, too, runs up against a limit which "integer" decimal arithmetic does not have. But Jim Horn may have something in mind, besides already knowing that the answer is less than 2^16 (is it "cheating" to already know that?) If it's this difficult to know what's "legal" in a calculator MC, how will we ever figure it out in the rest of life? Do we have the Supreme Court to turn to? What if it's a "split" 5-4 decision? It's a good thing that the only goal is to have fun, which means that Wall Street will not have a stake in this outcome, nor will the military-industrial complex: "In the councils of government, we must guard against the acquisition of unwarranted influence, whether sought or unsought, by the military-industrial complex. The potential for the disastrous rise of misplaced power exists and will persist. We must never let the weight of this combination endanger our liberties or democratic processes. We should take nothing for granted. Only an alert and knowledgeable citizenry can compel the proper meshing of the huge industrial and military machinery of defense with our peaceful methods and goals, so that security and liberty may prosper together." Dwight David Eisenhower, January 17 1961 http://www.youtube.com/watch?v=8y06NSBBRtY http://international-politics.suite101.com/article.cfm/the_world_of_the_military_industrial_complex http://en.wikipedia.org/wiki/Military-industrial_complex http://www.h-net.org/~hst306/documents/indust.html http://en.wikipedia.org/wiki/Dwight_D._Eisenhower http://www.whitehouse.gov/about/presidents/dwightdeisenhower http://www.history.army.mil/brochures/ike/ike.htm "Cadet Eisenhower, United States Military Academy Class of 1915. Classmates regarded him as a natural leader who looked for ways to smooth over disputes and organize a group's efforts toward a common goal." (photo caption in above document) -[ ]-
From: Han on 25 Mar 2010 18:43 > > On other thing I thought I should mention: the HP49G+ and HP50G take > > more time to do number crunching when the inputs are integers as > > opposed to real numbers. I was able to chop off a huge chunk of time > > simply by changing " 1 - " to " 1. - " (I believe integer operations > > take twice as long as real number operations) > > Is the result then raised to the 4th power? > No, I was referring to a portion in my program that decides if a number has a small digit. << 4 ^ ->STR DUP SIZE DO 1. - UNTIL DUP2 DUP SUB "4" > OVER AND NOT END SWAP DROP >> I only test against numbers ending in 2, 4, 6, or 8. Since raising such numbers to the 4th power always produces an integer ending in 6, we can skip checking the last digit. If you change 1. to 1 then the runtime will increase dramatically when looping over a large set of numbers. I also had to test whether AND is faster than * (originally I had used * but found that AND is faster than * when operating on an integer and real).
From: Han on 25 Mar 2010 19:08
On Mar 25, 3:32 pm, "Veli-Pekka.Nousiainen" <velipekka.nousiai...(a)saunalahti.fi> wrote: > Han wrote: > >> So how much logic is too much? > > > In terms of pure speed, I think you would have to simply compare the > > runtime of computing N^4 and determining if it has small digits with > > the runtime of actually producing the possible values of N to check. > > This is all up in my head, but what I was thinking was the following > > algorithm. > > > Let L be a list of all the valid last d digits. (1) Check if the last > > d digits of N belongs to the list L. If so, then (2) test N^4. > > > As our list gets larger, could (1) possibly take more time than just > > doing (2), for a given N? > > Me thinks th list is cheating unless you construct the list using an > algorithm... What if you can mathematically prove that any N such that N^4 cannot end in certain digits? Would such a list of digits be allowed? By analogy, suppose we are looking for primes. Can we use the fact that all primes larger than 2 cannot be even? |