- 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. - leavemsg1 wrote:

> the following program tries to determine the primality of a number by

Well, it fails on even numbers, for one.

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

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 - Danny Fleming wrote:
> Bertrand's postulate proved that there are at least two primes from x

Hopefully for Bertrand, he didn't say that. If I'm supposed to be

> to 2x for any integer.

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, 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

10 cls

>combining two tests into one, avoiding the usual pseudo-prime situ-

>ation:

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

<find a flaw or counter-example in this unproven technique ???

>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

>Bill B

---------------------------------------

http://www.echolalie.com

---------------------------------------

[Non-text portions of this message have been removed] - Hello Bill,

> the following program tries to determine the primality of a number by

Slightly less programatic description of the test: If both

> combining two tests into one, avoiding the usual pseudo-prime situ-

> ation:

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