The Museum of HP Calculators

HP Forum Archive 20

[ Return to Index | Top of Index ]

HP-12C mini-challenge - Heegner numbers
Message #1 Posted by Gerson W. Barbosa on 22 Mar 2011, 7:30 p.m.

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.

      
Re: HP-12C mini-challenge - Heegner numbers
Message #2 Posted by Kiyoshi Akima on 23 Mar 2011, 2:01 a.m.,
in response to message #1 by Gerson W. Barbosa

I suppose a program like RCL 1 : R/S : RCL 2 : R/S ... RCL 9 : R/S doesn't qualify.

            
Re: HP-12C mini-challenge - Heegner numbers
Message #3 Posted by Paul Dale on 23 Mar 2011, 2:31 a.m.,
in response to message #2 by Kiyoshi Akima

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

      
Re: HP-12C mini-challenge - Heegner numbers
Message #4 Posted by C.Ret on 23 Mar 2011, 5:01 a.m.,
in response to message #1 by Gerson W. Barbosa

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.

            
Re: HP-12C mini-challenge - Heegner numbers
Message #5 Posted by Paul Dale on 23 Mar 2011, 5:27 a.m.,
in response to message #4 by C.Ret

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

                  
Re: HP-12C mini-challenge - Heegner numbers
Message #6 Posted by Namir on 23 Mar 2011, 7:54 a.m.,
in response to message #5 by Paul Dale

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.

                        
Re: HP-12C mini-challenge - Heegner numbers
Message #7 Posted by Gerson W. Barbosa on 23 Mar 2011, 10:58 a.m.,
in response to message #6 by Namir

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.

                              
Re: HP-12C mini-challenge - Heegner numbers
Message #8 Posted by Paul Dale on 23 Mar 2011, 5:26 p.m.,
in response to message #7 by Gerson W. Barbosa

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

                                    
Re: HP-12C mini-challenge - Heegner numbers
Message #9 Posted by Gerson W. Barbosa on 23 Mar 2011, 6:57 p.m.,
in response to message #8 by Paul Dale

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:

http://oeis.org/A038551

I have used this to get a recurring formula for the fourth Heegner number ownards. No mathematical meaning, but it works.

Gerson.

                                          
Re: HP-12C mini-challenge - Heegner numbers
Message #10 Posted by Thomas Klemm on 24 Mar 2011, 4:03 a.m.,
in response to message #9 by Gerson W. Barbosa

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

                                                
Re: HP-12C mini-challenge - Heegner numbers
Message #11 Posted by Namir on 24 Mar 2011, 8:15 a.m.,
in response to message #10 by Thomas Klemm

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

                                                      
Re: HP-12C mini-challenge - Heegner numbers
Message #12 Posted by Gerson W. Barbosa on 24 Mar 2011, 1:31 p.m.,
in response to message #11 by Namir

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

                                                
Re: HP-12C mini-challenge - Heegner numbers
Message #13 Posted by Gerson W. Barbosa on 24 Mar 2011, 9:08 a.m.,
in response to message #10 by Thomas Klemm

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

                                                      
Re: HP-12C mini-challenge - Heegner numbers
Message #14 Posted by Gerson W. Barbosa on 24 Mar 2011, 10:48 a.m.,
in response to message #13 by Gerson W. Barbosa

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!!'

                                                            
Re: HP-12C mini-challenge - Heegner numbers
Message #15 Posted by Thomas Klemm on 24 Mar 2011, 12:57 p.m.,
in response to message #14 by Gerson W. Barbosa

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

                                                                  
Re: HP-12C mini-challenge - Heegner numbers
Message #16 Posted by Gerson W. Barbosa on 24 Mar 2011, 1:56 p.m.,
in response to message #15 by Thomas Klemm

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.

                  
Re: HP-12C mini-challenge - Heegner numbers
Message #17 Posted by Gerson W. Barbosa on 23 Mar 2011, 6:32 p.m.,
in response to message #5 by Paul Dale

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.

      
Re: HP-12C mini-challenge - Heegner numbers
Message #18 Posted by Gerson W. Barbosa on 26 Mar 2011, 10:07 a.m.,
in response to message #1 by Gerson W. Barbosa

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

            
Re: HP-12C mini-challenge - Heegner numbers
Message #19 Posted by Jeff O. on 26 Mar 2011, 1:02 p.m.,
in response to message #18 by Gerson W. Barbosa

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

                  
Re: HP-12C mini-challenge - Heegner numbers
Message #20 Posted by Gerson W. Barbosa on 26 Mar 2011, 2:41 p.m.,
in response to message #19 by Jeff O.

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.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall