major number theory discovery, if you can translate



#2

I read in the current issue of Scientific American that a fellow at Emory University has discovered a formula for determining the number of "partitions" (P) for n.

For example, the number 5 has 7 partitions:

  1. 5
  2. 1+1+1+1+1
  3. 1+1+1+2
  4. 1+1+3
  5. 1+2+2
  6. 1+4
  7. 2+3

I was hoping the formula would be "simple" so that I could readily understand it. Alas. I'm hoping somebody here can translate this to "simple" math.

References here and here.


#3

Don, I understand everything from the word INTRODUCTION to the number 1002 on page 1. Everything else is a little fuzzy. That's one reason why I'm a math MINOR not a Math Major.. in Engineering, we say.. "Look, it's off by 0.5 - close enough!", Send it to the marketing department and move on.

#4

It seems a quite elegant solution -- whatever it says.


#5

I especially like their 'amusing proof of the fact that p(1) = 1.'

No need for a calculator on that one! -- Jeff Kearns

#6

Really, it sounds like a great solution, but they propose a Theorem them offer a proof, but I fail to see a connection between either the proof, or the example, or the p(n) partitions introduction- in fact the whole thing seems like a joke.

#7

Is it the "APRIL" issue?!


#8

Dave, yes it is the April issue of Scientific American, it came in the mail today. I would not think a serious journal like Scientific American would be offering up April fools jokes, at least knowingly (the article in SA does not describe the algorithm, only its discovery).

One might wonder, if the description of the algorithm is so complex that an average person can't figure it out, perhaps it could be a practical joke. I teach middle school math, and this stuff is way way beyond my knowledge level. I posted this here hoping some brilliant person could convert this to "simple math," but I have a feeling that is probably not possible.


#9

Don,

SA may well be joking - I saw somewhere (here?) just the other day a reference to a Scientific American April Fool's article (from the 70's, I think).


#10

I don't think this is a joke. Watch the presentation, read the paper and make up your own mind. I'm not a professional mathematician but this looks to me about as as real as it gets. I have no idea if the proof is mistake free but the theorem seems reasonable and makes sense.

-Katie

p.s. here's the full, serious paper.


Edited: 25 Mar 2011, 12:10 a.m.

#11

There was an old SA April issue which was almost entirely an April Fool's joke. It contained, if I remember properly, a disproof of the four-color map theorem, an exception to the theory of relativity, and others.

(edited to fix a typo)


Edited: 25 Mar 2011, 1:05 p.m.

#12

Quote:
I would not think a serious journal like Scientific American would be offering up April fools jokes [...]
It's tradition. Even HP did this once. You know which calculator has been targeted by the HP fools? :-)
#13

An HP-41 program would make it all very clear. I would have to decipher the maths to be able to make one, and I believe others on this forum is better equipped to decipher this... any takers?


#14

Although this is a major theoretical breakthrough and gives a non-infinite series for computing p(n), for practical purposes Euler's generating function is much faster for reasonably small values of n. It's quite understandable and is described
here.


I think that this would make for a good programming exercise on any calculator with a decent amount of memory. You need to store the values of p(n) in order to avoid an impossible amount of recursion. Of course p(100) is a 9-digit number, and p(200) is a 13-digit number, so unless you've got bignums you're going to be limited anyway.


Here is the algorithm in Java

Edited: 25 Mar 2011, 12:12 p.m.


#15

I wasn't really looking for a program to calculate the partitions - but rather a way to understand the new work... and an HP-41 program would (for me) be the easiest way to get my head around it.

#16

Thanks, Don, for the links! I watched Ken Ono's presentation. Fascinating stuff.

Katie, thanks for digging out that code.

I did a quick adaptation to JavaScript.

You're quite right, this method by Euler runs fast for reasonably small numbers. It takes about 3s to compute the number of partitions for 1000. The result is returned as a BigInt.

(It would run at similar speed in RPL, btw, because the time is spent in BigInt functions.)

Anyone with ND0 or ND1 can pick this up by downloading the new "Number Theory" shared folder.

I sure would like to try and implement Ken Ono's method. My understanding needs to catch up with the paper first, though...

I'd love to see an implementation.

Cheers.

Code:

function(n) {
var depent = Math.sqrt(1.0+n);
var signArray = [];
var pentArray = [];
signArray[0]=-1; signArray[1]=1;
pentArray[0]=0; pentArray[1]=1;
for (var i=1; i<=depent; i++) {
signArray[2*i] = -signArray[2*i-2];
signArray[2*i+1] = -signArray[2*i-1];
pentArray[2*i] = (i*(3*i+1))/2;
pentArray[2*i+1] = ((i+1)*(3*i+2))/2;
}
var partitionArray = [];
partitionArray[0] = BigInteger.ONE;
for (var j=1; j<=n; j++) {
var partSum = BigInteger.ZERO;
for (var k=1; pentArray[k]<=j; k++) {
if (signArray[k]==1)
partSum = partSum.add(partitionArray[j-pentArray[k]]);
else
partSum = partSum.subtract(partitionArray[j-pentArray[k]]);
}
partitionArray[j] = partSum;
}
return partitionArray[n];
}

Edited: 26 Mar 2011, 7:31 a.m.


#17

Oliver,

Can you please add some minimal html code so I can save the source code and html tags to an html file and then run it?

Thanks!

Namir


#18

Hi Namir,

Getting this to work in the browser needs a bit more than some HTML tags. You need a bit of a UI and, crucially, you need a BigInteger library. The given code is JavaScript but it assumes one. (BigInteger math is *not* standard in JavaScript.)

As you seem to have an iOS device, can I ask you to do the much easier thing and give ND0 (or ND1) another try?

As you didn't like Modern mode, just go into the Settings app, find ND0 and switch it to "Classic".

In ND0, go to My Data, under Downloadables, tap Folders, tap "Number Theory". That downloads the data and makes it available in the calculator.

Tap ND0, and operate this exactly like an HP-28, -48, 50g:
tap VAR, tap Number Theory and you're ready to play with it.

Enter a number, and tap the "p" soft-key. You'll get your result on the stack. (For values to about 100, this is instantaneous.)

If you want to play with the code, edit "p" using the RCL and EDIT keys. (Or use, as on the 50g, the 2nd-level key + soft-key shortcut.) The code will appear in a scrolling editor. When you're done, enter, and use STO to save the code again as 'p', or under a new name.

If you're familiar with any RPL calc, these operations function just the same way.

If you manage to implement Ken Ono's "simple and beautiful function" we'll all be in awe. (And I'm willing to lend support to your efforts.) This can be done either in JavaScript or in RPL.

Oliver

Edited: 27 Mar 2011, 2:52 p.m.

#19

As a lot of you, I am unable to clearly understand and play with the specific mathematical notioa couple of n, Bessel function and infinite series extensively used in this publication. I am unable to follow the tricky path the authors have used to achieve to an ‘arithmetic expression’ of the partition p(n) of any integer n.

But the link and recommendations that Katie give us in her post, allow me to use one of the recurrent approach of the problem to write of few codes to calculate partitions on any HP28C/S or HP41C.

Recursion, arithmetic and memory

As Katie have advert it, my code stores the values of p(n) in order to avoid an impossible amount of recursion. In the same time, this makes computation much more time efficient.

The philosophy of my approach is to store the first m pre-calculated values of p(n) into the calculator register
Thus, asking for any partition number p(n) where n<m is as trivial as recalling a register content.
For any non pre-calculated p(n), the following method is used to compute and store in memory p(n) from previous (and already store in most case) p(n-q) :
From Euler’s pentagonal number theorem, we have the general sum:

p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15)...


Where terms of this sum are where k is a relative integer used to generate a suitable set of “Euler’s pentagonal numbers” q.

This summation gives the new and unknown number of partitions p(n) as a function of previous value p(n-q).
Validity is that we have to sum for any 0 < n-q < n, which lead to a sequence of alternatively positive and negative k 1, -1, 2, -2, 3, -3, 4, -4, ... and so on until q>n.
A special attention have to be care incase when q = n where p(0) = 1 has to be consider.
But this will be treated later in code, due to a specific memory usage. Only p(n) for n = 1 to m are store in memory or memory register from R01 to Rmm

Example1:

Already in memory: p(1) = 1, p( 2 ) = 1
Computing p(3)

k | 1 -1 2
------+----------------------------------------------
Sign | + + -
q | 1 2 5 out of range q>n
n-q | 2 1
p(n-q)| +2 +1
------+---------------------------------------------
Thus p(3) = 2 + 1 = 3

Example2:

Already in memory : p(1) = 1, p( 2 ) = 1, p(3) = 3, p(4) = 5
Computing p(5)

k | 1 -1 2
------+----------------------------------------------
Sign | + + -
q | 1 2 5
n-q | 3 2 0
p(n-q)| +3 +5 -1
------+---------------------------------------------
Thus p(5) = 3 + 5 – 1 = 7

Example3:

Already in memory : p(1) to p(5)
Computing p(10)

k | 1 -1 2 -2 3
------+----------------------------------------------
Sign | + + - - +
q | 1 2 5 7 12 out of range q>10
n-q | 9 2 5 3
p(n-q)|+(30) +(22) -7 -3 () indicate external recursive calls
------+---------------------------------------------
Thus p(5) = 30 + 22 – 7 - 3 = 42


The behavior of the summation when attempting to use an non pre-calculated p(n-q) partition depends of the power of the calculator and its ability to recursively compute it.

That why I have first developed an algorithm on my HP28S, since large memory allow directly recursive calls for unknown (and non store) value.

For the HP41C version, the purely recursive algorithm was adapted for using no strictly recursive calls.
In fact, the really first tries on the HP28S show me that any attempt to compute a new p(n) greater that the last p(m) in memory generate cascading recursive calls to compute p(n-1), p(n-2), p(n-3), ... p(m+1) since any summation start with q=1.
So, the HP41C avoid any recursive calls by simply looping from m to n by step 1. This spares large among of memory and time.

To generate the sign sequence, two flag are used which greatly help generated the k sequence and summation/subtraction alternate.


k ope | Flag#1 Flag#2 | q p(n-q) | sum/sub
------------+-----------------+-------------+---------
1 +1 | 0 0 | 1 p(n-1) | +
-1 neg | 1 0 | 2 p(n-2) | +
2 +1 | 0 1 | 5 p(n-5) | -
-2 neg | 1 1 | 7 p(n-7) | -
3 +1 | 0 0 | 12 p(n-12)| +
etc
------------+-----------------+-------------+---------
Clearly two flags are needed to code a four steps sequence.
Flag#1 indicate when k have to be incremented after its sign change.
Flag#2 indicate when subtraction is replacing addition of p(n-q)


HP 28C/S version

Three programs:
INIT to initiate PDAT array in memory and set p(1)=1.
P to compute p(n) from memory (i.e. PDAT array) or by recursively calling PCALC

PCALC to compute p(n) when n is greater then pre-calculated p(m).

Memory usage:
The p(n) are stored in the array 'PDAT' initialized up to 200 elements with ‘PDAT(1) = 1’ only, all other set to zero.

Usage:
Before any use of P, one may invoke initialization of memory array ‘PDAT’ by typing INIT [ENTER] or using USER menu soft key.

Recursive computation of any p(n) from 1 to m can be lunch by typing or using softkeys
m P [ENTER] or equivalently m PCALC [ENTER]

After initial pre-calculation, any p(n) with n<m can be obtain immediately by typing :
n P [ENTER]


CODE for HP28C/S or any RPL calculators

@@ -------------------------- INIT      ---------------:

« {200} 0 CON 1 1 PUT 'PDAT' STO »
'INIT' STO @ construct an array of 200 elements all zero except #1 which is 1 (p(1)=1)


@@ -------------------------- P ---------------:
« 'PDAT' OVER GET
IF DUP @ test zero which indicate non pre-stored value
THEN SWAP DROP @ makes p(n) top of the stack
ELSE DROP PCALC @ call n PCALC to compute unknown p(n)
END
»
'P' STO

@@ -------------------------- PCALC ---------------:
« -> n @ n
« 1 SF 2 SF
0 @ Initialise sum
0 @ Initialise k
DO @ main loop - summing/soustracting p(q_k)
NEG @ k --> -k
IF 1 FS?C @ clear flag #1 (next loop only change sign of k)
THEN
2 NF @ change position of flag #2 (cf. NF )
1 + @ k --> k+1
ELSE
1 SF @ set flag #1 (next loop increment k)
END
3 OVER * 1 - OVER * 2 / @ compute pentagonal integer q = k(3k-1)/2
n SWAP -
IF DUP 0 > @ test validity of n-q as
THEN
« P » RSTF @ recursively call p(n-q) preserving flags status (cf. RSTF)
ELSE
0 == @ hold 1 when p(0) is involve in the sum
SWAP DROP 0 SWAP @ set k to zero ( = loop exit condition )
END
ROT SWAP
IF 2 FS? @ test flag #2 for
THEN - @ soustrating
ELSE + @ or additing p(n-q) to sum
END
SWAP
UNTIL DUP NOT END @ loop until k has been set to zero
DROP
'PDAT' n 3 PICK PUT @ put p(n) in PDAT for further uses
n 1 DISP @ display n in line 1
DUP 2 DISP @ display p(n) in line 2
CLMF
»
»
'PCALC' STO


@@ -------------------------- flag #1 & #2 rules ---------------:
F#1 F#2 Sum q=k(3k-1)/2 p()
k= 1 c c + 1 p(n-1)
k=-1 s c + 2 p(n-2)
k= 2 c s - 5 p(n-5)
k=-2 s s - 7 p(n-7)
k= 3 c c + 12 p(n-12)
k=-3 s c + 15 ...
etc...
k= 0 exit loop q>n

P.S.: if n=q, p(0)=1 have to be take into account.

@@ -----------------------------------NF subprogram ----------------------
« IF DUP FS? @ negate flag status
THEN CF
ELSE SF
END
»
'NF' STO

@@ ----------------------------------RSTF subprogram ---------------------
« RCLF -> F « EVAL F STOF » » @ Execute (EVAL) a program and restore initial flag's status


HP 41C version

This version is an adaptation of the HP28S version code. The same sub-programs may be found in the code at the specific labels.
Main differences are that direct recursive calls of PCALC have been transform into a from m+1 to n one by one step loop using ISG 00.

Program:
Type [EXC][ALPHA]PART[ALPHA] to initiate memory and set p(1)=1.
The calculator display 1.0000 indicates a successfully initialization.

Usage
To compute p(n) simply enter n and press [ A ] soft key ( S+ key in USER mode).

If p(n) already in memory, result is immediately display. The sequence is equivalent to recalling or viewing register (RCL nn or VIEW nn can be used to display p(nn) for any nn<100).
If n is greater than previously computed and memorized p(n), the calculator sequentially compute any p(n) from last in memory up to n.
The larger n, the slowest is the computation.

Memory usage:
The p(n) are stored in the register from R01 up to Rmm depending of available memory and the SIZE mmm setting.

The register R00 is used to count/loop and store the last register position.

The ALPHA register is used to display progression during extended computations.

Flag#0 is used for indicating erroneous condition (mainly badly initiate register or interrupted R/S)
Flag#1, Flag#2 are used for k sequence and summation/subtraction alternate.
Flag#3 is used for treated the special n = q cases.


CODE for HP41C/CV/CX or any compatible calculators

PRGM		t:	z:	y:	x:/disply	Comments

01 LBL "PART @ Init PARTition program
02 CLRG @ clear all the registers
03 1 1
04 STO 01 @ p(1) = 1
05 STO 00 @ nb of registred p(n) set to 1 (m)
06 RTN
1.0000
------------------------------------------------------------
n
07 LBL "A @ ENTER n PRESS "A" key
08 CF 00 @ clear error indicator (Flag #0)
09 RCL IND X n Rn @ recall p(n)
10 x=0?
11 GTO 00 n 0 @ Goto to PCalc routine
12 RTN
n p(n)
------------------------------------------------------------ PCalc
13 LBL 00 n 0
14 RDN n
15 1 E 3
16 / .nnn @
17 RCl 00 .nnn m
18 INT
19 + m.nnn
20 STO 00 @ store loop index in R00
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
21 LBL 01 @ increment R00 (m.nnn)
22 ISG 00
23 GTO 02 @ goto new p(n) computation
24 DSE 00 @ decrease R00 to match register contents
25 RTN
26 RTN p(n) @ stop when m = n
@ leave p(n) in x: (true end of program)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - p(n)=SUM +- p(n-q)
27 LBL 02
28 CF 01 @
29 SF 02
30 0 m.nnn 0 @ Initialise sum
31 0 m.nnn 0 0 @ Initialise k
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Main Loop SUM +-
32 LBL 03 S k @ Main loop (summing)
33 CHS
34 FS?C 01 @ F1=c next k is k+1
35 GTO 04
36 1
37 + @ k <-- k+1
38 SF 01 @ F1=s next k is -k
39 FS?C 02
40 GTO 04 @ invert F2
41 SF 02 @ F2=s substrat p(n-q)
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
42 LBL 04 ~ S k @ compute pentagonal integer k(3k-1)/2
43 3 S k 3
44 RCL Y S k 3 k
45 * S S k 3k
46 1 S k 3k 1
47 - S S k 3k-1
48 RCL Y S k 3k-1 k
49 * S S k k(3k-1)
50 2 S k k(3k-1) 2
51 / S S k q @ q=k(3k-1)/2
52 RCL 00 S k q m.nnn
53 INT S k q n
54 x<=y? @ test n<=q ?
55 GTO 05 @ then exit main loop
56 x<->y S k n q
57 - S S k n-q
58 RCl IND X S k n-q p(n-q)
59 x=0?
60 SF 00 @ tag error (unconsistant register value)
61 FS? 02
62 CHS +-p
63 ST+ T S+-p k n-q p(n-q)
64 RDN ~ S+-p k n-q
65 RDN ~ ~ S+-p k
66 GTO 03 @ do main loop (summing)
- - - - - - - - - - - - - - - - - - - - - - - - - - -
67 LBL 05 S k q n @ End of main loop
68 x=y?
69 SF 03 @ n=q flag
70 R^ k q n S
71 FC?C 03 @ test special cas n=q ?
72 GTO 06
73 1 q n S 1
74 FS? 02 @ test +/- sequence position
75 CHS q n S +-1
76 + q q n S+-1
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
77 LBL 06 n S
78 STO IND Y @ memorize p(n) <-- S
79 CLA
80 ARCL Y @ Prepare display
81 "~:
82 ARCL X
83 AVIEW @ display progress during PRGM run
84 GTO 01
85 END
----------------------------------------------------------------------

@@ ------------------ Flag 1 & 2 rules
F1 F2 sum
k= 1 s c +
k=-1 c c +
k= 2 s s -
k=-2 c s -


Conclusion

As expected, this code may not obtain exact partition number up to p(200) due to the calculator’s number of digit limits.
The 12-digit HP28C/S arithmetic allow me to compute exact p(179)= 625846753120.
And the limit of exact partition number on the HP41C (with two memory modules) is p(131)=5964539504.
This result is confirmed by the HP28S display.
Note that expected largest 10-digit partition number was p(135)=9035836076 but is unachieved on the HP41C due to the 10-digits limitation in summation/subtraction process.
As well the expected maximal 12-digit number of partition p(184)= 980462880430 is not exact on the HP28S.

I am waiting for any improvements of this from any HP enthusiast user.


Edit: Add missing END of the DO ... UNTIL main loop


Edited: 31 Mar 2011, 12:10 p.m. after one or more responses were posted


#20

Quote:
As well the expected maximal 12-digit number of partition p(184)= 980462880430 is not exact on the HP28S.

The HP-50g in exact mode gets it right. The last number in the list matches the one in page 155 of my translated copy of Marcus du Sautoy's The Music of Primes. Your program runs unchanged (except for a missing END in the DO structure and the CLMF command, which the 50g lacks). For n=200, it takes 11 minutes and 7 seconds:

%%HP: T(3)A(R)F(,);
DIR
PCALC
\<< \-> n
\<< 1 SF 2 SF 0 0
DO NEG
IF 1 FS?C
THEN 2 NF 1 +
ELSE 1 SF
END 3 OVER * 1 - OVER * 2 / n SWAP -
IF DUP 0 >
THEN
\<< P
\>> RSTF
ELSE 0 == SWAP DROP 0 SWAP
END ROT SWAP
IF 2 FS?
THEN -
ELSE +
END SWAP
UNTIL DUP NOT
END DROP 'PDAT' n 3 PICK PUT n 1 DISP DUP 2 DISP
\>>
\>>
INIT
\<< { 200 } 0 CON 1 1 PUT 'PDAT' STO
\>>
NF
\<<
IF DUP FS?
THEN CF
ELSE SF
END
\>>
P
\<< 'PDAT' OVER GET
IF DUP
THEN SWAP DROP
ELSE DROP PCALC
END
\>>
PDAT [ 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565 5604
6842 8349 10143 12310 14883 17977 21637 26015 31185 37338 44583 53174 63261 75175 89134 105558 124754 147273 173525
204226 239943 281589 329931 386155 451276 526823 614154 715220 831820 966467 1121505 1300156 1505499 1741630 2012558
2323520 2679689 3087735 3554345 4087968 4697205 5392783 6185689 7089500 8118264 9289091 10619863 12132164 13848650
15796476 18004327 20506255 23338469 26543660 30167357 34262962 38887673 44108109 49995925 56634173 64112359 72533807
82010177 92669720 104651419 118114304 133230930 150198136 169229875 190569292 214481126 241265379 271248950 304801365
342325709 384276336 431149389 483502844 541946240 607163746 679903203 761002156 851376628 952050665 1064144451 1188908248
1327710076 1482074143 1653668665 1844349560 2056148051 2291320912 2552338241 2841940500 3163127352 3519222692 3913864295
4351078600 4835271870 5371315400 5964539504 6620830889 7346629512 8149040695 9035836076 10015581680 11097645016
12292341831 13610949895 15065878135 16670689208 18440293320 20390982757 22540654445 24908858009 27517052599 30388671978
33549419497 37027355200 40853235313 45060624582 49686288421 54770336324 60356673280 66493182097 73232243759 80630964769
88751778802 97662728555 107438159466 118159068427 129913904637 142798995930 156919475295 172389800255 189334822579
207890420102 228204732751 250438925115 274768617130 301384802048 330495499613 362326859895 397125074750 435157697830
476715857290 522115831195 571701605655 625846753120 684957390936 749474411781 819876908323 896684817527 980462880430
1071823774337 1171432692373 1280011042268 1398341745571 1527273599625 1667727404093 1820701100652 1987276856363
2168627105469 2366022741845 2580840212973 2814570987591 3068829878530 3345365983698 3646072432125 3972999029388 ]
RSTF
\<< RCLF \-> F
\<< EVAL F STOF
\>>
\>>
END

The math involved is far beyond my skills. I would suggest only a few minor changes to your didactic RPL listing above. Not much gain, though: 10 minutes and 40 seconds for n=200.

Regards,

Gerson.

--------------

%%HP: T(3)A(R)F(,);
DIR
PCALC
\<< \-> n
\<< { 200 } 0 CON 1 1 PUT 'PDAT' STO 1 SF 2 SF 0 0
DO NEG
IF 1 FS?C
THEN 2 DUP FS? { CF } { SF } IFTE 1 +
ELSE 1 SF
END 3 OVER * 1 - OVER * 2 / n SWAP -
IF DUP 0 >
THEN
\<< P
\>> RSTF
ELSE 0 == NIP 0 SWAP
END ROT SWAP 2 FS? { - } { + } IFTE SWAP
UNTIL DUP NOT
END DROP 'PDAT' n 3 PICK PUT n 1 DISP DUP 2 DISP
\>>
\>>
P
\<< 'PDAT' OVER GET DUP { NIP } { DROP PCALC } IFTE
\>>
RSTF
\<< RCLF \-> F
\<< EVAL F STOF
\>>
\>>
END
--------------


#21

Hi,

Thank you Gerson for pointing my attention on the missing END.

It is a shame that, I have no way to transmit data from my HP28S to my computer. A way to connect a HP28S to a computer is missing. And I am prone to copy/past error when typing code.

May I have to spend same time to look for a way to use the IR port of my laptop to receive any IR transmissions from my HP28S?

The HP28S is about 23min to compute up to p(200) with << INIT 200 PCALC >>

I am currently looking for sparing a few minutes by using:
<< INIT 2 200 FOR I I PCALC NEXT >>
I am currently suspected the numerous recursive calls to consume a large bunch of memory and as a consequence to be slow in execution time.

The HP 41C’s algorithm seems to be much faster than my HP28S (I just start the two computation on both calculators at the same time). The rabbit looks to be beaten by the turtle! again?

Concerning the mathematic underneath, I also not really sure to understand all the detail in depth. It appears to me as a combinational approach. To compute one p(n) partition you have to add partition of previous , but because of a couple of redundancies in your count you have to subtract same of them.
Why is working with these specific “Euler’s pentagonal number” is a mystery for me ! Is “pentagonality” equivalent in the additions to the “orthogonality” in the multiplication?
This is one more mystery. There is a lot of mystery in nature and numbers are really natural mathematical objet. This is part of the charm of the “number theory”.

Edited: I was right, INIT 2 200 FOR I I PCALC NEXT reach p(200) in only 12 min. It's less than half the time of brute force direct recursion !!

Edited: 31 Mar 2011, 1:00 p.m.


#22

Quote:
A way to connect a HP28S to a computer is missing.

I think there is an indirect way, by using INPRT and one HP-48.

Once I read about a serial interface design for the HP-28S, perhaps here, but I am not sure. Anyway, I don't think you would be willing to open up your HP-28S :-)

Quote:
The HP 41C’s algorithm seems to be much faster than my HP28S.

Your HP-41C program demonstrates the importance of that new discovery. I don't know about the previous methods, but I guess they would be hard to implement even on the 50g. The program should run very fast and accurately on Free42 Decimal. I'll try it later.

Regards,

Gerson.


#23

I am sorry. I was mistakely comparing speed of HP41C's to sequently compute from p(2) to p(100) with HP28S's time to compute directly p(200) by worste case using most loads of direct recurrence calls.

In fact, the HP41C is much slower than the HP28C by a factor of nearly 4.

Here are execution times running for HP41C and HP28C

 p(n) |   10     25     50     75    100    125    150    175   200
------+------------------------------------------------------------
HP41C| 40" 2'05" 5'35" 10'20" 15'30" 21'40" 28'25" 35'40" na
HP28S| 10" 30" 1'25" 2'35" 4'00" 5'35" 7'30" 9'20" 12'

Edited: 31 Mar 2011, 3:21 p.m.

#24

Hmm.

Something seems to kill performance here.

I bet a non-recursive version would run quite a bit faster.

The JavaScript version takes 0.2s for p(200) on ND1 (on an iPhone 3GS), by the way.


#25

You are right, recursive calls kill the beast !

The best way to get the p(n) list is to compute it one step by one step since the previous and previous by one are needed. Making things in order is logical and speed up the process.


 p(n)      |   10     25     50     75    100    125    150    175   200
-----------+------------------------------------------------------------
HP41C (1) | 40" 2'05" 5'35" 10'20" 15'30" 21'40" 28'25" 35'40" na
-----------+------------------------------------------------------------
HP28S (1) | 10" 30" 1'25" 2'35" 4'00" 5'35" 7'30" 9'20" 12'
(2) | 10" 30" 1'30" 2'50" 4'25" 6'10" 8'05" 10'10" 13'
(3) | 10" 30" 1'40" 3'25" 5'45" 8'50" 12'40" 17'20" 23'
-----------+------------------------------------------------------------

(1) Best method: each p(n) is compute when any p(n-1) p(n-2) p(n-3) ... are already know and store in memory register. Memory is initiated only once.

(2) Intermediate method: Memory is initiated only once. For each column, the results from the previous run are kept in memory. The recursive depth s limited; only 25 p(n) values are missing at each run.

(3) Worst method: memory is clear before each computation (each column in table) resulting in deepest recursive calls stack.

This table clearly shows the effect of massive recursive calls. This is specific to the HP28C/S calculators which have specific memory management.

Edited: 2 Apr 2011, 1:44 a.m.


#26

Ok. Here's a non-recursive, stack- and local vars-based implementation:

p:
\<< \-> n \<<
   0. 'n>180' {R\->I} IFT \-> zero \<< 
   0. \-> k \<< 
   n mkpents \-> pents \<<
   [0. 1. 1. 0.] \-> signs \<<
   {1} @ partitions; kept top-of-stack 
   1. n FOR j
      zero @ running sum
      1. 'k' STO
      WHILE
         pents k GET
         DUP @ for re-use next
         j \<= 
      REPEAT
         PICK3 j ROT - 1. + GET
         signs k 4. MOD 1. + GET {+} {-} IFTE
         1. 'k' STO+
      END
      DROP @ duped condition val
      + @ add to partitions
   NEXT
   n 1. + GET
\>>\>>\>>\>>\>>\>>

mkpents:
\<< DUP 1. + \v/ \-> n m \<<
   {1.}
   1. m FOR i
      i 3. * 1. + i * 2. /
      +
      i 3. * 2. + i 1. + * 2. /
      +
   NEXT
\>>\>>

As is, this will only run on HP-49, HP 50g or on ND1.

I *think* I'm using only two commands specific to those.

In order to make this run on HP-28S

- make the second line simply "0 \-> zero" (lacking bignums, I'm not sure how high you'll be able to go before results get wrong on the HP-28S)

- change PICK3 into "3 PICK"

Note, the code switches from using Reals to using Real Integers (bignums) for n>295. I've not tried it on a 50g. It may need a lesser number.

Run-time for p(200) is 7s on ND1. It's 16s, if I set the threshold to n>195 and force it to use bignums.


[EDIT: I changed the threshold value to 180, so this code gives an exact result on HP-49 and 50g, which have lower precision.]


Edited: 6 Apr 2011, 7:11 a.m. after one or more responses were posted


#27

I implemented recently proposed array and local operators in RPL+.

Here's the RPL+ version of the code above:

\<< =n
   0 'n>295' {R\->I} IFT =zero
   n mkpents2 =pents
   [0 1 1 0] =signs
   {1} =partitions
   1 n FOR j
      zero @ running sum
      1 =k
      WHILE
         j pents[k] - =:diff
         0 >=
      REPEAT
         partitions[diff]
           signs[k,4] {+} {-} IFTE
         ++k
      END
      =partitions[j]
   NEXT
   partitions[n]
\>>

Run-time for p(200) is 2.3s on ND1. It's 2.7s, if I set the threshold to n>195 and force it to use bignums.
That is, the speed gain for RPL+ is 300% and 700%, respectively.

I don't know how fast the RPL code in the previous post runs on a 50g. I'd love to get a result from someone who has one.
(I punched the code into HP-49G running on Emu48 on a Mac, and get 35.2s for p(200). Extrapolated from previous results, this suggest 2.5 to 5 minutes for 50g.)


Edited: 6 Apr 2011, 7:14 a.m.


#28

1 minute and 50.3 seconds (HP 50g)

<< 200 p >> TEVAL

-> 3972999029388
s:110.4585


#29

Nice.

Thank you, Gerson!

Over at comp.sys.hp48 someone posted a Sys RPL implementation that runs in 8s! I'm impressed at that gain thru Sys RPL.
I can't read Sys RPL. I wonder if he's doing anything cleverer algorithmically.
The implementation above could be improved by having the full sign array precomputed vs doing the circular buffer.

#30

After spending more time trying to understand the math (and learning and still failing--by a large shot) I sent email to Mr. Bruinier, congratulating and asking if they have an implementation that they could share, for any kind of math system or platform.

He kindly responded, and told me that they don't have complete code yet, and that he will give this task to a student as a thesis project.

Wow. What a surprise.


Speaking of slightly hard to read and surprising.

Can you believe that this piece of code computes p using the Euler method:

f=:[:(0<@-."1~>@{:)](,([:<@;(-i.)@#([,.(>:{."1)#])&.>]))@]^:[(<i.1 0)"_
Code Golfing for p()

I'm working on a 3rd language for ND1, which, I think, will allow an even shorter implementation (and be just as unreadable).


#31

Hi,
It’s true that this code is concise and not really easy readable by human eyes.

Actually it's not Golfing code, pas a true J code. J is a very terse array programming language, and is most suited to mathematical and statistical programming, especially when performing operations on matrices. J will certainly perfectly fit into the NT1 project.

And precisely, P is not computing the partition number p(n) but the partition itself.

     P =: [: (0 <@-."1~ >@{:) ] (, ([: <@; (- i.)@# ([ ,. (>: {."1) # ])&.> ]))@]^:[ (<i.1 0)"_

P 1
+-+
|1|
+-+
P 2
+-+---+
|2|1 1|
+-+---+
P 3
+-+---+-----+
|3|2 1|1 1 1|
+-+---+-----+
P 4
+-+---+---+-----+-------+
|4|3 1|2 2|2 1 1|1 1 1 1|
+-+---+---+-----+-------+
P 5
+-+---+---+-----+-----+-------+---------+
|5|4 1|3 2|3 1 1|2 2 1|2 1 1 1|1 1 1 1 1|
+-+---+---+-----+-----+-------+---------+

The useful # verb in J returns the size of an array, thus the correct J program to compute number of partitions p(n) is # P n.

   #P 1
1
#P 2
2
#P 3
3
#P 4
5
#P 5
7
#P 10
42
#P 50
204226
#P 100
|out of memory: P
| # P 100

As can be seen, despite its concise and terse syntax, this code has to draw all the partitions in order to count it. This is not as efficient or power full as it looks at first. On my system (2 Go RAM) draw all the 190569292 partitions of integer 100 seems to be impossible.

Here is a code to display any partition on a HP41C.

It use statistic fonctions + and - to add or remove element in the partition. This is a trick sparing a few instruction to maintain the sum of element (x) and the number of element in the current partition (n).

Usage

Enter the integer and press [EXQ][ALPHA]PART[ALPHA] to get the list of all the way to get this integer.
Press R/S key at each individual display to get the next one.

Example

7[EXQ]PART
"7 " [R/S]
"6+1 " [R/S]
"5+2 " [R/S]
"5+1+1 " [R/S]
"4+3 " [R/S]
"4+2+1 " [R/S]
"4+1+1+1 " [R/S]
"3+3+1 " [R/S]
"3+2+2 " [R/S]
"3+2+1+1 " [R/S]
"3+1+1+1+1 " [R/S]
"2+2+2+1 " [R/S]
"2+2+1+1+1 " [R/S]
"2+1+1+1+1+1 " [R/S]
"1+1+1+1+1+1+"
"+1+1+1+1+1+1" [R/S]
7.0000

Code for HP41C

01 LBL "PART
02 REG 31
03 CL
04 STO 00
05 FIX 0

06 LBL 01 @ ------------- Put value in the partition
07 +
08 LastX
09 STO IND 36
10 RCL 00
11 RCl 31 @ x
12 -
13 x=0?
14 GTO 02 @ Display partition
15 x>y?
16 RDN @ limit max of next value to previous one
17 GTO 01

18 LBL 02 @ ------------- Display partition
19 RCL 36 @ nb of value in partition (n)
20 1 E3
21 /
22 SF 01 @ Flag to add + between value
23 CLA @ clear alpha register
24 ISG X @ start with value 1.nnn

25 LBL 03 @ -------------- Put values in alpha register
26 FC?C 01
27 "~+ @ where ~ is the 'append' symbol
28 ARCL IND X
29 ISG X
30 GTO 03 @ loop until x is greater than n (R36)
31 AVIEW
32 STOP @ display partition wait for user R/S press

33 LBL 04 @ -------------- Decrease/remove last element
34 1
35 RCL IND 36
36 -
37 LastX @ remove last element
38 -
39 x<->y
40 CHS
41 x>0?
42 GTO 01 @ if element is one or bigger, put it in partition
43 RDN @ else put n top of stack
44 x>0?
45 GTO 04 @ if still an element in partition, decrease it by one
46 FIX 4
47 END @ of PART


Edited: 2 Apr 2011, 2:26 p.m. after one or more responses were posted


#32

Hi C.Ret.

Thanks for telling me what the J implementation did. It's so unreadable... I certainly missed that.

The language I'm working on for ND1 (really MorphEngine) is GolfScript. Even terser than J. And even better suited as it starts out as a stack-based language.
I morph it into RPL (you can even see the RPL result which makes it so much more readable...), which is byte-code compiled (in the future: morphed) into JavaScript. It will be interesting to see how its performance compares to the Ruby implementation.
And it'll be fun to play with those terse one-liners on-the-go.

I've not found a GolfScript implementation of p(n). If you come across one...


#33

If GolfScript / RPL interests you, you may wanna check out GolfScript/MorphEngine.

Edited: 3 Apr 2011, 8:04 a.m.


Possibly Related Threads...
Thread Author Replies Views Last Post
  OT--Found!!! An HP reference on 'The Big Bang Theory' Matt Agajanian 0 323 11-08-2013, 10:23 PM
Last Post: Matt Agajanian
  OT--Discovery Channel bio on Evel Kneivel Matt Agajanian 2 327 10-15-2013, 01:05 PM
Last Post: Matt Agajanian
  OT--'The Big Bang Theory' and RPN/HP--Any connections? Matt Agajanian 19 1,443 09-05-2013, 08:27 AM
Last Post: Adrien Bertrand
  HP 50g: Major updates for MLP / OSE / HLP released Software49g 2 412 04-15-2013, 04:49 AM
Last Post: Michael Lopez
  (OT) Discovery over DC David Tellet 9 820 04-20-2012, 01:24 PM
Last Post: Richard Ottosen (Denver)
  OT: "The Big Bang Theory" actress visits the Datamath Calculator Museum Joerg Woerner 8 761 03-07-2012, 03:15 AM
Last Post: Johnny Bjoern Rasmussen
  WP 34S - major changes! Marcus von Cube, Germany 18 1,123 07-18-2011, 01:45 PM
Last Post: Marcus von Cube, Germany
  Inefficient Market Theory for the HP collector Mike Ingle 4 462 06-23-2007, 01:02 PM
Last Post: Seth Morabito
  MAJOR RESULT DISCREPANCY; 50g vs. 41CX Edward J Pec 5 476 03-06-2007, 10:09 AM
Last Post: Palmer O. Hanson, Jr.
  Translate TI-59 programs to HP-67/97 Paul 7 427 05-23-2005, 02:31 AM
Last Post: Palmer O. Hanson, Jr.

Forum Jump: