# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
DrJones
Posted: Sun Jan 15, 2006 1:07 am    Post subject: 1

Yeah, it can't find primes over 2209 with just 64 bit integers.

However, to test if 523 is prime, for example, it has to perform just 6 mod operations:

(223092870 = 2x3x5x7x11x13x17x19x23 has been calculated in previous steps)
223092870 mod 523 = 421 (this is the only operation involving big numbers)
523 mod 421 = 102
421 mod 102 = 13
102 mod 13 = 11
13 mod 11 = 2
11 mod 2 = 1 (this step proves 523 is prime)
2 mod 1 = 0 (this step is superfluous)
Greatest common divisor = 1 --> 523 is prime.

while the classic sieve has to perform 8 mod operations and 8 additional reads from arrays/files (it can avoid doing 8 comparations with sqrt(523) if it searchs the list backwards, though):

23 > sqrt(523)
19 < sqrt(523)
523 mod 19 = 10
523 mod 17 = 13
523 mod 13 = 3
523 mod 11 = 6
523 mod 7 = 5
523 mod 5 = 3
523 mod 3 = 1
523 mod 2 = 1
Stop. 523 is prime.

So, yes. My algorithm becomes soon impractical for standard integers, and it is still a naive method, which is not a good way for finding primes. The doubt is if it is faster in time than old sieve. The euclidean algorithm has time O(n^2) for two consecutive Fibonacci numbers, but that is not likely to happen except at the very beginning. On average, it takes O(12 ln 2/pi^2 ln n) == O(0.843 ln n).

Erathostenes sieve takes O(N log log N), as seen on http://portal.acm.org/citation.cfm?id=62072.
extro...*
Posted: Sun Jan 15, 2006 12:59 am    Post subject: 0

extro...* wrote:
I think this method is called the Seive of Erathostenes.

No, it's spelled Eratosthenes, and it's a different algorithm.
extro...*
Posted: Sat Jan 14, 2006 11:35 pm    Post subject: -1

DrJones wrote:
4. It has a variable Y which starts at 1, which stores the multiplication of all primes up to sqrt(X), at least.

This quickly becomes a big number to store, and if you find a way to store it outside of using standard 32 or 64 bit integers (Java big integers are ideally simple, but then Java has built in efficient methods for primality testing), it will also be a big number to work with. You're going to want to determine if some other number X is coprime with this number. Given this number is a product of primes in your list, it would likely be far more efficient to just check whether X is divisible by any of those primes - iff it isn't, it is coprime with the product.

So, you have a list of N-1 primes (initially [2,3]). To determine the Nth prime,

Let the Nth number be the (N-1)th number, plus 2.
Test if it is prime by testing for divisibilty by all numbers in the list <= the square root of the one being tested. If you find a divisor, add 2 to the Nth number and repeat test. Continue adding 2 until you find a number with no divisor in the list (checking up to its square root).

I think this method is called the Seive of Erathostenes.
old grey mare*
Posted: Sat Jan 14, 2006 9:11 pm    Post subject: -2

DrJones wrote:
"Nx + (N-1)!y = 1"

has always a solution for "y = (-1)"
I have no way to prove this, of course. If it were true, it would simplify my equation a lot.

This looks like Wilson's Theorem
DrJones
Posted: Sat Jan 14, 2006 8:43 pm    Post subject: -3

Cool! Thank you very much

I've been testing the Program that calculates the Bezout Relation.

From what I've seen, it looks that for N>2 prime, the Bezout Relation

"Nx + (N-1)!y = 1"

has always a solution for "y = (-1)"
I have no way to prove this, of course. If it were true, it would simplify my equation a lot.

(N-1)! = Nx - 1 where x is in Z, for N prime.

In other words, there exists a number x in Z such that:

x = (N-1)!/N + 1/N for N prime. (this shows that x > 0)

Which is true if (N-1)! mod N = N-1 for every N prime. I can't prove if this is true, either.

Finally, to know if for N prime, (1+N!) is prime, I have to test if (1+N!) is coprime with... ((N!)!) (gosh!)

u(1+N!) - (N!)! = 1.
u(1+Nx-1)) - (Nx-1)! = 1.
uNx - (Nx-1)! = 1.
uNx = 1 + (Nx-1)!.
u = 1/Nx + (Nx-1)!/Nx.

If I name "Nx = z" then,

u = 1/z + (z-1)!/z.

So, u will be an integer if "(z-1)! mod z = z-1" for z prime.

EDIT: This equals to "(z-2)! mod z = 1" for z prime.

