The Museum of HP Calculators

HP Forum Archive 18

[ Return to Index | Top of Index ]

Mini Challenge
Message #1 Posted by Egan Ford on 22 Jan 2009, 5:00 p.m.

The number 48 is special in that if you add one to it, or add one to half of it, the sum is a perfect square, i.e.:

48   + 1 = 49 = 7 * 7
48/2 + 1 = 25 = 5 * 5
Using your favorite calculator how many more can you find?
      
Re: Mini Challenge
Message #2 Posted by PeterP on 22 Jan 2009, 6:10 p.m.,
in response to message #1 by Egan Ford

Not many on my 41 without the MPL...

as X/2 need to be an integer, X needs to be even. So we have

2n+1 = A^2
n+1 = B^2
with A and B odd. The code below tries all odd numbers from the start number to see if (A^2-1)/2 + 1 is a perfect square, in which case it shows it via XEQ 01 until the next one is found.

So far it has found 48, 1680, 57120, 1940448, 2239277040... Addendum - all of these are divisible by 48... Hmmm...

Lbl 'EF'
Lbl 00
  'START VAL:'
  PROMPT       %enter a odd number here from which you want to start
  STO 00
  Lbl 00
      X^2
      DECX
      2
      /
      INCX
      SQRT
      INT
      LastX
      X=Y?
      XEQ 01
      RCL 00
      IncX
      IncX
      Sto 00
  GTO 00
  LBL 01
      Rcl 00
      X^2
      DecX
      View X
  RTN
END
edit - found a typo

Edited: 22 Jan 2009, 6:20 p.m.

      
Re: Mini Challenge RPL
Message #3 Posted by Paul Dale on 22 Jan 2009, 6:11 p.m.,
in response to message #1 by Egan Ford

