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

[Albert Chan]

(01-29-2020 11:18 AM)Gerald H Wrote:  For input

123456789

a real 49G returns

1111111101

in

6.8 sec.

Since N is odd, not divisible by 5, we know P last digit is 1

P = 123456789 M ≡ -M ≡ 1 (mod 10)
M ≡ -1 ≡ 9 (mod 10)

123456789 * 9 = 1111111101

Another example, P(17) is not as lucky, but still not too bad:

P = 17 M ≡ -3 M ≡ 1 (mod 10)
M ≡ 1/-3 ≡ -9/-3 ≡ 3 (mod 10)

17 * 3 = 51
17 * 13 = 221, 1001/17 ≈ 58.88
17 * 63 = 1071
17 * 73 = 1241, 10001/17 ≈ 588.29
17 * 593 = 10081
17 * 603 = 10251, 11001/17 ≈ 647.12
17 * 653 = 11101

We could also try P(17) that ends in 01 vs 11, and pick the smaller P:

P = 17*M ≡ 1 or 11 (mod 100)

Using my InverseMod trick:

1
2     -floor(1/2*15) = -7, 15*17=255 > 100
15
17     --floor(-7/15*100) = -47 = 17^-1 (mod 100)
100

M ≡ (1 or 11)/17 ≡ (1 or 11)*(-47) ≡ 53 or 83 (mod 100)

17 * 53 = 901
17 * 83 = 1411, 10001/17 ≈ 588.29
17 * 653 = 11101