I can only say... Wow!!
CrystyB
Posted: Sat Jan 14, 2006 6:45 pm    Post subject: -4

Factoris says that:
Code:
1!+1 = 3 is a certified prime;
2!+1 = 3 is a certified prime;
11!+1 = 39916801 is a certified prime;
37!+1 = 13763753091226345046315979581580902400000001 is a probable prime.
DrJones
Posted: Sat Jan 14, 2006 1:24 pm    Post subject: -5

Thank you!

I thought I could use Bezout's Identity to start finding big primes soon. It seems that it won't work.

extro...* wrote:

"Anyway, I think a better (but equivalent) definition, at least for basing a naive prime testing or generation algorithm on, would be:

Being N>1 an integer, N is said to be prime iff it is not divisible by any prime (equivalently integer) A <= sqrt(N)"

I already know that, I just thought it would be more difficult to explain myself that way.

Take a look at my algorithm:

-------------------------------------------------
1. It has a read pointer to the beginning of a list of prime numbers.
2. It has a write pointer to the end of a list of prime numbers.
3. It has a variable X with the current candidate for primality testing.
4. It has a variable Y which starts at 1, which stores the multiplication of all primes up to sqrt(X), at least.
5. It has a "cyclic" array that keeps the next value that will be added to the current candidate to get the next candidate (this is made so it only tests numbers ending in 1, 3, 7 or 9 that aren't multiple of 3).

The algorithm moves the read pointer and reads the next prime A on the list, it multiplies Y for A, and stores the value A^2 in a variable Z.

Function Write_Prime(X)
It writes the number X at the end of the prime list.

Function coprime(X,Y)
It applies the Euclidean or the Binary GCD algorithms (Y being the larger number), and returns TRUE if the greatest common divisor of X and Y is 1.

Function Next_candidate
It adds to X the next value on the array, to get the next candidate for primality testing.

Main Function

1. Read_Next (to get the first prime in the list, the list can't start empty)
2. loop
2.1. while (X > Z) Read_Next
2.2. if coprime(X,Y) Write_Prime(X)
2.3. Next_candidate

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

I don't know if it will be more (or less) efficient than the classic naive method, though.
old grey mare*
Posted: Sat Jan 14, 2006 3:18 am    Post subject: -6

Yes. Bezout's Identity says that for A, B coprime there exists u,v such that uA+vB=1. It does NOT say that for all u there exists a v such that uA+vB=1. Maybe that is your confusion.
extro...*
Posted: Sat Jan 14, 2006 12:47 am    Post subject: -7

Quote:
I was resolved in getting something from that equation, though, so I started assigning values to the variables:

For u=0 ...

I'm missing the part where you can just assign a value to the variables. We know that for N a prime, there exist x,y,u and v such that uy + Nu - N^2ux + Nv - N^2xv = y.

How do you get that u can be 0?

Anyway, I think a better (but equivalent) definition, at least for basing a naive prime testing or generation algorithm on, would be:

Being N>1 an integer, N is said to be prime iff it is not divisible by any prime (equivalently integer) A <= sqrt(N)
DrJones
Posted: Fri Jan 13, 2006 7:36 pm    Post subject: -8

I was designing a naïve iterative algorithm for finding primes, based on the following idea:

Being N>1 an integer, N is said to be prime iff it is coprime with every integer A <= sqrt(N)", that implies that N is prime iff it is coprime with the number M resulting of multiplying every number from 1 to the first number greater than sqrt(N) (However, I will use (N-1)! instead of mul(sqrt(N)), as it looks easier to explain).

By Bézout's identity, we have that there exist integers X and Y such that xN + y(N-1)! = 1.
This implies that (N-1)! = (1-Nx)/y (for y!=0).

Now, I was interested in knowing which values of N satisfy that, for N prime, (1 + N!) is prime.

Using Bézout's identity again, I get u(1+N!) + v(N!) = 1.
Replacing (N-1)!... u(1+N(1-Nx)/y) + v(N(1-Nx)/y) = 1.
Cleanup step... u + (Nu - N^2ux)/y + Nv/y - N^2xv/y = 1.
After multiplying by y... uy + Nu - N^2ux + Nv - N^2xv = y.

Which is a mess. I was resolved in getting something from that equation, though, so I started assigning values to the variables:

For u=0 --> Nv - N^2xv = y (y != 0)
For x=1 --> Nv - N^2v = y (y != 0)

However, the last equation always work for any N distinct of 0 or 1, which has to be wrong because (1 + 5!) = 121 = 11^2, and therefore it's not prime.

I must have made a mistake somewhere.