(02-15-2020 02:14 PM)Albert Chan Wrote: [ -> ]Using unique_permute() code from post #9, ignoring 1-digit scramble primes, below proved that
scramble primes are either repunit (all 1's), or XXXXXX ... Y (X=1,3,7,9. *only* 1 Y ≠ X)
We can rewrite XXXXX...Y as X*(11111...) + (Y-X) = XR + (Y-X)
Modulo 7:
I = 1 10 100 1000 10000 100000 1000000 ... ≡ 1 3 2 6 4 5 1 ...
R = 1 11 111 1111 11111 111111 1111111 ... ≡ 1 4 6 5 2
0 1 ...
Note that both sequence have period of 6, and 6k digits repunit always divisible by 3 and 7.
Also, if k not divisible by 7, k×I will also hit mod7 of 1 to 6 (albeit in different order), and never hit 0.
Example, 2×I = 2×(1 3 2 6 4 5 1 ...) ≡ 2 6 4 5 1 3 2 ...
Letting Y-X = k, this implied XR must be divisible by 7
Otherwise, with 6 (or more) digits R, XR+(Y-X) will have some permutations divisible by 7
For X=1,3,9, removing patterns divisible by 3 and 7, we have:
1*R(6k) + [2,8]
3*R(6k) + [-2,4]
9*R(6k) + [-8,-2]
For X=7, XR always divisible by 7. We can only apply mod3 sieve
7*R(3k+0) + [-4,2]
7*R(3k+1) + [-6,4]
7*R(3k+2) + [-6,2]
Combined, we can search scramble primes of form XXXXX...Y, 6 digits at a time
Code:
from gmpy2 import is_prime
def check_permutations(n, x, offset):
for k in offset:
k0 = k
for i in xrange(n): # permutations to check
if not is_prime(x+k): break
k *= 10 # shift to permute
else: print x+k0 # scramble prime found
def XXXXXY(k):
'check 6k to 6k+5 digits patterns that have no factor 3 or 7, k>0'
n = 6*k
r = 10**n//9 # 6k digits repunit
check_permutations(n, r, [2,8])
check_permutations(n, 3*r, [-2,4])
check_permutations(n, 7*r, [-4,2])
check_permutations(n, 9*r, [-8,-2])
r = 70*r+7; check_permutations(n+1, r, [-6,4])
r = 10*r+7; check_permutations(n+2, r, [-6,2])
r = 10*r+7; check_permutations(n+3, r, [-4,2])
r = 10*r+7; check_permutations(n+4, r, [-6,4])
r = 10*r+7; check_permutations(n+5, r, [-6,2])
>>> for k in xrange(1,200): print k,XXXXXY(k)
1 None
2 None
3 None
...
198 None
199 None
This showed that, ignoring repunit, there is no scramble primes between 6 to 1199 digits !
Considering how rare to hit
repunit primes, this make sense ...
Update: I should have skip the mod 7 test, and go straight for
mod 19
order(10,19) = 18 → 18k repunit ≡ (I(18k+1)-1)/9 ≡ (1-1)/9 ≡ 0 (mod 19)
Removed factors 3 and 19, we have this simple, and better test.
1*R(18k) + [2,8]
3*R(18k) + [-2,4]
7*R(18k) + [-4,2]
9*R(18k) + [-8,-2]
Update 2: Adding
mod 17 to above, we can replace 18k to LCM(16,18)*k' = 144k'
We can do this recursively !
Once confirmed 144 digits is no good, we can rebuild the sieves.
Including *all* p < 144, that satisfy order(10,p)=p-1, it implied 144k' can be replaces with LCM of all p-1 = 2884321440k''