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.

Quote:

---

Originally Posted by superdude

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

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 ?

This was one of the first programs I made and it was a number of years ago. My style was very poor(Doh)
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.

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)

Quote:

---

Originally Posted by Bacterius

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

Quote:

---

Originally Posted by superdude

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 for some . is exponential time

CB

Quote:

---

Originally Posted by CaptainBlack

Polynomial time is for some . is exponential time

CB

---

So n depends on the input and k depends on the algorithm (program)?

Quote:

---

Originally Posted by superdude

So n depends on the input and k depends on the algorithm (program)?

---

is the length of the input and is specified by the algorithm used (can sometimes be variable with computation/memory tradeoffs).

Quote:

---

Originally Posted by Bacterius

is the length of the input and 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'?

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.

Quote:

---

Originally Posted by superdude

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

Quote:

---

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.

2702811 also crashes the program. I notice 3 is a common factor in both cases.

Quote:

---

Originally Posted by superdude

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

Quote:

---

Originally Posted by CaptainBlack

"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 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"?