# Thread: A leading question: what do these numbers have in common?

1. ## A leading question: what do these numbers have in common?

The numbers are 113, 131, 311 and 199, 919, 991.

2. They're all prime-numbers,
They all have a '1' digit,
and at least one of their digits is a multiple of 3,

What more could they have in common ;p

3. ## As I said

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.

4. Originally Posted by wonderboy1953
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!

5. Originally Posted by Defunkt
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.)

"By the way, is the number allowed to have the digit 0?" The answer is yes (it'd be interesting to see what happens in other bases too).

7. Originally Posted by wonderboy1953
"By the way, is the number allowed to have the digit 0?" The answer is yes (it'd be interesting to see what happens in other bases too).
I just realised it was silly to ask if zero is allowed, since then certain permutations are guaranteed to be divisible by 10 and thus composite. Anyway I estimate being able to work on this starting ~12 hrs from now.

8. 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)

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();
}
}
Output for 10^8:

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 10^9 version took about 26 seconds to sieve and 0.1 second for the main algorithm.

The algorithm is brute force for the digit multisets (only odd digits) and backtracking for the permutations.

9. "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).

10. Originally Posted by wonderboy1953
"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.

11. I searched up to 10^12 and found no others.

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();
}
}
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.

12. Decided to look up the sequence of prime repunits and found A004023 on OEIS.

Also, found no 13-digit numbers (which ran surprisingly fast, about 30 seconds) and the program is currently looking for 14-digit ones.

13. Originally Posted by undefined
Decided to look up the sequence of prime repunits and found A004023 on OEIS.

Also, found no 13-digit numbers (which ran surprisingly fast, about 30 seconds) and the program is currently looking for 14-digit ones.
How far did you get?

14. Originally Posted by wonderboy1953
How far did you get?
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.

15. ## Further thought

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.

Page 1 of 2 12 Last