Short & Sweet Math Challenges #16: Thinking square !


Hi all,

    A month-and-a-half has elapsed since I posted my S&SMC#15 (April 1st Special) and it's about
    time for me to offer you yet-another-challenge for your potential enjoyment and dusting off
    your alleged HP-programming skills.

    As #16 is both the square of 4 and the square of the square of 2, I feel it's only
    appropriate that this time we think squarely so here you are, a couple of square challenges for you to try and solve with your HP.

    As always, I'll post my original solutions and comments within a few days, so if you want to try your hand
    at them you'll have the whole weekend at the very least to try and solve them for good.

    In all cases, you must write a program for your chosen HP handheld preferably, but other
    brands are also acceptable as long as they're handhelds (but no PDAs). Emulators/simulators for said models
    are also welcome, of course. Any programming language or paradigm is acceptable as long as it actually
    runs in your chosen handheld. Now for

The Challenge


    Scroll 1: Being yourself ...

      Write a program that finds out all 10-digit integers (base 10, of course) that upon being
      squared, the result's rightmost digits exactly reproduce the original number. For example, 9573921746 would be a solution if we had
                95739217462 =  91659977599573921746
      which, alas, it's not the case. Take note that 10-digit solutions beginning by one or
      more 0's obviously aren't 10-digit numbers, of course, and thus aren't valid solutions.

      I'll give both a 4-line, 101-byte BASIC solution for the HP-71B, which takes negligible
      time to find all solutions, as well as a 44-step RPN solution for the HP-15C, which takes
      slightly over a minute to do likewise.

    Scroll 2: ... Big Time !

      Now that you've conquered the previous challenge, you're up to the next summit, where we'll square the conditions, i.e.: write a program to find and orderly output all solutions with the same requirements
      as above, but this time for 10-squared, i.e. 100-digit integers !

      Don't worry, it isn't nearly as insurmountable as it seems, given the correct approach
      and algorithm. To prove it, I'll provide a short (600+ bytes)
      solution for the HP-71B in a mere 18 lines of code, which finds out and outputs all 100-digit solutions fairly fast.

    Scroll 3: All included

      Write a program to find and output all pairs of 5-digit integers such that taken together
      they do include all digits from 0 to 9 and each of their respective 10-digit squares also
      include all digits from 0 to 9 as well.

      For example, 54903 and 12786 would be a solution pair if their squares
      were, respectively, 2570184639 (which includes all digits from 0 to 9) and 1540783926 (ditto)
      but, unfortunately, they aren't.

      I'll give a 13-line, 393-byte solution for the HP-71B which finds all solutions in
      less than 9 seconds in Emu71 @ 2.4 Ghz, and less than 25 min. in a real HP-71B.


    As always, the following caveats strictly apply, namely:

      Please refrain from posting just the solutions, actual code written by yourself *is* mandatory.
      Googling solutions and posting them out is pretty lame and only serves to spoil the challenge
      for others and to make blatantly public your lack of programming skills and/or utter disrespect
      for fair rules and this forum's visitors.

    That said, let's see your answers before I post my solutions next week.

Best regards from V.


I've finally found out the equation for one of the possibilities, but I get overflows while calculating the answer.

I'm currently working on calculating the other possibility.

So looking forward to reading your answer.


I've finally found out the equation for one of the possibilities, but I get overflows while calculating the answer.


The first problem isn't too hard once you realize that n^2 ends with the same digits as n means n*(n-1) is divisible by 10^10.

If n is divisble by 2, n-1 is not, and vice versa; also, if n is divisible by 5, n-1 is not, and vice versa. This means that either n or n-1 is divisble by 2^10, and either n or n-1 is divisble by 5^10.

If n is divisble by 2^10, n-1 must be divisble by 5^10, and vice versa. Neither n nor n-1 can be divisble by 2^10 and 5^10, because that would mean n >= 10^10, but the requirement is that n is a 10-digit number, hence n < 10^10.

So, all you have to do is check all multiples of 5^10, from 103*5^10 to 1023*5^10, and check if they are equal to 1 or -1 (mod 1024). If a multiple of 5^10 is equal to 1 (mod 1024), then n is that number; if a multiple of 5^10 is equal to -1 (mod 1024), then n is that number plus 1. Since 5^10 mod 2^10 is prime, no more than one solution of each type can exist.

The following (very quick-and-dirty!) program finds the solutions on the HP-42S:

00 { 64-Byte Prgm }
01>LBL "SS16"
02 5
03 10
04 Y^X
05 STO 00
06 1023
07 ×
08 STO 01
09>LBL 00
10 RCL 01
11 1024
12 MOD
13 1
14 X!=Y?
15 GTO 01
16 RCL 01
17 PRX
18 Rv
19>LBL 01
20 Rv
21 1023
22 X!=Y?
23 GTO 02
24 RCL 01
25 1
26 +
27 PRX
28>LBL 02
29 RCL 00
30 STO- 01
31 RCL 01
32 X!=0?
33 GTO 00
35 .END.


    8,212,890,625    ***
1,787,109,376 ***

Unfortunately, problem 2 is not so easy. :-) Brute force checking is not practical because the above reasoning does not eliminate enough possibilities. Back to the drawing board to find ways to reduce the amount of work even further...

- Thomas


Hi, Thomas:

    Very clever approach indeed, though I didn't expect anything
    less from you. Besides, your approach is a book example of the hint I usually included in the 'Caveats' section in my past challenges, that is, to achieve a proper balance between the two extremes, namely

    • (a) the approach of letting the program do all the work by brute-force alone, which is likely to result in a much-too-simple, uninteresting program which takes ages to deliver, or else,

    • (b) having the user think too much about the problem, doing all the work, to the point of solving or nearly solving it completely, which results in a much-too-simple, uninteresting program which does nothing but regurgitate the user's solution.

    The ideal is, of course, what you just did: to have the user think just a little about the problem, in order to provide some clever insights, then create an interesting, smart program which uses said insights to deliver orders of magnitude faster. Well done.

    Now, way to go. And, by the way, though you describe your program as intended for the HP-42S, it actually runs perfectly in the HP-41 family as well, unchanged. I also hope you find the time to solve the remaining Scrolls, and it would be great if you would provide timings for your programs, both running on a physical HP-42S as well as under Free42 in various platforms, if at all possible. It will be interesting and potentially useful for future readers.

