## it works!

Expand Messages
• the following program tries to determine the primality of a number by combining two tests into one, avoiding the usual pseudo-prime situ- ation: 10 cls 20
Message 1 of 5 , Feb 5, 2008
the following program tries to determine the primality of a number by
combining two tests into one, avoiding the usual pseudo-prime situ-
ation:

10 cls
20 input N
30 NN= int((N-1)/2)
40 X= (2^N-3^NN-(N-1)) mod N
50 Y = N mod 5
60 print N;X
70 if (X=2 or X=4) and Y<>0 then print "prime"
80 goto 10

it inevitably misses the 2, 3, and 5, but catches all the rest as far
as I can test it.

my computer is somewhat outdated, but it told me that there were 168
primes before the number 1001, when I used this code inside a for-
loop.

i am aware of the law of small numbers, but can anyone realistically
find a flaw or counter-example in this unproven technique ???

Bill B.
• ... Well, it fails on even numbers, for one. Additional failures occur a bit later on odd numbers: x y Error at 1729 2 4 Error at 2821 2
Message 2 of 5 , Feb 5, 2008
leavemsg1 wrote:

> the following program tries to determine the primality of a number by
> combining two tests into one, avoiding the usual pseudo-prime situ-
> ation:
>
> 10 cls
> 20 input N
> 30 NN= int((N-1)/2)
> 40 X= (2^N-3^NN-(N-1)) mod N
> 50 Y = N mod 5
> 60 print N;X
> 70 if (X=2 or X=4) and Y<>0 then print "prime"
> 80 goto 10
>
> it inevitably misses the 2, 3, and 5, but catches all the rest as far
> as I can test it.
>
> my computer is somewhat outdated, but it told me that there were 168
> primes before the number 1001, when I used this code inside a for-
> loop.
>
> i am aware of the law of small numbers, but can anyone realistically
> find a flaw or counter-example in this unproven technique ???

Well, it fails on even numbers, for one.

Additional failures occur a bit later on odd numbers:

x y
Error at 1729 2 4
Error at 2821 2 1
Error at 7921 2 1
Error at 8911 4 1
Error at 13699 4 4
Error at 15841 2 1
Error at 18721 2 1
Error at 29341 2 1
Error at 31621 2 1

Sorry.

--
Alan Eliasen | "Furious activity is no substitute
eliasen@... | for understanding."
http://futureboy.us/ | --H.H. Williams
• ... Hopefully for Bertrand, he didn t say that. If I m supposed to be finding counterexamples and errors today, that single sentence contains a treasure
Message 3 of 5 , Feb 6, 2008
Danny Fleming wrote:
> Bertrand's postulate proved that there are at least two primes from x
> to 2x for any integer.

Hopefully for Bertrand, he didn't say that. If I'm supposed to be
finding counterexamples and errors today, that single sentence contains
a treasure trove.

You may also wish to mention how you believe it related to the
messages that you replied to.

--
Alan Eliasen | "Furious activity is no substitute
eliasen@... | for understanding."
http://futureboy.us/ | --H.H. Williams
• Assuming N odd, First counter-examples with their prime factors : 1729 { 7, 13, 19} 2821 { 7, 13, 31} 7921 { 89} 8911 { 7, 19, 67} 13699 { 7, 19,
Message 4 of 5 , Feb 6, 2008
Assuming N odd, First counter-examples with their prime factors :

1729 { 7, 13, 19}
2821 { 7, 13, 31}
7921 { 89}
8911 { 7, 19, 67}
13699 { 7, 19, 103}
15841 { 7, 31, 73}
18721 { 97, 193}
29341 { 13, 37, 61}
31621 { 103, 307}
32761 { 181}
41041 { 7, 11, 13, 41}
46657 { 13, 37, 97}
49141 { 157, 313}
52633 { 7, 73, 103}
63973 { 7, 13, 19, 37}
64177 { 29, 2213}
75361 { 11, 13, 17, 31}
83333 { 167, 499}
93961 { 7, 31, 433}
115921 { 13, 37, 241}
126217 { 7, 13, 19, 73}
129481 { 11, 79, 149}
162401 { 17, 41, 233}
.......
if( N < 10 000 000) whe have 123 failures.

Regards,
JT

>the following program tries to determine the primality of a number by
>combining two tests into one, avoiding the usual pseudo-prime situ-
>ation:

10 cls
20 input N
30 NN= int((N-1)/2)
40 X= (2^N-3^NN-(N-1)) mod N
50 Y = N mod 5
60 print N;X
70 if (X=2 or X=4) and Y<>0 then print "prime"
80 goto 10

>it inevitably misses the 2, 3, and 5, but catches all the rest as far
>as I can test it.

>my computer is somewhat outdated, but it told me that there were 168
>primes before the number 1001, when I used this code inside a for-
>loop.

>i am aware of the law of small numbers, but can anyone realistically
<find a flaw or counter-example in this unproven technique ???

>Bill B

---------------------------------------
http://www.echolalie.com
---------------------------------------

[Non-text portions of this message have been removed]
• Hello Bill, ... Slightly less programatic description of the test: If both 1) N must not be divisible by 5, and 2) 2^N - 3^((N-1)/2) = 1 or 3 (mod N), then N
Message 5 of 5 , Feb 7, 2008
Hello Bill,

> the following program tries to determine the primality of a number by
> combining two tests into one, avoiding the usual pseudo-prime situ-
> ation:

Slightly less programatic description of the test: If both
1) N must not be divisible by 5, and
2) 2^N - 3^((N-1)/2) = 1 or 3 (mod N),
then N is declared prime.

Clearly, this test is surely not stronger (although it is likely strictly
weaker) than a combination of
1) Divisibility by 5 test,
2) Base 2 Fermat test and
3) Base 3 Euler test
while having about the same time-complexity as these three together (in
fact, performing the step 3 only if step 2 succeeds can improve the
actual speed).

Combining the tests the way you did is usually not a good idea, as you're
losing some potentially useful information. In particular, instead of
checking 2^N = 2 (mod N) and 3^((N-1)/2) = +/-1 mod N, you're just
checking if their difference is equal to something -- which can, unless
proven otherwise, happen a lot more often.

Peter

--
[Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278
Your message has been successfully submitted and would be delivered to recipients shortly.