## Other

drummers-lowrise

Message boards : General discussion : Newbie question.

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Message 29211 - Posted: 13 Dec 2010 | 11:17:51 UTC - in response to Message 29209.

I don't know but you can look it up here: http://primes.utm.edu/lists/small/millions/

I would do it but I don't have the means to unzip files on this computer.

Oh and 0 and 1 are not a prime because they are not integers greater than 1 with the only positive factors being zero and the number. There are some other fancier answers but this one works for me.

Message 29212 - Posted: 13 Dec 2010 | 11:20:12 UTC - in response to Message 29209.

Primes are defined as being greater than 1, this makes it easy to say things like:

"Any integer greater than 1 can be written as a unique product of prime numbers"

If we allowed 1 then we wouldn't have a unique product as we'd always be able to write things like: 5 = 5, 5 = 5*1, 5 = 5*1*1 etc... And 0 is of no use as a prime as x = y * 0 implies x must be 0.

Best app on the web for determining if some arbitrary number is a prime: http://www.alpertron.com.ar/ECM.HTM

Where you'll find 8579697 = 3 x 7 x 19 x 21503

And is therefore not a prime.

Message 29216 - Posted: 13 Dec 2010 | 12:56:58 UTC - in response to Message 29214.

Hi finnenummer.

You were searching for a Woodall Prime. They have the structure (n × 2^n) − 1 . Cullen Primes are of the form (n × 2n)+ 1 . So those kinds of primes always have the same number repeated. Other kinds of primes don't have this structure. For example Mersenne Primes are (2^n)-1.

Just becasue n is composite it doesn't mean that the whole number is composite as you'll see if you try the Woodall formula where n is 6.

Keep 'em coming.

Cheers!

T

Message 29225 - Posted: 13 Dec 2010 | 15:52:09 UTC - in response to Message 29216.

Although an exercise for the reader is to show:

M = (2^n)-1, where M and n are natural numbers, then if M is prime it implies than n is prime.

Which is a nice 1st year undergraduate problem.

Message 29226 - Posted: 13 Dec 2010 | 16:18:28 UTC - in response to Message 29225.

Although an exercise for the reader is to show:

M = (2^n)-1, where M and n are natural numbers, then if M is prime it implies than n is prime.

Which is a nice 1st year undergraduate problem.

I had 7 years at university* and they never taught me how to demonstrate that.

I'd be interested to see a demonstration of it assuming there is one that some who did A level (ie just pre university) maths** in the 70s could understand.

Cheers!

T

* Mind you I didn't do maths at universtiy
** And I damn nearly passed it.

Message 29252 - Posted: 13 Dec 2010 | 22:46:39 UTC - in response to Message 29250.

Means that M = (2 ^ 9) - 1

M -> 511 - - - 2^9 -1 -> 512 -1 -> 511

511 looks to me to be a prime, but 9 (n) really is 3*3 .

511 is not prime: 511 = 7 * 73

Edit: Should add that of course I do know that computing
8579697*2^8579697-1 gets slightly more difficult than just
3 * 7 * 19 * 21503 .

I guess it may become 1.5 million digits or so. At least I saw that being mentioned for one of the official announcements (.pdf) I had a brief look at.

8579697*2^8579697-1 has log(8579697)+8579697*log(2) = ~ 2582754 digits.
____________   Message 29279 - Posted: 14 Dec 2010 | 14:30:14 UTC - in response to Message 29254.

Indeed you are correct where there are projects designed to find large Mersenne Primes, i.e that of the form M = 2^n -1, they only use known primes for n. As any other numbers are a waste of time and this is provable.

The biggest project to do this was GIMPS, found here: http://www.mersenne.org/

Where they found 2^43112609 - 1, which is a 12,978,189 digit number. The project now exists mainly just to double check that they haven't missed a smaller Mersenne Prime.

Negative, Fractions, Real and Complex numbers are not considered as sets with prime numbers as you can not use them to derive the nice property like:

"Any integer greater than 1 can be written as a unique product of prime numbers"

Message 29282 - Posted: 14 Dec 2010 | 15:45:34 UTC

Hah found the answer to Zurtex's puzzle here http://primes.utm.edu/notes/proofs/Theorem2.html.

I can follow the proof but not clever enough to have deduced it myself.

Cheers!

T

PS Thanks to Steve_Martin for explaining how to put links in.

PPS I enjoyed The Jerk btw

Message 29309 - Posted: 14 Dec 2010 | 21:43:37 UTC - in response to Message 29294.

Hi guys!

Thanks for the link. I will check it out.

Anyway - this means that if 37 is prime, then (2^37) - 1 is also a prime.

M = 137438953471 (or ...472). Someone on my door. You can finish it for me if you want to.

Aren't you looking down the wrong end of the telescope?

Zurtex's proposition was that for

M=(2^n)-1

where M is prime then n will prime.

Your proposition is that where n is prime then M is prime.