Best regards from V.


I also hope you find the time to solve the remaining Scrolls, and it would be great if you would provide timings for your programs, both running on a physical HP-42S as well as under Free42 in various platforms, if at all possible.

On my HP-42S, my program for problem 1 takes 2 minutes 52 seconds. On Free42 on my PC, it's instantaneous -- probably a matter of milliseconds.

I'm sure it's possible to do much better -- you say you have a program that does the job in just over a minute on an HP-15C... That's almost three times as fast as my program, on a machine that is MUCH slower than an HP-42S!

But, I'll leave my program as it is. Never optimize something that's fast enough already. ;-)

- Thomas


Hi Valentin,

Thanks for these again interesting challenges.

I happen to notice a strategy that might, I repeat: might lead to an answer.

I start with 10 single digits and throw away those that do not fulfill the criteria. That leaves me the digits 0, 1, 5 and 6.

For each of them I add 10 tens and repeat the actions. One of them that will be left is 76 for 76*76=5776

I add 10 hundreds which will give me (amongst others?) 376 for 376*376=141376

After this: 9376*9376=87909376

and 09376*09376=87909376

and eventually I will get to the already given answer of 1787109376 (I think)

To test this approach I still have to write the requested program for my 32sii, but I fear a lack of time this weekend.

I'll have to find an efficient way to square large numbers. I think it can be done, but it will take a lot of calculating power, I guess. I keep thinking about it. Maybe I'll manage to have a program in time.

I find this number behavior intriguing. I cannot prove if you get all the answers this way, but I'm sure you can comment on it in your solutions.

Have a nice weekend.


Bram's approach will indeed find all solutions. The key observation is that when you add a new digit to the left of an existing n-digit number, this does not affect the final n digits of the square:

  (x + d * 10^n)^2 - x^2
= x^2 + 2 * x * d * 10^n + 10^(2 * n) - x^2
= (2 * x * d + 10^n) * 10^n
= 0 (mod 10^n)

So, you start with the 1-digit numbers 0, 1, 5, and 6, and then, for each of those, try adding all 10 possible digits to the left, and keep the 2-digit numbers that satisfy the condition of the challenge. Repeat for the 3rd digit, and so on. Since for every n-digit solution, all "tails" (numbers obtained by removing leading digits from the solution) also satisfy the condition, you are guaranteed to find all solutions this way.

It's a bit tricky to implement in RPN, but this approach does have the excellent property that its time usage is proportional to the number of digits squared, which is a lot better than the brute force approach (or the modified brute force approach I used to solve problem 1), which is exponential in the number of digits.

Now, to see if I can get this to work on my HP-42S. If it turns out to be too hard, maybe I'll risk my karma and do it on my HP-48G instead. :-)

Nice challenge -- thanks V!

- Thomas


Thomas posted:

    "Nice challenge -- thanks V!"

      You're welcome. :-)

      If you do like this kind of challenge, you'll certainly *love* my next one, come due next June 1st but already in the works. Meanwhile, waiting for your solutions, most specially the 100-digit behemoths.

Best regards from V.


Bram's approach is even better than I thought, once you add another observation to the mix: given an n-digit number that satisfies the condition x^2=x (mod 10^n), there is no more than one "extended" solution x+d*10^n:

Suppose x^2=x (mod 10^n). We're looking for a solution that differs from x only in its first digit, that is, x+p*10^(n-1). So,

  (x+p*10^(n-1))^2 = (x+p*10^(n-1)) (mod 10^n)
<=> x^2 + 2*x*p*10^(n-1) + p^2*10^(2*n-2) = x + p*10^(n-1) (mod 10^n)
<=> (2*x-1)*p*10^(n-1) + p^2*10^(2*n-2) = 0 (mod 10^n) (since x^2=x (mod 10^n))
<=> (2*x-1)*p*10^(n-1) = 0 (mod 10^n)
<=> (2*x-1)*p = 0 (mod 10)

Since x must end in 0, 1, 5, or 6, (2*x-1) ends in 1 or 9, so (2*x-1) is neither a multiple of 2 nor a multiple of 5. Since p is a 1-digit number, it can only be a multiple of 10 if it is 0 -- which means it is impossible to modify a solution by changing its leading digit. (Unless n = 1, of course; in that case, the penultimate step in the above proof is not allowed.)

So, there can be no more than 2 solutions to the general problem. This simplifies the code to look for those solutions considerably, since there is no need to track an arbitrarily large set of solutions.

I guess that leads to another question: do solutions exist for arbitrarily high values of n? If so, prove it; if not, which n-digit solutions cannot be extended to n+1 digits?

Also note that 8,212,890,625 + 1,787,109,376 = 10,000,000,001

- Thomas

Edited: 12 May 2006, 11:26 a.m. after one or more responses were posted


I found the general equation 5^2^n mod 10^n, but could not simplify it, hence making it unuseable on a calculator. I've also found the formula for the "6" possibility.


If you line up the two answers then you'll see that every pair of digits on the same place add up to 9 (apart from the right most).

Two questions I ask myself (in words, not mathematically ;-):

1. the two numbers can be considered been built up to ten digits. Can they be extended to an inifinitive amount, still matching the criteria?

2. If so, will they to inifinity fulfill the "9 test"?

(looks like science: every answer yields more new questions ;-)

Edited: 13 May 2006, 6:21 a.m.


1. the two numbers can be considered been built up to ten digits. Can they be extended to an inifinitive amount, still matching the criteria?

Yes; actually gave the formula in his previous posting. It needs to be modified a bit to make it usable on a calculator, but it is definitely correct.

2. If so, will they to inifinity fulfill the "9 test"?

Yes; so that simplifies the programming task even further...

- Thomas



Here's my solution to problem 2:

