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