scramble prime challenge

[Albert Chan]

(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''