00 { 283-Byte Prgm }
01>LBL "16-2"
02 STO "N"
03 STO "M"
04 3
05 +
06 4
07 ÷
08 IP
09 STO "S"
10 1
13 STO "SQ"
15 5
16 STO 00
17>LBL 00
18 1
21 0
22>LBL 01
24 I+
25 FC? 77
26 GTO 01
27 RCL "S"
28 1
29 -
30 1E3
31 ÷
32 STO "I"
33>LBL 02
34 0
35 STO "P"
36 RCL "I"
37 IP
38 1E3
39 ÷
40 STO "J"
41>LBL 03
42 RCL "I"
43 IP
44 RCL "J"
45 IP
46 -
48 RCL× IND "J"
49 STO+ "P"
50 ISG "J"
51 GTO 03
52 RCL "I"
53 1
54 +
55 1
57>LBL 04
58 RCL "P"
59 1E4
60 MOD
62 +
64 1E4
65 MOD
67 CLX
69 ÷
70 IP
71 RCL "P"
72 1E4
73 ÷
74 IP
75 +
76 STO "P"
77 X=0?
78 GTO 05
79 I+
80 FC? 77
81 GTO 04
82>LBL 05
83 ISG "I"
84 GTO 02
85 RCL "SQ"
87 DSE "M"
88 GTO 00
89 RCL "S"
90 1
91 -
92 STO "I"
94 RCL "N"
95 1
96 -
97 4
98 MOD
99 1
100 +
101 10^X
102 MOD
104 CLA
105 SF 21
106 TONE 9
107 GTO 08
108>LBL 06
109 3
110 RCL IND "I"
111 X>0?
112 LOG
113 IP
114 -
115 X=0?
116 GTO 08
117>LBL 07
118 |-"0"
119 DSE ST X
120 GTO 07
121>LBL 08
122 RCL IND "I"
123 AIP
125 17
126 X<=Y?
128 X<=Y?
129 CLA
130 RCL "I"
131 1
132 -
133 STO "I"
134 X>=0?
135 GTO 06
137 X>0?
139 BEEP
140 .END.

To use, enter the desired number of digits and say XEQ "16-2".

The program is based on the formula 5^2^n mod 10^n, which discovered. The difference is that my program performs the repeated squares in n digits, instead of leaving the mod 10^n operation for last; this way, the size of the numbers to be manipulated stays small enough to be manageable. Discarding the leading digits and only keeping the n least significant digits, at each squaring step, is OK, since the higher digits never affect the less significant ones anyway.

To see that 5^2^n mod 10^n satisfies the condition of the challenge:

  (5^2^n)^2 = 5^2^n (mod 10^n)
<=> 5^2^(n+1) = 5^2^n (mod 10^n)
<=> 5^2^n * (5^2^n - 1) = 0 (mod 10^n)

The factor (5^2^n - 1) can be rewritten as

  (5^2^(n-1) + 1) * (5^2^(n-1) - 1)
= (5^2^(n-1) + 1) * (5^2^(n-2) + 1) * (5^2^(n-2) - 1)
= (5^2^(n-1) + 1) * (5^2^(n-2) + 1) * (5^2^(n-3) + 1) * (5^2^(n-3) - 1)

The full expansion has n+1 factors, all of which are even, so that 5^2^n - 1 is divisible by 2^n. Since 5^2^n is obviously divisble by 5^n, the product 5^2^n * (5^2^n - 1) is divisible by 10^n, so 5^2^n equals (5^2^n)^2 (mod 10^n), Q.E.D.

In another posting, I proved that every n-digit solution has a unique extension to n+1 digits; since the solution must end in 0, 1, 5, or 6, there can be no more than 4 solutions. The solutions ending in 0 and 1 are trivial: they can only be extended by adding leading zeroes. The solutions ending in 5 are generated by Thibaut's formula.

So, all that remains are the solutions ending in 6. I already noticed that the sum of the two 10-digit solutions is 10,000,000,001; could this be true in general? I.e., assuming x is a valid n-digit solution ending in 5,

  (10^n+1-x)^2 = 10^n+1-x (mod 10^n)
<=> 10^(2*n)+2*10^n+1-2*x*(10^n+1)+x^2 = 10^n+1-x (mod 10^n)
<=> 1-2*x*(10^n+1)+x^2 = 1-x (mod 10^n)
<=> x*(-2*10^n-1)+x^2 = 0 (mod 10^n)
<=> x^2-x = 0 (mod 10^n)

So 10^n+1-x is also a solution, ending in 6; this is in fact the only other solution.

I'm still waiting for my HP-42S to finish running the above program; I expect it to take between 2 1/2 and 3 hours. I also ran it on Free42 Decimal, which takes about 2 seconds on my laptop (1.4 GHz Celeron). It returns this result:


I verified that this is correct using the bc program under Linux.

- Thomas

UPDATE: The HP-42S took 3 hours 31 minutes. While waiting for it to finish, I realized that there are two pretty simple ways to speed the program up: first, use groups of 5 digits instead of 4, and second, take advantage of the fact that x*x can be computed in slightly more than half the time of the more general x*y. So, basically the same algorithm *could* run in about 75 minutes on a standard HP-42S...

Oh, well, some other time. I haven't even looked at problem 3 yet! :-)

Edited: 13 May 2006, 8:30 p.m.


Hi Valentin,

I have found all four pairs of 5-digit numbers that are solution to #3 (11 if the pairs with one or two squares beginning with zero are not discarded). However, since the HP-200LX is technically a PDA and QBASIC is a "computer language" I will not post my solution here. Anyway, the program takes about 45 minutes to run on the 200LX (an estimated 14 hours on a real HP-71B; 9.5 seconds on a 500 MHz Pentium III), which is an eternity compared to your optimized solution.

Best regards,



Hi, Gerson:

    Thanks for your interest, seems you got it right as there are indeed just four solutions which meet the requirements.

    As for my "optimized" solutions, matter of fact they are but just the barely reasonably efficient ones I could come up with without spending too much time concocting them, which I don't have. For this particular #3, I've recently found a way to make it even faster than I stated in my initial post, but nevertheless I'll simply post my original solution and will give a hint on how it can be optimized even further.

    By the way, I firmly encourage you to try and convert your QBASIC solution to run in any of the acceptable models, say the HP-71B or some RPL machine. Running time is secondary as long as the solutions are correct, as I'm sure yours are, and forum visitors, myself included, will learn and appreciate your very own techniques to deal with these highly unusual problems.

Best regards from V.


Hi Valentin,

Thanks for your encouraging words. I began thinking about this new challenge of yours only yesterday night. I had taken a look at it on Friday but this seemed too difficult for a curious one like me to give it a try. Anyway, even knowing I would not come up with a brilliant solution like yours, Bram's, Thomas Okken's et. al. I decided to try number three as an exercise.

My approach is very straightforward: just ten nested loops. The first five loops yield the 252 possible combinations (10C5); the next five loops yeeld the 120 possible five-element permutations (5P5). In all, 30240 permutations are obtained. These five-digit non-repeating digit numbers are squared. Only if the digits of the squares add up to 45 AND the product of the digits is zero, a time consuming digit comparison routine is performed. The forty or so five-digit numbers are stored on a table. At the end, the matching pairs are found and the digit comparison routine is reused. This approach is not obviously the fastest one but at least I am sure I didn't miss any pair. I hope I have made myself clear :-) (I always have trouble trying to explain how I did something, especially in a language not my own).

Well, that digit-comparison routine is not something I am proud of. I just wrote it a while back for generating the numbers that are displayed in my calculators pictures. If you pay attention to them, they all show 10 non-repeating digits. For instance, my 11C depicted in thread below shows 34679108.25. Dividing this number by pi, we obtaing an integer factor, in this case 11038703, which is related to the calculator by the first two digits (This will work even in a 12-digit calculator, like the 42S).

I am sorry not being able to convert the program to the HP-71B Basic. I'd have to print the HP-71B manual and read it all, as I know practically nothing of 71B.

Best regards,


Edited: 14 May 2006, 7:59 p.m.


By the time I saw this, challenges 1 and 2 were pretty much solved, which mostly killed my interest in them.

But I do have a calculator program (inelegant though it may be) for challenge 3, and it's running now.

It's already found two solutions:

( 35172 , 60984 )


( 57321 , 60984 )

I'll post the other answers and the source code to the program later tonight.


The solution pairs are

( 35172 , 60984 )

( 57321 , 60984 )

( 59403 , 76182 )

( 58413 , 96702 )

I used a TI-89 to solve the problem. I could have used an RPL machine, too, I guess, but I just so happened not to. I'm not surprised to hear about a QBasic solution. Comparing digits by converting numbers to strings is part of the idea of the solution, which is easily done in basic languages.

The solution is straightforward, pretty much just brute force. It's rather slow on a real TI-89, but fairly fast on an emulator.

It only finds one 5 digit number whose digits are all different, and whose square has all ten digits. I then manually recorded the result, and manually changed the line


to just past the given answer to get the next solution. (eg., to 35178->x).

There are only so many solutions of this kind, so it's trivial for a human being to compare them and see which pairs satisfy the required condition.

Anyway, the code:


@Program's purpose is to find two 5-digit numbers, together which
have all digits, 0-9, and whose squares, independently, also each
have all ten digits.

Local x
Local x1
Local s
Local s1
Local n
Local old
Local new


Lbl again

@Now we must test that every digit is unique.


Lbl test1


If (new and old) =/= 0 Then

If x>98765 Then

Goto again


if n<=5 Then
Goto test1



@Now we test that the square has all the digits

Lbl test2


If (new and old) =/= 0 Then

If x>98765 Then

Goto again


if n<=10 Then
Goto test2

Disp x


The numbers output by the program are


The interesting thing is, both the first and last numbers are used in solution pairs.

Edited: 16 May 2006, 7:28 p.m.


And for the heck of it, I ported my program to Qbasic:


DIM m(27)

x = 35172

l = 1


s$ = STR$(x)

old = 0

n = 1


s1$ = MID$(s$, n + 1, 1)

new = 2 ^ VAL(s1$)

IF new AND old THEN

x = x + 3
IF x > 98765 THEN GOTO final

GOTO again


old = old + new
n = n + 1

IF n <= 5 THEN GOTO test1


x1 = x ^ 2

s$ = STR$(x1)

old = 0

n = 1


s1$ = MID$(s$, n + 1, 1)

new = 2 ^ VAL(s1$)

IF new AND old THEN

x = x + 3
IF x > 98765 THEN GOTO final

GOTO again


old = old + new
n = n + 1

IF n <= 10 THEN GOTO test2


m(l) = x

x = x + 3

l = l + 1

IF x < 98765 THEN GOTO again


FOR a = 1 TO 26

FOR b = a + 1 TO 27

old1 = 0
old2 = 0

FOR n = 1 TO 5

s$ = STR$(m(a))

s1$ = MID$(s$, n + 1, 1)

old1 = old1 + 2 ^ VAL(s1$)


FOR n = 1 TO 5

s$ = STR$(m(b))

s1$ = MID$(s$, n + 1, 1)

old2 = old2 + 2 ^ VAL(s1$)


IF (old1 AND old2) THEN


PRINT m(a), m(b)




It's even more complete than the earlier version, because it actually finds the pairs on its own. It runs (on this computer) in about 9 seconds.

I guess part of the point of these challenges is to impress us with how much can be done with just a calculator. So, I can see why submitting a solution in Qbasic or something could be seen as subverting that purpose.

However, one application of calculators is that they give a portable and easy way of testing "proof of principle" of some programs. So, writing a program on a calculator, verifying that it works, and then running a similar program on a computer to get the answer faster seems to me to be almost a "real world" way of demonstrating a way to use a calculator.


Hello Crawl,

It runs (on this computer) in about 9 seconds

I've just tested it on my computer, a Pentium III @ 500MHz: 9.5 seconds, the same time I achieved with my program. I made a slight modification in my program to avoid losing time with unallowed numbers, that is, five-numbers or squares beginning with zero. The running time has dropped to 7.3 seconds. However, if you do a simple modification to your program it will run faster (or less slow) than mine: 5.9 seconds.

Just insert the lines below between DIM m(27) and x = x + 3 and replace the ocurrences of 2 ^ VAL(s1$) with P2(VAL(s1$)).

FOR I = 0 TO 9
P2(I) = 2 ^ I

Comparing both programs I realize mine is needlessly more complicated than it should have been.



Edited: 17 May 2006, 6:04 p.m.


Thanks for the comments. I also realized belatedly that I inadvertantly cheated on my second program. I started searching at 35172, which is actually the first solution, instead of 32016. (The smallest number could be sqr(1023456789) = 31992, but that has two repeated digits. 32016 is the smallest number greater than 31992 that has no repeated digits and is divisible by three)

