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: John H Meyers on 25 Mar 2010 08:57 Videos! http://www.youtube.com/watch?v=1kvdq8cRNBM http://www.youtube.com/watch?v=-cPBNMe0TOE http://www.youtube.com/watch?v=ru0NLrPsQeg Compare that with how little ramen you can cook by reversing the batteries in an HP48, and you'll no doubt see the wisdom (and pleasure) of diving full-bore into the hardware business, instead of chasing a few small digits :) [r->] [OFF]
From: Joe Horn on 25 Mar 2010 12:09 > That's why I think we should have some "challenges" take the form > of devising the most convoluted and wasteful way to do something, > to be more like real life :) Heh heh! Reminds me of good old "Bogosort", the worst possible algorithm for sorting a list: http://www.hpcalc.org/details.php?id=6705 -Joe-
From: Wes on 25 Mar 2010 12:37 On Mar 25, 5:02 am, Han <handuongs...(a)gmail.com> wrote: > > 91.4 seconds. #306Dh 141 bytes. > > I am really enjoying this MC. > 72.8 seconds, #A937h, 176 bytes > Winner: Fastest solver that doesn't cheat. > Use programming tricks, and/or math tricks (e.g. number theory), > whatever pleases you. I'm finding that these two statements are starting to collide with each other! A simple check shows that the answer must end in one of the 5 following digits: 2, 4, 5, 6, or 8; thus eliminating half of the possible values to check. I don't think anyone would describe this as cheating. However, a little more checking reveals that the last two digits of the answer must be one of only 24 possible values, resulting in a 37.0 second program. A similar check of the last three digits of the answer reveals that the last three digits must be one of 112 possible values, resulting in an 11.8 second program. If you apply the same logic to the last four digits, ... well, let's just say it would be a very fast program. So how much logic is too much? > Remember the #1 goal of mini-challenges is not to win but to > have fun. If you are enjoying the journey, you're on the right > path. Then I'm definitely on the right path. :-) Thanks Joe. -wes
From: Han on 25 Mar 2010 13:17 > A simple check shows that the answer must end in one of the 5 > following digits: 2, 4, 5, 6, or 8; thus eliminating half of the > possible values to check. I don't think anyone would describe this as > cheating. You can actually eliminate the 5 as well. One can prove that our desired number cannot end in an odd digit by considering any number written as 10a+b where b is the least significant digit. For example, 2375 = 273*10+5. You can extend the proof to more digits. > However, a little more checking reveals that the last two digits of > the answer must be one of only 24 possible values, resulting in a 37.0 > second program. > This is what I was getting at when I asked "is this a math question, or a programming one?" =) Personally, I am more interested in the mathematics behind this problem. On the other hand, suppose we require that all programs take the input of N and do an "honest" search starting at the value of N. That is, the program should output the first integer M > N such that M^4 does not have small digits. 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)
From: Han on 25 Mar 2010 13:31
> 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? |