▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 325
Threads: 18
Joined: Jul 2006
I suppose a program like RCL 1 : R/S : RCL 2 : R/S ... RCL 9 : R/S doesn't qualify.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
Posts: 260
Threads: 0
Joined: Oct 2008
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.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 735
Threads: 34
Joined: May 2007
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
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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!!'
▼
Posts: 735
Threads: 34
Joined: May 2007
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
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
▼
Posts: 875
Threads: 37
Joined: Jul 2005
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
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
|