The numbers are 113, 131, 311 and 199, 919, 991.
That was a leading question and now for the real puzzle. Do any 4- and 5-digit numbers exist that have the property where for any combination of their digits, you will get a prime number? What's the biggest digit number that does have that property?
As a note I feel certain this had to have been explored before, yet in over 40 years I've seen no record of this. Unless somebody preceded me in this, I propose calling these type of numbers complete primes since no matter how you arrange the digits, you'll get a prime number.
I'm rather positive that there is a problem in Project Euler which deals with this question. Try looking it up!
You could be right, but I was not able to find such a problem when I looked (I only looked for about five minutes though).
I can work on answering the OP's question (maybe not the largest-digit question, but the 4- and 5- digit ones at least), but won't have time for a little while.
By the way, is the number allowed to have the digit 0? (Which would mean some permutations of digits will have at least one leading zero.)
Now that the forum is updated..
I tried up to 10^9 and found nothing beyond 3-digit numbers. However there is another 3-digit group you didn't mention: 337, 373, 733.
Here is my Java code (hopefully bug-free, probably hard to read; I used a compact style)
Output for 10^8:Code:import java.util.BitSet; public class PrimePermus { static final int L=1000000000,L2=(int)Math.sqrt(L); static BitSet p=new BitSet(L); static boolean q; static void init() { int i,j; p.set(0); p.set(1); for(i=2;i<=L2;i++) if(!p.get(i)) for(j=i+i;j<L;j+=i) p.set(j); } public static void main(String[] args) { int i; long t=time(),t2,t3; init(); System.out.println("Prime sieve took "+(((t2=time())-t)/1000.0)+" s"); for(i=2;i<10;i++) solve(0,1,new int[i]); System.out.println("Main algorithm took "+(((t3=time())-t2)/1000.0)+" s"); System.out.println("Elapsed: "+((t3-t)/1000.0)+" s"); } static void solve(int n,int m,int[] a) { int i,d; if(a[a.length-1]!=0) { q=false; permute(0,a,new boolean[a.length],new int[a.length]); if(!q) { d=0; for(i=0;i<a.length;i++) { d+=a[i]; if(i<a.length-1) d*=10; } System.out.println(d); } return; } for(i=m;i<10;i+=2) { int[] b=a.clone(); b[n]=i; solve(n+1,i,b); } } static void permute(int n,int[] a,boolean[] b,int[] c) { int i,f=0; if(q) return; if(n==a.length) { for(i=0;i<a.length;i++) { f+=a[c[i]]; if(i<a.length-1) f*=10; } if(p.get(f)) q=true; return; } for(i=0;i<a.length;i++) if(!b[i]) { boolean[] d=b.clone(); int[] e=c.clone(); d[i]=true; e[n]=i; permute(n+1,a,d,e); } } static long time() { return System.currentTimeMillis(); } }
The 10^9 version took about 26 seconds to sieve and 0.1 second for the main algorithm.Code:Prime sieve took 2.168 s 11 13 17 37 79 113 199 337 Main algorithm took 0.094 s Elapsed: 2.262 s
The algorithm is brute force for the digit multisets (only odd digits) and backtracking for the permutations.
"However there is another 3-digit group you didn't mention: 337, 373, 733."
You're right as it only takes two groups to set up the puzzle (it also helped to make the puzzle a bit more interesting by having people wonder, like you did, whether I missed any 3-digit groups).
Well I wasn't really thinking about whether you'd missed any, I just wrote the program to print all such numbers and thought it was worth mentioning that there's another 3-digit one.
Also I just realised I could eliminate the digit 5 from consideration, although the current time bottleneck is the prime sieving. Usually for larger numbers I "cheat" and use Java's BigInteger primality tests. By the way, just playing around on PARI/GP (just now), I found a 19-digit number, and a 23-digit one:
1111111111111111111
11111111111111111111111
Edit: Also a 317-digit (as above).
Edit 2: Also 1031-digit.
I searched up to 10^12 and found no others.
Note that I use a low value for the argument in isProbablePrime(). That's because there's only a possibility for false positive here, not false negative. (isProbablePrime() might report a composite as probably prime, but never a prime as composite.) Took about 364 seconds to run.Code:import java.math.BigInteger; import java.util.BitSet; public class PrimePermus { static final int L=100000000,L2=(int)Math.sqrt(L); static BitSet p=new BitSet(L); static boolean q; static void init() { int i,j; p.set(0); p.set(1); for(i=2;i<=L2;i++) if(!p.get(i)) for(j=i+i;j<L;j+=i) p.set(j); } public static void main(String[] args) { int i; long t=time(),t2,t3; init(); System.out.println("Prime sieve took "+(((t2=time())-t)/1000.0)+" s"); for(i=2;i<13;i++) solve(0,1,new int[i]); System.out.println("Main algorithm took "+(((t3=time())-t2)/1000.0)+" s"); System.out.println("Elapsed: "+((t3-t)/1000.0)+" s"); } static void solve(int n,int m,int[] a) { int i; if(a[a.length-1]!=0) { q=false; permute(0,a,new boolean[a.length],new int[a.length]); if(!q) System.out.println(concat(a)); return; } for(i=m;i<10;i+=2) if(i!=5) { int[] b=a.clone(); b[n]=i; solve(n+1,i,b); } } static void permute(int n,int[] a,boolean[] b,int[] c) { int i; if(q) return; if(n==a.length) { if(!isPrime(concat(a,c))) q=true; return; } for(i=0;i<a.length;i++) if(!b[i]) { boolean[] d=b.clone(); int[] e=c.clone(); d[i]=true; e[n]=i; permute(n+1,a,d,e); } } static long concat(int[] a) { int i; long n=0; for(i=0;i<a.length;i++) { n+=a[i]; if(i<a.length-1) n*=10; } return n; } static long concat(int[] a,int[] b) { int i; long n=0; for(i=0;i<a.length;i++) { n+=a[b[i]]; if(i<a.length-1) n*=10; } return n; } static boolean isPrime(long n) { if(n<L) return !p.get((int)n); return BigInteger.valueOf(n).isProbablePrime(2); } static long time() { return System.currentTimeMillis(); } }
I had to restart my computer that day, 14 digits was taking forever, forgot to start it back up again.. but it does become increasingly unlikely to find such a number, and I'm wondering about restricting the search to digit sets like {1,1,1,1,1,1,1,1,1,1,3} or similar.
I believe it can be proven that no number larger than a three-digit number can be found
with the desired properties.
With larger numbers the number of combinations grows rapidly. So for a three-termed number, there are six combinations; when it's four termed, 24 combinations exist; five terms - 120 combinations and so on. It's already known that the primes thin out as they get bigger.
The proof based on the aforementioned should be interesting if it hasn't been done yet.