Page 1 of 3 123 LastLast
Results 1 to 15 of 34

Math Help - What's so special about this composite number

  1. #1
    Senior Member
    Joined
    Jun 2009
    Posts
    251

    [RESOLVED]What's so special about this composite number

    15999

    I had written a program in PHP that determined whether an integer is composite or prime. Under certain versions of EasyPHP, 15999 would cause the virtual server to crash in a very abnormal way. I tested numbers close to 15999 and numbers much larger and I was unable to repeat the problem with any other number. From a mathematical perspective is there anything unique about this composite number?

    When I did a google search it came up with pages about pseudo primes, but my program was deterministic so that doesn't make sense.
    Last edited by superdude; May 14th 2010 at 02:24 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by superdude View Post
    15999

    I had written a program in PHP that determined whether an integer is composite or prime. Under certain versions of EasyPHP, 15999 would cause the virtual server to crash in a very abnormal way. I tested numbers close to 15999 and numbers much larger and I was unable to repeat the problem with any other number. From a mathematical perspective is there anything unique about this composite number?

    When I did a google search it came up with pages about pseudo primes, but my program was deterministic so that doesn't make sense.
    Test with some other semiprimes (that is products of just two primes). If you want a test case try 15989

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Maybe we ought to see the code in order to check whether it is a computer problem or if indeed the algorithm you use somehow crashes on this number. It might just be a integer capacity overflow problem, does it work with bigger prime numbers ?

    Here is a test vector list to check your code :
    - 3
    - 17
    - 51
    - 5891
    - 15603
    - 49
    - 36
    - 99999
    - 2
    - 65

    Do these numbers work ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    This was one of the first programs I made and it was a number of years ago. My style was very poor
    here's the relevant code. primefind gets called first with the first argument being the number in question, startnum is initially 1, and handel is unrelated to prime factoring:
    [PHP]
    <?php
    $num = 15989;
    $startnum = 1;
    if($num == 1){
    print("<link rel=\"stylesheet\" type=\"text/css\" href=\"external.css\" />The only factor of 1 is 1.<br /> However 1 is not prime because there are no two numbers which can be multiplied together to make 1.<br /> Therefore 1 does not fit the definition of a prime number.");
    exit;
    }
    if($num == 0){
    print("<link rel=\"stylesheet\" type=\"text/css\" href=\"external.css\" />The only factor of 0 is 0.<br /> However 0 is not prime because there are no two numbers which can be multiplied together to make 0.<br /> Therefore 0 does not fit the definition of a prime number.");
    exit;
    }else{
    print("The factors of ".$num." are:<br />");
    }
    primefind($num, $startnum);//calls this functin
    if($num == 0){
    print("0");
    }
    else if($num == 1){
    print("1");
    }else{
    }
    function primefind($num, $startnum){
    $primestat = 'f';
    for($counter1 = $startnum; $counter1<=$num; $counter1++){
    for($counter2 = 2; $counter2<$counter1; $counter2++){
    $primecheck = $counter1%$counter2;
    if($primecheck != 0){
    $primestat = 't';
    }else{
    $primestat = 'f';
    break;
    }
    }
    if($primestat == 't'||$counter1 == 2){
    factorcheck($counter1, $num);
    break;
    }
    }
    }
    function factorcheck($prime, $num){
    $remainder = $num%$prime;
    if($remainder == 0)
    {
    print($prime.'<br />');
    $startnum = 1;
    primefind(($num/$prime), $startnum);
    //exit;
    return $prime;
    }
    else{
    $prime++;
    primefind($num, $prime);
    }
    }
    ?>
    [/PHP]

    I began writing pseudo code but I got stuck and the following is incomplete. I don't know how to account for when one function calls another in pseudo code.

    Terms & Conditions:
    0.1 let num be an integer greater than 2
    0.2 % denotes the modulus operator
    START
    1. set counter1 = 1
    2. while(counter1 is less than or equal to num) do
    2.1 set counter2 = 2[/FONT]
    2.2 while(counter 2 is less than counter1) do
    2.2.1 set primecheck = counter1%counter2
    2.2.2 if(primecheck is not equal to 0) then
    2.2.2 set primestat = ‘t’
    2.2.3 else
    2.2.3 set primestat = ‘f’
    2.2.3 goto END
    2.2.3 end if
    2.2.4 set counter2 = counter2+1
    2.3 if(primestat equals ‘t’ OR counter1 equals 2) then
    2.3.1 set prime=counter1
    2.3.2 set remainder=prime%num
    2.3.3 if(remainder is 0) then
    2.3.4 set startnum=1
    2.3.5 else
    2.3.5 set prime=prime+1
    2.3.5 goto 1 with new num and startnum=prime



    This problem only existed under EasyPHP 1.8 so I'll try to recreate the conditions. After writing this program it became clear to me that primality testing and integer factorizing where two distinct ideas.
    Last edited by superdude; April 19th 2010 at 10:05 PM. Reason: change PHP code
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by superdude
    After writing this program it became clear to me that primality testing and integer factorizing where two distinct ideas.
    Indeed, it is. The former is a decision problem, thus considerably simpler than the latter which is a NP problem. The former can now be done efficiently (in P, i.e. polynomial time) whether the latter is still hard to achieve with big numbers (NP, and subexponential time)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by Bacterius View Post
    Indeed, it is. The former is a decision problem, thus considerably simpler than the latter which is a NP problem. The former can now be done efficiently (in P, i.e. polynomial time) whether the latter is still hard to achieve with big numbers (NP, and subexponential time)
    What is polynomial time? You remind me of big-O notation. I gather polynomial time is a measure of the efficency of an algorithm. Is polynomial time a certain type of of big-O, such as big O(2^n)?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by superdude View Post
    What is polynomial time? You remind me of big-O notation. I gather polynomial time is a measure of the efficency of an algorithm. Is polynomial time a certain type of of big-O, such as big O(2^n)?
    Polynomial time is O(n^k) for some k \in \mathbb{N_+}. O(2^n) is exponential time

    CB
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by CaptainBlack View Post
    Polynomial time is O(n^k) for some k \in \mathbb{N_+}. O(2^n) is exponential time

    CB
    So n depends on the input and k depends on the algorithm (program)?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by superdude View Post
    So n depends on the input and k depends on the algorithm (program)?
    n is the length of the input and k is specified by the algorithm used (can sometimes be variable with computation/memory tradeoffs).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by Bacterius View Post
    n is the length of the input and k is specified by the algorithm used (can sometimes be variable with computation/memory tradeoffs).
    Is n always the length, no exceptions? For example if a subroutine (or whatever you call it) takes a string as an argument and replaces the first value with 'a'?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    I have managed to recreate the error. I have tried everyone's suggestions but still only have 15999 crash the program. I have changed the code I posted, this is exactly what I'm working with now.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by superdude View Post
    Is n always the length, no exceptions? For example if a subroutine (or whatever you call it) takes a string as an argument and replaces the first value with 'a'?
    It depends on the definition of big O you use. But if you are not considering the length as the function of O, then it is equivalent to just replace n by \log{(n)}.

    For example if a subroutine (or whatever you call it) takes a string as an argument and replaces the first value with 'a'?
    Warning : mathematics and computing are two different things. An algorithm wouldn't take its input and set it to some defined value, so this doesn't count as part of the algorithm.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    2702811 also crashes the program. I notice 3 is a common factor in both cases.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by superdude View Post
    Is n always the length, no exceptions? For example if a subroutine (or whatever you call it) takes a string as an argument and replaces the first value with 'a'?
    "n" is the size of the problem, for instance in sorting n would normally be the length of the list to be sorted, it might be the number of digits in the input, and so n=O(log(N)) where N is the input etc.

    CB
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by CaptainBlack View Post
    "n" is the size of the problem, for instance in sorting n would normally be the length of the list to be sorted, it might be the number of digits in the input, and so n=O(log(N)) where N is the input etc.

    CB
    I think I'm getting the idea. So when you say n=O(log(N)) you're giving a particular example? You're not saying, whenever a subroutine depends on length of the argument then its big O is n=O(log(N)), that's not what you're saying?

    For example, knowing that if a number does not have a factor less than or equal to its square root, the number if prime, an algorithm implementing this idea would have big O of \sqrt{n} and a person would write O(n) where [manth]n=\sqrt(N)[/tex] and a person would speak "the algorithm has an efficiency of big O of square-root-n"?
    Last edited by superdude; April 20th 2010 at 10:35 AM. Reason: added math tag
    Follow Math Help Forum on Facebook and Google+

Page 1 of 3 123 LastLast

Similar Math Help Forum Discussions

  1. composite number proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 7th 2010, 07:35 PM
  2. Show that this number is odd and composite
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 11th 2010, 03:12 AM
  3. rolling a composite number with one die
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 29th 2009, 01:19 PM
  4. Composite number proof help
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 6th 2007, 10:26 AM
  5. Special Number
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 31st 2007, 04:51 PM

Search Tags


/mathhelpforum @mathhelpforum