Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - A leading question: what do these numbers have in common?

  1. #1
    Banned
    Joined
    Oct 2009
    Posts
    769

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

    The numbers are 113, 131, 311 and 199, 919, 991.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    769

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by wonderboy1953 View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Defunkt View Post
    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.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    769

    Reply

    "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).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by wonderboy1953 View Post
    "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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Last edited by undefined; June 18th 2010 at 07:12 AM. Reason: small typo
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Oct 2009
    Posts
    769
    "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).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by wonderboy1953 View Post
    "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.
    Last edited by undefined; June 18th 2010 at 07:35 AM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Oct 2009
    Posts
    769
    Quote Originally Posted by undefined View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by wonderboy1953 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Banned
    Joined
    Oct 2009
    Posts
    769

    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. What do these numbers have in common?
    Posted in the Math Puzzles Forum
    Replies: 7
    Last Post: August 2nd 2010, 08:23 AM
  2. Replies: 3
    Last Post: May 29th 2009, 11:11 AM
  3. Replies: 2
    Last Post: March 14th 2009, 03:56 AM
  4. What do these numbers have in common, please?
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: October 30th 2008, 05:29 PM
  5. Prime Numbers and common divisors
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 1st 2006, 06:54 PM

Search Tags


/mathhelpforum @mathhelpforum