HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's & 0's
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,611 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[0] in '139' and x.count(x[0]) == len(x):         return 10**((ord(x[0])-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
 « Next Oldest | Next Newest »

 Messages In This Thread HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's & 0's - Gerald H - 01-24-2020, 04:06 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - ijabbott - 01-24-2020, 08:48 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Gerald H - 01-25-2020, 05:37 AM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Albert Chan - 01-24-2020, 11:48 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Gerald H - 01-25-2020, 05:39 AM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Albert Chan - 01-25-2020, 02:12 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - John Keith - 01-25-2020, 05:58 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Albert Chan - 01-25-2020, 11:50 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Albert Chan - 01-27-2020 04:11 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Albert Chan - 01-28-2020, 12:13 AM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - John Keith - 01-27-2020, 08:09 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Gerald H - 01-29-2020, 07:25 AM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Albert Chan - 01-30-2020, 12:18 AM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - John Keith - 01-30-2020, 07:33 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Gerald H - 01-29-2020, 11:18 AM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Albert Chan - 01-29-2020, 01:58 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Gerald H - 01-29-2020, 03:12 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Albert Chan - 01-29-2020, 03:22 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Gerald H - 01-29-2020, 03:37 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Gerald H - 01-30-2020, 08:32 PM RE: HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's &... - Gerald H - 01-31-2020, 08:01 AM

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