scramble prime challenge

[Don Shepherd]

Let's say a number is a "scramble prime" if you can scramble its digits and always come up with a prime number. For example, 37 is a scramble prime because both 37 and 73 are primes. 317 is not a scramble prime because 371 is composite. 971 is not a scramble prime because 917 is composite.

So the challenge is to devise a HP calculator program such that you enter a number and the program tells you whether it is a scramble prime or not.

Now, if the number contains certain digits, it will be impossible for it to be a scramble prime.

[Dave Britten]

Hmm, interesting idea. Unique or repeatable digits? If unique, that limits it to at most 4 digits. There would be 60 possible 2, 3, and 4-digit numbers using the allowable 4 digits.

[Don Shepherd]

(02-14-2020 01:40 AM)Dave Britten Wrote:  Hmm, interesting idea. Unique or repeatable digits? If unique, that limits it to at most 4 digits. There would be 60 possible 2, 3, and 4-digit numbers using the allowable 4 digits.

repeatable digits are fine ...

[Paul Dale]

Off the top of my head, any number with a 5 or an even digit isn't allowed. The numbers can only be composed of 1, 3, 7 and 9.

By inspection there are five two digit possibilities.

Three digits has more cases. Divisibility by three rules out a single repeated digit, 117, 177 and all combinations that only contain 3 or 9. This brings it down to a more manageable number than 64 for manual checking. I've found three three digit possibilities.

Four, I'll need my calculator for.

[Albert Chan]

I think the search is easier with a list of primes, with digits other than 1379 removed.
Then list the primes in sorted order, and mark primes with its digits in sorted order.

For example: this is all "1379" only primes below 10000, with likely case underlined.

3 7

11 13 17 19 31 37 71 73 79 97

113 131 137 139 173 179 191 193 197 199
311 313 317 331 337 373 379 397
719 733 739 773 797
911 919 937 971 977 991 997

1117 1171 1193 1319 1373 1399 1733 1777 1913 1931 1933 1973 1979 1993 1997 1999
3119 3137 3191 3313 3319 3331 3371 3373 3391 3719 3733 3739 3779 3793 3797 3911 3917 3919 3931
7177 7193 7331 7333 7393 7717 7793 7919 7933 7937 7993
9133 9137 9173 9199 9311 9319 9337 9371 9377 9391 9397 9719 9733 9739 9791 9931 9973

The non-bold numbers only used for confirmation of bolded numbers.
Example, for 1777, scan the primes for 7177, 7717, 7771 (not prime).

Scramble primes below 10000 (digits combinations given smallest prime) = 3 7 11 13 17 37 79 113 199 337

Update: I had missed 2 and 5, the only "non-1379" scramble primes. Thank you, Paul Dale

Update 2: 3779 is a rotatable prime, i.e. 7793 7937 9377 are all primes.
And, from post #12, scramble primes is a subset of rotatable prime

[Paul Dale]

The two and three digits numbers match those I found. I didn't bother with single digit ones. If they are included, you missed two. Both 2 and 5 are scramble primes.

Pauli

[Dave Britten]

So, let's say one were to write a program to test arbitrary input numbers. The program can obviously immediately reject anything containing 0, 2, 4, 5, 6, or 8, or where the digits sum to a multiple of 3. After that, you need to start testing permutations of the digits.

Something like Heap's algorithm could be used to generate all permutations of the input number's digits. I think the practical limit on a pocket calculator would be about 7 or 8 digits total, where you have 5,040 or 40,320 permutations to iterate through respectively.

Of course, many of these permutations would be identical, since there are only 4 available digits. If enough memory is available, the program could track which numbers have already been tested as prime, and use that as a lookup table to skip the prime test when the same number comes up again. The number of unique permutations of the four digits 1, 3, 7, and 9 for an n-digit number would be n! / a! / b! / c! / d! where a is the number of 1s, b is the number of 3s, c is the number of 7s, d is the number of 9s, and the worst-case scenario (most unique permutations) for a given n would be the one where a! * b! * c! * d! is minimized (i.e. the four digits are represented as evenly as possible).

This gives a worst-case for 7-digit numbers needing 630 prime tests (7! / 2! / 2! / 2! / 1!), and 8-digit numbers needing 2,520 prime tests (8! / 2! / 2! / 2! / 2!). So the calculator in question would need quite a bit of memory to store all those found primes. Insertion sort could be used to add new numbers to the lookup table, and binary search could be used for lookup if it's large enough.

Here's a list of total permutations, and worst-case unique permutations for n-digit numbers:

2: 2; 2
3: 6; 6
4: 24; 24
5: 120; 60
6: 720; 180
7: 5,040; 630
8: 40,320; 5,040
9: 362,880; 7,560
10: 3,628,800; 25,200
11: 39,916,800; 92,400
12: 479,001,600; 369,600

I think the practical limit for solving this problem on a typical RPN pocket calculator is around 5 or maybe 6 digits if you're very patient. The average graphing calculator probably has enough memory/speed to handle up to 7 digits, as well as maintain a list of confirmed primes to speed up the search (most will handle lists up to 999 elements, with that consuming about 12 KB on my Casio fx-9860), and the highest-end models might be able to tackle 8 or 9 digits.

A modern desktop computer could easily handle 12 and beyond, particularly by parallelizing the prime tests.

[ttw]

This paper on divisibility may help.
https://arxiv.org/pdf/1903.04903.pdf

[Albert Chan]

I tried building the primes first, but it turns out very slow.

Instead, I loop over permutations, but only the digits sorted cases.
This reduces the permutations to manageable size.

Code:

digits  permutations to check
2       10
3       20
4       35
5       56
6       84
7       120
8       165
9       220
10      286

Another benefit is there is no big list to handle, with space complexity = O(digits)

Code:

from gmpy2 import is_prime, mpz

def unique_permute(lst, i, n):          # update in-place !
    if i >=n : yield lst                # reference only !
    for j in xrange(i, n):
        if lst[j] in lst[i:j]: continue # unique only
        lst[i],lst[j] = lst[j],lst[i]   # swap
        for x in unique_permute(lst,i+1,n): yield x
        lst[i],lst[j] = lst[j],lst[i]   # restore

def scramble_primes(digits):
    lst = ['0']*digits
    idx = range(digits-1,-1,-1)
    next = '1307000901'
    while lst[0] != '9':
        for i in idx:
            x = lst[i] = next[ord(lst[i])-48]
            if x == '1': continue                   # do carry
            for j in xrange(i+1,digits): lst[j]=x   # force sorted
            break
        if is_prime(mpz(''.join(lst))):
            gen = unique_permute(lst[:],0,digits)
            gen.next()                              # first case checked
            if all(is_prime(mpz(''.join(y))) for y in gen):
                yield int(''.join(lst))             # scramble prime found!

Note: I did not add the trivial test to return 2,5 as 1-digit scramble primes.

>>> for d in xrange(2,21): print d, list(scramble_primes(d))
...
2 [11, 13, 17, 37, 79]
3 [113, 199, 337]
4 []
5 []
6 []
7 []
8 []
9 []
10 []
11 []
12 []
13 []
14 []
15 []
16 []
17 []
18 []
19 [1111111111111111111L]       # see http://oeis.org/A004022
20 []

Above take 0.3 seconds on my laptop

[John Keith]

Here is a brute-force HP49/50 program using ListExt commands. DIFF is the 4th program in this post. It is a faster version of the GoferLists command Diff, which is set difference or complement.

This program does not check for 2 or 5 but it does check for ineligible digits.

Code:


Spoilers...










\<< I\->NL DUP { 1. 3. 7. 9. } DIFF
  IF SIZE
  THEN DROP 0.
  ELSE DUP SIZE
    \<< NL\->I ISPRIME?
    \>> DOPERM 0. POS NOT
  END
\>>

[Don Shepherd]

(02-14-2020 10:09 PM)John Keith Wrote:  Here is a brute-force HP49/50 program using ListExt commands. DIFF is the 4th program in this post. It is a faster version of the GoferLists command Diff, which is set difference or complement.

This program does not check for 2 or 5 but it does check for ineligible digits.

Code:


Spoilers...










\<< I\->NL DUP { 1. 3. 7. 9. } DIFF
  IF SIZE
  THEN DROP 0.
  ELSE DUP SIZE
    \<< NL\->I ISPRIME?
    \>> DOPERM 0. POS NOT
  END
\>>

thanks John.

What exactly does this program do, I'm not familiar with RPL.
Don

[Albert Chan]

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)

Post#9 already checked all the scramble primes 20 digits or less, all have patterns stated above.
All bigger scramble primes must have at least 1 digit with frequency of 6 or more.

I did a brute force check, for X with frequency of 5, and two other digits ≠ X.
In other words, checked pattern = XXXXXYZ (Y, Z are non X's, but may equal to each other)

With this patterns, some permutations will hit with mod7 = 0, thus not scramble prime.

Code:

def dec(lst, t=0):
    for x in lst: t = 10*t + x
    return t

def mod7_pat(lst):
    mod7 = [0]*7
    for x in unique_permute(lst, 0, len(lst)):
        mod7[dec(x)%7] = 1
    return mod7

Example:
>>> mod7_pat([1,1,3])
[0, 1, 0, 1, 0, 1, 0]
>>> 113%7, 131%7, 311%7       # matched mod7 patterns, with 1 at index 1,3,5
(1, 5, 3)
>>> mod7_pat([1,1,1,1,3,7])      # some permutations have factor of 7, thus not scramble prime
[1, 1, 1, 1, 1, 1, 1]

To automate the search, a simple test to loop over all XXXXXYZ cases.

Code:

def mod7_test(digits=(1,3,7,9), n=7):
    for d in digits:
        lst = [d] * n
        remain = [x for x in digits if x!=d]
        for y in remain:
            for z in remain:
                lst[-2:] = y, z
                mod7 = mod7_pat(lst)
                if all(mod7): continue
                print lst, mod7

>>> mod7_test()                        # no output, thus all mod7 cases covered
>>>

This implied all digits patterns with 5 (or more) X's, and 2 (or more) non X's cannot be scrambled primes.

[John Keith]

(02-14-2020 10:30 PM)Don Shepherd Wrote:  

(02-14-2020 10:09 PM)John Keith Wrote:  

Code:


Spoilers...










\<< I\->NL DUP { 1. 3. 7. 9. } DIFF
  IF SIZE
  THEN DROP 0.
  ELSE DUP SIZE
    \<< NL\->I ISPRIME?
    \>> DOPERM 0. POS NOT
  END
\>>

thanks John.

What exactly does this program do, I'm not familiar with RPL.
Don

The first 3 lines check for any digits other than 1, 3, 7, or 9 and return 0 (false) if any are present. The next 3 lines create all permutations of the digits of the given number and test if they are prime. If all are prime the program returns 1 (true) else 0 (false).

The documentation for the ListExt Library (see here) explains the commands used better than I can.

As Dave Britten said above, this would get very slow for numbers with more than 6 or 7 digits. Since Albert Chan has shown that there are no scramble primes with more than 3 and less than 19 digits, it's really not that practical anyway.

[Don Shepherd]

(02-15-2020 06:59 PM)John Keith Wrote:  

(02-14-2020 10:30 PM)Don Shepherd Wrote:  thanks John.

What exactly does this program do, I'm not familiar with RPL.
Don

The first 3 lines check for any digits other than 1, 3, 7, or 9 and return 0 (false) if any are present. The next 3 lines create all permutations of the digits of the given number and test if they are prime. If all are prime the program returns 1 (true) else 0 (false).

The documentation for the ListExt Library (see here) explains the commands used better than I can.

As Dave Britten said above, this would get very slow for numbers with more than 6 or 7 digits. Since Albert Chan has shown that there are no scramble primes with more than 3 and less than 19 digits, it's really not that practical anyway.

Thank you very much, John. I just never have been able to deal with the cryptic (although powerful) nature of RPL, but you explained it well.

Don

[Dave Britten]

(02-15-2020 10:15 PM)Don Shepherd Wrote:  Thank you very much, John. I just never have been able to deal with the cryptic (although powerful) nature of RPL, but you explained it well.

Don

I've always considered RPL a "write-only" language. It's very difficult to read others' (or your own!) code and work out what it does, largely because of the unlimited stack depth. At least with the RPN machines, elaborate programs need to use more intermediate storage registers, which pulls back the curtain a little. I've found the best way to get by with RPL is to write very small, focused programs/functions, and name them clearly.

[Allen]

Ran the actual numbers in python, then made a quick-n-dirty set check based on the MOD function. 61 bytes on free42 (I think it can be cut down to 57-59 without too much effort..)

The function allows the checking of several primes in parallel:

Code:


143313465 [3, 5, 31, 311, 991]
90201098 [2, 13, 71, 131, 373]
47258521 [17, 73, 113, 337]
51869279 [7, 11, 733, 919]
56422669 [37, 79, 97, 199]

Returns 0 if it is a "scramble prime" otherwise some other number.

Code:


00 { 61-Byte Prgm }
01 STO 01
02 143313465
03 RCL 01
04 MOD
05 90201098
06 RCL 01
07 MOD
08 ×
09 47258521
10 RCL 01
11 MOD
12 ×
13 51869279
14 RCL 01
15 MOD
16 ×
17 56422669
18 RCL 01
19 MOD
20 ×
21 .END.

[Allen]

(02-15-2020 11:11 PM)Allen Wrote:  I think it can be cut down to 57-59 without too much effort..

Don, thanks for an interesting challenge! Using some random trials to pack the primes into fewer registers try to minimize the number of bytes used as sum(length(numbers)+number of registers)

Code:


00 { 56-Byte Prgm }
01 STO 01
02 3446782235
03 RCL 01
04 MOD
05 7592533501
06 RCL 01
07 MOD
08 ×
09 8332054977
10 RCL 01
11 MOD
12 ×
13 8199551426
14 RCL 01
15 MOD
16 ×
17 .END.

I looked at using primitive roots and indices to see if there was a cheaper way to store set membership, but since several of these primes are under 20, there is no primitive root product that has a smaller product than just these primes.

For example, \( 7^p \mod 997 \) is a primitive root with a unique index for all of these primes \(p \), but you get [49, 343, 855, 21, 571, 63, 716, 704, 118, 433, 280, 840, 746, 818, 152, 936, 278, 700, 833, 601, 241, 667] rather than the original list.. which has no numbers under 20. (plus there is a minor annoyance that none of the HP calculators I know of have modular exponentiation.. maybe the prime does?)

Our hand held could not calculate \( 7^{991} =91706260460847671 \ldots 772735017410743 \)
(883 decimal digits )
but with a small program could easily calculate

\( 7^{991} \mod 997 = 667 \)

Modular exponential on HP 42S (free42 program)
enter base,exponent, modulus then XEQ PMOD
returns \( b ^ x \mod m\) on ST X

Code:


00 { 40-Byte Prgm }
01>LBL "PMOD"
02 STO 03
03 SIGN
04 X<>Y
05>LBL 01
06 STO 02
07 1
08 AND
09 RCL× ST Z
10 X=0?
11 SIGN
12 ×
13 RCL 03
14 MOD
15>LBL 02
16 X<>Y
17 X^2
18 RCL 03
19 MOD
20 X<>Y
21 RCL 02
22 2
23 BASE÷
24 X!=0?
25 GTO 01
26 Rv
27 END

[John Keith]

(02-15-2020 10:32 PM)Dave Britten Wrote:  I've always considered RPL a "write-only" language. It's very difficult to read others' (or your own!) code and work out what it does, largely because of the unlimited stack depth. At least with the RPN machines, elaborate programs need to use more intermediate storage registers, which pulls back the curtain a little. I've found the best way to get by with RPL is to write very small, focused programs/functions, and name them clearly.

I have always considered programs for 4-level RPN calculators to be harder to read, mostly due to the lack of high-level control structures. I will admit that I generally prioritize program speed and size over readability, but then this is 15 year old tech emulating 30 year old tech.

In any case, liberal use of comments is always a good idea.

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

[Don Shepherd]

Thanks Albert and all those who contributed.

So, only a few scramble primes with 2 or 3 or 4 digits, and none beyond that. I had no idea how many I expected, but I guess I'm not surprised at the lack of scramble primes with more than 3 digits; primes are less elusive than I would have thought.

I appreciate all the work you guys put into this, there are really some amazing people in this forum.

Now, who wants to find an odd perfect number.....