scramble prime challenge

[Dave Britten]

(02-18-2020 12:55 AM)Don Shepherd Wrote:  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.

Yeah, I suppose it makes sense intuitively when you think about it. The more digits in the number, the more permutations, and the more chances that at least one will be composite. I wasn't expecting none over 4, though.

[Don Shepherd]

(02-18-2020 03:05 PM)Dave Britten Wrote:  

(02-18-2020 12:55 AM)Don Shepherd Wrote:  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.

Yeah, I suppose it makes sense intuitively when you think about it. The more digits in the number, the more permutations, and the more chances that at least one will be composite. I wasn't expecting none over 4, though.

Yeah, I was hoping that, for example, 917371993771911 might be a scramble prime, but with over 1 trillion permutations of those 15 digits, it would be highly unlikely.

[Albert Chan]

(02-18-2020 05:26 PM)Don Shepherd Wrote:  Yeah, I was hoping that, for example, 917371993771911 might be a scramble prime, but with
over 1 trillion permutations of those 15 digits, it would be highly unlikely.

With repeating digits, permutations should use multinomial coefficient

For 917371993771911, permutations = \(\large\binom{15}{5,2,4,4} = {15! \over 5! 2! 4! 4!} \) = 9,459,450

I made the same mistake with Python's itertools.permutations, which do n! permutations.
With repeated digits, many permutations produce the same patterns, wasting cycles.

Then, I googled and found this: Distinct permutations of the string | Set 2
Post #9 unique_permute were "borrowed" from article's Python3 code

[Don Shepherd]

Thanks Albert.

Fascinating stuff indeed.