Post Reply 
50g Mini-Challenge: Number of positive divisors of x!
09-29-2017, 11:49 PM
Post: #1
50g Mini-Challenge: Number of positive divisors of x!
The HP 50g program << ! DIVIS SIZE >> returns the number of positive divisors of the input factorial. However, this brute-force program becomes impossibly slow for medium-sized inputs, and runs out of memory for any input that's interestingly large. Just look how this slows down:

<< 12 ! DIVIS SIZE >> returns 792 in 6.1 seconds
<< 13 ! DIVIS SIZE >> returns 1584 in 17.5 seconds
<< 14 ! DIVIS SIZE >> returns 2592 in 39.3 seconds
<< 15 ! DIVIS SIZE >> returns 4032 in 86.2 seconds!

(Unrelated note: Prime's CAS returns 4032 for size(idivis(15!)) in 0.7 seconds)

The winner of this challenge will be the 49G/49g+/50g RPL program that returns the exact number of positive divisors of X! the fastest. Testing will focus on large inputs.

Although half the fun of this challenge will consist in thinking up different ways of doing it (obviously avoiding the factorial and DIVIS functions), some algorithmic hints can be found here if you totally get stuck: https://oeis.org/A027423

Many thanks to Gerald H for his many OEIS-related postings and programs which inspired this mini-challenge.

<0|ΙΈ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
50g Mini-Challenge: Number of positive divisors of x! - Joe Horn - 09-29-2017 11:49 PM



User(s) browsing this thread: 1 Guest(s)