(And I kind of cheated anyway, by DIM'ing m with 27 entries, because I knew ahead of time that there were 27 5-digit candidates, but that's a minor cheat, imho)

I tried my program, with your suggestions, on this computer (a 3800+ AMD Athlon; I'm not sure of the clockspeed, but it must be Ghz), and it finished in 1.5 seconds! And that's Qbasic. A compiled Quickbasic .exe file should finish almost instantly.

Edited: 17 May 2006, 10:10 p.m.


Hi again,

I had figured the smallest number should be greater than 35136 because I had wrongly taken the square root of 1234567890 instead of 1023456789. Anyway, I forgot to take this into account in my previous program. Now, by discarding numbers beginning with 0, 1 and 2 the running time has dropped a little: 5.7 seconds (2 seconds on my son's AMD Athlon 1700+ next room :-) (1700+ and 3800+ in Athlon processors allegedly means they are equivalent to Pentium processors running at 1.7 GHz and 3.8 GHz respectively although their actual clock speeds are lower). On the 200LX it took 27 minutes and 46 second to run (measured with the built-in timer in QBasic), faster but 20 times slower than Valentin's program.

Your QBX-compiled program runs in less than 1 second (~ 0.8 s) on this computer (500 MHz). I estimate it runs in about 120 milliseconds on a 3800+ Athlon.



It occured to me that you don't need to "solve" for the next digit to get the correct answer. Well, it depends on how you do it. For the "6" solution, you do. But for the "5" solution, you don't! The correct next digit is given by squaring the current number.

Example, the one digit solution is "5". 5^2 = 25. So, the correct two digit solution is "25".

25^2 = 625. The correct 3 digit solution is 625.

625^2 = 390625. So, the correct 4 digit solution would be 625 again. We can save some time here then and say the 5 digit solution is 90625.

90625^2 = 8212890625. The 6 digit solution is 890625.

890625^2 = 793213890625. The 7 digit solution is 3890625.

I didn't notice anyone else make that observation.

Anyway, this is the program that will solve for any number of digits. You put the number of digits you want on the stack, then call the program:

<< 5 1 -> N X M
M 1 + 'M' STO

It gives the exact same answers as quoted before for the 10 and 100 digit solutions, so no need to repost those.

It takes just over 14 seconds to give the 100 digit solution on a real 49G+.

It could be sped up a little bit by grabbing two digits when the next digit is zero (like I did above "manually"), but oh, well.

I might try some of the other posted ideas for speeding up my program for challenge 3, if I have the time and inclination, for the heck of it (since of course the challenge is technically over).

Edited: 28 May 2006, 2:22 p.m.


Hi all,

As always, thanks to all of you who were interested in my S&SMC#16, most
specially to the ones who took their time to analyze and eventually solve it.
As promised, I'm posting now my original solutions plus relevant comments:

Scroll 1: Being yourself ...

    "Write a program that finds out all 10-digit integers (base 10, of course) that upon being
    squared, the result's rightmost digits exactly reproduce the original number"

    These are well-known numbers, usually called automorphs. In a sense, they can
    be considered additional roots to the equation:

                          x2 = x
    if we're willing to accept 'infinite' numbers as solutions. For all numeric bases,
    there are always two solutions, namely 0 and 1. For N-base
    numbers where N is either prime or the power of a prime, these are the
    only solutions. On the other hand, when N=10, we also have
    two other solutions, namely:
         ... 8212890625  and  ... 1787109376
    which can be extended infinitely. In all numeric bases, their sum is always of
    the form 11, 101, 1001, 10001, 1000000000...0000000001, etc, so it suffices
    to compute just one of them and the other can be immediately written down with
    a trivial computation. As Thomas Okken and Bram demonstrated, a little
    theoretical work can do wonders to help implement a simple, concise algorithm,
    and in particular, to stablish that 5 and 6 are the only possible 1-digit solutions in base 10
    (disregarding the trivial solutions 0 and 1, which can't be extended with non-zero
    digits), and they can be extended indefinitely a digit at a time. Which is more, only the
    "5" solution needs to be extended, the "6" solution is computed immediately from it.

    This is my original 4-line (101-byte) version for the HP-71B:

        1 N=5 @ FOR K=2 TO 10 @ P=10^K @ R=P/10 @ FOR D=0 TO 9
    2 M=R*D+N @ IF NOT MOD(M*M-M,P) THEN 4
    3 NEXT D
    4 N=M @ NEXT K @ DISP M;10000000001-M

    Running it produces:

    8212890625 1787109376
    in negligible time. This works Ok thanks to the extreme high-quality nature of HP's
    arithmetic routines
    , as implemented in the HP-71B and most other HP calc models, which allows for proper
    computation of MOD even
    when you would fear that lost digits beyond 12-digit precision in the
    computation of M2 would lead to inaccurate results. That's
    not so and the above program works fine in the HP-71B.
    It might *not*
    if converted to other less accurate, non-HP models.

    The solutions are indeed correct, as we have:

          82128906252 = 67451572418212890625

    17871093762 = 3193759921787109376

    We also have the following interesting results:
        8212890625 + 1787109376 =  10000000001

    8212890625 * 1787109376 = 14677333840000000000

    8212890625 * (8212890625-1) = 67451572410000000000

    1787109376 * (1787109376-1) = 3193759920000000000

    (1787109376-1)2 = 3193759918212890625

    (8212890625-1)2 = 67451572401787109376

    The equivalent RPN version for the HP-15C is this short, fast 44-step routine:

        01 *LBL A   14  10      27 ENTER    37 PSE  
    02 6 16 / 28 X^2 38 STO 0
    03 STO 0 17 STO 3 29 LASTX 39 ISG 1
    04 2.01 18 .09 30 - 40 GTO 1
    08 STO 1 21 STO I 31 RCL/ 2 41 1
    09*LBL 1 22*LBL 0 32 FRAC 42 RCL 0
    10 RCL 1 23 RCL I 33 ISG I 43 RCL- 2
    11 INT 24 INT 34 TEST 0 44 -
    12 10^X 25 RCL* 3 35 GTO 0
    13 STO 2 26 RCL+ 0 36 X<>Y
    which is essentially a direct translation of the above, which the
    added nice touch that it will pause to let you see each correct digit as it's being added. Let's run it:
        GSB A -> (76) -> (376) -> ... 
    -> 8212890625
    X<>Y -> 1787109376
    which only takes 85 seconds to run, including 9 one-second pauses.

    Amazingly this program also works, despite the fact the HP-15C is
    limited to 10-digit results, not 12-digit as in the HP-71B !.
    would seem to be a fatal pitfall when having to deal with the square
    of 10-digit integers, which comes out to 19/20-digit results,
    but thanks again to the utterly incredible quality of
    HP's arithmetic routines as implemented in the HP-15C, the above
    program does run fine, against all odds, and directly computes the
    correct "6" solution, which is immediately used to get the "5" solution
    without further computation.
    Again, it would very likely fail if converted to non-HP 10-digit models.

Scroll 2: ... Big Time !
    "Write a program to find and orderly output all solutions with the same requirements
    as above, but this time for 100-digit integers"

    My original solution is this short, 635-byte program for the HP-71B:

        100 DESTROY ALL @ DIM M$[128],N$[128],P$[256] @ M$="5"
    110 FOR I=2 TO 100 @ CALL MS(M$,P$) @ M$=REV$(P$)[I,I]&M$ @ NEXT I
    120 GOSUB 140 @ DISP @ M$[100]="6"
    130 FOR I=1 TO 99 @ M$[I,I]=STR$(9-VAL(M$[I,I])) @ NEXT I @ GOSUB 140 @ END
    140 FOR I=1 TO 5 @ DISP M$[20*I-19,20*I] @ NEXT I @ RETURN
    150 !
    160 SUB MS(P$,R$) @ OPTION BASE 1 @ DIM A$[512],E$[512] @ A$=FNL$(P$)
    170 X=LEN(A$) DIV 6 @ Z=2*X @ U=10^6 @ V=U-1 @ DIM A(X),C(Z),C$[Z*6]
    180 FOR I=1 TO X @ A(X+1-I)=VAL(A$[I*6-5,I*6]) @ NEXT I
    190 FOR I=1 TO X @ M=A(I) @ IF RES THEN L=I ELSE 230
    200 FOR J=1 TO X @ N=A(J) @ IF RES THEN P=M*N @ C(L)=C(L)+RES ELSE 220
    210 P=RES @ IF RES>V THEN C(L)=RMD(P,U) @ C(L+1)=C(L+1)+P DIV U
    220 L=L+1 @ NEXT J
    230 NEXT I @ FOR I=Z TO 1 STEP -1 @ IF C(I) THEN 250
    240 NEXT I
    250 C$=STR$(C(I))
    260 FOR I=I-1 TO 1 STEP -1 @ C$=C$&FNL$(STR$(C(I))) @ NEXT I @ R$=C$
    270 DEF FNL$[512](A$) @ E$=A$
    280 IF RMD(LEN(E$),6) THEN E$="0"&E$ @ GOTO 280 ELSE FNL$=E$

    where the main program is a mere 5 lines long, and simply calls subprogram MS
    to compute the multiprecision square of a multiprecision integer. MS is
    a very simple subprogram which takes two string arguments, namely:

          P$   contains the multiprecision number to square, as a string
    R$ contains the multiprecision result
    Having the number and result be strings is much less efficient and
    more memory-wasting than using arrays, but it makes for easy use right from
    the keyboard
    and I happened to have at hand this little subprogram I wrote
    long ago. Tha main program simply uses it to compute the "6" solution, and
    then outputs both the 100-digit "6" solution and "5" solution in 20-digit groups:


    These results are indeed correct, as we do have:
    By the way, this program is general in nature so you can use it to compute more or less than 100 digits by simply changing some constants here and there. Also, as stated, you can use subprogram MS from the keyboard to square large integer numbers, like this:
        >M$="3147926784726726563780030042374237187751" @ CALL MS(M$,P$) @ P$


Scroll 3: All included
    "Write a program to find and output all pairs of 5-digit integers such that together
    they do include all digits from 0 to 9 and each of their respective 10-digit squares also
    include all digits from 0 to 9 as well"

    This is my original 13-line, 393-byte program for the HP-71B:

        10 DESTROY ALL @ DIM S(50) @ A$="1234567890" @ L=0 @ FOR A=3 TO 9
    20 T=10000*A @ FOR B=0 TO 9 @ IF B=A THEN 100
    30 U=T+1000*B @ FOR C=0 TO 9 @ IF C=A OR C=B THEN 90
    40 V=U+100*C @ FOR D=0 TO 9 @ IF D=A OR D=B OR D=C THEN 80
    50 W=V+10*D @ FOR E=0 TO 9 @ IF E=A OR E=B OR E=C OR E=D THEN 70
    60 N=W+E @ IF NOT SPAN(A$,STR$(N*N)) THEN L=L+1 @ S(L)=N @ DISP N;N*N
    70 NEXT E
    80 NEXT D
    90 NEXT C
    100 NEXT B @ NEXT A @ DISP "Checking matching pairs ..."
    110 FOR I=1 TO L @ A=S(I) @ FOR J=I+1 TO L @ B=S(J)
    130 NEXT J @ NEXT I @ DISP "OK"
    Upon running, it first does find out all 5-digit (nonrepeated) numbers
    whose 10-digit squares feature all digits from 0 to 9, then automatically
    matches them in pairs to quickly produce all four solutions, namely:
    35172 1237069584
    37905 1436789025
    39147 1532487609
    43902 1927385604
    46587 2170348569
    53976 2913408576
    54918 3015986724
    57321 3285697041
    58413 3412078569
    59403 3528716409
    60984 3719048256
    63051 3975428601
    63129 3985270641
    69513 4832057169
    76182 5803697124
    78453 6154873209
    80361 6457890321
    81945 6714983025
    85743 7351862049
    86073 7408561329
    87639 7680594321
    89145 7946831025
    89523 8014367529
    90153 8127563409
    91248 8326197504
    91605 8391476025
    96702 9351276804

    Checking matching pairs ...

    35172 60984 1237069584 3719048256
    57321 60984 3285697041 3719048256
    58413 96702 3412078569 9351276804
    59403 76182 3528716409 5803697124


    This runs in less than 9 seconds in Emu71 @ 2.4 Ghz, and less
    than 25 minutes in a real HP-71B.

    The algorithm used is pretty straightforward: 5 nested loops
    generate all 5-digit numbers from 30000 to 99999, in an optimized
    way to minimize computation, and sieving out those having repeated
    digits. The ones which remain after the sieving process are then
    squared and their squares are checked to see if they feature all
    digits from 0 to 9. The ones which pass muster are then collected
    in an array, later to be matched to select compatible pairs that
    together include all digits as well, which are suitably output
    with their respective squares for added visual confirmation.


      You might be interested to see how a 10-digit number is checked to
      see if it includes all digits from 0 to 9. This is done in two
      separate occasions at lines 60 and 120. Instinctively, one would
      resort to using a loop to do the check, but it's far better to use
      the SPAN function as shown, thus completely avoiding both loops
      within the maximum nesting level, and so speeding up the program
      a real lot.

      The SPAN function is a little-known, little-used string function which
      can be found in a number of different LEX files for the HP-71B,
      though it was originally featured in STRNGLEX, which is a very common LEX,
      included in a number of ROMs and thus easily available. In particular. it
      comes already installed and ready to use in Emu71.

      If you don't have Emu71 or STRNGLEX, you can substitute it for a simple
      loop, using POS instead, but it's good to know about non-obvious, time-saving
      uses for such functions as SPAN. By the way, the program can still be
      optimized even further by noticing that once you have generated a
      5-digit number N which doesn't have repeated digits (say 34567), then
      another suitable candidate is 99999-N (99999-34567 = 65432) which is
      automatically guaranteed to also have no repeated digits as well. This
      can reduce the outer loop (and running time) by almost 50%. I'll leave that as an "exercise for the reader" :-)

Well, that's all for now. Hope you enjoyed it and thanks again to the
kind contributors, your postings were as keen as usual and certainly
enlightening to all interested readers. See you in S&SSMC#17, coming next month.

Best regards from V.

Edited: 19 May 2006, 7:11 a.m.


Hello Valentin,

Thanks for this one more S&SMC. I am looking forward to the next one.

Though this only shows my "lack of programming skills", I am submitting my solution to the third problem. It is essentially the same one I wrote last Sunday with some minor improvements (added line 46; replaced the testing routine, not so much faster but more compact than the previous one). It is still in QBASIC, I hope you don't mind. Anyway, this should be easy to port to SHARP or CASIO pocket computers (I am not sure their BASIC dialects can handle line 520 though).

It runs in slightly less than 30 minutes on the HP-200LX (precisely 29m49s). In short, I'd need an HP-200LX to do what you can do on the HP-71B, which is about 19 times slower, according to a certain benchmark. And I needed ten nested loops and countless more lines while you needed only five loops and a few lines! I am just glad I don't have to program for a living, otherwise I'd starve :-)

Best regards,



96702 58413 9351276804 3412078569
59403 76182 3528716409 5803697124
60984 35172 3719048256 1237069584
60984 57321 3719048256 3285697041



7 T$ = TIME$
18 DIM X(50)
20 FOR I = 0 TO 5
22 LOCATE 2, 2: PRINT I;
25 FOR J = I + 1 TO 6
30 FOR K = J + 1 TO 7
35 FOR L = K + 1 TO 8
40 FOR M = L + 1 TO 9
43 A(1) = I: A(2) = J: A(3) = K: A(4) = L: A(5) = M
45 FOR N = 1 TO 5
46 IF A(N) < 3 THEN 180
50 FOR P = 1 TO 5
60 IF N = P THEN 170
70 FOR Q = 1 TO 5
75 IF (N = Q) OR (P = Q) THEN 160
90 FOR R = 1 TO 5
95 IF (N = R) OR (P = R) OR (Q = R) THEN 150
110 FOR S = 1 TO 5
115 IF (N = S) OR (P = S) OR (Q = S) OR (R = S) THEN 140
130 X = 10000 * A(N) + 1000 * A(P) + 100 * A(Q) + 10 * A(R) + A(S)
135 Y = X * X
138 GOSUB 500
140 NEXT S
150 NEXT R
160 NEXT Q
170 NEXT P
180 NEXT N
190 NEXT M
195 NEXT L
200 NEXT K
205 NEXT J
210 NEXT I
212 CLS : KT = 100
214 ' Searches for matching pairs
215 FOR I1 = 0 TO 48
217 IF X(I1) = 0 THEN 250
220 FOR J1 = I1 + 1 TO 49
225 Y = 100000 * X(I1) + X(J1)
230 IF X(J1) <> 0 THEN GOSUB 500 ELSE 240
235 NEXT J1
240 NEXT I1
250 PRINT : PRINT " "; T$: PRINT " "; TIME$
260 END
499 ' Tests whether squares include digits from 0 to 9
500 Y$ = STR$(Y): TS$ = "1111111111"
510 FOR T = 2 TO 11
515 V = VAL(MID$(Y$, T, 1))
520 MID$(TS$, V + 1, 1) = "0"
530 NEXT T
540 IF TS$ = "0000000000" THEN IF KT <> 100 THEN X(KT) = X: KT = KT + 1 ELSE PRINT X(I1); X(J1); X(I1) ^ 2; X(J1) ^ 2



Checking my original program again, I discovered lines 47, 65, 80, 100 and 120 were not necessary. So these lines have been erased in the listing above and line 130 has been changed. Now the program runs in 29m36s and is five lines shorter (still too many lines though). I hope there are no other primary mistakes left.

 47             B(1) = A(N)
65 B(2) = A(P)
80 B(3) = A(Q)
100 B(4) = A(R)
120 B(5) = A(S)
130 X = 10000 * B(1) + 1000 * B(2) + 100 * B(3) + 10 * B(4) + B(5)

Edited: 21 May 2006, 11:17 p.m.


Hi, Gerson:

Gerson posted:

    "Thanks for this one more S&SMC. I am looking forward to the next one."

      You're welcome, thanks to you for your continued interest and excellent solutions to my challenges.

    "It is still in QBASIC, I hope you don't mind. Anyway, this should be easy to port to SHARP or CASIO pocket computers (I am not sure their BASIC dialects can
    handle line 520 though)."

      As for minding, I'll pass this one and yes, it's pretty easy to port it to SHARP models, line 520 can be entered as is in models such as the SHARP PC-1350, PC-1475, PC-1403H, etc, but not so in earlier models such as the original SHARP PC-1211 (aka TRS-80 PC-1 in the US).

    "I am just glad I don't have to program for a living, otherwise I'd starve :-)"

      Thanks for the compliment, Gerson, but don't be so unfair to yourself, your solutions are indeed correct and perfectly adequate as they *do* solve the challenge. To be able to analyze an unusual problem, decide on a workable algorithm, then correctly implement it and get valid solutions is no mean feat in itself at all, quite the opposite.

    I hope you'll like my very next S&SMC#17, which will be out next month and, in a sense, it's the 'complementary' of this one. Also, it includes a 41-related subproblem ;-)

