Thread: What's so special about this composite number

Originally Posted by superdude

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.

Originally Posted by undefined

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?

Originally Posted by undefined

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.

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

Sorry for taking so long to reply. I've been traveling and busy with projects.

Originally Posted by superdude

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:

After first increment:

After second increment:

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).

Originally Posted by superdude

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.

Originally Posted by superdude

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.