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 30 Mar 2010 13:40 On 3/29/2010 10:02 PM, Han wrote: > "{\"0\"\"1\"\"2\"\"3\"\"4" STR\-> STR\-> also invokes the compiler, which is probably quite costly to execution time. Much of life's effort is probably devoted to evaluating trade-offs, and positioning oneself at the best distance from both the Devil and the Deep Blue Sea :) Some old MCs attempted to minimize size*time, as some sort of compromise, but there are always other intangibles to real life situations, such as how long it takes to develop (and perhaps debug) a program, and how much time is left for lunch (which is right now my immediate concern :) Thanks for the notes. --
From: Scott Hemphill on 3 Apr 2010 09:25 John H Meyers <jhmeyers(a)nomail.invalid> writes: > On 3/29/2010 5:58 PM: > >> @ Fourth power of positive integer having no digit less than 5 >> >> @ Short (size) program for HP49/50 >> @ can search until insufficient memory to hold data >> \<< 0 DO 1 + DUP SQ SQ \->STR >> { "0" "1" "2" "3" "4" } POS >> UNTIL \GSLIST NOT END \>> >> >> @ Program for HP48G[X], can search up to 2^16-1 >> \<< 64 STWS DEC #0 DO 1 + DUP DUP * DUP * \->STR >> { "0" "1" "2" "3" "4" } POS >> UNTIL \GSLIST NOT END \>> >> >> @ [End] > > If we accept having proved that all odd 4th powers > end in "1" or "25" (and thus would be rejected) > then we can change 1 + to 2 + > to approximately halve the times of the above. > > \GSLIST NOT can also be replaced by { 0. 0. 0. 0. 0. } SAME > to be a bit faster, at the expense of larger program. It's also true that all 4th powers of numbers that start with 6 or 7 lie between 1296... and 4095... and therefore can be eliminated. But eliminating these would make the code more complex, and it's not clear whether you could reduce the time. Scott -- Scott Hemphill hemphill(a)alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear
From: Scott Hemphill on 3 Apr 2010 13:29
Joe Horn <joehorn(a)holyjoe.net> writes: >> Presuming that you have already found one such integer, do you have a >> proof that there cannot be more than one? > > I have no proof that the known solution is the only solution, nor do I > have a proof that another solution exists. A fast PC (Intel Core i5 > 750 @ 2.67 GHz) running 4 parallel loops failed to find another > solution after several hours; ergo, if another solution exists, it is > extremely large. None of this has anything to do with the mini- > challenge, although it is stimulating in its own right as a math > problem. Did you know that X^12 always contains a 0 or a 1? But I > digress. How far did you let your program run? This is not a proof, but it can educate our expectations: Let the digits (5..9) be called "good" and the digits (0..4) be called "bad". Also a "good" integer is a positive integer whose decimal digits are all good. If any decimal digits are bad, then a positive integer is "bad". If you take a collection of fourth powers of a range of integers, you find that the last few digits are not evenly distributed, and the first few digits are not evenly distributed, but the middle digits are pretty evenly distributed. So the middle digits of a random integer have a 50% chance of being good. For large integers, almost all of the digits are "middle digits", so the chance of a k-digit number being good is approximately (1/2)^k. The number of decimal digits in an integer n is FLOOR(LOG(n)+1). For large n, this will be approximately LOG(n). The number of digits in n^4 will be approximately 4*LOG(n). Each one of these digits has a (1/2) chance of being good, so the chance of the entire fourth power being good is (1/2)^(4*LOG(n)) = n^-s, where s = 4*LOG(2) ~= 1.20412 So the chance of a large number n having a good fourth power is pretty small, since it is even less than 1/n. The question is, what is the expected total number of solutions? In other words, what is the sum of the probabilities for all integer n? Ignoring the fact that our approximation isn't very good for small n, the sum is sum(1..infinity, n^-s) = zeta(s) This is the Riemann Zeta function. If you haven't seen this function before, you may be intrigued to know that, e.g. the infinite series 1 + 1/4 + 1/9 + 1/16 + 1/25 + ... + 1/k^2 + ... converges to the sum pi^2/6. In fact all positive even values for s produce a sum which is a rational multiple of pi^s. But the key thing here is that as long as s is greater than 1, the sum converges. That means we can expect a finite number of solutions to our problem. In this case, zeta(4*LOG(2)) ~= 5.49095. So if our approximations our good, we can expect about 5 solutions. However, most of the contribution to the sum is due to the small integers. If we have ruled out all the integers up through 1000, we can form the sum sum(1001..infinity, n^-s) ~= 1.19594 So it is still expected that there might be one solution beyond 1000. If we've tested everything up to one million, the expected number of solutions beyond that is 0.292008. I've tested all the integers out to 10^15. The expected number of solutions beyond that is down to 0.00424927. So there's still a small chance of finding another solution. Note that the key thing about whether there are a finite number of solutions depends on the fact that 4*LOG(2) is greater than one. If we had been interested in cubes instead of fourth powers we would have s = 3*LOG(2) ~= 0.90309, and expect an infinite number of solutions. Similarly, for squares. For all powers greater than the fourth, the expected number of solutions is finite. There is one obvious solution for fifth powers. Are there any other solutions for fifth or higher powers? Another thing to note is that my approximations didn't depend on which digits were good and which were bad. They only depended on the fact that half the digits were good. However, if zero is included as a good digit, the approximations don't work, since if you have one solution, you can always append any number of zeros to the end of it to produce infinitely more solutions. So if you interchange the definition of good and bad digits are there any solutions other than 10^k for fourth powers? Scott -- Scott Hemphill hemphill(a)alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear |