+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: scramble prime challenge (/thread-14502.html)
Pages: 1 2
RE: scramble prime challenge - Dave Britten - 02-18-2020 03:05 PM
(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.
RE: scramble prime challenge - Don Shepherd - 02-18-2020 05:26 PM
(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.
RE: scramble prime challenge - Albert Chan - 02-19-2020 12:16 AM
(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
RE: scramble prime challenge - Don Shepherd - 02-19-2020 11:04 AM
Thanks Albert.
Fascinating stuff indeed.