Best regards from V.


Though the deadline to post solutions has passed, I'd like to send an entry for problems #1 and #2. Number theory being very close to my heart and having recently discovered the HP-49G/G+ function "IABCUV", it suffices to use successive approximations à la Newton's method to "roots" of the polynomial x^2-x (not in the sense that x^2-x is near zero, but in the sense that it ends in many zeros). I realized any attempt would involve arithmetic with large integers, so nothing better suited to this purpose than the exact mode of the HP-49G/G+ that allows for many-digit integral arithmetic.

Note that successive approximations to a root of x^2-x are done via the usual Newton method by iterating y=x-(x^2-x)/(2x-1). Using modular arithmetic instead, we obtain the solution below. What IABCD does in the case at hand is compute -(x^2-x)/(2x-1) modulo a suitable power of 10.

Program 'HUNDRED' follows:

<< 10 -> X P
X 2 * 1 - P X X SQ - IABCUV DROP X + P MOD 'X' STO

Size: 133.5, Crc # 64962d


EXACT mode needed (flag 105 cleared in HP 49G).

Level 2: integer n (greater than or equal to 1)
Level 1: integer x0 (equal to 5 or 6)

Integer x with last digit x0 and such that x^2 has the same last 2^n digits as x.

Each iteration doubles the number of digits of the (infinitely long formal) solution, hence the interpretation of the parameter n as giving the "approximate" solution to 2^n digits (or less).

