COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

MC: 4th power with no small digits

• Follow

```It would *seem* that all integers raised to the 4th power contain at
least one digit less than 5.  For example, 26 to the 4th power is
456976, which contains a 4.  However, there does exist a positive
integer X such that X^4 contains no digits less than 5.

Mini-challenge: Write a User-RPL program that finds the only (?)
positive integer X such that X^4 contains no digits less than 5.

Winner: Fastest solver that doesn't cheat.

-Joe-
```
 0

```On Mar 23, 5:14=A0pm, Joe Horn <joeh...@holyjoe.net> wrote:
> It would *seem* that all integers raised to the 4th power contain at
> least one digit less than 5. =A0For example, 26 to the 4th power is
> 456976, which contains a 4. =A0However, there does exist a positive
> integer X such that X^4 contains no digits less than 5.
>
> Mini-challenge: Write a User-RPL program that finds the only (?)
> positive integer X such that X^4 contains no digits less than 5.
>
> Winner: Fastest solver that doesn't cheat.
>
> -Joe-

Is this really a math problem at heart? or did you actually want a
programming problem? The difference for me lies in whether or not we
are supposed to (a) do a search for such an x versus (b) simply coming
up with a method for determining if a given x satisfies the conditions
above. Problem (a) is more of a mathematical problem. Assuming our
program has to also verify that all smaller integers have "small"
digits when raised to the power of 4, one can eliminate various
classes of integers from the search. This knowledge would certainly
produce a program that is faster than a program by someone who is not
as familiar with properties of integers. Problem (b) is more of a
programming problem, phrased in my mind as: how would one implement in
User-RPL a routine that quickly determines if x^4 has a "small" digit?

Perhaps you can clarify the problem by setting up what the expected
input and output of the program should be.
```
 0

```In article
Joe Horn <joehorn@holyjoe.net> wrote:

> It would *seem* that all integers raised to the 4th power contain at
> least one digit less than 5.  For example, 26 to the 4th power is
> 456976, which contains a 4.  However, there does exist a positive
> integer X such that X^4 contains no digits less than 5.
>
> Mini-challenge: Write a User-RPL program that finds the only (?)
> positive integer X such that X^4 contains no digits less than 5.
>
> Winner: Fastest solver that doesn't cheat.
>
> -Joe-

Presuming that you have already found one such integer, do you have a
proof that there cannot be more than oner?

If not, I suggest that you ask for a program which finds the smallest
such integer.
```
 0

```> Is this really a math problem at heart? or did you actually want a
> programming problem?

The mini-challenge is a programming one.  The *implied* math challenge
is far from mini, and probably belongs in a math newsgroup.

> Perhaps you can clarify the problem by setting up what the expected
> input and output of the program should be.

Input: none; output: solution.  Since the winner is determined by
minimal runtime (the "fastest" program), optimizing the program is
left up to the cleverness of the programer.  Use programming tricks,
and/or math tricks (e.g. number theory), whatever pleases you.
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.  Yes,
you may quote me on that. ;-)

The other usual rules apply: No embedded machine language; single
leads to an interesting diversion, go for it.  It's all about having
fun.

-Joe-
```
 0

```Well, Excel makes it easy to search manually, giving me 0xB34 in short
order.  I know, that doesn't count.  Gotta keep my HP50g where I can
get at it (or put a programming language on my work laptop).

Where *do* you come up with these interesting problems, anywho?

Jim   (Why the Hex answer?  Don't want to give it entirely away for
those who want to solve it themselves)
```
 0

```> 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.

> If not, I suggest that you ask for a program which finds the smallest
> such integer.

Or we can go the other direction and simply ask for ANY solution,
whether smallest or not.  Whatever.  It only matters if other
solutions actually exist, which the Achilles in me tends to doubt.
(cf. "G=F6del, Escher, Bach")

-Joe-
```
 0

```On Mar 23, 7:25=A0pm, Jim Horn <jamesludwigh...@gmail.com> wrote:
> Well, Excel makes it easy to search manually, giving me 0xB34 in short
> order. =A0I know, that doesn't count. =A0Gotta keep my HP50g where I can
> get at it (or put a programming language on my work laptop).
>
> Where *do* you come up with these interesting problems, anywho?
>
> Jim =A0 (Why the Hex answer? =A0Don't want to give it entirely away for
> those who want to solve it themselves)

My HP 49G+ just confirmed Jim's answer. Using TIME and HMS-:
0.0429166382 (just under 4.5 minutes). I'm working on improving the
algorithm. Let's see how quickly this time is destroyed. =3D)
```
 0

