HP-12C mini-challenge - Heegner numbers



#21

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.


#22

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


#23

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

#24

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.


#25

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


#26

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.


#27

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.


#28

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


#29

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.


#30

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


#31

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


#32

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

#33

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


#34

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


#35

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


#36

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.

#37

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.

#38

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


#39

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


#40

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 461 12-06-2013, 02:36 PM
Last Post: parisse
  [HP Prime] Plots containing complex numbers bug? Chris Pem10 7 860 12-05-2013, 07:40 AM
Last Post: cyrille de Brébisson
  comparing numbers on the WP 34S Kiyoshi Akima 7 819 10-19-2013, 09:28 AM
Last Post: walter b
  HP Prime: Operations with Large Numbers Eddie W. Shore 0 231 10-19-2013, 12:24 AM
Last Post: Eddie W. Shore
  HHC 2013 room numbers David Hayden 2 382 09-20-2013, 05:34 PM
Last Post: sjthomas
  HPCC Mini Conference 2013 hugh steers 6 596 09-13-2013, 04:27 PM
Last Post: BruceH
  [HP-Prime xcas] operations with complex numbers + BUGs + Request CompSystems 9 936 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 484 09-05-2013, 12:54 PM
Last Post: Ken Shaw
  Irrationality in numbers....the book Matt Agajanian 4 509 08-30-2013, 04:14 PM
Last Post: Matt Agajanian
  Best HP calculator for crunching numbers rpn fan 51 3,449 08-05-2013, 03:17 PM
Last Post: rpn fan

Forum Jump: