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:58 PM)John Keith Wrote:  Chai Wah Wu's Python program from the OEIS page and it returned A(99) in less than one second.
I then tried A(9990) on the Python program and it took over 15 minutes to complete.

You could try the sage code, which is also a valid Python code if "^" replaced as "**"

>>> minmulzo(999) * 10     # = p(9990)
1111111111111111111111111110

Above finished in my old Pentium 3 in under 0.1 second
Roughly, this is why above is so fast.

Since N=9990, P must also end in 0, since N divides P.
If N is odd (but not end in 5's, see my post), P must also be odd
To minimize P, we multiply by only a ten, to add a zero to P.
This optimization speedup the already fast minmulzo() by 4X

Instead of doing all the unnecessary base conversions, it build a list of mod values.
The program loops thru the combinations of sum of mods, looking for multiples of N.
Here is what each "bit" contribute to the mod value, for P(999):

>>> for i in range(21): print i, pow(10,i,999)
...
0 1
1 10
2 100
3 1
4 10
5 100
6 1
7 10
8 100
...

Above repeating pattern, P(999) required 27 1's, to have sum of mods = 9*111 = 999 = N