Note that x may have fewer than 2^n digits.
x0 is the "zeroth-level" solution: namely x0=6 (since 6^2 ends in 6) or x0=5 (since 5^2 ends in 5)

For instance:
4 5 HUNDRED gives 6259918212890625, a 16-digit number whose square ends in the same 16 digits (16=2^4, and the number ends in 5). Taking only the last 10 digits solves half of challenge #1. The other half of challenge #1 is solved by taking the last 10 digits of 4 6 HUNDRED (calculation takes less than a second in my Tungsten E2 emulating the 49G).

Similarly, the last 100 digits of 7 5 HUNDRED and 7 6 HUNDRED solve challenge #2 (less than 2 seconds in my Tungsten E2 emulating the 49G).





Hi, Eduardo:

    Really, really excellent RPL solution for the 49 series !!

    I was wondering why RPL solutions to my challenges are usually few and far between, when actually RPL machines are indeed the more powerful models available for the tasks featured, and thus, in theory, ideally suited to this kind of computation-intensive challenges of mine.

    Fortunately, yours is a perfect example of the innovative solutions one can arrive at using the powerful RPL capabilities present in HP's flagship models.

    Never mind the (nonexistent) deadline, all ideas and implementations are always welcome, not the mention such original ones as yours. I sincerely hope you'll be interested in future S&SMCs and meanwhile, thanks for contributing and

