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

01252020, 11:50 PM
Post: #8




RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01252020 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. 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 

« Next Oldest  Next Newest »

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