My 49g+ is dead. I pulled it out to do this challenge and there is a big ink blob inside the screen. The LCD has died :-(

Anyway, without that resource, I fired up *sfix and entered this program:

    << 0 48 1 5 START OVER NEG 48 + OVER 34 * + NEXT >>

Which gives the first seven terms of the sequence. Change the 5 before the START to whatever you want to generate more.

- Pauli

Edited: 22 Jan 2009, 9:12 p.m.

            
Re: Mini Challenge RPL
Message #4 Posted by David Hayden on 22 Jan 2009, 11:07 p.m.,
in response to message #3 by Paul Dale

If I'm reading this code right, it basically says that if you know the two previous values in the sequence X and Y, then the next value is 34Y-X+48.

Can you explain why this formula gives the right answer?

Thanks, Dave

                  
Re: Mini Challenge RPL
Message #5 Posted by PeterP on 23 Jan 2009, 12:13 p.m.,
in response to message #4 by David Hayden

I'm not 100% sure, but check out this link about the Pell Equation and scroll down to Solution Technique where they show how you can generate subsequent solutions iteratively. I feel actually quite stupid (aka my normal state of mind) for not figuring out that this is again a Pell equation, even after I wrote down the challenge in a more general form! And seeing that all solutions are divisible by 48...

HTH

Cheers

Peter

                        
Re: Mini Challenge RPL
Message #6 Posted by Paul Dale on 23 Jan 2009, 11:27 p.m.,
in response to message #5 by PeterP

If you also realise that (n/2+1)(n+1) being a perfect square is equivalent to the mini challenge problem (since n/2+1 and n+1 are coprime) then you'll see the connection to Sloane A078522.

- Pauli

      
Re: Mini Challenge 15C
Message #7 Posted by Paul Dale on 22 Jan 2009, 6:22 p.m.,
in response to message #1 by Egan Ford

And a 15c version:

001-42,21,11  LBL A
002-       0  0
003-      36  ENTER
004-       4  4
005-       8  8
006-42,21, 0  LBL 0
007-  42  31  PSE
008-      36  ENTER
009-      36  ENTER
010-       3  3
011-       4  4
012-      20  *
013-       4  4
014-       8  8
015-      40  +
016-  43  33  R^
017-      30  -
018-   22  0  GTO 0

This version keeps spitting numbers out until your press R/S or it overflows.

- Pauli

Edited: 22 Jan 2009, 9:11 p.m.

      
Re: Mini Challenge 16C
Message #8 Posted by Paul Dale on 22 Jan 2009, 9:10 p.m.,
in response to message #1 by Egan Ford

And a 16c version that takes advantage of the 64 bit decimal mode to the go further:

001-43,22, A  LBL A
002-      24  DEC
003-   42  3  UNSGN
004-       0  0
005-  42  44  WSIZE
006-       1  1
007-       1  1
008-  44  32  STO I
009-       0  0
010-      36  ENTER
011-       4  4
012-       8  8
013-43,22, 0  LBL 0
014-  43  34  PSE
015-      36  ENTER
016-      36  ENTER
017-       3  3
018-       4  4
019-      20  *
020-       4  4
021-       8  8
022-      40  +
023-  43  33  R^
024-      30  -
025-  43  23  DSZ
026-   22  0  GTO 0
027-  43  21  RTN

This produces these numbers:

                     48
                   1680
                  57120
                1940448
               65918160
             2239277040
            76069501248
          2584123765440
         87784138523760
       2982076586042448
     101302819786919520
    3441313796169221280

- Pauli

Edited: 22 Jan 2009, 9:11 p.m.

      
Re: Mini Challenge
Message #9 Posted by Thomas Klemm on 22 Jan 2009, 10:49 p.m.,
in response to message #1 by Egan Ford

n   + 1 = x2
n/2 + 1 = y2

x2 - 2y2 = -1

What a suprise: a Pell equation!

Here's my program for HP-41C using brute force:

01 -1                      15 -             
02 ENTER                   16 LASTx         
03 +                       17 GTO 00        
04 LASTx                   18 LBL 01        
05 ENTER                   19 x=0?          
06 STO 00                  20 VIEW 00       
07 LBL 00                  21 RCL Z         
08 x<>y                    22 4             
09 x<=0?                   23 +             
10 GTO 01                  24 +             
11 x<>y                    25 LASTx         
12 2                       26 x<> Z         
13 +                       27 GTO 00        
14 ST+ 00

It might be faster in assembler though.

Nevertheless it gives enough values to find the sequence: Sloane A008845

            
Re: Mini Challenge
Message #10 Posted by C.Ret on 23 Jan 2009, 7:22 a.m.,
in response to message #9 by Thomas Klemm

Hi,

Note, that before n=48, n=0 is a valid solution since :

 0   + 1 = 12
 0/2 + 1 = 12

Following list of intergers n using an HP-28S (HP-28C will do it too):

# 0d
# 48d
# 1680d                    << 64 STWS DEC 0 0 #0d
# 57120d                      1 13 START
# 1940448d                          DUP PR1 
# 65918160d                         34 * 48 + ROT -
# 2239277040d                 NEXT
# 76069501248d             >>
# 2584123765440d
# 87784138523760d
# 2982076586042448d
# 101302819786919520d
# 3441313796169221280d

Edited: 23 Jan 2009, 7:26 a.m.

      
Re: Mini Challenge
Message #11 Posted by Egan Ford on 25 Jan 2009, 1:58 p.m.,
in response to message #1 by Egan Ford

Quote:
The number 48 is special in that if you add one to it, or add one to half of it, the sum is a perfect square, i.e.:
48   + 1 = 49 = 7 * 7
48/2 + 1 = 25 = 5 * 5
Using your favorite calculator how many more can you find?
I found this problem in Recreations in the Theory of Numbers by Beiler. This very inexpensive Dover reprint is very well written and a lot of fun. Chapter 22 (The Pellian) is entirely devoted to Pell Equations.

NOTE: All code will be end of this post.

MC1: Brute Force

As Thomas pointed out:

Quote:
n   + 1 = x2
n/2 + 1 = y2
x2 - 2y2 = -1

This program takes a single argument (number of solutions to find), then sequentially tests each odd square. The output below took over an hour (I stopped watching) with an input of 7.

MC2: Algebraic

As Thomas pointed out x2 - 2y2 = -1 is a Pell Equation. Clearly x = 1 and y = 1. To find any x the following can be use:

x = [(1 + sqrt(2))r + (1 - sqrt(2))r]/2.

However, r must be odd. See Beiler for details.

This program counts odds from 1 to 13 to find the first seven solutions in seconds. NOTE: the 7th solution is a bit off (rounding error), however the following 50g version does not have this problem:

<< 1 13 FOR r 1 2 v/ + r ^ 1 2 v/ - r ^ + 2 / 2 ^ 1 - EVAL 2 STEP >>

MC3: Recurrence Relation

As Peter pointed out this can be found here: http://en.wikipedia.org/wiki/Pell%27s_equation.

However, like MC2, for this type of Pell Equation (-1) only every other recurrence will have a valid solution. Solving for xn+2 a new recurrence relation can be obtained:

xn+1 = 3xn + sqrt(8(xn2 + 1)).

This program will compute the first 7 solutions in seconds. This was my final solution.

MC4: Recurrence Relation

This identical to Pauli's 50g version (thanks for the incredible find (A078522)).

This program will find the first 7 solutions in seconds.

The On-Line Encyclopedia of Integer Sequences is treasure trove of integer sequences. You can find many interesting solutions there, e.g. when I searched for 1, 49, 1681 I found A008843 and created the following 15C version:

001  LBL A      010  x          
002  SF 8       011  COSH       
003  2          012  x^2        
004  x          013  CHS        
005  1          014  1          
006  -          015  -          
007  2          016  INT        
008  SQRT       017  RTN        
009  ATANH      
Note the requirement for complex numbers and hyperbolic functions. To use, just enter the term you want (1 through 7). NOTE: the 7th solution is a bit off.

41CX Code and Results

I liked this problem because there were so many ways to write programs for it. Thanks all for participating.

Edited: 25 Jan 2009, 2:19 p.m.

            
Re: Mini Challenge
Message #12 Posted by PeterP on 25 Jan 2009, 6:05 p.m.,
in response to message #11 by Egan Ford

I thank you for posting it and for the great writeup! Great job Egan!

Cheers

Peter

                  
Re: Mini Challenge
Message #13 Posted by Chris Dean on 27 Jan 2009, 1:03 p.m.,
in response to message #12 by PeterP

Seeing as Egan took the trouble to pose the Mini-Challenge it is only fitting (polite) to respond with any programs that have been developed. I generally have a go at all of the challenges that are posed but have possibly not posted my programs sometimes because I have thought it too late or the programming not good enough. I suspect that I am just one of many who think this but this is the type of attitude that possibly contributed to the demise of previous challenges which I thoroughly enjoyed.

I have written two 'brute force' programs for this mini-challenge. One for the HP 15c which I now have on an iPod Touch and seems to run considerably faster than the real thing and is a fraction of the cost! The other is for my HP-50g which I had bought for me for Christmas (yet another nerd!) so I am just re-learning RPL. I originally had a HP 49g but did not get on with it.

Using X + 1 = A^2 and X / 2 + 1 = B^2 the formula B^2 = (A^2 + 1) / 2 can be derived. Using the premise that 'Equality does not exist in the Real world of computing' I always take the absolute difference of two values and then compare the result to a small value (1.0e-6). This increases the number of steps but accounts for most rounding errors.

HP 15c

f Lbl A STO 0 1 EEX 6 CHS STO 1 g X^2 1 + 2 / STO 2 SQRT RCL 1 + g INT g X^2 RCL 2 g TEST 6 (x<>y) GTO C g X^2 1 - R/S f Lbl C 2 STO+0 GTO B

HP 50g

<< -> A << WHILE 'A < 200000' REPEAT '(SQ(A) + 1) / 2' ->NUM 'B2' STO 'SQ(IP(SQRT(B2) + 0.000001))' ->NUM 'C2' STO IF ABS(B2 C2) < 0.000001' THEN 'SQ(A) 1' ->NUM HALT (press back arrow CONT to continue) END 'A + 2' ->NUM 'A' STO END

SQRT - means square root in both programs

The programs yield the usual results

0 48 1680 57120 1940448

Although not very quickly.

Considering the speed of obtaining results using 'a calculator' I wonder, is the challenge getting the results or developing the programs? I must admit developing the algorithms and code is the exciting bit for me and getting the correct results the confirmation that I have done so. If I wanted quick results I would possibly code up the algorithms in C++, VBA or Java but this would spoil the fun, wouldn't it?

Egan thanks again for the mini-challenge.

                        
Re: Mini Challenge
Message #14 Posted by Egan Ford on 27 Jan 2009, 6:15 p.m.,
in response to message #13 by Chris Dean

Quote:
Considering the speed of obtaining results using 'a calculator' I wonder, is the challenge getting the results or developing the programs?
Both. What I like about calculator challenges is that for many of them you need to have an in-depth understanding of the problem to effectively get results from 1980s hand-held tech in a reasonable amount of time.
Quote:
Egan thanks again for the mini-challenge.
You are welcome. Thanks for participating.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall