OEIS A228297: Need Help to Find Algorithm

[Thomas Okken]

(09-17-2017 04:08 PM)Gerald H Wrote:  I would like the range of input on the real calculator to be at least in the millions.

That would require an algorithm that doesn't store all of A(1)...A(N). I don't know if that's possible.

Iterative implementation for HP-42S:

Code:

00 { 134-Byte Prgm }
01▸LBL "AA"
02 X>0?
03 GTO 00
04 0
05 RTN
06▸LBL 00
07 5
08 X<>Y
09 X≤Y?
10 RTN
11 STO "N"
12 1
13 +
14 1
15 NEWMAT
16 STO "REGS"
17 5
18▸LBL 01
19 STO IND ST X
20 DSE ST X
21 GTO 01
22 6
23 STO "I"
24▸LBL 02
25 RCL "I"
26 STO "J"
27 DSE "J"
28 RCL- IND "J"
29 RCL IND ST X
30 RCL "J"
31 DSE "J"
32 RCL- IND "J"
33 X<>Y
34 RCL+ IND ST Y
35 RCL "J"
36 DSE "J"
37 RCL- IND "J"
38 X<>Y
39 RCL+ IND ST Y
40 RCL "J"
41 DSE "J"
42 RCL- IND "J"
43 X<>Y
44 RCL+ IND ST Y
45 RCL "J"
46 DSE "J"
47 RCL- IND "J"
48 X<>Y
49 RCL+ IND ST Y
50 STO IND "I"
51 1
52 STO+ "I"
53 RCL "I"
54 RCL "N"
55 X≥Y?
56 GTO 02
57 R↑
58 END

This calculates a(100) is 97 seconds, on a real HP-42S.

UPDATE: The program doesn't avoid tight-memory situations; it really should do CLV "REGS" before NEWMAT, and do CLX after STO "REGS", to make sure nothing is competing with REGS for the calculator's RAM.
Still, even it its current form, running in Free42 on an iPhone 5s, it calculates a(2,000,000) in under a minute, so Gerald's requirement can be met, as long as you use the right equipment. :-)