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

01302020, 12:18 AM
(This post was last modified: 01302020 07:03 PM by Albert Chan.)
Post: #18




RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01292020 07:25 AM)Gerald H Wrote: A nonbrute force algorithm would be very useful. Sage code is nonbrute force. It generated a list of mod restricted possibilities. Time complexity = O(N log(P)) Example, for p(7), it produced a list, pfrem = [3, 0, 2, 1, 1, 2, 2]. This list, in modulo 7, meant this: 1??? ≡ 0 1 ≡ 1 1?? ≡ 2 1? ≡ 3 1? ≡ 4 1?? ≡ 5 1?? ≡ 6 ? is either 0 or 1, not yet determined. We can solve for P: P = 1??? ≡ 0 (mod 7) ??? ≡ 1000 ≡ 1 (mod 7) From the list, 1 ≡ 1 → ??? = 001 → P(7) = 1001 The problem is above required N item list, which may be huge, and takes time to build. The code shines if N is small, but P is big. Example: >>> minmulzo(142857) 1010001010001110001110101110101110111111111L Above finished on my Pentium3 in 3.6 seconds. Brute force, oddp(142857) would take about 10 hours. Code: def minmulzo(n, b=10) : 

« Next Oldest  Next Newest »

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