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
 Gerald H Senior Member Posts: 1,598 Joined: May 2014
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 ijabbott Senior Member Posts: 1,229 Joined: Jul 2015
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
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
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:

https://oeis.org/A004290

The challenge is to write an HP 49G programme to find minimal P/N.

Fastest unerring programme wins.

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
 Gerald H Senior Member Posts: 1,598 Joined: May 2014
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...
(01-24-2020 08:48 PM)ijabbott Wrote:  In base 10, presumably? The math is trivial for base 2!

Yes, in base 10, sorry for the omission.
01-25-2020, 05:39 AM (This post was last modified: 01-25-2020 05:41 AM by Gerald H.)
Post: #5
 Gerald H Senior Member Posts: 1,598 Joined: May 2014
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:

https://oeis.org/A004290

The challenge is to write an HP 49G programme to find minimal P/N.

Fastest unerring programme wins.

All positive integer N that can be interpreted as valid binary gives minimal P/N = 1

Example: N=1, 10, 11, 100, 101 ...

A quick solution for an infinite number of integers, leaving an infinite number still unresolved.

01-25-2020, 02:12 PM (This post was last modified: 01-26-2020 11:10 PM by Albert Chan.)
Post: #6
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
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

Example: N=1, 10, 11, 100, 101 ...

A quick solution for an infinite number of integers, leaving an infinite number still unresolved.

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) def p(n, mod=0, t=1, step=1):     while f(t)%n != mod: t += step     return f(t)

>>> 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 John Keith Senior Member Posts: 884 Joined: Dec 2013
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:
 @ spoiler alert! \<< PUSH BIN I\->R \-> n   \<< 0. 1. 2. n     FOR k 1. 4095.       FOR m m R\->B \->STR 3. OVER SIZE 1. - SUB OBJ\-> DUP k MOD         IF NOT         THEN 4096. 'm' STO         ELSE DROP         END       NEXT     NEXT n 1. + \->LIST POP   \>> \>>
01-25-2020, 11:50 PM
Post: #8
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
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.
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
01-27-2020, 04:11 PM (This post was last modified: 01-29-2020 12:29 PM by Albert Chan.)
Post: #9
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
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):

>>> 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
...

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,      1000,1001,1010,1011,1100,1101,1110,1111] def p(n, oddp=oddp, k=1):     if n<2: return n     while n%5==0: k *= 10; n //= 10-5*(n&1)     while n&1==0: k *= 10; n >>= 1     x = str(n)                  # n%10 = 1,3,7,9     if x in '139' and x.count(x) == len(x):         return 10**((ord(x)-48)*len(x)) // 9 * k     return oddp(n) * k

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     h1 = [ -hd[i] % n for i in range(1,16,2)]     h2 = [10000*x % n for x in hd]     h3 = [10000*x % n for x in h2]     bad = {}     while 1:         for m3 in h3:           # mods of 3rd 'hex digit'             m4 = m3 + mod       # adjust for p(n) trillions             for m2 in h2:       # mods of 2nd 'hex digit'                 if (m4+m2)%n not in h1: continue                 p = ( hd[h1.index((m4+m2)%n)*2+1]                     + 10000*(hd[h2.index(m2)]                     + 10000*(hd[h3.index(m3)])))                 if td: p += td                 return p        # note: p is odd         bad[mod] = 1         while 1:             t += 1             td = int(bin(t)[2:]) * 10**12             mod = int(td % n)             if mod not in bad: break

>>> p(12345) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ # = oddp(12345 // 5) * 10
11000111010L

