Page 3 of 3 FirstFirst 123
Results 31 to 34 of 34

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

  1. #31
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by superdude View Post
    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.
    $inc is initalialised as 2. Then after each loop iteration, $inc = 6 - $inc results in the sequence 2, 4, 2, 4, ...

    All multiples of a prime are composite. The idea of skipping even numbers greater than 2 is that they are all congruent to 0 (mod 2), meaning they are all multiples of 2. Thus, it is perfectly safe to skip all multiples of 3 greater than 3 without fear of skipping any primes.

    The reason the incrementation scheme works is that, we start with 5, which is congruent to 2 (mod 3). We add 2, which results in 2 + 2 = 4 is congruent to 1 (mod 3). Next we add 4, which is congruent to 1 (mod 3). 1 + 1 = 2 is congruent to 2 (mod 3). This is a cycle with period 2. In addition, we are guaranteed to avoid all multiples of 2 because we are always performing 1 + 0 = 1 is congruent to 1 (mod 2). It can be seen that it is not possible to choose numbers lower than 2, 4, 2, 4, ... with the desired properties, thus we skip only multiples of 2 and 3 greater than 2 and 3, respectively.

    Possibly it looks easier considering everything mod 6, but it is up to preference. What we are doing is picking all the numbers that are congruent to 1 or 5 (mod 6).

    If we wanted to be very ambitious, we could work out an incrementation scheme that avoids multiples of 5 greater than 5, and so on. However, optimization often comes at the cost of legibility of code.

    Note that a very bad way to avoid multiples of 5 is to test $i % 5. This is because % is a computationally expensive operation, compared with + and - which are computationally cheap.
    Follow Math Help Forum on Facebook and Google+

  2. #32
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    Quote Originally Posted by undefined View Post
    We add 2, which results in 2 + 2 = 4 is congruent to 1 (mod 3). Next we add 4, which is congruent to 1 (mod 3). 1 + 1 = 2 is congruent to 2 (mod 3).
    I'm confused. If we have 4 then add 4 we get 8, which isn't congruent to 1 (mod 3) unless I'm mistaking. I may understand this better if you can give me a generalized formula where multiples of x are skipped.

    Also, with respect to % not being resource intensive is it the same in other languages or just PHP?

    Quote Originally Posted by undefined View Post
    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.
    Are you sure? I don't check 5 in the checkSmallPrimes method. In the in the main loop $i starts at 5 but there's no reason to assume it's prime. I added the checkSmallPrimes method partly because it can be expanded, for example it could be fed a file containing a list of prime numbers.

    Thanks for the advice about calculating the square root of $num outside the body (signature?) of the loop.
    Last edited by superdude; April 22nd 2010 at 11:28 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #33
    Senior Member
    Joined
    Jun 2009
    Posts
    251
    This is the program in pseudo-code. I'm looking for criticism to the design of the program and my pseudo-coding technique
    Code:
    Conventions
    1.	:= denotes an assignment e.g. x:=6
    2.	== <= => < and > are comparison operators: equals, less than or equals, greater than or equals, less than, greater than, respectively
    3.	% denotes modulus operator e.g. 15%4 is 3
    
    
    
    
    Function main
    
    Terms and conditions
    0.1	this function called first
    0.2	assume num is a positive integer
    
    START
    1.if(num == 2  OR num == 3 OR isPrime(num)) then
    1.1 	output “num is prime”
    1.2	 GOTO END
    1.3 end if
    2.doFactor(num, 2)
    3.doFactor(num, 3)
    4.set sqrtOfNum := sqrt(floor(num))
    5.set i := 5
    6. while(i <= sqrtOfNum) do
    6.1 	set i:=i+2
    6.2 	if(isPrime(i)) then
    6.3 .1 		doFactor(num, i)
    6.3.2 		if(num == 1 OR isPrime(num)) then
    6.3.2.1			if(num ≠ 1) then
    6.3.2.2				display num
    6.3.2.3			end if
    6.3.3			GOTO END
    6.3.4		end if
    6.4	end if
    7. end while
    8. END
    
    Function isPrime
    argument: maybePrime
    return: true iff maybePrime is prime, otherwise false
    
    Terms and Conditions
    0.1	assume maybePrime is a positive integer
    
    START
    1.  set sqrtOfMaybePrime := floor(sqrt(maybePrime))
    2.  set j := 3
    3. while(j <= sqrtOfMaybePrime) do
    3.1	set j:=j+2
    3.2	if(maybePrime%j == 0) then
    3.2.1		return false
    3.2.2		GOTO END
    3.2.3	end if
    3.3	 return true
    4. end while
    5. END
    
    Function doFactor
    arguments: &num, determinedToBePrime
    return: none 
    
    Terms and Conditions
    0.1	num is passed by reference such that any changes made to it in this function, will still hold once this function has returned
    0.2	assume num is a positive integer that is to be factored
    0.3	assume determinedToBePrime is a positive integer that has been established to be prime
    
    START
    1.  while(num%determinedToBePrime == 0) do
    1.1 	set num := num/determinedToBePrime
    1.2 	display “determinedToBePrime”
    2. end while
    3.END
    well if anyone cares I found the answer to my question here
    Last edited by superdude; May 1st 2010 at 05:41 PM. Reason: added italics, underline, bold
    Follow Math Help Forum on Facebook and Google+

  4. #34
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Sorry for taking so long to reply. I've been traveling and busy with projects.

    Quote Originally Posted by superdude View Post
    I'm confused. If we have 4 then add 4 we get 8, which isn't congruent to 1 (mod 3) unless I'm mistaking. I may understand this better if you can give me a generalized formula where multiples of x are skipped.
    I checked it over and it's written properly, but to make it easier to follow I probably should have used LaTeX; I was just a bit lazy to write all those [ math] tags.

    Start with: 5 \equiv 2\ (mod\ 3)

    After first increment: 2 + 2 \equiv 4 \equiv 1\ (mod\ 3)

    After second increment: 1 + 4 \equiv 1 + 1 \equiv 2\ (mod\ 3)

    Leading to a cycle of 2, 1, 2, 1, 2, 1, ... (mod 3).

    I don't have a generalized formula where multiples of x are skipped. But I can tell you how I would look for an incrementation scheme for skipping multiples of 5.

    In this case, considering moduli 2, 3, and 5 separately is cumbersome, so instead consider modulus 2*3*5 = 30. We want the numbers that are not multiples of 2, 3, or 5. It's not hard to list them:

    1, 7, 11, 13, 17, 19, 23, 29 (mod 30)

    The way I got this list was simply to write out the numbers 1 through 29 on paper and cross out multiples of 2, 3, and 5. If you've worked with sieves before, then this will feel familiar. In this case, we went up to 5, which happens to be the floor of the square root of 30, so we are left with the number 1 and all the primes greater than 5 and less than 30.

    Now we look at the differences between terms in the above list. We start with 7. (The first "4" below corresponds to 11 - 7 = 4).

    4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, ...

    where the bold part is the second cycle.

    We will have to go through some hoops in order to produce that sequence with only addition and subtraction. One possible way (I don't know if the fastest) is to introduce a new variable that keeps track of where we are in the cycle.

    [php]
    <?php
    if ($_GET['n']) {
    if (is_numeric($_GET['n'])) {
    echo '(Note: casting input to int.)<br /><br />'; // refine later
    $n = (int)$_GET['n'];
    if ($n < 2) {
    echo 'You have entered a number that is not in range.';
    exit;
    }
    }
    else {
    echo 'You have entered a value that is not numeric.';
    exit;
    }
    }
    else {
    echo 'You have not entered a number.';
    exit;
    }
    $origN = $n;
    $facts = '.';
    echo 'The prime factorization of ' . $n . ' is:<br /><br />';
    for ($i = 2; $i < 6; $i += ($i == 2) ? 1 : 2) {
    while ($n % $i == 0) {
    $facts .= $i . '.';
    $n /= $i;
    }
    }
    $lim = floor(sqrt($n));
    for ($i = 7, $inc = 6, $cyc = 8; $i <= $lim; $i += $inc, $cyc++) {
    if ($n % $i == 0) {
    $facts .= $i . '.';
    $n /= $i;
    while ($n % $i == 0) {
    $facts .= $i . '.';
    $num /= $i;
    }
    $lim = floor(sqrt($n));
    }
    // set increment
    if ($cyc == 8) {
    $cyc = 0;
    $inc = 4;
    }
    else {
    if ($cyc > 4) {
    $inc = 8 - $inc;
    if ($cyc == 5) $inc += 2;
    }
    else $inc = 6 - $inc;
    }
    }
    if ($n != 1) $facts .= $n . '.';
    echo trim($facts, '.');
    if ($origN == $n || $origN == 2 || $origN == 3 || $origN == 5)
    echo '<br /><br />Prime!';
    ?>
    [/php]
    As you can see, the code becomes less legible the more you do this. I've never used this optimization personally, just wrote and tested it to make this post. At some point, it's easier and/or more practical to abandon trial division and use other algorithms (like these).

    Quote Originally Posted by superdude View Post
    Also, with respect to % not being resource intensive is it the same in other languages or just PHP?
    You changed my meaning, what I said is that % is computationally expensive compared with + and -, and this is not specific to PHP. I don't know the details of how % is translated into CPU instructions, all I know is that it uses a lot of clock cycles, like integer division.

    Quote Originally Posted by superdude View Post
    This is the program in pseudo-code. I'm looking for criticism to the design of the program and my pseudo-coding technique
    Code:
    Conventions
    1.    := denotes an assignment e.g. x:=6
    2.    == <= => < and > are comparison operators: equals, less than or equals, greater than or equals, less than, greater than, respectively
    3.    % denotes modulus operator e.g. 15%4 is 3
    
    
    
    
    Function main
    
    Terms and conditions
    0.1    this function called first
    0.2    assume num is a positive integer
    
    START
    1.if(num == 2  OR num == 3 OR isPrime(num)) then
    1.1     output “num is prime”
    1.2     GOTO END
    1.3 end if
    2.doFactor(num, 2)
    3.doFactor(num, 3)
    4.set sqrtOfNum := sqrt(floor(num))
    5.set i := 5
    6. while(i <= sqrtOfNum) do
    6.1     set i:=i+2
    6.2     if(isPrime(i)) then
    6.3 .1         doFactor(num, i)
    6.3.2         if(num == 1 OR isPrime(num)) then
    6.3.2.1            if(num ≠ 1) then
    6.3.2.2                display num
    6.3.2.3            end if
    6.3.3            GOTO END
    6.3.4        end if
    6.4    end if
    7. end while
    8. END
    
    Function isPrime
    argument: maybePrime
    return: true iff maybePrime is prime, otherwise false
    
    Terms and Conditions
    0.1    assume maybePrime is a positive integer
    
    START
    1.  set sqrtOfMaybePrime := floor(sqrt(maybePrime))
    2.  set j := 3
    3. while(j <= sqrtOfMaybePrime) do
    3.1    set j:=j+2
    3.2    if(maybePrime%j == 0) then
    3.2.1        return false
    3.2.2        GOTO END
    3.2.3    end if
    3.3     return true
    4. end while
    5. END
    
    Function doFactor
    arguments: &num, determinedToBePrime
    return: none 
    
    Terms and Conditions
    0.1    num is passed by reference such that any changes made to it in this function, will still hold once this function has returned
    0.2    assume num is a positive integer that is to be factored
    0.3    assume determinedToBePrime is a positive integer that has been established to be prime
    
    START
    1.  while(num%determinedToBePrime == 0) do
    1.1     set num := num/determinedToBePrime
    1.2     display “determinedToBePrime”
    2. end while
    3.END
    well if anyone cares I found the answer to my question here
    Glad you got an answer to your question.

    Regarding your pseudo-code: the general style looks pretty good to me, but I think it could be a good idea to do away with the step numbers altogether, since they are easily inferred from context. You could keep the numbering in the terms and conditions parts, replacing 0.1, 0.2, ... with 1, 2, ... And if you want to refer to some particular line, it's enough to have a text editor or text display mechanism that shows the line number before each line. The display on this forum doesn't have line numbers presently, but if you go to Pastebin.com, you can see the line numbers are made visible.

    In your function isPrime(), line 3.2.2 GOTO END is dead code, because after the return statement in 3.2.1, this line will never be executed.

    You'll notice that you skipped the prime 5 in the main loop, because you initialise to 5 but increment it to 7 before doing anything with it.

    Checking isPrime(i) in line 6.2 is completely unnecessary. The reason is that if i is composite, it is composed of smaller primes that we will already have divided out of our number. That is, if i is composite then it has no possibility of dividing the number.

    It might benefit you to take a break from trial division and work with sieves, then after you've mastered that, review your trial division algorithm. You may understand the concepts more intuitively and see how things could be improved, simplified, optimised.
    Follow Math Help Forum on Facebook and Google+

Page 3 of 3 FirstFirst 123

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum