The Wilson formula states that:
iff p > 1 and p is prime then:
!(p-1) ≡ _1 (mod p)
I used the following to determine if 13 was prime.
!(13-1) =&(13&|) _1
1
I got the same answer when I tried to see if 3 was prime.
Maybe I am missing something. Am I using _1 when I should
not be? If so, how do I test for primality with the Wilson
routine?
I know it works, because I have cut/paste others code and
saw it work.
----- Original Message Follows -----
From: Tracy Harms <[email protected]>
To: Programming forum <[email protected]>
Subject: Re: [Jprogramming] how to speed up 2^N where N >
10,000,000
Date: Sat, 28 Feb 2009 17:48:50 -0800
>Hi, Butch,
>
>Several tests to determine whether a number is prime are
>detailed in the J wiki, here:
>
>http://www.jsoftware.com/jwiki/Essays/Primality%20Tests
>
>The Wikipedia article on Wilson's theorem says:
>"Wilson's theorem is useless as a primality test in
>practice, since computing (n - 1)! modulo n for large n is
>hard, and far easier primality tests are known"
>
>That recognized, we can of course code that test in J. Hope
>it doesn't deflate any of your efforts to do so for me to
>post my solutions here.
>
> wilsonX=: verb :'=/ y | _1 , ! y-1x'"_1
> wilson0=: (] | _1:) = ] | 1x !...@-~]
>
> }.I. wilsonX i. 55
>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
> }.I. wilson0 i. 55
>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
>
> NB. compare:
> I. 1 p: i.55
>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
>
>It's important to note that p: is a primary verb within J.
>Beyond that, the tests on the previously mentioned wiki
>page may the most applicable to your quest.
>
>Tracy
>-----------------------------------------------------------
>----------- For information about J forums see
>http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
