Results 1 to 15 of 15

Math Help - Conditional number problem

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    5

    Conditional number problem

    I am assisting a programming comp, and our team had a practice question for finding values a,b,c such that:

    a^3 - b^3 - c^3 = 100

    Currently, we had the idea of doing random number tests which squares, by restricting the possibilities for the numbers based on size and nature (obviously we had to end with an even number, etc). Additionally, we tried doing random testing for a (i.e subbing a value in) and then making the condition b^3 + c^3 = a^3 - 100 to find appropriate b and c values through more testing. However, both methods, as you image, take too long. We have a limit of about 10 seconds so some guessing is possible.

    I am really stumped and would appreciate any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    Let a^3 = 100 and b = 0 and c = 0 and you get 100 - 0 - 0 = 100 so (100^{1/3},0,0) satisfies the equation. What is the exact purpose of this question. Maybe you should write the question in full.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2010
    Posts
    5
    a,b,c are defined as positive non zero integers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by corndog View Post
    I am assisting a programming comp, and our team had a practice question for finding values a,b,c such that:

    a^3 - b^3 - c^3 = 100

    Currently, we had the idea of doing random number tests which squares, by restricting the possibilities for the numbers based on size and nature (obviously we had to end with an even number, etc). Additionally, we tried doing random testing for a (i.e subbing a value in) and then making the condition b^3 + c^3 = a^3 - 100 to find appropriate b and c values through more testing. However, both methods, as you image, take too long. We have a limit of about 10 seconds so some guessing is possible.

    I am really stumped and would appreciate any help.
    Simple brute force gives answer very quickly, the numbers are very small.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2010
    Posts
    5
    The exact problem:
    There are only three known solutions to the equation
    a^3 – b^3 – c^3 = 100
    with positive integer values for a, b and c.
    Write a program that can generate all of them systematically and in a reasonable time.
    The program must be able to produce the answers without duplicates in less than 10 seconds real
    time*, so you may need to do some analysis first to avoid having to search billions of possibilities. Any
    shortcuts that you build into the program must be logically justified, not the result of implementing a
    long-running brute-force algorithm and using the results to filter the generator.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    [ignore]Here's another thing

    let a = 2x^{1/3}, b = a = x^{1/3} and c = x^{1/3}. This gives 8x -x -x = 6x = 100. x = 100/6. Then take the 3rd root of it and you get all three numbers right away.[/ignore]

    I just realized you are talking about integers!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    Quote Originally Posted by corndog View Post
    The exact problem:
    There are only three known solutions to the equation
    a^3 – b^3 – c^3 = 100
    with positive integer values for a, b and c.
    Write a program that can generate all of them systematically and in a reasonable time.
    The program must be able to produce the answers without duplicates in less than 10 seconds real
    time*, so you may need to do some analysis first to avoid having to search billions of possibilities. Any
    shortcuts that you build into the program must be logically justified, not the result of implementing a
    long-running brute-force algorithm and using the results to filter the generator.
    This is much, much better. You can start off by a brute force triple for loop where you generate each number from 1 to 100 for each of the variables, but obviously this is going to be very inefficient since you will be testing 100^3 = 1,000,000 triplets. However you can definitely explore the symmetry of the question since if you get a solution a,b,c then a,c,b will be a solution also. Since you have only 3 known solutions one of those must have b = c . So you can reduce the equation to a^3 - 2 b^3 = 100 to find that one.

    To solve the rest you can assume b and c are different and take it from there.
    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
    Quote Originally Posted by corndog View Post
    The exact problem:
    There are only three known solutions to the equation
    a^3 – b^3 – c^3 = 100
    with positive integer values for a, b and c.
    Write a program that can generate all of them systematically and in a reasonable time.
    The program must be able to produce the answers without duplicates in less than 10 seconds real
    time*, so you may need to do some analysis first to avoid having to search billions of possibilities. Any
    shortcuts that you build into the program must be logically justified, not the result of implementing a
    long-running brute-force algorithm and using the results to filter the generator.
    Kind of hard to help you with a question when we don't know what the question is!

    However there is something wrong with the problem. Maybe it means b \ge c. Because in 1 second on my system, naive brute force gives four solutions

    (7,6,3)
    (7,3,6)
    (190,161,139)
    (190,139,161)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Aug 2010
    Posts
    5
    Perhaps it's a typo in the question?
    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 corndog View Post
    Perhaps it's a typo in the question?
    My guess is they forgot to specify b \ge c, or equivalently, b \le c.

    I will put the code I wrote in a spoiler box so you can try to guess at an algorithm.

    Spoiler:

    Code:
    import java.util.ArrayList;
    import java.util.TreeSet;
    
    public class CubeMinus100Sum2Cubes {
        static ArrayList<Long> cubes = new ArrayList<Long>();
        static TreeSet<Long> cubes2 = new TreeSet<Long>();
        
        public static void main(String[] args) {
            long c, c2, c3, t=time();
            int i, j, lim = 2000, count=0; // limit chosen arbitrarily (guess)
            for(c=1; c<lim+1; c++) {
                c2=c*c*c;
                cubes.add(c2);
                cubes2.add(c2);
            }
            outer:
            for(i=4; i < lim; i++) {
                c=cubes.get(i)-100;
                for(j=0, c2=cubes.get(j); c2 <= c/2; j++, c2=cubes.get(j)) {
                    if (cubes2.contains(c-c2)) {
                        c2 = Math.round(Math.pow(c-c2,(1/3.0)));
                        System.out.println(i+1+","+(j+1)+","+c2);
                        if (++count == 3)
                            break outer;
                    }
                }
            }
            System.out.println("Elapsed: "+(time()-t)/1000.0+" seconds");
        }
        
        static long time() {
            return System.currentTimeMillis();
        }
    }
    Output:
    Code:
    7,3,6
    190,139,161
    1870,903,1797
    Elapsed: 0.132 seconds
    Edit: This code is rather sloppy, I will rewrite in a little bit.
    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
    Quote Originally Posted by undefined View Post
    Edit: This code is rather sloppy, I will rewrite in a little bit.
    Hmm, my sloppier code runs faster. Go figure.

    Spoiler:

    Code:
    import java.util.ArrayList;
    import java.util.TreeSet;
    
    public class CubeMinus100Sum2Cubes {
        static ArrayList<Long> cubes = new ArrayList<Long>();
        static TreeSet<Long> cubes2 = new TreeSet<Long>();
        
        public static void main(String[] args) {
            long c, c2, i, t=time();
            int j, count=0;
            outer:
            for(i=1, c=1;; i++, c=i*i*i) {
                cubes.add(c);
                cubes2.add(c);
                c-=100;
                if(i > 4)
                for(j=0, c2=1; c2 <= c/2; j++, c2=cubes.get(j)) {
                    if(cubes2.contains(c-c2)) {
                        c2 = Math.round(Math.pow(c-c2,(1/3.0)));
                        System.out.println(i+","+(j+1)+","+c2);
                        if(++count == 3)
                            break outer;
                    }
                }
            }
            System.out.println("Elapsed: "+(time()-t)/1000.0+" seconds");
        }
        
        static long time() {
            return System.currentTimeMillis();
        }
    }
    Output:
    Code:
    7,3,6
    190,139,161
    1870,903,1797
    Elapsed: 0.165 seconds
    Last edited by undefined; August 14th 2010 at 07:09 AM. Reason: small typo
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Aug 2010
    Posts
    5
    Thank you very much for your assistance.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by corndog View Post
    Thank you very much for your assistance.
    You're welcome.

    Note that I stopped checking for answers as soon as 3 were found. I also made no attempt to prove that only 3 answers exist. In a sense, I already found twice the number of solutions asked for by the problem anyway..

    By the way, I guess you looked at my code. Did you have any questions about it?

    Edit: I forgot the problem stated "three known solutions" instead of "three solutions", so maybe proving the number of solutions is difficult, I haven't studied this kind of Diophantine much and wouldn't attempt a proof at present. (And the wording of the question implies it is an open problem.)
    Last edited by undefined; August 13th 2010 at 11:40 PM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    Undefined, is your code so fast because it is storing all the values in arrays first and then doing the math with them so that you don't have to do the powers all the time?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Vlasev View Post
    Undefined, is your code so fast because it is storing all the values in arrays first and then doing the math with them so that you don't have to do the powers all the time?
    Yes, that's the main speedup. ArrayList is the standard growable array in Java, compared with normal arrays which aren't growable (have fixed size). TreeSet has a much faster contains() method than ArrayList, but TreeSet does not have a get() method (you must access the elements through an Iterator which is a little slow), so I used both in coordination.

    And the algorithm is just: generate cubes starting from 1 and increasing; if the cube is greater than 100, subtract 100 from it and then subtract cubes from that (stop halfway to ensure b\le c) and see if the result is a cube.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. conditional variance problem
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: October 1st 2011, 07:49 PM
  2. Replies: 0
    Last Post: July 22nd 2011, 01:39 AM
  3. Conditional problem
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 8th 2010, 04:59 PM
  4. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  5. Conditional probability problem
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: January 27th 2008, 01:10 PM

Search Tags


/mathhelpforum @mathhelpforum