Page 2 of 3 FirstFirst 123 LastLast
Results 16 to 30 of 34

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

  1. #16
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by superdude View Post
    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 [mant]n=\sqrt(N)[/tex] and a person would speak "the algorithm has an efficiency of big O of square-root-n"?
    What is an appropriate measure of the size of the problem depends on the problem.

    CB
    Follow Math Help Forum on Facebook and Google+

  2. #17
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by superdude View Post
    2702811 also crashes the program. I notice 3 is a common factor in both cases.
    I like how there are a couple conversations going on at once here, heh.

    I copied and pasted your code for use with my XAMPP setup and got problems with 2702811 sometimes but not always, and I wasn't able to get an error with 15999.

    To tell the truth, I don't understand the logic of your code, but I notice that the two functions call each other an awful lot.

    It seems like you're not doing anything more complex than trial division, so what do you think of this instead?

    [php]
    <?php
    $num = 342132;
    if ($num < 2) {
    echo "No prime factors.";
    exit;
    }
    echo "The prime factorization of " . $num . " is:<br />";
    while ($num % 2 == 0) {
    echo "2<br />";
    $num /= 2;
    }
    while ($num % 3 == 0) {
    echo "3<br />";
    $num /= 3;
    }
    $lim = floor(sqrt($num));
    for ($i = 5, $inc = 2; $i <= $lim; $i += $inc, $inc = 6 - $inc) {
    if ($num % $i == 0) {
    echo $i . "<br />";
    $num /= $i;
    while ($num % $i == 0) {
    echo $i . "<br />";
    $num /= $i;
    }
    $lim = floor(sqrt($num));
    }
    }
    if ($num != 1) echo $num;
    ?>
    [/php]
    Note: I introduce $inc in order to avoid numbers congruent to 0 (mod 3).
    Last edited by undefined; April 20th 2010 at 12:42 PM. Reason: added syntax highlighter
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by undefined View Post
    I like how there are a couple conversations going on at once here, heh.

    I copied and pasted your code for use with my XAMPP setup and got problems with 2702811 sometimes but not always, and I wasn't able to get an error with 15999.

    To tell the truth, I don't understand the logic of your code, but I notice that the two functions call each other an awful lot.

    It seems like you're not doing anything more complex than trial division, so what do you think of this instead?

    Code:
    <?php
    $num = 342132;
    if ($num < 2) {
      echo "No prime factors.";
      exit;
    }
    echo "The prime factorization of " . $num . " is:<br />";
    while ($num % 2 == 0) {
      echo "2<br />";
      $num /= 2;
    }
    while ($num % 3 == 0) {
      echo "3<br />";
      $num /= 3;
    }
    $lim = floor(sqrt($num));
    for ($i = 5, $inc = 2; $i <= $lim; $i += $inc, $inc = 6 - $inc) {
      if ($num % $i == 0) {
        echo $i . "<br />";
        $num /= $i;
        while ($num % $i == 0) {
          echo $i . "<br />";
          $num /= $i;
        }
        $lim = floor(sqrt($num));
      }
    }
    if ($num != 1) echo $num;
    ?>
    Note: I introduce $inc in order to avoid numbers congruent to 0 (mod 3).

    Edit: Can anyone tell me how to get the syntax highlighter? I'm searching around for the bbcode...
    Consider semi-primes of the form n=2 \times p or n=3 \times p where p is a prime greater than 5.

    Note that p>\sqrt{n} which looks like it will crash your algorithm.

    I would guess that 31998 may also give this problems.

    I would conjectute that any number of the form 2^n3^mp where p>2^n3^m is a prime will give problems (this is a conjecture because I cant be bothered to analyse such horrible code in detail)

    CB
    Last edited by CaptainBlack; April 20th 2010 at 02:24 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    Consider semi-primes of the form n=2 \times p or n=3 \times p where p is a prime greater than 5.

    Note that p>\sqrt{n} which looks like it will crash your algorithm.

    CB
    Suppose n = 14, then the program will first divide out all the 2's, so that $lim = floor(sqrt(7)) = 2. The program will effectively skip the main loop and then correctly conclude that 7 is prime and print it as one of the factors.

    Edit: This stuff was added afterwards

    Quote Originally Posted by CaptainBlack View Post
    I would guess that 31998 may also give this problems.

    I would conjectute that any number of the form 2^n3^mp where p>2^n3^m is a prime will give problems (this is a conjecture because I cant be bothered to analyse such horrible code in detail)

    CB
    31998 worked fine. If my code is so horrible, let's see yours.

    Oh and for the conjecture, 745848 = 2^3*3^4*1151 works just fine as well.
    Last edited by undefined; April 20th 2010 at 02:53 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by undefined View Post
    Suppose n = 14, then the program will first divide out all the 2's, so that $lim = floor(sqrt(7)) = 2. The program will effectively skip the main loop and then correctly conclude that 7 is prime and print it as one of the factors.

    Edit: This stuff was added afterwards



    31998 worked fine. If my code is so horrible, let's see yours.
    The horror of the code may be a result of using watever language that is in, or it may be the result of a poorly thought out algorithm I can't tell.

    If you had an algorithm spec in a more comprehensible language or psuedo-code I would have more confidence in it being the language rather than the algorithm.

    CB
    Follow Math Help Forum on Facebook and Google+

  6. #21
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    The horror of the code may be a result of using watever language that is in, or it may be the result of a poorly thought out algorithm I can't tell.

    If you had an algorithm spec in a more comprehensible language or psuedo-code I would have more confidence in it being the language rather than the algorithm.

    CB
    Fair enough, although PHP is quite common. Here's Java:

    Code:
    public ArrayList<Integer> naiveFactorise(int n) {
        // returns prime factors in ascending order, duplicates allowed
        ArrayList<Integer> pFacts = new ArrayList<Integer>();
        if (n < 2) return pFacts;
        while (n % 2 == 0) {
            pFacts.add(2);
            n /= 2;
        }
        while (n % 3 == 0) {
            pFacts.add(3);
            n /= 3;
        }
        int lim = (int)Math.sqrt(n);
        for (int i = 5, inc = 2; i <= lim; i += inc, inc = 6 - inc) {
            if (n % i == 0) {
                pFacts.add(i);
                n /= i;
                while (n % i == 0) {
                    pFacts.add(i);
                    n /= i;
                }
                lim = (int)Math.sqrt(n);
            }
        }
        if (n != 1) pFacts.add(n);
        return pFacts;
    }
    The reason 2 and 3 are treated specially is to ease incrementing the loop variable; otherwise they would be included in the main loop like all the other prime candidates.

    Edit: For clarification, from my first post I've been writing about a program to produce the prime factorization of n using trial division. Although the OP said the original goal was merely to decide prime vs. composite, the functionality of the program posted by the OP was to produce all the prime factors with multiplicity, so that's what I went by. Obviously the decision problem is easier and simpler. This might have contributed to my code seeming "horrible."
    Last edited by undefined; April 20th 2010 at 03:17 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by superdude View Post
    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:
    Unless you are dealling with very large numbers or speed is of the essense keep it simple:

    Code:
    function IsPrm(num)
    //
    //  psuedo-code for crude primallity testing
    //
    //  assumption: num is an integer type
    //
       if (num<=1)
         return false
       end
     
      if (num==2)
         return true
      elseif (mod(num,2)==0)
         return false
      end
     
      for idx=3 to floor(sqrt(num)) step 2
           if mod(num,idx)==0
              return false
           end
      end
     
      return true
     
    endfunction
    There are more efficient ways to do it but do you need efficiency?

    CB
    Follow Math Help Forum on Facebook and Google+

  8. #23
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by CaptainBlack View Post
    Unless you are dealling with very large numbers or speed is of the essense keep it simple:

    Code:
    function IsPrm(num)
    //
    //  psuedo-code for crude primallity testing
    //
    //  assumption: num is an integer type
    //
       if (num<=1)
         return false
       end
     
      if (num==2)
         return true
      elseif (mod(num,2)==0)
         return false
      end
     
      for idx=3 to floor(sqrt(num)) step 2
           if mod(num,idx)==0
              return false
           end
      end
     
      return true
     
    endfunction
    There are more efficient ways to do it but do you need efficiency?

    CB
    I realize that both my logic and style where very poor for this program. I have written a much more elegant prime factoring program and if you like I can post it. Efficiency is not an issue, if it was I'd use this. My question that I'm asking is why do certain numbers crash the program?
    Follow Math Help Forum on Facebook and Google+

  9. #24
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by superdude View Post
    I realize that both my logic and style where very poor for this program. I have written a much more elegant prime factoring program and if you like I can post it. Efficiency is not an issue, if it was I'd use this. My question that I'm asking is why do certain numbers crash the program?
    I don't have a definitive answer (debugging your code slows down my system so it's a bit of a pain), but your two functions call each other a huge number of times in general, so maybe there is a situation where a stop condition is accidentally skipped and you are left with infinite recursion. If I were you I would introduce global variables to keep track of function calls, and periodically print out the values of the key variables, either as soon as the function is called, or within the loops, or both, to try to catch runaway recursion. In the process you might spot an issue such as integer overflow, if such a problem exists. And of course, infinite recursion is essentially the same as an infinite loop, which might be the culprit.
    Follow Math Help Forum on Facebook and Google+

  10. #25
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by undefined View Post
    I don't have a definitive answer (debugging your code slows down my system so it's a bit of a pain), but your two functions call each other a huge number of times in general, so maybe there is a situation where a stop condition is accidentally skipped and you are left with infinite recursion. If I were you I would introduce global variables to keep track of function calls, and periodically print out the values of the key variables, either as soon as the function is called, or within the loops, or both, to try to catch runaway recursion. In the process you might spot an issue such as integer overflow, if such a problem exists. And of course, infinite recursion is essentially the same as an infinite loop, which might be the culprit.
    The strange thing is with 15999 the program crashes even if the first thing is to print something to the screen. That is if step 1 is print("hello world") the program will not do that for 15999.
    Follow Math Help Forum on Facebook and Google+

  11. #26
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by superdude View Post
    The strange thing is with 15999 the program crashes even if the first thing is to print something to the screen. That is if step 1 is print("hello world") the program will not do that for 15999.
    Then perhaps the error lies somewhere outside the block of code you posted, because I ran it as-is and never got that problem.

    I find it extremely unlikely that my version of PHP would behave that much differently from yours and that it's a bug with the PHP interpreter, although I suppose it can't be ruled out entirely without further testing.
    Follow Math Help Forum on Facebook and Google+

  12. #27
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    This is my new version. I'm looking for criticism:
    [PHP]
    <?php
    $num = 15999;
    if($num%2 != 0 && $num%3 != 0 && isPrime($num))
    {
    print($num.' is prime');
    exit;
    }
    print('The primefactorization of '.$num.' is:<br />');
    checkSmallPrimes($num, 2);//factors out 2s
    checkSmallPrimes($num, 3);//factors out 3s
    for($i = 5; $i <= floor(sqrt($num)); $i += 2)
    {
    if(isPrime($i))
    {
    while($num%$i==0)//having this as a while loop instead of if increases efficency
    {
    $num = $num/$i;
    print($i.'<br />');
    }
    if(isPrime($num))
    {
    print($num);
    exit;
    }
    }
    }

    /*returns true if agrument is prime greater than 3, otherwise returns false*/
    function isPrime($maybePrime)
    {
    for($j = 3; $j <= floor(sqrt($maybePrime)); $j += 2)
    if($maybePrime%$j == 0)
    return false;
    return true;
    }

    //$num is being passed by reference
    function checkSmallPrimes(&$num, $smallPrime)
    {
    while($num%$smallPrime==0)
    {
    $num /= $smallPrime;
    print($smallPrime.'<br />');
    }
    }
    ?>[/PHP]
    Last edited by superdude; April 22nd 2010 at 10:54 PM. Reason: changed $j = 3 in isPrime
    Follow Math Help Forum on Facebook and Google+

  13. #28
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by undefined View Post
    Then perhaps the error lies somewhere outside the block of code you posted, because I ran it as-is and never got that problem.

    I find it extremely unlikely that my version of PHP would behave that much differently from yours and that it's a bug with the PHP interpreter, although I suppose it can't be ruled out entirely without further testing.
    I said it only happens using EasyPHP 1.8. I've reproduced the problem on different computers (with different architecture) so you must be doing something wrong.
    Follow Math Help Forum on Facebook and Google+

  14. #29
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by superdude View Post
    I said it only happens using EasyPHP 1.8. I've reproduced the problem on different computers (with different architecture) so you must be doing something wrong.
    Sorry, I missed that part. I've never had to debug a language interpreter before, and I don't intend to replace my current PHP with one that is potentially buggy, so I guess I won't be of much help on that.

    Quote Originally Posted by superdude View Post
    This is my new version. I'm looking for criticism:
    A small consistency issue: It seems that the program says "$num is prime" when $num is prime and > 3, but if $num == 2 or $num == 3, it will output its prime factorization rather than telling you it's prime.

    I don't understand why you treat 3 as a special case; you could just start your loops at 3 instead of 5. The reason I treated 3 as special was because my increment scheme avoided multiples of 3 other than 3, thus I checked the numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ... where the differences between two successive terms are 2 and 4 alternating, but starting with 5. This is just an optimization.

    Also, I'm not sure if this is a real optimization or not, but I tend to pre-calculate the loop limit floor(sqrt($blah)) as another variable to prevent re-calculating the same thing many times -- possibly a given compiler/interpreter would do this anyway, depends on how smart it is I guess.

    There's another inefficiency I noticed: you call isPrime() from within the main for() loop (the one that's not contained in a function), and you start trial division over at 5, but in reality it's impossible to have factors between 5 and $i of the main loop because you've divided them out already.

    Also, you only call checkSmallPrimes() twice, but the while() loop inside your main for() loop has identical code. If you're going to encapsulate that code as a function, you might as well just call checkSmallPrimes() each time, possibly renaming it to reflect what it does more closely.

    One final optimization I can see is that, for composite $num, at the beginning you call isPrime() and trial divide by 2 and all odd numbers up to sqrt($num), and then you do the exact same thing (starting at 5) in the main for() loop. It would be more efficient to keep a boolean value for primality, starting it at true and then setting it to false as soon as a factor < $num is found, thus combining the two loops into one.

    One last very small point is that using the variable name $maybePrime inside a function called isPrime() seems redundant to me.

    Hope you don't mind my tearing apart your code... it's all meant constructively.
    Follow Math Help Forum on Facebook and Google+

  15. #30
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by undefined View Post
    Sorry, I missed that part. I've never had to debug a language interpreter before, and I don't intend to replace my current PHP with one that is potentially buggy, so I guess I won't be of much help on that.



    A small consistency issue: It seems that the program says "$num is prime" when $num is prime and > 3, but if $num == 2 or $num == 3, it will output its prime factorization rather than telling you it's prime.

    I don't understand why you treat 3 as a special case; you could just start your loops at 3 instead of 5. The reason I treated 3 as special was because my increment scheme avoided multiples of 3 other than 3, thus I checked the numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ... where the differences between two successive terms are 2 and 4 alternating, but starting with 5. This is just an optimization.

    Also, I'm not sure if this is a real optimization or not, but I tend to pre-calculate the loop limit floor(sqrt($blah)) as another variable to prevent re-calculating the same thing many times -- possibly a given compiler/interpreter would do this anyway, depends on how smart it is I guess.

    There's another inefficiency I noticed: you call isPrime() from within the main for() loop (the one that's not contained in a function), and you start trial division over at 5, but in reality it's impossible to have factors between 5 and $i of the main loop because you've divided them out already.

    Also, you only call checkSmallPrimes() twice, but the while() loop inside your main for() loop has identical code. If you're going to encapsulate that code as a function, you might as well just call checkSmallPrimes() each time, possibly renaming it to reflect what it does more closely.

    One final optimization I can see is that, for composite $num, at the beginning you call isPrime() and trial divide by 2 and all odd numbers up to sqrt($num), and then you do the exact same thing (starting at 5) in the main for() loop. It would be more efficient to keep a boolean value for primality, starting it at true and then setting it to false as soon as a factor < $num is found, thus combining the two loops into one.

    One last very small point is that using the variable name $maybePrime inside a function called isPrime() seems redundant to me.

    Hope you don't mind my tearing apart your code... it's all meant constructively.
    You have some valuable suggestions. Can you elaborate on how your increment scheme avoids multiples of 3 and how you know you won't miss any primes in between? So how do you know alternating between adding 2 and 4 skips multiples of 3? I'm busy today so I'll consider your suggestions in more depth and post back in a day or two.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 3 FirstFirst 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