If that was true I could automatically generate primes by taking a prime number and putting it in the equation as n. The equation would then spit out a larger prime M which I could put in the equation as a new n and generate a still larger M. I could repeat that for as long as I could find fingers and toes to count on. It is also not true as you will see if try the equation will n having the value of 11.

Cheers!

T

Message 29336 - Posted: 15 Dec 2010 | 9:01:59 UTC - in response to Message 29334.

Yes, I see the difficulty in this. 2047 = 23 * 89 for example.

Edit on this: Shouldn't it suffice to compute 2^n to see if the result is then prime (you have to do the usual routine on that number as well).

If n is either an odd number or a prime number itself, maybe the chances are bigger that the 2^n (or really (2^n) -1 is a prime number.

This goes for big n's of course.

But 2^n is never prime*! I'm not sure I follow you.

*Except where n=1

Message 29360 - Posted: 15 Dec 2010 | 11:31:38 UTC - in response to Message 29355.

Bear in mind my mathematical training ended after some maths for undergraduate chemists classes in the 1970’s. I’m probably not the person best able to comment but hey! that is not going to stop me!

One of the reasons for primes fitting a formula is the fact that they do is interesting.

Another reason is that the general test for a prime of dividing by all possible factors takes an awfully long time once you get to really big numbers. Potential primes which satisfy some formulae are quick to search for. This is the reason why the largest known primes are Mersenne primes; there is an efficient method of testing for them.

Proth primes are of the form P=(k.2^n)+1. An example is (1924.2^13018586)+1.

Message 29363 - Posted: 15 Dec 2010 | 12:11:12 UTC - in response to Message 29360.

One of the reasons for primes fitting a formula is the fact that they do is interesting.

The bigger reason for OUR primes fitting a formula is that there's no known way of testing for primality of large arbitrary prime numbers in a reasonable time (i.e., before the universe ends).

The primality tests we use only work because of the work of some truly brilliant mathematicians were figured out a way of testing the primality of numbers of particular forms, specifically those that fit those formulas.

We can test numbers from those formulas. We can not test those that are not in those formulas. So, all the numbers you'll see here will always be expressed as formulas.

Undoubtedly, there's many more primes that don't fit those formuals, but we have no way of testing them.
____________
My lucky number is 75898524288+1

Message 29407 - Posted: 15 Dec 2010 | 20:40:23 UTC - in response to Message 29355.

Can you give me an example of a couple of Proth Prime Search numbers right here so I easily can discern that fact. They apparently never are prime numbers regardless how they are put up.

Plenty of the numbers searched in the Proth Prime Search project are prime - if they were never prime we wouldn't be searching! There are some on this page for example :
http://www.primegrid.com/primes/?section=primelist&userid=51439

Note that you well never find any primes on the Proth Prime Search (Sieve) project, which you have been crunching on - but what you will do is cheaply eliminate lots of non-primes from the big list of potential Proth Numbers we still have to search!

- Iain

Message 29411 - Posted: 15 Dec 2010 | 21:10:29 UTC - in response to Message 29386.

Hi Tim!

You meant with your posting, last line, the multiplication or what I interpret or use as the "*". You wrote "." That goes for the same, right ?

Meaning whole number(s), not fractional ones.

I get the sense that you may perhaps treat even vs. odd numbers a little different than what is common use or standard or practice elsewhere.

Am I right in that assumption ?

Could I add: While I was away, I get an error message now for pps_sr2_sieve_X
(at least two different tasks in CUDA) saying "exited with zero status but
no finished file.

New version is 1.36 which I had two of yesterday in non-CUDA. Those CUDA-tasks were 1.35.

Thanks!

Hi finnenummer.

Yes indeed I was using using * as a multiplication symbol because x can be a little ambiguous.

Iain who is a very much better mathematician and computer chap than me (who isn't?) has I think dealt with one of your other points. I'm not clever enough to deal with the others.

Cheers!

T

Message 30017 - Posted: 27 Dec 2010 | 0:24:30 UTC

Factoring a number and to a lesser extent working out if a number is prime or not is one of the most computationally challenging traditional problems.

However, in the last 200 years or so working out if a number is prime or not a "primality test" has got a lot easier thanks to a lot of clever mathematicians. Working out if a "fairly random number" (refereed to as arbitrary) is prime is still quite hard but there's a good method called the AKS test of primality.

However there are even better tests for very specific numbers that match a very specific pattern, these are the ones tested on PrimeGrid. Because the tests are easier it means much much larger numbers can be tested.

The seive tests use a clever algorithm to try and quickly show if a number is composite (not prime), GPUs are fantastic at this algorithm and hence why they are able to show so quickly that so many numbers are composite. In fact I am quite sure that the algorithm, and the programming language below it, will improve at least 10 fold yet. GPUs however are not as good at showing that a number is prime and we will have to rely on CPUs for this.

Message boards : General discussion : Newbie question.