Mini-challenge: MAX(factors of 2 or 5)

[Joe Horn]

(01-17-2018 04:49 AM)Thomas Okken Wrote:  I'm a bit conflicted about this challenge because what's mathematically elegant and what's RPL-ically elegant are probably quite different.

Quite right. Several brute-force routines have been suggested, performing trial divisions one at a time and counting them. This works but is terribly slow for large inputs. For example, Gerald's User RPL program takes 25 times longer than mine (in the OP) on an input of 10^50 (exact integer). This is no doubt because looping in User RPL is much slower than the FACTORS command.

Quote:... why find the complete prime factorization when all you want is the multiplicity of two specific factors? ... Also, the FACTORS approach fails if the factors you're looking at happen not to be primes.

Agreed. FACTORS is pretty fast, but it's overkill, and fails if you're looking for composites. But brute-force looping and tallying trial divisions is terribly slow. Isn't there a way to avoid all that looping?

Here's one idea that's haunting me: Instead of doing MOD(X, 2) repeatedly, how about doing GCD(X, 2^10) repeatedly? That could be used to chop off 10 powers of 2 at a time (until none are left), instead of just one at a time.

It's reminiscent of the old 'COTENS' program ('Cast Out TENS') which takes any integer and discards any factors of 2 or 5 from it:

<< WHILE DUP 1000000000000 GCD DUP 1 > REPEAT / END DROP >>

Example:
Input: 1500000000000000000
Output: 3

It's very fast because it discards up to twelve 2's and up to twelve 5's in every iteration. But I'm not sure how to tally the factors.

Darn... my brain just ran out of caffeine and I must go to bed.