>>> p(123456) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿# = oddp(123456 >> 6) * 10**6
1110110100111000000L
01-27-2020, 08:09 PM
Post: #10 John Keith Senior Member Posts: 884 Joined: Dec 2013
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
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
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] hd = hd + [1000+x for x in hd] hd = hd + [10000+x for x in hd] hd = hd + [100000+x for x in hd] def bdec(x):     if x<64: return hd[x]     return hd[x&63] + bdec(x>>6) * 1000000 def oddp(n, t=0, td=0, mod=0):     m = n >> 1                  # assumed n is odd     while m % 5: m += n         # loop upto 4 times     m = m//5                    # = -1/10 (mod n)     h1 = dict(((m-x)%n, x) for x in reversed(hd))     m = 1000000%n     h2 = [m*x%n for x in hd]     bad = {}     while 1:                    # assumed n%10 = 1,3,7,9         for m2 in h2:             if (m2+mod)%n not in h1: continue             m = h1[(m2+mod)%n] + 1000000*hd[h2.index(m2)]             if td: m += td             return 10*m+1         bad[mod] = 1         while 1:             t += 1             td = bdec(t) * 10**12             mod = int(td % n)             if mod not in bad: break def p(n, oddp=oddp, k=1):       # 2nd arg can use minmulzo     if n<2: return n     while n%5==0: k *= 10; n //= 10-5*(n&1)     while n&1==0: k *= 10; n >>= 1     x = str(n)                  # n%10 = 1,3,7,9     if x in '139' and x.count(x) == len(x):         return 10**((ord(x)-48)*len(x)) // 9 * k     return k * oddp(n)

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
 Gerald H Senior Member Posts: 1,598 Joined: May 2014
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:
 A4290 ::   CK1&Dispatch   # FF   ::     " MIN K*N ONLY 1'S & 0'S CF A79339"     DispCoord1     SetDA3Temp     ::       FPTR2 ^PUSHFLAGS_       DOBIN       BINT64       dostws       DUP       FPTR2 ^Z>S       BINT2       ZERO_DO       INDEX@       #>$NULL$       FPTR F 1A       DROPLOOP       NULL$? ?SEMI FPTR2 ^ZTrialDiv2 BINT0 ROT BEGIN DUP ZINT 5 FPTR2 ^ZDIVext ZINT 0 EQUAL WHILE :: SWAPDROPSWAP #1+SWAP ; REPEAT DROPDUP FPTR2 ^Z>S "9" NULL$       FPTR F 1A       OVER       NULL$? ITE :: ROTDROP COERCE BINT9 #* ZERO_DO CHR_1 >H$         LOOP         FPTR2 ^S>Z       ;       ::         2DROP         DUP         ZINT 1         EQUAL         ?SEMI         ZINT 10         OVER         PTR 2F3A3         COERCE         FPTR2 ^RP#         FPTR2 ^Z>S         "# "         SWAP&$"b" &$         DOSTR>         HXS 00001 1         bit-         BINT0         BEGIN         DROP         HXS 00001 2         bit+         DUP         hxs>$BINT3 LAST$         FPTR2 ^S>Z         DUP         4PICK         FPTR2 ^ZMod         ZINT 0         EQUAL         UNTIL         ROTROT2DROP       ;       ZINT 10       2SWAP       #MAX       FPTR2 ^RP#       FPTR2 ^RMULText     ;     FPTR2 ^POPFLAGS_   ; ;
01-29-2020, 11:18 AM
Post: #13
 Gerald H Senior Member Posts: 1,598 Joined: May 2014
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
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
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

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
01-29-2020, 03:12 PM (This post was last modified: 01-29-2020 03:14 PM by Gerald H.)
Post: #15
 Gerald H Senior Member Posts: 1,598 Joined: May 2014
RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &...

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
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
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
 Gerald H Senior Member Posts: 1,598 Joined: May 2014
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
 Albert Chan Senior Member Posts: 2,142 Joined: Jul 2018
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) :     if n<2 : return n     pfrem = [n] * n     pfrem = 0                # p%n=1 -> p = 1     m, i = 1, b%n     while pfrem == n:        # p%n=0 -> p < 10**n         for r in xrange(1,n) :             if pfrem[r] >= m: continue             if pfrem[r+i-n] == n: pfrem[r+i-n] = m         if pfrem[i] == n: pfrem[i] = m         i = b*i % n         m = m + 1     res = r = 0     while 1:         m = b**pfrem[r]         r = (r-m) % n         res += m         if not r: return res
01-30-2020, 07:33 PM
Post: #19 John Keith Senior Member Posts: 884 Joined: Dec 2013
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
 Gerald H Senior Member Posts: 1,598 Joined: May 2014
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 CkSum: # 5EABh ::   CK1&Dispatch   # FF   ::     " MIN K*N ONLY 1'S & 0'S CF A79339"     DispCoord1     SetDA3Temp     ::       FPTR2 ^PUSHFLAGS_       DOBIN       BINT64       dostws       DUP       FPTR2 ^Z>S       BINT2       ZERO_DO       INDEX@       #>$NULL$       FPTR F 1A       DROPLOOP       NULL$? casedrop ZINT 1 FPTR2 ^ZTrialDiv2 BINT0 ROT BEGIN DUP ZINT 5 FPTR2 ^ZDIVext ZINT 0 EQUAL WHILE :: SWAPDROPSWAP #1+SWAP ; REPEAT DROPDUP FPTR2 ^Z>S "9" NULL$       FPTR F 1A       OVER       NULL$? ITE :: ROTDROP COERCE BINT9 #* ZERO_DO CHR_1 >H$         LOOP         FPTR2 ^S>Z       ;       ::         2DROP         DUP         ZINT 1         EQUAL         ?SEMI         %2         OVER         PTR 2F3A3         %^         %>#         HXS 00001 1         bit-         BINT0         BEGIN         DROP         HXS 00001 2         bit+         DUP         hxs>$BINT3 LAST$         FPTR2 ^S>Z         DUP         4PICK         FPTR2 ^ZMod         ZINT 0         EQUAL         UNTIL         ROTROT2DROP       ;       ZINT 10       2SWAP       #MAX       FPTR2 ^RP#       FPTR2 ^RMULText     ;     FPTR2 ^POPFLAGS_   ; ;
 « Next Oldest | Next Newest »

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