scramble prime challenge

02142020, 01:14 AM
Post: #1




scramble prime challenge
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. 

02142020, 01:40 AM
Post: #2




RE: scramble prime challenge
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 4digit numbers using the allowable 4 digits.


02142020, 02:32 AM
Post: #3




RE: scramble prime challenge  
02142020, 03:02 AM
Post: #4




RE: scramble prime challenge
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. 

02142020, 04:39 AM
(This post was last modified: 02162020 03:01 AM by Albert Chan.)
Post: #5




RE: scramble prime challenge
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 nonbold 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 "non1379" 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 

02142020, 04:43 AM
Post: #6




RE: scramble prime challenge
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 

02142020, 01:40 PM
Post: #7




RE: scramble prime challenge
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 ndigit 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 worstcase 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 worstcase for 7digit numbers needing 630 prime tests (7! / 2! / 2! / 2! / 1!), and 8digit 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 worstcase unique permutations for ndigit 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 fx9860), and the highestend 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. 

02142020, 01:56 PM
Post: #8




RE: scramble prime challenge
This paper on divisibility may help.
https://arxiv.org/pdf/1903.04903.pdf 

02142020, 04:02 PM
(This post was last modified: 02182020 09:24 PM by Albert Chan.)
Post: #9




RE: scramble prime challenge
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 Another benefit is there is no big list to handle, with space complexity = O(digits) Code: from gmpy2 import is_prime, mpz >>> 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 

02142020, 10:09 PM
Post: #10




RE: scramble prime challenge
Here is a bruteforce 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:


02142020, 10:30 PM
Post: #11




RE: scramble prime challenge
(02142020 10:09 PM)John Keith Wrote: Here is a bruteforce 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. thanks John. What exactly does this program do, I'm not familiar with RPL. Don 

02152020, 02:14 PM
(This post was last modified: 02192020 12:18 AM by Albert Chan.)
Post: #12




RE: scramble prime challenge
Using unique_permute() code from post #9, ignoring 1digit 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): 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): >>> 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. 

02152020, 06:59 PM
Post: #13




RE: scramble prime challenge
(02142020 10:30 PM)Don Shepherd Wrote:(02142020 10:09 PM)John Keith Wrote: 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. 

02152020, 10:15 PM
Post: #14




RE: scramble prime challenge
(02152020 06:59 PM)John Keith Wrote:(02142020 10:30 PM)Don Shepherd Wrote: thanks John. 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 

02152020, 10:32 PM
Post: #15




RE: scramble prime challenge
(02152020 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. I've always considered RPL a "writeonly" 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. 

02152020, 11:11 PM
Post: #16




RE: scramble prime challenge
Ran the actual numbers in python, then made a quickndirty set check based on the MOD function. 61 bytes on free42 (I think it can be cut down to 5759 without too much effort..)
The function allows the checking of several primes in parallel: Code:
Code:
17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

02162020, 02:19 PM
Post: #17




RE: scramble prime challenge
(02152020 11:11 PM)Allen Wrote: I think it can be cut down to 5759 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:
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:
17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

02162020, 07:11 PM
(This post was last modified: 02162020 07:11 PM by John Keith.)
Post: #18




RE: scramble prime challenge
(02152020 10:32 PM)Dave Britten Wrote: I've always considered RPL a "writeonly" 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 4level RPN calculators to be harder to read, mostly due to the lack of highlevel 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. 

02172020, 06:23 PM
(This post was last modified: 02192020 03:57 PM by Albert Chan.)
Post: #19




RE: scramble prime challenge
(02152020 02:14 PM)Albert Chan Wrote: Using unique_permute() code from post #9, ignoring 1digit scramble primes, below proved that We can rewrite XXXXX...Y as X*(11111...) + (YX) = XR + (YX) 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 YX = k, this implied XR must be divisible by 7 Otherwise, with 6 (or more) digits R, XR+(YX) 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 >>> 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 ≡ (11)/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)=p1, it implied 144k' can be replaces with LCM of all p1 = 2884321440k'' 

02182020, 12:55 AM
Post: #20




RE: scramble prime challenge
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..... 

« Next Oldest  Next Newest »

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