Best regards from V.



Thanks for your praise. My first HP calculator was a 28S that I bought when I was in high school, so RPL is what I'm most familiar with. Later I sold it to upgrade to a 48SX which was later unfortunately stolen. Now that I could more easily afford calculators, the golden era is over. I have all models in the 48-49 series, a 42S that I happened by chance to buy from Raymond del Tondo almost three years ago, a 33s, and a couple others (20s and 32Sii with barely working ENTER key). But I still miss my 28S on occasion.

I envy you, and would love to have a 71B. My first programmable calculators were actually a Tandy/Radio Shack PC7 and later a Casio FX-850P, both with BASIC language. I also would like a 41CX very much. Unfortunately, it's unlikely I'll ever buy them if I have to pay eBay prices for them. Not to mention I dislike and distrust eBay in general.

I read your piece "Long Live the HP 42S" a few months back. Thanks for your contributions to this community.


Edit: I noticed you are actually selling some of these jewels! I'll drop you a note.

Edited: 23 May 2006, 11:20 a.m.

Possibly Related Threads...
Thread Author Replies Views Last Post
  Need help understanding math.... cyrille de Brébisson 9 2,408 12-13-2013, 02:23 AM
Last Post: Didier Lachieze
  [HP-Prime CAS] "Warning, ^ (Command) Is ambiguous on non square matrices"?? CompSystems 1 1,405 12-07-2013, 07:15 PM
Last Post: CompSystems
  HP Prime - Short "learning" modules CR Haeger 1 971 11-27-2013, 02:13 PM
Last Post: Jonathan Cameron
  I have written a short introduction to the HP Prime Michael Carey 7 2,020 11-18-2013, 08:04 PM
Last Post: Michael Carey
  HP-65 short circuit Ignacio Sánchez 2 1,100 10-22-2013, 08:27 AM
Last Post: Ignacio Sánchez Reig
  Flash Flood Warning: 9/16/2013 (One Week from HHC13) Eddie W. Shore 8 2,078 09-17-2013, 09:20 PM
Last Post: Craig Ruff
  OT: a math competition site Pier Aiello 0 761 09-16-2013, 06:03 AM
Last Post: Pier Aiello
  A brand new calculator benchmark: "middle square method seed test" Pier Aiello 25 4,996 09-13-2013, 01:58 PM
Last Post: Pier Aiello
  HP's thinking behind the 20b/30b? John Ioannidis 3 1,223 09-07-2013, 10:21 AM
Last Post: Tim Wessman
  Simple Math Question Namir 2 1,014 08-09-2013, 06:13 PM
Last Post: Eddie W. Shore

Forum Jump: