Write a script to find permutable prime numbers

Another quick challenge via Fermat's Library:

Via Wikipedia:

A permutable prime, also known as anagrammatic prime, is a prime number which, in a given base, can have its digits' positions switched through any permutation and still be a prime number.

Here is the list of permutable primers under 1,000:

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991

In the language of your choice, write a script to find permutable primes.

Happy coding! 🤓

Comments

[Florian Rohrer]

Nice one!

from collections import deque 

def perms(p):
    result = []
    d = deque(str(p))
    for _ in range(len(str(p))):
        d.rotate(1)
        result.append(int(''.join(d)))
    return result

prev_primes = []

for poss_prime in range(2,1001):
    for n in prev_primes:
        if poss_prime % n == 0:
            break
    else: # no break
        prev_primes.append(poss_prime)

result = [p for p in prev_primes if all(q in prev_primes for q in perms(p))]
print(result)

[Vinay Pai]

This solution has a bug but happens to produce the correct output. This doesn't test all permutations of digits. An n digit integer has n! permutations, but this only tests n of them. For example, 241 has six permutations (241, 214, 421, 412, 124, 142) but this only tests three (241 , 412, 124) of them.

It happens to work because all the three digit permutable prime happen to belong to a family that contain repeated digits, so you never get a false positive. It will fail for larger numbers, it will report 1193 as a permutable number, but it's not (1139 is not a prime number). It's a circular number, solved by Jonathan's Go code below.

Amazingly the next number in the permutable prime sequence after 991 is 1111111111111111111.

You can of course easily fix the bug with itertools.permutations). Just replace perms(p) with this:

def perms(p):
    return [int(''.join(p)) for p in itertools.permutations(str(p))]

[Sung M. Kim]

Pretty long compared to the Python version by Florian Rohrer.

It uses Sieve of Eratosthenes to generate prime numbers up to 1000.
Then just compares if all permutations of each prime number are in the prime set.

The main method that does the job is GetPermutablePrimes.

using System.Collections.Generic;
using System.Linq;
using Xunit;

namespace Demo.LearnByDoing.Tests.RandomStuff
{
    /// <summary>
    /// https://dev.to/peter/write-a-script-to-find-permutable-prime-numbers-1gg0
    /// </summary>
    public class PermutablePrimesTest
    {
        private const int UPTO = 1000;

        [Fact]
        public void TestSieveOf()
        {
            var expected = new[]
                {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61
                , 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139
                , 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229
                , 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317
                , 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421
                , 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521
                , 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619
                , 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733
                , 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839
                , 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953
                , 967, 971, 977, 983, 991, 997};
            var actual = GetPrimeNumbers(UPTO).ToList();

            Assert.True(expected.SequenceEqual(actual));
        }

        [Fact]
        public void TestPermutablePrimes()
        {
            var expected = new[] {2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991};
            var actual = GetPermutablePrimes(UPTO).ToList();
            Assert.True(expected.SequenceEqual(actual));
        }

        private IEnumerable<int> GetPermutablePrimes(int upto)
        {
            // For O(1) lookup
            var primes = new HashSet<int>(GetPrimeNumbers(upto));

            foreach (var prime in primes)
            {
                List<int> perms = GetPermutations(prime.ToString()).ToList();
                if (perms.All(perm => primes.Contains(perm))) yield return prime;
            }
        }

        private IEnumerable<int> GetPermutations(string input)
        {
            return FillPermutations(input).Select(int.Parse);
        }

        private IEnumerable<string> FillPermutations(string input)
        {
            if (input.Length == 1) yield return input;
            else if (input.Length == 2)
            {
                yield return input;
                yield return new string(new[] { input[1], input[0] });
            }
            else
            {
                for (int i = 0; i < input.Length; i++)
                {
                    string prefix = input[i].ToString();
                    string left = input.Substring(0, i);
                    string right = input.Substring(i + 1);
                    string newInput = left + right;

                    foreach (var rest in FillPermutations(newInput))
                    {
                        yield return prefix + rest;
                    }
                }
            }
        }

        private IEnumerable<int> GetPrimeNumbers(int upto)
        {
            // Initialize all numbers as true to "upto + 1" since array is 0-based.
            var primes = Enumerable.Repeat(true, upto + 1).ToArray();

            for (int i = 2; i * i <= upto; i++)
            {
                // It's already processed.
                if (!primes[i]) continue;

                for (int j = i * 2; j <= upto; j += i)
                {
                    primes[j] = false;
                }
            }

            // Skip 0 & 1
            // Return indexes, which are prime numbers
            const int skipBy = 2;
            return primes
                .Skip(skipBy)
                .Select((_, i) => new { IsPrime = _, Value = i + skipBy })
                .Where(obj => obj.IsPrime)
                .Select(obj => obj.Value);
        }
    }
}

[Dave Cridland]

So this doesn't sort... But on the other hand it uses recursive generators, so that has to be a good thing, right?

def perm(l):
    if 1 == len(l):
        yield l[0]
        return
    for i in range(len(l)):
        ll = []
        for j in range(len(l)):
            if j != i:
                ll.append(l[j])
        for p in perm(ll):
            yield l[i] + p
    return

def perms(x):
    l = [ c for c in str(x) ]
    p = [ str(x) ]
    for pp in perm(l):
        yield int(pp)
    return

def primes(r):
    pr = [2]
    yield 2
    for p in range(3, r + 1):
        if p not in pr:
            for n in pr:
                if p % n == 0:
                    break
            else:
                pr.append(p)
                t = []
                for n in perms(p):
                    if n in t:
                        continue
                    if n not in pr:
                        break
                    else:
                        t.append(n)
                else:
                    for n in t:
                        yield n

print [i for i in primes(1000)]

[Seiei Miyagi]

Ruby✨💎✨

require 'prime'
require 'set'

Prime.take_while {|n| n < 1000 }.to_set.yield_self {|ps| ps.select {|n| ps.superset?(n.digits.permuta
tion.map(&:join).map(&:to_i).to_set) } }

[Jonathan]

A friend of mine got this as an interview question, and asked me about it. I wrote this solution in Go:

jmcphers.github.io/programming/201...