```> Where *do* you come up with these interesting problems, anywho?

Tumbolia, the place where hiccups go when they go away.  ;-)

-Joe-
```
 0

```> My HP 49G+ just confirmed Jim's answer. Using TIME and HMS-:
> 0.0429166382 (just under 4.5 minutes). I'm working on improving the
> algorithm. Let's see how quickly this time is destroyed. =)

Current speed: 0.0256074341 (2 minutes 56 seconds)
```
 0

```On Mar 23, 4:48=A0pm, Joe Horn <joeh...@holyjoe.net> wrote:
> > Where *do* you come up with these interesting problems, anywho?
>
> Tumbolia, the place where hiccups go when they go away. =A0;-)
>
> -Joe-

Uh, as I recall, one of the GEB dialogs refers to Tumbolia as the
destination of lost / mismatched socks.  Those two ingredients lead to
a disquieting mental image...
```
 0

```> > Tumbolia, the place where hiccups go when they go away. =A0;-)
>
> Uh, as I recall, one of the GEB dialogs refers to Tumbolia as the
> destination of lost / mismatched socks. =A0Those two ingredients lead to
> a disquieting mental image...

That's why getting a good sock in the mouth makes hiccups go away.

-Joe-
```
 0

```On Mar 24, 3:19=A0am, Han <handuongs...@gmail.com> wrote:
> > My HP 49G+ just confirmed Jim's answer. Using TIME and HMS-:
> > 0.0429166382 (just under 4.5 minutes). I'm working on improving the
> > algorithm. Let's see how quickly this time is destroyed. =3D)
>
> Current speed: 0.0256074341 (2 minutes 56 seconds)

I've got 124.5 seconds (2 minutes 4.5 seconds) using TEVAL.

-wes
```
 0

```On Mar 24, 8:21=A0pm, Wes <wjltemp...@yahoo.com> wrote:
> On Mar 24, 3:19=A0am, Han <handuongs...@gmail.com> wrote:
>
> > > My HP 49G+ just confirmed Jim's answer. Using TIME and HMS-:
> > > 0.0429166382 (just under 4.5 minutes). I'm working on improving the
> > > algorithm. Let's see how quickly this time is destroyed. =3D)
>
> > Current speed: 0.0256074341 (2 minutes 56 seconds)
>
> I've got 124.5 seconds (2 minutes 4.5 seconds) using TEVAL.
>
> -wes

Make that 102.4 seconds (1 minute 42.4 seconds)

-wes
```
 0

```On Mar 24, 10:02=A0pm, Wes <wjltemp...@yahoo.com> wrote:
> On Mar 24, 8:21=A0pm, Wes <wjltemp...@yahoo.com> wrote:
>
> > On Mar 24, 3:19=A0am, Han <handuongs...@gmail.com> wrote:
>
> > > > My HP 49G+ just confirmed Jim's answer. Using TIME and HMS-:
> > > > 0.0429166382 (just under 4.5 minutes). I'm working on improving the
> > > > algorithm. Let's see how quickly this time is destroyed. =3D)
>
> > > Current speed: 0.0256074341 (2 minutes 56 seconds)
>
> > I've got 124.5 seconds (2 minutes 4.5 seconds) using TEVAL.
>
> > -wes
>
> Make that 102.4 seconds (1 minute 42.4 seconds)
>
> -wes

Down to 97.6 seconds

-wes
```
 0

```On Mar 24, 3:41=A0pm, Wes <wjltemp...@yahoo.com> wrote:
> On Mar 24, 10:02=A0pm, Wes <wjltemp...@yahoo.com> wrote:
>
>
>
> > On Mar 24, 8:21=A0pm, Wes <wjltemp...@yahoo.com> wrote:
>
> > > On Mar 24, 3:19=A0am, Han <handuongs...@gmail.com> wrote:
>
> > > > > My HP 49G+ just confirmed Jim's answer. Using TIME and HMS-:
> > > > > 0.0429166382 (just under 4.5 minutes). I'm working on improving t=
he
> > > > > algorithm. Let's see how quickly this time is destroyed. =3D)
>
> > > > Current speed: 0.0256074341 (2 minutes 56 seconds)
>
> > > I've got 124.5 seconds (2 minutes 4.5 seconds) using TEVAL.
>
> > > -wes
>
> > Make that 102.4 seconds (1 minute 42.4 seconds)
>
> > -wes
>
> Down to 97.6 seconds
>
> -wes

Very impressive... I've only managed to get down to about 115 seconds.
```
 0

