HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's & 0's

[Albert Chan]

(01-25-2020 05:39 AM)Gerald H Wrote:  

(01-24-2020 11:48 PM)Albert Chan Wrote:  All positive integer N that can be interpreted as valid binary gives minimal P/N = 1

Example: N=1, 10, 11, 100, 101 ...

A quick solution for an infinite number of integers, leaving an infinite number still unresolved.

Please supply algorithm (programme) to effect your partial solution.

Oh, I see. "minimal P/N" meant min(P)/N, not min(P/N)

Sorry, I don't know HP-49G. Algorithm (not optimized) is like this:

Code:

f = lambda n: n if n<2 else 10*f(n>>1) + (n&1)

def p(n, mod=0, t=1, step=1):
    while f(t)%n != mod: t += step
    return f(t)

>>> p(85)
111010
>>> 111010 / 85
1306.0

Note: options to p(n) allowed some optimizations.
p(n that can be intepreted as valid binary) = n
Remove n trailing 0's: p(10k) = 10 * p(k) ; must be removed first
Remove n trailing 5's: p(10k + 5) = 10 * p(2k+1)
Remove even n's      : p(2k) = 10 * p(k)

What is left is n mod 10 = 1,3,7,9 → p(n) must be odd → step = 2 is ok

>>> 10 * p(17, step=2) # = p(85)
111010