HP-12C mini-challenge - Heegner numbers « Next Oldest | Next Newest »

 ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-22-2011, 07:30 PM Heegner Numbers is a finite set of integer numbers which share some interesting properties. They were discovered by Gauss who conjectured there were only nine of them {1, 2, 3, 7, 11, 19, 43, 67, 163}, what was eventually proved by Stark and Heegner. The challenge is to write an HP-12C program that displays these nine numbers, one at a time, using 22 steps or less (final GTO 00, if necessary, included). For example: ```GTO 00 R/S => 1 R/S => 2 . . . . . . R/S => 67 R/S => 163 R/S => 9.999999E99 (to indicate 163 is the last number in the set) ``` The displaying of the last result above is not required, provided the program stops when the last Heegner number is shown. Have fun! :-) Gerson. Edited: 22 Mar 2011, 7:38 p.m. ▼ Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 03-23-2011, 02:01 AM I suppose a program like RCL 1 : R/S : RCL 2 : R/S ... RCL 9 : R/S doesn't qualify. ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 03-23-2011, 02:31 AM Come on, we can do neater: ```1 R/S 2 R/S 3 R/S 7 R/S 11 R/S 19 R/S 43 R/S 67 R/S RCL 0 GTO 00 ``` Where 163 is stored in register 0. 22 steps exactly. I've had no luck solving this one properly. Not yet at least. I can't think of a generating function for the tail of the sequence. Likewise, I can't see how to save two keystrokes... - Pauli C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 03-23-2011, 05:01 AM Here is my humble attempted RPN code to display the nine Heegner’s numbers. Nearly adapted for an HP-12C , without any guaranty, since I have no HP12C at hand to verify. ```Initialisation 4122175134. STO 01 1. STO 00 Usage: GTO 00 R/S 1. R/S 2. R/S 3. R/S 7. R/S 11. R/S 19. R/S 43. R/S 67. R/S 163. R/S Error Divide by zero 'Error' statment indicates end of Heegner's integer list. Program: 01 * LBL 00 02 RCL 00 03 STO/ 01 04 R/S 05 * LBL 01 06 1 07 STO+ 00 08 RCL 01 09 RCL 00 10 / 11 FRAC 12 x==0 ? 13 GTO 00 14 LAST x 15 INT 16 x==0 ? 17 1/x 18 GTO 01 ``` Edited: 23 Mar 2011, 5:03 a.m. ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 03-23-2011, 05:27 AM Converted for the 12c: ```01- 45 0 RCL 0 02- 44 10 1 STO/ 1 03- 31 R/S 04- 1 1 05- 44 40 0 STO+ 0 06- 45 1 RCL 1 07- 45 0 RCL 0 08- 10 / 09- 43 24 FRAC 10- 43 35 x=0 11- 43,33 01 GTO 01 12- 43 36 LSTx 13- 43 25 INTG 14- 43 35 x=0 15- 22 1/x 16- 43,33 04 GTO 04 ``` So 16 steps plus two registers is the smallest so far. - Pauli ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-23-2011, 07:54 AM Starting with the products of all the Heegner numbers and then using integer division tests certainly works, but I have a feeling it's NOT what Gerson had in mind. The approach used by the last two listings basically works for any sequence of prime numbers. :-) Namir Edited: 23 Mar 2011, 8:13 a.m. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-23-2011, 10:58 AM Playing with the product I've found it is equivalent to ```'744*(744^2*(10+7/744)-(10+17/744))-1' = '744*(10+7/744)*(744^2-1)-11' = '744*(744*(744*10+7)-10)-18'``` None of these will help towards a better solution though. In terms of memory usage, each storage register is equivalent to seven steps. However, since I made no restriction about that I think all solutions that have been presented here are valid. Thanks everyone for the interest! My program uses one register, no initialization and takes up 22 steps, only two shorter than what would be required to just listing the numbers (1 R/S 2 R/S . . . 163 GTO 00). By the way, it would be nice if there were a neat formula in the OEIS sequence. :-) Regards, Gerson. ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 03-23-2011, 05:26 PM Quote:By the way, it would be nice if there were a neat formula in the OEIS sequence. :-) I know, I checked OEIS after I couldn't find an obvious pattern. - Pauli ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-23-2011, 06:57 PM Well, I checked OEIS prior to trying to find a pattern. The first differences was the next idea. This shows a feeble pattern, but again no formula: I have used this to get a recurring formula for the fourth Heegner number ownards. No mathematical meaning, but it works. Gerson. ▼ Thomas Klemm Senior Member Posts: 735 Threads: 34 Joined: May 2007 03-24-2011, 04:03 AM I'm using recursive formulas of the form: xn+1 = a xn + b xn-1 + c A: xn+1 = 4 xn-1 - 1 B: xn+1 = 4 xn - 2 xn-1 - 11 C: xn+1 = (- xn + 9 xn-1 + 6)/2 These produce just the next three elements correctly but they may be combined to achieve the whole list of Heegner numbers: ```A: 1 2 3 7 11 27 ... B: 3 7 11 19 43 123 ... C: 11 19 43 67 163 223 ... ``` ``` 01>LBL "Heegner" 12>LBL C 24>LBL A 32>LBL B 02 1 13 X<>Y 25 X<>Y 33 ENTER 03 STOP 14 9 26 4 34 ENTER 04 2 15 * 27 * 35 + 05 STOP 16 RCL Y 28 1 36 R^ 06 XEQ A 17 - 29 - 37 - 07 XEQ A 18 6 30 STOP 38 ST+ X 08 XEQ B 19 + 31 RTN 39 11 09 XEQ B 20 2 40 - 10 XEQ C 21 / 41 STOP 11 XEQ C 22 STOP 42 END 23 RTN ``` Well, not exactly for the HP-12C but you still might like the solution. Cheers Thomas Edit: Replaced PROMPT by STOP as suggested by Namir below. Edited: 24 Mar 2011, 8:55 a.m. after one or more responses were posted ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-24-2011, 08:15 AM Thomas, I like your very elegant solution as it uses two simple values to initialize the sequence and then employed recursive relations to calculate the rest of the sequence numbers. I ran it on my 41CX (replacing PROMPT with R/S) and got the Heegner numbers. I also like the way it ends wihout using errors. Namir ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-24-2011, 01:31 PM Quote: I also like the way it ends wihout using errors. So do I. Also, when the program stops at 163 the next R/S displays it again so as to confirm this is really the last number in the sequence. In my first version, written on the HP-32SII, after the last number the sequence would cycle again. I've changed to the 12C because on the 32SII the program required one third more memory than when just displaying the numbers. However, in order to save a couple of steps I had to resort to using an overflow error to stop to program. Looks like I haven't succeeded in turning this minor shortcoming in an advantage :-) ```HP-32SII program B01 LBL B B02 1 B03 STOP B04 2.007 B05 STO N B06 IP B07 STOP B08 3 C01 LBL C C02 STOP C03 RCL N C04 0.6 C05 * C06 IP C07 x! C08 4 C09 * C10 + C11 ISG C12 GTO C C13 RTN size checksum B: 20 bytes 5EF3 C: 27.5 bytes 70C0 ``` Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-24-2011, 09:08 AM Thomas, Interesting recursive formulas albeit they don't allow for less memory usage when compared to just displaying the list. I am not sure whether mine is a true recursive formula though. Not so useful as one third of the elements of such a small set has to be predefined. Cheers, Gerson. ```-------------------- h0 = 1 h1 = 2 h2 = 3 hn = hn-1 + 4*(Floor(3/5*(n - 1))!) spread sheet | F G G (formulas) --+----------------- 3 | n Hn 4 | 0 1 =1 5 | 1 2 =2 6 | 2 3 =3 7 | 3 7 =G6+4*FACTORIAL(INT(3/5*F6)) 8 | 4 11 =G7+4*FACTORIAL(INT(3/5*F7)) 9 | 5 19 =G8+4*FACTORIAL(INT(3/5*F8)) 10| 6 43 =G9+4*FACTORIAL(INT(3/5*F9)) 11| 7 67 =G10+4*FACTORIAL(INT(3/5*F10)) 12| 8 163 =G11+4*FACTORIAL(INT(3/5*F11)) HP-12C program 01- 1 02- R/S 03- 2 04- R/S 05- STO 0 06- + 07- R/S 08- ENTER 09- n! ; overflows when hn > 67 10- Rv 11- RCL 0 12- . 13- 6 14- * 15- INTG 16- n! 17- 4 18- * 19- 1 20- STO+ 0 21- Rv 22- GTO 06 ``` ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-24-2011, 10:48 AM I think this is the proper way to write it: ```hn+1 = hn + 4*(Floor(3/5*n)!) ``` 3/5, 5/8, 8/13, 13/21, 21/34... would work as well, but 3/5 or .6 is more compact. A little trivia involving 163: EVAL these on the HP-48/50g ```'(163/3)^2*(5/2+1/(2/5*163^2))' 'pi!!' ``` ▼ Thomas Klemm Senior Member Posts: 735 Threads: 34 Joined: May 2007 03-24-2011, 12:57 PM My first attempt was to use the continued fraction: ```1+1/(2+1/(3+1/(7+1/(11+1/(19+1/(43+1/(67+1/163))))))) = 7,300,315,266/5,100,342,683 ``` But unfortunately the accuracy of the HP-12C is not sufficient. However it works with Free42. The program in the main loop would be very short: ```FRAC 1/X ``` Another idea would be to use the #RAN function of the HP-11C/15C with a well chosen seed. Thanks for the challenge. They are always inspiring. Best regards Thomas ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-24-2011, 01:56 PM I've checked your idea manually on WP-34s and it worked up to 67. The Monte Carlo approach would qualify if the HP-11C were allowed. However you'd need a fast simulator to find a suitable seed. Unfortunately Nonpareil doesn't offer a maximum speed option. Quote: Thanks for the challenge. They are always inspiring. You're welcome. The best part of these challenges it they sometimes yield unexpected by-products. Best regards, Gerson. Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-23-2011, 06:32 PM C.Ret's program can be shortened even more: ```01- 1 1 02- 44 0 STO 0 03- 45 0 RCL 0 04-44 10 1 STO/ 1 05- 31 R/S 06- 43 3 n! 07- 1 1 08-44 40 0 STO+ 0 09- 45 1 RCL 1 10- 45 0 RCL 0 11- 10 / 12- 43 24 FRAC 13- 43 35 x=0 14-43,33 01 GTO 03 15-43,33 04 GTO 07 ``` One step and one initialization less if 9.999999e99 after 163 instead of Error is not a concern. Gerson. Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-26-2011, 10:07 AM I haven't been able to make my HP-12C any shorter than the 22-step program I presented ealier. However, I've come up with a nicer algorithm (not necessarily less memory consuming though). I've noticed the last seven Heegner numbers can be expressed as: ``` 3 = 1*4 - 1 7 = 2*4 - 1 11 = 3*4 - 1 19 = 5*4 - 1 43 = 11*4 - 1 67 = 17*4 - 1 163 = 41*4 - 1 ``` Notice that 2, 3, 5, 11, 17 and 63 in the sequence of multiplicands above are the Euler's lucky numbers. Since there is not a formula for them this doesn't help much. However, the first differences of the terms of that sequence (1, 1, 2, 6, 6, 24) can be determined by a simple formula: ```a(n) = (Floor(3*n/4))!, n=1..6) ``` The following HP-71B BASIC program illustrates the algorithm: ```10 DESTROY ALL @ DISP 1 @ DISP 2 20 A=1 30 FOR N=1 TO 7 40 DISP 4*A-1 50 B=FACT(IP(3*N/4)) 60 A=A+B 70 NEXT N > >RUN 1 2 3 7 11 19 43 67 163 > ``` Here is an equivalent 22-step HP-12C program: ```01- CLEAR SIGMA ; R2 <- 0 02- SIGMA+ ; R1 <- 1 03- R/S 04- 2 05- R/S 06- 1 07- STO+ 2 08- RCL 1 09- 4 10- * 11- 1 12- - 13- R/S ; 167! will cause the 14- n! ; program to stop here 15- RCL 2 16- 9 17- 12/ ; 3/4 18- * 19- INTG 20- n! 21- STO+ 1 22- GTO 06 ``` Thanks again to all participants. I hope you have enjoyed. Gerson. Edited to fix a typo as per Jeff's observation below. Edited: 26 Mar 2011, 2:43 p.m. after one or more responses were posted ▼ Jeff O. Posting Freak Posts: 875 Threads: 37 Joined: Jul 2005 03-26-2011, 01:02 PM Gerson fixed the typo, no need to preserve the details... Edited: 28 Mar 2011, 7:49 p.m. after one or more responses were posted ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 03-26-2011, 02:41 PM Quote: 63*4 - 1 equals 251, and 163 equals 41*4 - 1. You're right. Thanks for pointing this out. Actually that was a typo. Will fix it right away. Regards, Gerson.

 Possibly Related Threads... Thread Author Replies Views Last Post HP Prime: complex numbers in CAS. Alberto Candel 1 640 12-06-2013, 02:36 PM Last Post: parisse [HP Prime] Plots containing complex numbers bug? Chris Pem10 7 1,258 12-05-2013, 07:40 AM Last Post: cyrille de Brébisson comparing numbers on the WP 34S Kiyoshi Akima 7 1,121 10-19-2013, 09:28 AM Last Post: walter b HP Prime: Operations with Large Numbers Eddie W. Shore 0 342 10-19-2013, 12:24 AM Last Post: Eddie W. Shore HHC 2013 room numbers David Hayden 2 550 09-20-2013, 05:34 PM Last Post: sjthomas HPCC Mini Conference 2013 hugh steers 6 827 09-13-2013, 04:27 PM Last Post: BruceH [HP-Prime xcas] operations with complex numbers + BUGs + Request CompSystems 9 1,343 09-08-2013, 10:40 PM Last Post: CompSystems TED Talk: Adam Spencer: Why I fell in love with monster prime numbers Les Bell 3 684 09-05-2013, 12:54 PM Last Post: Ken Shaw Irrationality in numbers....the book Matt Agajanian 4 721 08-30-2013, 04:14 PM Last Post: Matt Agajanian Best HP calculator for crunching numbers rpn fan 51 4,737 08-05-2013, 03:17 PM Last Post: rpn fan

Forum Jump: