Avoid DIVIS in some URPL number theory functions
Joe Horn
by Joe Horn
Some number theory functions are defined in terms of the divisors of
X. But the DIVIS function in RPL is slow. Here are six User-RPL
number theory functions that avoid DIVIS and are therefore very fast.
TAU -- How many divisors does X have?
SIG -- The sum of ALL the divisors of X
SIG0 -- The sum of the PROPER divisors of X
Ad -- Algebraic Mean of the divisors of X
Hd -- Harmonic Mean of the divisors of X
PId -- Product of all the divisors of X
-------------------------------------------------
%%HP: T(3);
@ TAU, by Joe Horn
@ Number of divisors of X
\<< \-> n
\<< n XQ FACTORS R\->I 1 + OBJ\-> # 1h SWAP # 2h /
START SWAP 1 + * NIP
NEXT
\>>
\>>
Input: Integer > 1
Output: Number of divisors of X
(same as DIVIS SIZE but much faster)
Example: 15! TAU --> 4032 in 0.21 seconds
15! DIVIS SIZE --> same answer in 82.96 seconds
-------------------------------------------------
%%HP: T(3)F(.);
@ SIG, by Joe Horn
@ Sum of ALL the divisors of X
\<< \-> n
\<< n XQ FACTORS R\->I 1 + OBJ\-> 1. SWAP 2. / IP
START PICK3 ROT 1 + ^ 1 - ROT 1 - / *
NEXT
\>>
\>>
Input: Integer > 1
Output: Sum of all its divisors
(same as DIVIS \GSLIST but much faster)
Example: 15! SIG --> 6686252969760 in 0.42 seconds
15! DIVIS \GSLIST --> same answer in 92.81 seconds
-------------------------------------------------
%%HP: T(3);
@ SIG0, by Joe Horn
@ Sum of the PROPER divisors of X
\<< DUP SIG SWAP -
\>>
Input: Integer > 1
Output: Sum of its divisors without X
(same as DUP DIVIS \GSLIST SWAP - but much faster)
Example: 15! SIG0 --> 5378578601760 in 0.42 seconds
15! DUP DIVIS \GSLIST SWAP - --> same answer in 92.81 seconds
Note: SIG0 calls the SIG program, listed above.
-------------------------------------------------
%%HP: T(3);
@ Ad, by Joe Horn
@ Algebraic Mean of all the divisors of X
\<< DUP SIG SWAP TAU /
\>>
Input: Integer > 1
Output: Average of all its divisors
(same as DIVIS DUP \GSLIST SWAP SIZE / )
Example: 15! Ad --> 3316593735/2 in 0.64 seconds
15! DIVIS DUP \GSLIST SWAP SIZE / --> same answer in 95.75 seconds
Note: Ad calls the SIG and TAU programs, listed above.
-------------------------------------------------
%%HP: T(3);
@ Hd, by Joe Horn
@ Harmonic Mean of all the divisors of X
\<< DUP Ad / EVAL
\>>
Input: Integer > 1
Output: Exact harmonic mean of all its divisors
Example: 15! Hd --> 3316593735/2 in 0.64 seconds
Note: Hd calls the Ad program, listed above.
-------------------------------------------------
%%HP: T(3);
@ PId, by Joe Horn
@ Product of all the divisors of X
\<< DUP TAU 2 / ^
\>>
Input: Integer > 1
Output: Product of all its divisors
(same as DIVIS \PILIST
Example: 11! PId --> Huge integer (approx 2.05E2052) in 9.11 seconds
11! DIVIS \PILIST --> Same answer in 31.84 seconds
Note: PId calls the TAU program, listed above.