From: John H Meyers on
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
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
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