```On Mar 24, 7:29=A0pm, Han <handuongs...@gmail.com> wrote:
> On Mar 24, 3:41=A0pm, Wes <wjltemp...@yahoo.com> wrote:
>
>
>
> > On Mar 24, 10:02=A0pm, Wes <wjltemp...@yahoo.com> wrote:
>
> > > On Mar 24, 8:21=A0pm, Wes <wjltemp...@yahoo.com> wrote:
>
> > > > On Mar 24, 3:19=A0am, Han <handuongs...@gmail.com> wrote:
>
> > > > > > My HP 49G+ just confirmed Jim's answer. Using TIME and HMS-:
> > > > > > 0.0429166382 (just under 4.5 minutes). I'm working on improving=
the
> > > > > > algorithm. Let's see how quickly this time is destroyed. =3D)
>
> > > > > Current speed: 0.0256074341 (2 minutes 56 seconds)
>
> > > > I've got 124.5 seconds (2 minutes 4.5 seconds) using TEVAL.
>
> > > > -wes
>
> > > Make that 102.4 seconds (1 minute 42.4 seconds)
>
> > > -wes
>
> > Down to 97.6 seconds
>
> > -wes
>
> Very impressive... I've only managed to get down to about 115 seconds.

New time: 92.10 seconds; program size: 181 bytes, checksum # 41D9h
```
 0

```In article
Han <handuongster@gmail.com> wrote:

> On Mar 24, 3:41�pm, Wes <wjltemp...@yahoo.com> wrote:
> > On Mar 24, 10:02�pm, Wes <wjltemp...@yahoo.com> wrote:
> >
> >
> >
> > > On Mar 24, 8:21�pm, Wes <wjltemp...@yahoo.com> wrote:
> >
> > > > On Mar 24, 3:19�am, Han <handuongs...@gmail.com> wrote:
> >
> > > > > > My HP 49G+ just confirmed Jim's answer. Using TIME and HMS-:
> > > > > > 0.0429166382 (just under 4.5 minutes). I'm working on improving the
> > > > > > algorithm. Let's see how quickly this time is destroyed. =)
> >
> > > > > Current speed: 0.0256074341 (2 minutes 56 seconds)
> >
> > > > I've got 124.5 seconds (2 minutes 4.5 seconds) using TEVAL.
> >
> > > > -wes
> >
> > > Make that 102.4 seconds (1 minute 42.4 seconds)
> >
> > > -wes
> >
> > Down to 97.6 seconds
> >
> > -wes
>
> Very impressive... I've only managed to get down to about 115 seconds.

91.4 seconds. #306Dh 141 bytes.
```
 0

```>
> 91.4 seconds. #306Dh 141 bytes.

I am really enjoying this MC.
72.8 seconds, #A937h, 176 bytes
```
 0

```On 3/24/2010 7:38 PM, Han wrote:

> New time: 92.10 seconds; program size: 181 bytes, checksum # 41D9h

80.5 thus far here.

What happens when time spent writing and entering a program
is added to the time spent running it, to produce
"time spent getting the answer" ?

[r->] [OFF]
```
 0

```> 80.5 thus far here.

That's bytes, not seconds -- on Emu48,
the "real time" (4-5 seconds with this Intel CPU)
is not "real calculator" time,
so comparison with calculator times is not available.

Individual calculators may also vary,
as may repeated results on even the same calculator
(try forcing a GC before each timing,
via MEM or even just ON/Cancel,
and run several times to ignore "outlier" times,
which seem to occur at random in the ARM emulator).

Byte counts seem to be more stable,
even though most of are paid by the hour, rather than by the byte
(hence the longest-running program may make the most money,
as do some of the most wasteful and poorly crafted
applications, operating systems, and political decisions :)

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 :)

http://www.rubegoldberg.com/ (Contest finals only two days from today!)

http://en.wikipedia.org/wiki/Rube_Goldberg_machine

http://en.wikipedia.org/wiki/Rube_Goldberg

[r->] [OFF]
```
 0

```Videos!

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]

```
 0

```> 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-
```
 0

```On Mar 25, 5:02=A0am, Han <handuongs...@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),

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
```
 0

```> 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. =A0I 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 =3D 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?" =3D) 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)
```
 0

```> 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?
```
 0

```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...
```
 0

```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!
```
 0

```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,
(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://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.history.army.mil/brochures/ike/ike.htm
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)

-[ ]-
```
 0

```> > 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).

```
 0

```> It would *seem* that all integers raised to the 4th power contain at
> least one digit less than 5. =A0For example, 26 to the 4th power is
> 456976, which contains a 4. =A0However, there does exist a positive
> integer X such that X^4 contains no digits less than 5.
>

I am starting to believe that it is possible to solve this problem
completely using elementary number theory. Let's see what a few more
days of proofs produce =3D)
```
 0

```On Mar 23, 8:23=A0pm, Joe Horn <joeh...@holyjoe.net> wrote:
> > > Tumbolia, the place where hiccups go when they go away. =A0;-)
>
> > Uh, as I recall, one of the GEB dialogs refers to Tumbolia as the
> > destination of lost / mismatched socks. =A0Those two ingredients lead t=
o
> > a disquieting mental image...
>
> That's why getting a good sock in the mouth makes hiccups go away.
>
> -Joe-

Ahmghnathkuhfthtwhn
(removes sock from mouth)
I'm gonna sock you for that one. *hic*

Brian
```
 0

```Hi everyone,

Can I just say that I love this?

I just bought my first HP calculator a few months ago.  Not used an
RPN
calculator before, though did do Forth programming earlier in my
career
so very familiar with the concept.

I bought the HP48Gii which I know a lot of you will probably have a
problem with, but I couldn't really afford or justify an HP50g, though
I
might buy one one day if I really use this one a lot.
It's also the duff old HP48Gii with only 3xAAA and no USB port.  Read
several things saying this one had been superseded, but even HP's
website now lists the model I have as current and doesn't mention a
USB
version.

I happened upon this group while using google to search for the
solution
to a problem I had.  What luck!

Anyway, I managed to solve the MC, though my version of the program
took
just over an hour to run! :-D

I really wasn't trying hard to optimise it, I just wanted to produce
something and to try out some of the stuff I've learned since I bought
the calculator.

I also wanted to break the program down into manageable chunks so I
used
several routines to achieve what I wanted to do.  I know this will
probably affect how long it took significantly, but I'm really just
doing this for fun and to learn, not to compete! :-)

Here's what I did, if anyone is interested.  Don't rip it all apart,
but

First I figured that I would want to work out how to check if one of
these numbers matches the criterion of having no digits less than 5,
and
to do this I would want to treat each digit separately, so I thought
it
would be nice to separate the number out into a list of digits.

My first routine takes a number from the stack, and returns to the
stack
the last digit along with the rest of the number ready for processing:

GetD:
<< DUP 10 IDIV2 DROP SWAP 10 MOD >>
e.g. 123 GetD returns 12 3

The next routine takes a list and a number, and returns the same list
with the last digit of the number added, plus the rest of the number
for
processing:

<< GetD ROT SWAP + SWAP >>
e.g. { 1 } 23 returns {1, 2} 3

The next routine takes a number from the stack, and returns a list
containing the digits of that number on the stack

DList:
<< { } SWAP
WHILE
DUP 0 <>     # ok, so really it's the proper not equals symbol!
REPEAT
END DROP
>>
e.g. 12345 returns {1, 2, 3, 4, 5}

The next routine tests if a number has any digits less than 5.  I was
thinking about how to do a foreach type thing and how I could write
something to run a given routine on each element of a list and either
AND or OR the results together.  Then I remembered that I can do an
operation on a list and it does it on each element.
I really like this!

DigL5:
<< DList 5 >= #LIST NOT >>    # #LIST's # is really pi for product of
#list.

So then I did my main routine.  I skipped doing 1, since I found that
#LIST fails with one element.  Seems kind of daft to me, surely it
should just return that element, but never mind.
<< 2 -> X
<< WHILE X 4 ^ DigL5
REPEAT X 1 + DUP 'X' STO 4 DISP
END X
>>
>>
This returns the answer as Jim revealed above.

The DISP stuff was just added so I can tell it is really doing
something
because it takes so long!

I'll probably spend some time looking at how I can optimise it now.
One obvious optimisation, now I've structured it so I can understand
what's
going on would be to get rid of some of these abstraction layers.
Then
I'll be able to, for example, abort checking a number when I first see
a digit
<5 rather than having to extract all the digits before I process any
of
them.

Thanks very much Joe.  That was a very entertaining diversion, and
it's
really helping me to get acquainted with this great machine.

Hope I haven't bored everyone too rigid with all the detail!

Stephen Blythe

```
 0

```I think your program is great for someone who just recently started
programming in RPL. Over time you will learn how to optimize your
program as you discover how certain objects are handled by the
calculator. Also, the more mathematics you know (about the problem),
the more you can optimize your program.

For example, is it necessary to actually create a list of all the
digits prior to checking each digit? Perhaps within your subroutine
that extracts each digit, you may as well test the digit too... and
stop as soon as you find a "small" digit. You will eventually see that
oftentimes, there is a lot of "checking" that is extraneous. Regarding
what I just wrote, if you notice that the first digit is already
"small", then is there any reason to check the remaining digits?

Other things to try: consider turning a number into a character
string, and search the digits that way (see the SUB command). You may
find that extracting characters from a string requires less of the CPU
than using integer division. Moreover, the effect you want can also be
achieved with HEAD and TAIL (these are commands).

Anyway, as Joe said from the outset -- the key is to have fun. Judging
from your post, I think you've done just that! Good luck in your
pursuit of understanding RPN, RPL, and the HP series of calculators!

Han
```
 0

```On Mar 26, 7:05=A0pm, stephen <s...@urwick.co.uk> wrote:
> Hi everyone,

> I bought the HP48Gii which I know a lot of you will probably have a
> problem with, but I couldn't really afford or justify an HP50g, though
> I
> might buy one one day if I really use this one a lot.
> It's also the duff old HP48Gii with only 3xAAA and no USB port. =A0Read
> several things saying this one had been superseded, but even HP's
> website now lists the model I have as current and doesn't mention a
> USB
> version.

Personally, I think the 48gII is an excellent value.  Check out
HPUserEdit or Debug4x for programming. It's much easier to develop
programs on a PC and then download them to the calculator when you're
done.

> Anyway, I managed to solve the MC, though my version of the program
> took
> just over an hour to run! :-D

I think your post is an excellent example of how to break a program
into manageable parts, so even though it might not be super fast, it's
a great tutorial.  Thanks for posting it.

Dave

```
 0

```Thank you very much, Dave and Han, for the encouragement and advice!

I've got it down to about 7.5 minutes now.

I created this little program to help me to time it:

Just put the name of the program on the stack and run this one:

TimIt:
<< TIME -> X << EVAL TIME HMS-> X HMS-> - 3600 * "dt(s)" ->TAG >> >>

Thanks,

Stephen
```
 0

```> TimIt:
> << TIME -> X << EVAL TIME HMS-> X HMS-> - 3600 * "dt(s)" ->TAG >> >>

Good. Now look at the command TEVAL. Input is an item to
evaluate. . . :-)

TW
```
 0

```On 27 Mar, 18:58, TW <timwess...@gmail.com> wrote:
> > TimIt:
> > << TIME -> X << EVAL TIME HMS-> X HMS-> - 3600 * "dt(s)" ->TAG >> >>
>
> Good. Now look at the command TEVAL. Input is an item to
> evaluate. . . :-)
>
> TW

Oh great! I'm going to assign a user key for that one! :)

Thanks,

Stephen
```
 0

```Here's my solution. TEVAL on my 50g says it takes 26.3 seconds.
This program skips candidates ending in odd digits.  It further
restricts
he candidates by considering only those ranges of X that can result
in X^4 beginning with a digit between 5 and 9.

=AB 1 1. 0. =8D N OK ANSWER=AB
@ N is the number of digits in X^4
@ OK is a temporary

@ If X^4 has N digits then
@ 5x10^N < X^4 < 10^(N+1)
@ Also, it can be shown that numbers ending
@ in an odd digit always result in a small
@ value for the least significant digit (or
@ the second digit when last digit=3D5).  Numbers
@ ending in zero are also bad.

@ Compute low bound for X
5. LOG N + 4. / ALOG CEIL
IF DUP 2. MOD THEN 1. + END

@ Compute high bound for X
N 1. + 4. / ALOG FLOOR
IF DUP 2. MOD THEN 1. - END

FOR X
X 1. DISP
X R=8DI 4 ^ =8DSTR
1. 'OK' STO
WHILE DUP SIZE OK AND REPEAT
DUP HEAD "4" > 'OK' STO
TAIL
END
DROP
IF OK THEN
1.E499 'X' STO  @ stop the loop
END
2.
STEP @ even numbers only
1. 'N' STO+
END
=BB
=BB
```
 0

```Here is a solution in HPGCC.  On the 50g with TEVAL it takes 0.076
seconds.

Note that the original post specified User RPL, so this only qualifies
as an "interesting cheat." :)

Interestingly, calling sys_slowOff()/sys_slowOn() made no difference.
I suspect that most of the runtime is spent just loading the program.

Dave
---------------------

#include <hpgcc49.h>
#include "hpobjects.h"

int main (int argc, char **argv)
{
unsigned rpl_stack_bias = sat_stack_init();

int N;
long long X=0;
long long X4;		/* X^4 */

for (N=1; answer == 0; ++N) {
int low, high;

low = ceil(pow((log10(5) + N) / 4, 10));
if (low % 2) ++low;

high = floor(pow( (N+1)/4.0, 10));
if (high % 2) --high;

for (X=low; X <= high; X += 2) {
char buf[50];
int i;
int len;
int ok = 1;
X4 = X*X*X*X;
sprintf(buf, "%L", X4);
len = strlen(buf);
for (i=1; ok && i < len; ++i) {
if (buf[i] < '5') ok = 0;
}
if (ok) {
// You found it!!
break;
}
}
}
STACKpush(REALencode((double)X, 0));
sat_stack_exit(rpl_stack_bias);
return 0;
}
```
 0

```Dave,

Here are some slight modifications of your code. Mainly, HEAD and TAIL
are slow. Also, there is really no need to take the FLOOR of the upper
a filter for the last 2 digits; however, since the numbers in the
range 10^[(d+log(5)/4] ... 10^[(d+1)/4] is relatively small even for
14 digit numbers, and the time required to test the last two digits of
n (must compare against at most 24 values) is actually higher than
just testing all the digits of n^4 (at most 14), we would only include
the filter for sufficiently large d.

The only problem with the code below is that we are limited to 44-
digit integers unless we convert %n_low and %n_high to integers prior
to the FOR n statement (which eliminates the need for R->I). This can
easily be adjusted; however, computing with integers takes more time
than computing with reals.

This runs in about 17.58 seconds.

<<
0. 1.			@ n (desired number) and d (digits)
WHILE OVER NOT
REPEAT
.698970004336	@ precompute LOG(5)
OVER 1. + 4. /	@ lower bound: [d + LOG(5)]/4 < LOG(n)
IF DUP 2. MOD	@ integer n >
THEN 1. +
END
OVER 1. + 4. /	@ upper bound: LOG(n) < (d + 1)/4
ALOG
@ stack: 0. %d %n_low %n_high
FOR n		@ stack: 0. %d
n R->I 4 ^
->STR		@ \$ = digits of n^4
DUP SIZE          @ stack: 0. %d \$ %pos

DO 1. -		@ ok to skip last digit (always a 6)
UNTIL
DUP2 DUP SUB	@ stack: 0. %d \$ \$digit
"4" > OVER AND	@ big digit and more to go?
NOT		@ no, move on to next digit
END		@ much faster than HEAD/TAIL

SWAP DROP		@ stack: 0. %d %pos
@ if %pos = 0 then all digits
@ were big, otherwise small
@ digit occured at %pos
IF THEN ELSE	@ IF THEN ELSE faster than IF NOT THEN
n ROT		@ stack: 0. %d %n
DROP SWAP	@ stack: %n %d
1.E499 'n' STO	@ stop our loop
END

2.			@ only check evens
STEP

1. +		@ digits++
END DROP		@ %n %d -> %n
>>
```
 0

```@ 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]

```
 0

```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.

[r->] [OFF]

```
 0

```On Mar 29, 6:19=A0pm, John H Meyers <jhmey...@nomail.invalid> wrote:
> 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.
>
> [r->] [OFF]

Good call on the SQ SQ in place of 4 ^. Using SQ SQ reduces the time
from 17.58s to 13.71s
```
 0

```On Mar 29, 4:58=A0pm, John H Meyers <jhmey...@nomail.invalid> wrote:
> @ 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]

A list of 1-chr strings takes up a lot of space due to 5byte headers
(5 nibbles for object type, and 5 more nibbles for string length).
Here's one slightly shorter which embeds the list as a string:
\<<
0
DO
2 + DUP SQ SQ \->STR
"{\"0\"\"1\"\"2\"\"3\"\"4"
STR\-> POS
UNTIL
\GSLIST NOT
END
\>>
```
 0

```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.

--
```
 0

```John H Meyers <jhmeyers@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@alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear
```
 0

```Joe Horn <joehorn@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

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@alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear
```
 0

46 Replies
410 Views

Similiar Articles:

7/23/2012 12:02:25 AM