Post Reply 
Programming puzzle: Longest list of regular numbers?
04-17-2017, 02:10 PM
Post: #13
RE: Programming puzzle: Longest list of regular numbers?
(04-17-2017 12:28 PM)e_emil Wrote:  I read the wikipedia page on Hamming numbers and it appears that they use a very similar geometric approach to estimate the number of regular numbers not greater than N: the inequality (ln 2)x + (ln 3)y + (ln 5)z <= ln N is satisfied by all regular numbers that are less or equal than N (assumming that a number of the form 2^x3^y5^z corresponds to the point (x,y,z)), which is the same idea that I used in the algorithm Wink

Yes the fastest algorithm known (but I do like yours more, what about putting it in the talk page? So maybe it will be included one day) is quite smart but it requires a good memory management, indeed on /r/dailyprogrammer the problem for many was to use a proper data structure.

Quote:Time: 4 minutes 20 seconds on the nSpire CX CAS, using a modification of my previous program (calculating but not storing intermediate results). Had to switch to the "exact" mode, because the numbers already have 17 digits. The greatest power of two smaller than H(9733) is 2^57, so "smax" has to be 57 or more.

Well done and yes, I chose a "big enough" number (well I was unsure at first) to push the mathematical environment to handle integers bigger than the canonical 32 or 64 bits or 10-15 digits.

I would be really interested in RPN programmable calculators, prime and so on.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Programming puzzle: Longest list of regular numbers? - pier4r - 04-17-2017 02:10 PM



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