(50g) User-RPL Number Theory routines that avoid DIVIS

[Joe Horn]

How to Avoid DIVIS in HP49/50 User-RPL Number Theory Programs
by Joe Horn (originally posted on comp.sys.hp48 on 2010-08-05)

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 faster than they would be if they used DIVIS.

The names of these programs are the standard names used in Number Theory.

\Gt (τ) -- How many divisors does X have?
\Gs (σ) -- The sum of ALL the divisors of X
\Gs0 (σ0) -- 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 (Πd) -- Product of all the divisors of X

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

%%HP: T(3);
@ \Gt, 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! \Gt --> 4032 in 0.21 seconds
15! DIVIS SIZE --> same answer in 82.96 seconds

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

%%HP: T(3)F(.);
@ \Gs, 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! \Gs --> 6686252969760 in 0.42 seconds
15! DIVIS \GSLIST --> same answer in 92.81 seconds

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

%%HP: T(3);
@ \Gs0, by Joe Horn
@ Sum of the PROPER divisors of X
\<< DUP \Gs SWAP -
\>>

Input: Integer > 1
Output: Sum of its divisors without X
(same as DUP DIVIS \GSLIST SWAP - but much faster)

Example: 15! \Gs0 --> 5378578601760 in 0.42 seconds
15! DUP DIVIS \GSLIST SWAP - --> same answer in 92.81 seconds

Note: \Gs0 calls the \Gs program, listed above.

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

%%HP: T(3);
@ Ad, by Joe Horn
@ Algebraic Mean of all the divisors of X
\<< DUP \Gs SWAP \Gt /
\>>

Input: Integer > 1
Output: Average of all its divisors
(same as DIVIS DUP \GSLIST SWAP SIZE / but much faster)

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 \Gs and \Gt 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 --> 212889600/269971 in 0.82 seconds

Note: Hd calls the Ad program, listed above.

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

%%HP: T(3);
@ \PId, by Joe Horn
@ Product of all the divisors of X
\<< DUP \Gt 2 / ^
\>>

Input: Integer > 1
Output: Product of all its divisors
(same as DIVIS \PILIST but much faster)

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 \Gt program, listed above.