HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's & 0's
|
01-24-2020, 04:06 PM
(This post was last modified: 01-25-2020 05:43 AM by Gerald H.)
Post: #1
|
|||
|
|||
HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's & 0's
Surprisingly (?) every integer N is a factor of an integer P consisting solely of 1's & 0's, for the smallest N the values of P are given here:
https://oeis.org/A004290 The challenge is to write an HP 49G programme to find minimal P/N. Fastest unerring programme wins. |
|||
01-24-2020, 08:48 PM
(This post was last modified: 01-24-2020 08:49 PM by ijabbott.)
Post: #2
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
In base 10, presumably? The math is trivial for base 2!
— Ian Abbott |
|||
01-24-2020, 11:48 PM
(This post was last modified: 01-24-2020 11:56 PM by Albert Chan.)
Post: #3
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01-24-2020 04:06 PM)Gerald H Wrote: Surprisingly (?) every integer N is a factor of a integer P consisting solely of 1's & 0's, for the smallest N the values of P are given here: All positive integer N that can be interpreted as valid binary gives minimal P/N = 1 Example: N=1, 10, 11, 100, 101 ... |
|||
01-25-2020, 05:37 AM
Post: #4
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... | |||
01-25-2020, 05:39 AM
(This post was last modified: 01-25-2020 05:41 AM by Gerald H.)
Post: #5
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01-24-2020 11:48 PM)Albert Chan Wrote:(01-24-2020 04:06 PM)Gerald H Wrote: Surprisingly (?) every integer N is a factor of a integer P consisting solely of 1's & 0's, for the smallest N the values of P are given here: A quick solution for an infinite number of integers, leaving an infinite number still unresolved. Please supply algorithm (programme) to effect your partial solution. |
|||
01-25-2020, 02:12 PM
(This post was last modified: 01-26-2020 11:10 PM by Albert Chan.)
Post: #6
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(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 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) >>> 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 |
|||
01-25-2020, 05:58 PM
(This post was last modified: 01-25-2020 07:28 PM by John Keith.)
Post: #7
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
Hi Gerald,
Thanks for posting this intriguing challenge. Here is my attempt which returns a list of A004290(n) from 0 to n. It will only work on numbers up to 98 because A(99) has more than 12 digits. I opted to use approximate numbers because MOD is slow for exact integers and R->B is limited to 12 digits anyway. The program is still not very fast, taking almost 10 minutes for an input of 98. It could be extended to larger input values with exact integers and some ListExt commands but it would be slower still. Update: I tried an exact integer version for A(99) and it ran for over 10 minutes on EMU48 without completing. I don't think that my program is incorrect since it worked on smaller numbers. I then ran 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. I therefor conclude that numbers above 98 are impractical on the HP49/50 without a faster algorithm. Code:
|
|||
01-25-2020, 11:50 PM
Post: #8
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(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. 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 |
|||
01-27-2020, 04:11 PM
(This post was last modified: 01-29-2020 12:29 PM by Albert Chan.)
Post: #9
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01-25-2020 11:50 PM)Albert Chan Wrote: Here is what each "bit" contribute to the mod value, for P(999): We have the same "bit" contribution pattern for N = 333, 111 p(111) = (101*3-1)/9 = 111 p(333) = (103*3-1)/9 = 111111111 p(999) = (109*3-1)/9 = 111111111111111111111111111 We can pull this pattern out as special case, and reduce the combinatorial search. I got an OK from Gerald for posting this fast p(n) Python code. For my old Pentium 3, time for p(n = 0 to 9999) in 21 seconds (4 seconds for my laptop) Code: hd = [ 0, 1, 10, 11, 100, 101, 110, 111, oddp(n) search in chunks for 3 'hex digits' (12 decimal digits) at a time. Since returned p is odd, we only need to check 16×16×8 = 2048 cases / 3 'hex digits' Code: def oddp(n, t=0, td=0, mod=0): # assumed n%10 = 1,3,7,9 >>> p(12345) # = oddp(12345 // 5) * 10 11000111010L >>> p(123456) # = oddp(123456 >> 6) * 10**6 1110110100111000000L |
|||
01-27-2020, 08:09 PM
Post: #10
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
That's fast code alright, Albert!
Now, to translate to RPL. Hmmm... |
|||
01-28-2020, 12:13 AM
(This post was last modified: 02-01-2020 10:55 PM by Albert Chan.)
Post: #11
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01-27-2020 04:11 PM)Albert Chan Wrote: For my old Pentium 3, time for p(n = 0 to 9999) in 21 seconds (4 seconds for my laptop) To take advantage of Python's O(1) dictionary lookup, here is p(n) dict() based version. Timings for p(n = 0 to 9999) reduced to Pentium3 = 8.1 s., Laptop = 1.5 s. (≈ 2.5X speed) Code: hd = [0,1,10,11,100,101,110,111] Update: new algorithm, odd p = 10m+1, solve for m ≡ -1/10 (mod n), return 10m+1 Timings for p(n = 0 to 9999) improved to Pentium3 = 4.8 s., Laptop = 0.9 s. |
|||
01-29-2020, 07:25 AM
(This post was last modified: 01-29-2020 07:35 AM by Gerald H.)
Post: #12
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
Here my attempt for the 49G, incorporating insights of Albert Chan (as best I could).
Execution time remains lamentably high, improvements expected. A non-brute force algorithm would be very useful. Name of programme: A4290 Both FPTR F 1A is internal SREPL PTR 2F3A3 is internal SIZE for integers stable from 1.19-6 to 2.10-8. Size: 386.5 CkSum: #3E4Dh Code:
|
|||
01-29-2020, 11:18 AM
Post: #13
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
For input
123456789 a real 49G returns 1111111101 in 6.8 sec. |
|||
01-29-2020, 01:58 PM
Post: #14
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01-29-2020 11:18 AM)Gerald H Wrote: For input 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 |
|||
01-29-2020, 03:12 PM
(This post was last modified: 01-29-2020 03:14 PM by Gerald H.)
Post: #15
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
Albert, can you please try your programme on
2,470,747 to see how long it takes to get computed? |
|||
01-29-2020, 03:22 PM
(This post was last modified: 01-29-2020 03:48 PM by Albert Chan.)
Post: #16
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
p(2470747) = 110,101,011,111,111,011,101
0.027 seconds for my old Pentium 3 |
|||
01-29-2020, 03:37 PM
Post: #17
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
For
2470747 Emu 48 with 49G Rom 2.10-7 on my computer with processor Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz returns the same answer as yours in 76 sec. |
|||
01-30-2020, 12:18 AM
(This post was last modified: 01-30-2020 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 &...
(01-29-2020 07:25 AM)Gerald H Wrote: A non-brute force algorithm would be very useful. Sage code is non-brute 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) : |
|||
01-30-2020, 07:33 PM
Post: #19
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01-30-2020 12:18 AM)Albert Chan Wrote: The problem is above required N item list, which may be huge, and takes time to build. That would be a problem for the HP49 due to limited memory. The largest practical list is around 5000 - 10000 items depending on size of numbers and the amount of free memory in the calculator. I think GeraldH's time for 2470747 would be hard to beat. |
|||
01-30-2020, 08:32 PM
Post: #20
|
|||
|
|||
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
A slightly improved version of A4290, smaller & faster:
Code: Size: 358.5 |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: