Fun with Prime Numbers

Steve Litt writes "Fun With Prime Numbers contains a series of prime number finding algorithms starting with the most brute force imaginable, and working up to a paged algorithm capable of finding the first 1,716,050,469 primes in an hour and a half on a commodity machine. There are faster algorithms on the net, but these algorithms are within the reach of mere mortals and are fully explained."

Comments

Obligatory

[zedmelon]

This article will be a prime target for bad jokes.

Re:Obligatory

[spellraiser]

Don't worry ... I've got a grenade primed, ready to blow all the bad jokes to smithereens.

Re:Obligatory

[Anonymous Coward]

I'm primed.

Re:Obligatory

[zedmelon]

Ha ha, yeah! Now that's what I'm talking about! ;)

Re:Obligatory

[Anonymous Coward]

We must not be divided on this issue.

Re:Obligatory

[Anonymous Coward]

1337 i5 prm3...

Re:Obligatory

[jaywarrietto]

How exactly do you prime a grenade?
Don't you mean I've taken the pin out? Oh that wouldn't be funny though.

Re:Obligatory

[dtfinch]

7*191=1337

Re:Obligatory

[Anonymous Coward]

Sorry

Re:Obligatory

[dtfinch]

0x1337 is prime

Re:Obligatory

[Trejkaz]

Luckily when it comes to the quality of a Slashdot comment, bad jokes don't factor into it.

Re:Obligatory

[eclectro]

This article will be a prime target for bad jokes

It's true. Good jokes come alomg only so often, and we don't know when.

Re:Obligatory

[conan776]

God sieve us from these bad puns....

Re:Obligatory

[Surazal]

Not only don't we know when, we don't remember the last time, either.

Re:Obligatory

[Hognoxious]

Yes, they'll certainly be abundant, especially from the people who are deficient. Still, I shouldn't complain - nobody's perfect.

Re:Obligatory

[Ice_Balrog]

Our primeary focus must be to avoid them...

Re:Obligatory

[Anonymous Coward]

Oh fuck off you humorless dickhead k thx bye.

Re:Obligatory

[secretsquirel]

This is a prime example of my theory;

Secretsquirel's 1st theorum: The set of all possible replies to a given topic contain an infinite number of funny replies (prime replies) spaced exponentially furthur and furthur apart.

When people reply, as the funny replies get more and more used up, they take more and more comedic procesing to find and thus a smaller and smaller percent of all attempts turn out to be primes. Also, certain functions seem too output a higher than average number of prime replies. Interestingly such functions also seem to output a high number troll replies as well.
But dammit I just can't prove it!!

Re:Obligatory

[Mattcelt]

Hey, wait a minute - it's not redundant, they're twins!!

Re:Obligatory

[Infinityis]

Or if we shall be divided, let it be by one among us, or by our very selves.

Re:Obligatory

[Anonymous Coward]

It's true. Good jokes come alomg only so often, and we don't know when.

but every so often, they come in pairs at a spacing of two

Re:Obligatory

[Bush Pig]

You probably need a bigger margin - no, wait, that's a different conjecture. Damn!

Re:Obligatory

[0x00000dcc]

0x1337 is prime

Sadly, my slashdot user id is not.

Re:Obligatory

[acidblood]

So is 31337 in decimal.

Re:Obligatory

[Anonymous Coward]

although there are clearly not an infinite number of them

Re:Obligatory

[goatan]

How exactly do you prime a grenade? Don't you mean I've taken the pin out? Oh that wouldn't be funny though.

Take the pin out release the handle and your grenade is primed, you might want to throw it after that.

Re:Obligatory

[jaywarrietto]

oh I guess I'm just ignorant I didn't mean the flame.

Where is it?

[TamMan2000]

I got a 404...

Re:Where is it?

[zedmelon]

Google Cache

Re:Where is it?

[canwaf]

Sorry, 404 isn't a prime number. Try again.

Re:Where is it?

[Baelrun]

I got a 404.. That's not a prime number. No wonder the algorithm is so fast.

Re:Where is it?

[Anonymous Coward]

503 Service Unavailable

Math Deities?

[Anonymous Coward]

"There are faster algorithms on the net, but these algorithms are within the reach of mere mortals and are fully explained."

So there are math gods out there?

Re:Math Deities?

[Anonymous Coward]

yes, satan.

Re:Math Deities?

[Anonymous Coward]

Yes. I am one. Worship me, or i'll prove to you that 2 is an odd number.

Re:Math Deities?

[Anonymous Coward]

Admit it, you're a freshman engineering or CS student who cooked up that proof one night when you couldn't finish your calc homework, and as much as you've told people how cool you are for finding a proof that 2 is odd, you haven't bothered to consider that 2 is not odd by definition, and that therefore there must me something wrong with your proof.

Go back to algorithms class, and leave the heavy number crunching to the real math gods.

This begs the question:

[Anonymous Coward]

Why not just save primes on a disk instead of recalculating them all the time?

Re:This begs the question:

[Anonymous Coward]

Why waste disk space with primes instead of just recalculating them?

Re:This begs the question:

[XipX]

Thats been done too:
http://primes.utm.edu/links/lists_of_primes/small_ primes/first_n_primes/

Re:This begs the question:

[psetzer]

Actually, in the final implementation, I thought that he does that. It creates a few thousand files, each one containing n primes, and then it goes through each previous file up to the square root of the largest number in the current file, and then it quits and goes to the next file. If you want to duplicate this guy's efforts, I think that the biggest help for this would be a REALLY fast HD array and lots of RAM.

Re:This begs the question:

[Dasein]

There are a lot of them.

As a matter of fact 2048 bits can represent numbers up to 2^2048 ~= 3.23x10^616. By the Prime Number Theorem there is about 2.27x10^613 primes in that space. If each prime required 2048 bits to store, then storing all the 2048 bit primes requires more petabytes then you and I are likely to ever see.

(Jeez I hope I didn't do the math wrong. The most convenient calc I have available to me as I write this in the Windows calc)

Re:This begs the question:

[KillerCow]

Why not just save primes on a disk instead of recalculating them all the time?

Because it's faster to calculate all of the small primes in memory than to read them off of disk. At least it was not too long ago.

Re:This begs the question:

[Goalie_Ca]

Why waste time or space?

Re:This begs the question:

[Anonymous Coward]

there is about 2.27x10^613 primes in that space

"there are".

Re:This begs the question:

[Omniscient Ferret]

On my computer, generating primes from 2 to 2^32 takes a third of the time to unbzip2 the same list.

Re:This begs the question:

[Anonymous Coward]

just because there are a lot of them doesn't mean you cant fit them all on a disk. you just need the right representation. first, you could try mapping the set of primes to the set of integers. that way, 2048 bits could represent any one of the first 2^2048 primes. but it would still take a countably infinite amount of disk space to store all of them so we'll have to try harder. one idea is to just keep using the same 2048 bits over and over again. but this can get kind of tedious and repetitive. so the ultimate representation is to just use one bit to represent the presence of the set of prime numbers. so whenever you need a prime number, just turn that little bit on and you have all of them.

since this is slashdot, i'm hoping to get modded up as informative or insightful for clearing up this little problem that all the experts have somehow overlooked. as a regular reader, i feel that they owe me.

Re:This begs the question:

[maxwell demon]

Indeed, the number of particles in the universe is assumed to be approximately 10^85, so if you would store one bit per particle, you'd need about 5*10^530 universes to store all those primes. Hell, even if you stored at every single particle as many bits as there are particles in the universe, you'd still need 5*10^445 universes.

Of course that's assuming you stupidly write all those numbers individually down, using the whole 2048 bitf or each number. Now what if we compress the table?

The complete list can, of course, be stored in a bitfield with 2^2048 individual bits which tell if a given number is prime or not (e.g. 1 means the number is prime, 0 means it's not). Now, of those 3.23*10^616 bits, about 2.27*10^613 bits are 1. So a simple approximation would be to treat the bits as independent, with each one having a probability of (2.27*10^613)/(3.23*10^616)=7.03*10^-4 of being 1. So if we neglect all correlations of the bits, we get an information of about 0.0084 bits per bitfield bit, which means we can compress to about 2.7*10^614 bits. That is, even neglecting all correlations (even the trivial ones of all even numbers except 2 being non-prime) we get only about 12 bits per prime. That's substantially less than the 2048 bits per prime we'd need with straightforward storage. Of course, we would still need an insane number of universes to store our table :-)

Now, of course we know that we can "compress" the full table very well to a small prime-finding program which fits nicely on even a single floppy (but would take longer to "decompress" than we are willing to wait), so the list of primes doesn't actually contain too much information (indeed, the program can compress the whole infinite prime table - decompression of course needs unlimited ressources, then -, therefore the average information content of a single prime is obviously zero).

Re:This begs the question:

[StyroCupMan]

If each number only has a 0.000703 chance of being prime, we can simplify this whole calculation with this function (pseudo-coded):

boolean isPrime(int Number) {
return false;
}

That function is 92.97% accurate. That's an A-. Good enough for me. :)

Re:This begs the question:

[Dasein]

Thanks for doing the conversion to universes -- I couldn't remember the number of particles in the universe. It's the night before my midterm.

Anyway, how about units of Library of Congresses? :-)

Re:This begs the question:

[nova20]

Why waste time or space?

Prime numbers are our friends. They help us with several issues in computer science, not the least of which is encryption.

check out post #10773458

-nova20

Re:This begs the question:

[Infinityis]

Which raises the question: Why beg the question when you can raise the question? http://www.wsu.edu:8080/~brians/errors/begs.html

Re:This begs the question:

[dalleboy]

Well, if I'd had a quantum computer, I'd show you the entire list of primes.

Re:This begs the question:

[Darby]

there is about 2.27x10^613 primes in that space

"there are".

No need to be so formal:
"there're"

Re:This begs the question:

[ImprovOmega]

Or at least, it was the entire list of primes until you observed it. Now it's resolved into Richard Simmons's grocery list - thanks a lot!

Re:This begs the question:

[trilliwig]

From http://www.utm.edu/research/primes/prove/prove2_1. html

"[The sieve of Eratosthenes] is so fast that there is no reason to store a large list of primes on a computer--an efficient implementation can find them faster than a computer can read from a disk." ;)

Re:This begs the question:

[Anonymous Coward]

First off, don't store the primes in ASCII.
Secondly, try it with 64bit.
Thirdly, try it with gzip and compare the sizes.

Ugliest. Brace. Style.

[onallama]

EVER!!!

Re:Ugliest. Brace. Style.

[Anonymous Coward]

Actually, the brace style is just about perfect.
I wish that more people would use this very sensible method (left and right braces at same indent level, braces on lines by themselves, braces indented form parent). There are only two ways that it could be made better:
1. Set tab stops to every two characters, instead of every 8.
2. Have an extra indent level after the braces (i.e., braces occupy their own indent levels).

Here is an example, with dots and "b"s (stupid lamenes filter) representing spaces:

int myfun(int arg)
b {
b.b if (arg < 0)
b.b.b {
b.b.b.b (void)printf("Arg < 0\n");
b.b.b.b return -1;
b.b.b }
b.b else if (arg == 0)
b.b.b {
b.b.b.b (void)printf("Arg == 0\n");
b.b.b.b return 0;
b.b.b }
b.b else
b.b.b {
b.b.b.b (void)printf("Arg > 0\n");
b.b.b.b return 1;
b.b.b }

Re:Ugliest. Brace. Style.

[Anonymous Coward]

Yay! I've finally found someone else who does it the way that I do ... (well, the way that emacs seems to do it by default).

Re:Ugliest. Brace. Style.

[ajs318]

You'd think someone would have come up with a feature in a text editor for tidying up the alignment of posh brackets to conform to preferences, so this sort of thing wouldn't be an issue. My second-favourite editor, Kate, already highlights corresponding opening and closing brackets, be they round, square or posh ..... surely a tidier can't be far off. Maybe in KDE4!

Anyway, my personal preference is for the opening posh bracket to be on the same line as the loop control statement {if/while/foreach &c.}, all the stuff inside the loop indented by 4 spaces, and the closing posh bracket lined up with the first letter of the loop control statement above, on a line by itself {well, maybe a trailing semicolon; but definitely not } else { all on one line -- that's just minging}. I believe this is the original K&R style. Fewer than 4 spaces doesn't look indented enough {this may not be a problem unless you want to use a last if ...}, and more than 4 spaces takes up too much room without adding clarity. {In Perl, I like my trailing ifs and unlesses to line up.}

For me, indenting is all about indicating what belongs together and where natural breaks occur. Bits of programmes are like paragraphs. Putting the opening { on a line by itself wastes a line {in writing, if you start a new paragraph with an indent, you don't need a blank line as well}. I briefly flirted once with the idea of placing the closing bracket on the end of the last indented line. This was compact, but had the slight disadvantage of causing my code to look like Python ..... Also, I always expected there to come a {nearly} blank line after the loopy bit, so things weren't broken up quite so neatly.

Re:Ugliest. Brace. Style.

[ThJ]

/* I prefer to indent like this: */

if(1)
{
char *dumbString = "This is a test.";
puts(dumbString);
}

/* I think this is messy: */

if(1)
{
char *protest = "I hate messy indentation.";
puts(protest);
}

/* Now, I often do this: */

if(fsin(90) == 1 && fsin(0) == 0 && 1)
puts("My computer knows it's math.\n");

So I *might* accept the following:

if(trunc(M_PI) == 3)
{
printf("My name is... my name is... my name is...");
printf(" %s\n", argv[0]);
}

/* That would make for a more consistent style. I prefer to keep the brackets at the if() level, though, because it makes it much easier to find the conditional statement that starts a block, if the block enclosers are on the same level at the statement. You don't need to do any mental jumps to the left or the right, you just follow a straight line. */

Re:Ugliest. Brace. Style.

[ThJ]

Oh drat... That's supposed to be "its", not "it's"... *blushes in utter shame*

Re:Ugliest. Brace. Style.

[Yeochee]

The typo actually makes sense. A computer is math: it does nothing but add/subtract/or/and bits.

I'm prime!

[Anonymous Coward]

I'm number 1!!!!!

Re:I'm prime!

[Anonymous Coward]

Silly liar. 1 is not a prime. Get back to being the multiplicative identity, ok? Isn't that good enough for you?

What is special about prime numbers?

[Dancin_Santa]

I understand that number sequences like Fibonacci manifest themselves in Nature and others like pi provide a fairly decent random number generation method. However, aside from the interesting property that they can't be divided by anything other than themselves and 1, I do not 'get' what is interesting or useful about prime numbers.

But then again, I haven't studied mathematics to any great extent beyond the multi-var calc and linear algebra back in high school. That was such a long time ago. Any math Geniuses out there want to clue is in on why primes are interesting?

Re:What is special about prime numbers?

[dshaw858]

They have a lot of use in cryptography, which is certainly very useful.

/me shakes a fist at Big Brother

- dshaw

Re:What is special about prime numbers?

[Omkar]

They pop up a lot in number theory. For examply, Euler proved that the sum of all the integers is equal to the product of all the primes. (I'm not sure if that's important, but I thought it was a good example of how they tend to pop up).

Re:What is special about prime numbers?

[onallama]

Well, considering that all positive integers > 1 are either prime themselves (e.g., 2, 3, 5, 7, 11...), or if not, can be expressed as the product of various primes (e.g., 4 = 2 * 2, 6 = 2 * 3, 8 = 2 * 2 * 2, 9 = 3 * 3, 10 = 2 * 5...), you could say that prime numbers are the building blocks of all integers, which is kind of cool...

Re:What is special about prime numbers?

[MillionthMonkey]

Brief overview. There is also the Prime Spiral.

Re:What is special about prime numbers?

[notthe9]

That's just a result of the definition of primes.

Re:What is special about prime numbers?

[magefile]

The sum of all of *which* integers and *which* primes? Or do you mean, the limit of (1 + ... + n) as n=>infinity is equal to the limit of (p_1 * ... * p_n) as n => infinity?

Re:What is special about prime numbers?

[miskatonic alumnus]

The proof that the sum of all the POSITIVE integers equals the product of all the primes is quite trivial: Their common value is infinity.

Re:What is special about prime numbers?

[Jazzer_Techie]

I do not 'get' what is interesting or useful about prime numbers.

Prime numbers are useful in encyption, but those are very large primes that are difficult to factor. To a mathematician, prime numbers are fascinating. The distribution of primes, which is specifially random but generally predictable (check out the MathWorld article for more details) is of particular interest.

For example, the Riemann Zeta Function of n, which is the infinite sum of all terms k^(-n)[k varies from one to infinity], is expressable as the infinite product (1-p1^(-n))*(1-p2^(-n))*(1-p3^(-n))... [where pn is the nth prime number]. This is a mind-boggling connection. For example Zeta(2)= (pi^2)/6 = (1 + 1/2 + 1/4 +1/8 ...)= ((1-2^(-2))*(1-3^(-2))*(1-5^(-2))...) There is therefore a connection between pi and the distribution of the primes. Math is crazy stuff.

Re:What is special about prime numbers?

[Anonymous Coward]

Primes are the building blocks of the multiplicative structure of positive integers. Take your slashdot user id as an example. 265275 = 3 * 3 * 3 * 3 * 5 * 5 * 131, decomposed as the product of primes as if primes were lego blocks. This works for any positive integer.

Re:What is special about prime numbers?

[Anonymous Coward]

He probably means that {sum of 1/n^x} = {product of 1/(1-1/p^x)}, where n runs over all integers, p runs over all prime numbers, and x > 1.

Re:What is special about prime numbers?

[miskatonic alumnus]

I don't know how interesting this will be to you, but for each positive integer n there is a finite ring called Z_n or the integers mod n that consists of the integers 0 through n-1 inclusive. Addition, subtraction, and multiplication work the same as in the set of integers, EXCEPT all results are modulo n.

For example, in Z_8, 15*3 = 45 = 5 since the remainder of 45 upon division by the modulus 8 is 5. Strange things can happen in some of these rings. For example, in Z_8 we have 2*4 = 0. Here, 2 and 4 are called zero divisors. Neither 2 nor 4 have reciprocals in this ring, so we cannot form the quotient 3/2 for instance.

Here is the interesting part having to do with primes. If, and only if, p is prime, then Z_p is actually a FIELD, meaning that every nonzero element has a reciprocal element. This implies that there can be no zero divisors in Z_p, and that the ring is closed under division (except for dividing by zero, of course). I believe there are some computer applications of finite fields.

Re:What is special about prime numbers?

[rubee]

It has applications in abstract algebra (like group theory) and number theory. Besides cryptography, they are often used in pseudo-random number generators and hash tables. check out: http://en.wikipedia.org/wiki/Prime_numbers

Re:What is special about prime numbers?

[Anonymous Coward]

Primes are very useful in cryptography. In fact, many of today's cryptographical routines depend on primes utterly...

Re:What is special about prime numbers?

[mvdw]

I'm sorry, do you mean aleph 0, aleph 1, or some other (higher) value of infinity? And can you prove it?

Re:What is special about prime numbers?

[onallama]

Perhaps, but the statement that every positive integer can be written as a unique product of prime numbers is known as the Fundamental Theorem of Arithmetic -- so I'd still consider it worth knowing. ;-)

Re:What is special about prime numbers?

[spuzzzzzzz]

aleph-0 probably. The sum one is easy; it's a countable sum of finite numbers so if you looked at it as a union of sets, it would be countably infinite. I'm not too sure about the product one, but I think that the countable direct product of finite sets is countable, which would make the product of countably many numbers countably infinite.

Re:What is special about prime numbers?

[miskatonic alumnus]

I mean the standard lemniscate belonging to the extended real number system commonly used in Calculus and Real Analysis. I was not referring to transfinite cardinal arithmetic.

Re:What is special about prime numbers?

[Anonymous Coward]

Not taking your geek card, but you made the Bill Gates mistake, the numbers public key cryptographers are interested in are very large numbers with only two prime factors (besides the number and 1). I've never known anyone who couldn't factor even the largest prime numbers. : )

Re:What is special about prime numbers?

[notthe9]

Worth knowing, yes. It does, however, stem directly from what primacy means.

Basic logic:

for some number, it is either prime or a product of two numbers

those numbers are either prime or a product of numbers

those numbers are either prime or a product of numbers...

and so on. Until all the numbers being multiplied are prime, they can always be factored into numbers that can be factored further (which meet the same criteria) or are prime.

Since primes are integers that cannot be factored, they are clearly going to be the ones left.

Re:What is special about prime numbers?

[Anonymous Coward]

Hand in your geek membership card. now.

Re:What is special about prime numbers?

[Anonymous Coward]

For example Zeta(2)= (pi^2)/6 = (1 + 1/2 + 1/4 +1/8 ...)= ((1-2^(-2))*(1-3^(-2))*(1-5^(-2))...)

Let's see: (pi^2)/6 = 2 = a product obviously smaller than 1.

Math is crazy stuff.

When it comes out of your keyboard it is.

Re:What is special about prime numbers?

[Omkar]

I believe so, even though (as the AC reply says) I may be horribly wrong. I just remember something along those lines.

Re:What is special about prime numbers?

[N Monkey]

Here is the interesting part having to do with primes. If, and only if, p is prime, then Z_p is actually a FIELD, meaning that every nonzero element has a reciprocal element. This implies that there can be no zero divisors in Z_p, and that the ring is closed under division (except for dividing by zero, of course). I believe there are some computer applications of finite fields.

You forgot to mention all the powers of primes, i.e. P^N, also form Fields (aka Galois Fields). It's these that are major of interest in computing because you typically work with 8, 16, or 32 bits, i.e. 2^N.

For example, the error correction on CDs (Harddisks?) and digital television (DVB), uses Reed-Solomon codes which are based around these fields, usually 2^8.

Re:What is special about prime numbers?

[Anonymous Coward]

Prime numbers are useful in encyption, but those are very large primes that are difficult to factor.

1*p

That was easy.

Re:What is special about prime numbers?

[Anonymous Coward]

"very large primes that are difficult to factor."

I can go even further and say that those large primes are IMPOSSIBLE to factor!

Re:What is special about prime numbers?

[pAnkRat]

The interseting part here is that is says:
"a unique combination of prime numbers"

which translates to:

There are no 2 different multiple produkts of primes which result in the same integer.

(broken axample:)

3 * 5 * p != 7 * 11

For any prime number p

Re:What is special about prime numbers?

[miskatonic alumnus]

Your phraseology is a little ambiguous. You are not talking about Z_n except for the case where n is p^1 for some prime p. Also, the SET of powers of a prime is not finite, hence not a Galois Field. More general Galois Fields are extensions fields of Z_p for prime p, and it can be shown that they have p^n elements for some positive integer n. However, a discussion of the details of these fields is a little more involved.

Re:What is special about prime numbers?

[Smokybfgs]

Throughout history, mathematicians have been fascinated with prime numbers - the sheer concept of indivisibility is one aspect (I mean, here they have numbers of infinite possible size that cannot ever be taken down into smaller whole units), and at the same time, these primes are the building blocks of all other numbers. Many great mathematicians have talked of prime numbers and developed more theories on them. Euclid proved there was an infinite number of prime numbers (basically showing that given any number of prime numbers, he could create a bigger prime number, or a number who had as a factor a prime number not included in this n). Riemann had his famous zeta function about the distribution of primes. We've named a great piece of beef after them (ok, not really, but I couldn't help the corny joke). Long story short, prime numbers seem fascinating (at least to me) because they are the building blocks, they are indivisible, and they seem to appear at random (that is, unless we can prove the Riemann Hypothesis) :-) That said, I concede prime numbers hold very little interesting value to many of those who find math too blah (the distribution of prime numbers mystery is hardly the mystery of the fate of Atlantis!)

Re:What is special about prime numbers?

[ColdGrits]

" I'm sorry, do you mean aleph 0, aleph 1, or some other (higher) value of infinity? "

I'm sorry, but there is only one infinity.
It does not have a value (by definition).

You can not have multiple infinities, again by definition, no matter how much you want to pretend that the alep series are all kinds of infinity.

Re:What is special about prime numbers?

[yerfatma]

Mom wants you home by 7. We're having Stove Top.

Re:What is special about prime numbers?

[Anonymous Coward]

Told.

Re:What is special about prime numbers?

[i2hsu]

There are different sizes of infinity. In the context of number system, infinity does not exist... it cannot be treated as a number. In the context of measuring sizes of sets, infinity does exist, and some infinity is larger than others. Say you have the set of all real numbers R, and the set of all natural numbers N. Clearly, R and N are both infinite in size, but the size of R is larger than that of N. It is a weird concept at first. ;)

Re:What is special about prime numbers?

[N Monkey]

Your phraseology is a little ambiguous.

Sorry, yes, I was a little lax with my phrasing, but this is Slapdash, isn't it?

Perhaps I should have said something like you can form a field of order p^N, by representing the elements by the set of polynomials with cooefficients belonging to a base field of order p, with the elements of the p^N field taken modulo a polynomial of order N that is irreducible over the base field.

I only brought it up because I was doing some worj on Reed-Solomon en/decoding recently.

Re:What is special about prime numbers?

[Anonymous Coward]

Ummm, by your formula Zeta(n)=k^(-n), Zeta(2)= (1 + 1/4 + 1/9 +.....).

Re:What is special about prime numbers?

[Fenris Ulf]

On the contrary, very large primes are trivial to factor!

Anyways, the grandparent was probably talking about the product of two very large primes, which is difficult to factor.

Re:What is special about prime numbers?

[ColdGrits]

Nope, it's not a "wierd concept", it'#s simply erroneous thinking, erroneously applying finite concepts to infinite ones.

Simplistic mistake to make, but doesn't alter things. There is only one infinity.

There are not a series of larger and smaller infinities - by definition they are NOT infinite!

Re:What is special about prime numbers?

[i2hsu]

It is not erroneous. While it may not be intuitive, it is correct. I have learned this in both my stats and combinatorics course during my second year at University of Waterloo.

For more info, I found this page using Google: http://mathforum.org/library/drmath/view/59138.htm l

Re:What is special about prime numbers?

[ColdGrits]

Nope, it is definitly erroneous.

You (and the web site) are both applying finite concepts to infinity.

It doesn't work like that, though. By definition.

Sure, the term infinite has been adopted and redifined and treated as an infinitly-large-yet-finite number, but that's just laziness. Infinity itself is infinite, and there is only one of it.

No matter what they teach you back in 2nd year ;-)

I guess we'll not agree though...

Re:What is special about prime numbers?

[notthe9]

That property is also just a factor of the definition: For a simplified case, consider a set that contains more than one unique factoring. In that case, at least one of the factorings must have been split up into factors and applied different places, and therefore was not prime.

Re:What is special about prime numbers?

[Anonymous Coward]

> I guess we'll not agree though...

That is because you are wrong. "In mathematics, a distinction is made between different "grades" of infinity because it can be shown that some infinite sets have greater cardinality than others."

Re:What is special about prime numbers?

[i2hsu]

Which definition are you using exactly? Just curious

When it comes to the set theory, we need to define countable infinity and uncountable infinity.

By larger I don't mean that the value of an infinity is larger than the other. But a particular infinite set can be a larger set than another infinite set (eg. real numbers vs. natural numbers). The sizes of sets are compared using the concept of 1-1 correspondance.

Of course in terms of real analysis, infinity is not a number... so it would be absurd to say one is larger than the other. You are quite right about that.

Re:What is special about prime numbers?

[SillySlashdotName]

I still don't understand how there can be larger and smaller infinities. To my mind, there is only one infinity.

If I had an infinite number of bins numbered from 1 to infinity, then you could not give any listing or formula that would give a number that could not be put into one of the bins.

Non-intuitively, if you defined your set as (two rocks per each bin, each rock put into a separate bin) [2*infinity] they would still fit into the existing bins! [2*infinity=infinity]

A common example is the integer counting numbers (1,2,3,4...). They could be assigned, one to a bin, to my infinite number of bins.

There are an infinite number of decimals between the integer counting numbers (1.1, 1.01, 1.001,...) BUT THEY CAN STILL BE ASSIGNED, one to a bin, TO MY INFINITE NUMBER OF BINS . [infinity * infinity = infinity]

I have not had stats or combinatorics, so can not address what you were taught, but unless one infinitely large set can be larger than another infinitely large set then all infinitely large sets are the same size - by definition.

Any other contention is amphigory, as I see it.

Re:What is special about prime numbers?

[i2hsu]

>>but unless one infinitely large set can be larger than another infinitely large

Yes, some infinite sets are larger than the other. You can measure the sizes of sets using 1-1 correspondance between elements in the set to positive integers. The example I gave is real numbers vs. natural numbers. If you think about it, the set of all real numbes contain the set of al natural numbers... but not the other way around.

Re:What is special about prime numbers?

[ColdGrits]

Yes, but EACH set is infinitely large.

One set is not larger than the other set.

You are still thinking in terms of finite sets...

Re:What is special about prime numbers?

[i2hsu]

Two infinite sets can have diferent sizes.

An example I gave before is real and natural numbers... the set of all natural numbers N is a proper subset of the set of all real numbers R, but R is not a subset of N. So in the language of set theory, R is the larger set containing N.

Re:What is special about prime numbers?

[Darby]

Non-intuitively, if you defined your set as (two rocks per each bin, each rock put into a separate bin) [2*infinity] they would still fit into the existing bins! [2*infinity=infinity]


This is true to a point. How it's actually defined is that 2 sets are the "same size" i.e. your rocks and your buckets if each rock can go into a bucket and no buckets are left empty.

There are an infinite number of decimals between the integer counting numbers (1.1, 1.01, 1.001,...) BUT THEY CAN STILL BE ASSIGNED, one to a bin, TO MY INFINITE NUMBER OF BINS . [infinity * infinity = infinity]

This is where it breaks down.
The problem is that when you try and figure out a way to determine how to assign the real numbers to your buckets (heck even try it with just the numbers between zero and one) you realise that you can not do it.
Even in theory, it is absolutely impossible to determine a way to do this. There are far too many real numbers.

It kind of (i.e. the pedants will roust me for it but it is true enough for purposes of trying to understand it without getting into the details) works like this:

infinity + infinity=infinity
infinity * infinity = infinity
infinity ^ infinity (or even just 2^infinity) = biggerinfinity.

The typical way of proving that there does not exist any way to assign all the real number rocks to the natural number buckets is to assume that you can.

So assume that you have a mapping from the natural numbers onto the reals between 0 and 1.
Onto means that every real between zero and 1 is mapped to.

each real number will be a decimal number in the form 0.abcdxyz......

Heck, even assume that all of the digits are either 2 or 4. This leaves you intuitively with far less numbers. Certainly no more.

So now, if we can create a real number between zero and one whose only digits are 2 or 4, then we have proven that our list is not complete.

So take the first digit of the number 1 maps to. If it is 2, change it to 4. If it is 4, change it to 2.
Go to the second digit of the number mapped to by 2. Do the same thing.

Continue all the way down. Of course it's an infinitely long list, so doing it manually won't work. You can say for every n, if the nth digit of the number mapped to by n is 2 make it 4 else make it 2.

So you have constructed a real number which is between zero and 1 and all of whose digits are either 2 or 4 yet this number is not in your list.

The only assumption that we made is that it is possible to construct a mapping between the natural numbers and this subset of the reals. This assumption alone led to a contradiction, therefore it must be false.

Re:What is special about prime numbers?

[SillySlashdotName]

Think about what you are saying!

You can measure the sizes of sets using 1-1 correspondance between elements in the set to positive integers.

The set of positive integers is an infinite set, agreed? Any "proposed largerst positive integer" can be topped by adding one to the previous integer, so there is no 'largest positive integer'.

A 1-1 correspondence can be set up between any real number and a number in the set of positive integers.

As well, a 1-1 correspondence can be set up between any of the natural numbers and the positive integers.

Therefore the set of real numbers does not have the same set members as the natural numbers, but both sets have exactly the same number of members - i.e., infinity - and are the same size.

Like I said, there are an infinite number of fractions between each positive integer, but they can still be assigned a 1-1 correspondence to the infinite set that is the positive counting numbers.

If I had a computer that could count an infinite number of objects in one second, I could count all the positive integers (an infinite number) in one second. How long would it take to count all the fractions between 1 and 2 (an infinite number)? One second. How long to count all the possible fractions (an infinite number) between all the positive integers (another infinite number)? One second.

If you think about it, the set of all real numbes contain the set of al natural numbers... but not the other way around.

Agreed, but that does not matter. You can still assign a 1-1 correspondence between the positive integers and each member of the set of real numbers, and a 1-1 correspondence to the members of the set of all natural numbers - proving that both infinitely large sets are the same size.

SIZE(a) = SIZE(b) and SIZE(b) = SIZE(c), therefore SIZE(a) = SIZE(c).

Re:What is special about prime numbers?

[i2hsu]

I think we're talking about different concepts of infinity.

The set of all natural numbers N is a proper subset of the set of all real numbers R. So in the lanauge of set theory, R is strictly larger than N.

>>If I had a computer that could count an infinite number of objects in one second, I could count all the positive integers (an infinite number) in one second. How long would it take to count all the fractions between 1 and 2 (an infinite number)? One second. How long to count all the possible fractions (an infinite number) between all the positive integers (another infinite number)? One second.

You are already assuming all infinite sets to be the same size... so it doesn't show anything.

Going back to set theory, there are two types of infinite sets, countable and uncountable. The set of real numbers would be uncountable, while the set of natural numbers would be countable. The set of real numbers is larger than the set of natural numbers, you cannot argue against that.

Re:What is special about prime numbers?

[SillySlashdotName]

VERY interesting!

I still don't buy it, though.

This is, in my estimation, like saying God can do anything, but there are somethings God can't do -God can't make a rock so big God can't lift it - a basic contradiciton found in most religious beliefs in my estimation.

This is where it breaks down.
The problem is that when you try and figure out a way to determine how to assign the real numbers to your buckets (heck even try it with just the numbers between zero and one) you realise that you can not do it.
Even in theory, it is absolutely impossible to determine a way to do this.

Sure you can. Give me any real number between 1 and 2. Write it down on one of these infinite number of pieces of paper. Put that piece of paper in one of these infinite number of buckets. Repeat for all the real number between 1 and 2 without duplicating any. Because there are an infinite number of pieces of paper, you can not come up with more real numbers than there are pieces of paper to write them down on.

There are far too many real numbers.

More than an infinite number? Interesting concept, but I see a logical problem here.

The typical way of proving that there does not exist any way to assign all the real number rocks to the natural number buckets is to assume that you can.

Sounds like you have information or education I don't have. Can you point me toward this information? reductio ad absurdum is a classical technique, I have noy seen it used in this context, though. Links?

You are mapping between MEMBERS of infinite sets and saying they are different, and I am saying the NUMBER of members in two infinite sets (i.e., mapping both sets to the infinite set of positive integers) is the same - both are exactly equal to the number of positive integers. Two things equal to a third thing are equal to each other.

Did you leave something out, as I am not following the logic here -

Heck, even assume that all of the digits are either 2 or 4. This leaves you intuitively with far less numbers. Certainly no more.

So now, if we can create a real number between zero and one whose only digits are 2 or 4, then we have proven that our list is not complete.

I read this to say that we assume that all the digits are either a 2 or a 4, so creating a number whose only digits are 2 or 4, however accomplished, only proves our assumption, and no contradiction that I can see despite your statement that there is one.

Perhaps if you could point me toward some links it would be a faster way to educate me - I am not a math whiz.

Re:What is special about prime numbers?

[Anonymous Coward]

I think you are being trolled. Anyways, it is not absurd to talk about one infinity being larger than another as long as you define what you mean by larger. Similarly, you should know that infinity can be thought of as a number in a formal sense. If I remember correctly, this is explained in chapter 0 of _Real & Complex Analysis_ by Walter Rudin. Oh wait, here is a nice explanation from the wikipedia. You should read Rudin anyways though, it'll put hair on your chest.

Re:What is special about prime numbers?

[Anonymous Coward]

No, it is does not follow directly from the definition of prime. You have only attempted to show that every positive integer can be written as a product of primes. You must also show that this can be done uniquely(for a suitable definition of unique). That is what the fundamental theorem of arithmetic says.

Re:What is special about prime numbers?

[SillySlashdotName]

Again, I find this interesting, but lack the background for affirmming or refuting what you say.

What makes a set uncountable - the fact that there are an infinite number of members? If that is the definition of an uncountable set then all infinite sets are uncountable.

If the definition is that a countable set can be assigned a 1-1 correspondence to the positive integers ("counted") then I can contend that the real numbers can be assigned a 1-1 correspondence with the positive integers and therefore is countable.

Please point me to definitions of 'countable' and 'uncountable' infinities for my edification.

You are already assuming all infinite sets to be the same size... so it doesn't show anything.

The set of real numbers is larger than the set of natural numbers, you cannot argue against that.


Yes I can. There are an infinite number of natural numbers, and an infinite number of real numbers, and an infinite number of positive integers so UNLESS YOU ASSUME INFINITE SETS ARE NOT all the same size, they must all be identical in size.

I agree that, logically, if I have an infinite number of chickens and each lays two eggs then it would seem to require that there be more eggs than chickens, but there is only an infinity of chickens and an infinity of eggs, not (2*infinity) eggs as the statement (2*infinity) makes no sense.

If you (or anyone else) can give links to information on this topic I would be grateful.

Re:What is special about prime numbers?

[i2hsu]

>> If that is the definition of an uncountable set then all infinite sets are uncountable

That's not true... countable and uncountable sets both refer to infinite set.. but that's another topic.

>>If you (or anyone else) can give links to information on this topic I would be grateful.

http://en.wikipedia.org/wiki/Infinity - I love wikipedia.. read the part about infinity in set theory, it talks about countable and uncountable sets.
http://mathforum.org/library/drmath/view/53352.htm l - this page talks about different sizes of infinity

I hope the links help a bit... if you know anyone who knows set theory well you can talk to them... and maybe number theory, I'm not too sure about that (I've only taken one number theory course so far).

Re:What is special about prime numbers?

[Darby]

Sure you can. Give me any real number between 1 and 2. Write it down on one of these infinite number of pieces of paper. Put that piece of paper in one of these infinite number of buckets. Repeat for all the real number between 1 and 2 without duplicating any.


The bolded sentence is the problem.
You need to be able to specify a way to determine the n'th real number you are going to choose.
There isn't a way to do this.

For the integers, it's easy

f(1)=0
for n > 1, n even, f(n)=> -1^n(n/2)
for n > 1, n odd, f(n)=> -1^n((n-1)/2)

so essentially, you are ordering them in a different way.

1=>0
2=>1
3=>-1
4=>2
5=>-2
etc.
this function from the natural numbers to the integers is both one to one (no integer is mapped to by more than one natural) and onto (each integer is mapped to).

Then *by the definition of 2 sets having the same "size"* the set of natural numbers and the set of integers is the same size.

You can do something similar to produce a function from the naturals to the rational numbers that meets those requirements.

For the reals it is different.
Not only can't you find a neat and tidy function that you can write down, but you can prove that it isn't possible for one to exist.

More than an infinite number? Interesting concept, but I see a logical problem here.

There is no logical problem, I think the issue is that you don't know the exact way that these words are defined.

It's not like I am saying that there are 5 integers and that there are 10 real numbers.
When you say that 2 sets have the same size, you are saying that there exists a 1 to one function from one that maps onto the other.
That is the definition.

If you think about, it makes a lot of sense to define it this way. It's your bucket example exactly.
If you can put one and only one thing in each bucket, and everything is in a bucket, then intuitively there are the same "number" of things as buckets.

You are mapping between MEMBERS of infinite sets and saying they are different, and I am saying the NUMBER of members in two infinite sets (i.e., mapping both sets to the infinite set of positive integers) is the same - both are exactly equal to the number of positive integers. Two things equal to a third thing are equal to each other.

Being able to map between the members in a one to one correspondence is how you say that 2 sets have the same number of members.

The size of the integers is known, so testing for 2 different sets to have the same size by comparing each to the integers seperately works just fine.
The problem is that when you try to do this with the reals, you fail every time.

Sounds like you have information or education I don't have. Can you point me toward this information? reductio ad absurdum is a classical technique, I have noy seen it used in this context, though. Links?

This isn't reductio ad absurdum, it is a proof by contradiction.
This works like:
Assume that A is true
This implies B.
This implies C.
C is known to be false, i.e. not C is true

So if you can start out assuming that something is true and it leads you to a contradiction, in this case C and not C then you know that your initial assumption is wrong.


I read this to say that we assume that all the digits are either a 2 or a 4, so creating a number whose only digits are 2 or 4, however accomplished, only proves our assumption, and no contradiction that I can see despite your statement that there is one.

The core assumption isn't that the digits are either 2 or 4, it's that you have created a map from the natural numbers to the reals that is one to one and includes every real.

The trick of making a number out of this list by taking one digit from each of the other numbers and changing it gives you a new number which is not in your list. You know it is not in your list

Re:What is special about prime numbers?

[trilliwig]

No, this is only true in a unique factorization domain (UFD). There are lots of number fields which are not UFDs, in which there can be multiple decompositions into irreducibles.

For example, in the ring formed from sqrt(-5) and the integers closed under addition and multiplication, 6 has two factorizations.

6 = 2.3
6 = (1+sqrt(-5)).(1-sqrt(-5))

None of the factors above can be decomposed any further into non-units in the number field.

Re:What is special about prime numbers?

[notthe9]

I realize that my explanation was deficient to the point of incorrectness. I was trying to provide a heuristic explanation that would help provide some understanding of the uniqueness clause to those who might not be familiar with it. I assumed that those who were not already familiar with it would not be interested in or not able to understand a more formal, comprehensive, correct explanation.

When you get into complex, non-integer values, most people who do not already understand the concept would not gain any understanding.

Re:What is special about prime numbers?

[mvdw]

Well, I think that post sums up the total of your math knowledge.

Re:What is special about prime numbers?

[nebaz]

I'm going to try to give an example of Cantor's diagonalization method, to show that we can create a set which is "bigger" than the set of natural numbers.

Consider the set N, the set of natural numbers and the set X, where X is the set of all infinite binary sequences (i.e. all sequences {a(n),n=0..infinity|a(n) = 0 or 1}

Let's assume we can do a "1 to 1" correspondance between these two sets. If we can, we can find a function f(n) which when applied to the natural numbers will give f(1), f(2), f(3), and supposedly this will generate all members of X.

Let me create a new binary sequence that is not covered by that mapping.

Here is how I am going to create my sequence. For the first number in my sequence, I'm going to look at whatever f(1) is. Maybe it's {0,1,1,1,1,...} whatever. Whatever f(1) has as it's first number, I'm going to use the other number (0 if 1, 1 if 0), as the first number of my new sequence.
For the second number of my new sequence, I'm going to look at f(2), and the number in it's second position, and again, use the "other number".

For the third number in my sequence I'm going to use the "other" number than the third number in f(3), etc....
So for each position f(n), I will use the "other" number than the nth number in f(n).

What this gives me is a sequence that is guaranteed to be different than every f(n) sequence, because the number in position n is different.

Thus I have a new sequence. But this is supposedly impossible, because f(1), f(2), f(3) was supposed to be every sequence.

Thus, no function f exists. Thus this set X can not be put in a 1 to 1 correspondance with the natural numbers. Hope that helps.

Re:What is special about prime numbers?

[trilliwig]

Hm, ok, as long as you were aware of that. But you don't need to introduce the complex domain to get non-unique factorization! Consider the set of positive integers congruent to 1 mod 4.

S = {1, 5, 9, 13, ...}

This is closed under multiplication. 9, 21, and 49 are irreducible in this domain, but 9.49 = 21.21 = 441.

I guess what I'm getting at here is that unique factorization is a truly nifty result that is not at all a tautology. It gives the group of integers some nice structure that we can't count on in the general case. As a matter of fact, Fermat's Last Theorem was almost proved in the 19th century (by both Lamé and Cauchy), but the fatal flaw in their reasoning was that the generalized integers in a field generated from the roots of a polynomial do not necessarily form a UFD.

Re:What is special about prime numbers?

[Bush Pig]

You are quite wrong. Study some set theory some time, or read a few of Cantor's papers, and you'll see why.

Re:What is special about prime numbers?

[miskatonic alumnus]

There are not a series of larger and smaller infinities - by definition they are NOT infinite!

Here is where the issue lies. What is your working definition of infinity?

If you don't like the use of the word "infinity", use "transfinite cardinals" instead. They are indeed numbers --- cardinal numbers. They are well-ordered by less than. Each transfinite cardinal is greater than any finite cardinal. They can be added and multiplied. The set of all cardinals does not exist, but there are sets of distinct transfinite cardinals of any cardinality you like.

Re:What is special about prime numbers?

[miskatonic alumnus]

Okay, here we go (I love this topic).

A little notation is in order: A bijection f from a set A to a set B is a function that is onto, meaning every element b of B has a pre-image a in A, such that f(a) = b; and is one-to-one, meaning that distinct elements of A get mapped to distinct elements of B.

Now, I see from several posts "blah blah blah is/is not infinite by definition". But, the poster(s) supply no definition. In mathematics, the language is very precise. There are (at least) two working definitions of finite, which are equivalent provided we assume the Axiom of Choice:

1) A set is finite if there exists a bijection from the set to the set of counting numbers {1,...,n} for some counting number n.

2) A set is finite if there exists no bijection from the set to a proper subset of itself.

Now, a set is said to be infinite if it is not finite. That is, for an infinite set, there does exist a bijection from the set to a proper subset of itself.

Therefore, all questions regarding whether some set is finite or infinite boil down to the existence or nonexistence of certain bijections.

Now, it turns out that bijections exist between:
The set of Natural numbers and the set of Integers.
The set of Integers and the set of Rationals.

But, no bijection exists between any three of these sets and sets of the form {1,2,...,n} where n is a counting number. So, the sets of Natural numbers, Integers, and Rationals are indeed infinite.

Now, we need another definition. Two sets are said to be cardinally equivalent if there exists a bijection between them. Furthermore, if a set is finite, then the number of elements of the set is called the cardinality of the set. So, the cardinality of the set {8,7,-4,175,111} is 5. So, the finite cardinals are exactly the natural or counting numbers, along with zero.

Now, by a famous proof of Cantor, which I will not repeat here, there exists no bijection from the set of Natural numbers to the set of Real numbers. To fully appreciate the meaning of this statement, we need to talk about ordinal numbers --- truly the foundation of all number systems.

I will not get into the technical details of what makes a set an ordinal. Suffice it to say that the empty set {} is an ordinal. When treated as an ordinal number, we will call the empty set 0, or zero. Now, given any ordinal s, which is a set, we define its successor to be the set s union {s}, which is itself an ordinal. So, the successor to 0 is 0 union {0} or simply {0} which we will call 1, the successor to 1 is the set 1 union {1}, or {0} union {1} or, {0,1} which we will call 2. Likewise, 3={0,1,2}, 4={0,1,2,3}, and so on.

A few nice things happen here, 1 is a subset of 2 is a subset of 3, etc. so the usual order is built in. Also, the ordinal 4 cannot be put in bijection with 3 or 2 or 1 or 0, thus is finite, by the second definition of finite above. However, one of the axioms of set theory, namely the Axiom of Infinity, says that an infinite set exists that includes 0 and the successor of every element of the set. This axiom is what essentially "bounds" infinity, by regarding an infinite collection as a completed thing.

But, just because every successor belongs to this infinite set (the set of natural numbers or finite ordinals) does not mean every ordinal belongs to it. Indeed, this infinite set satisfies the definition of ordinal number, we call it omega. Now, omega has a successor, called "omega + 1" which is omega union {omega} per the previous definition of successor. "Omega + 1" has a successor, "Omega + 2", and so on. None of these ordinals can be put in bijection with any finite ordinal. But they are cardinally equivalent to omega itself. The process continues.

Now, if one assumes the Axiom of Choice, which in turn implies that the real numbers can be well-ordered, then there exists an ordinal that can be put

Re:What is special about prime numbers?

[notthe9]

was almost proved

Almost? I assure you he has a proof! Damn small ledgers...

Re:What is special about prime numbers?

[ColdGrits]

Take your first infinite-sized set. Then take your second infinite-sized set which you claim is larger. You are saying, therefore, than infinity > infinity.

See the flaw yet? You are treating infinite as just another finite value, which is where it's all going wrong.

It is a tricky concept for some to come to grips with, but think about it.

Re:What is special about prime numbers?

[Anonymous Coward]

the reals + infinity + -infinity = hyperreals

rtfm

Re:What is special about prime numbers?

[i2hsu]

I'm not saying that infinity infinity. But one set is strictly larger than the other. Thus, one infinite set is larger than another infinite set. This is set theory.

Re:What is special about prime numbers?

[SillySlashdotName]

Thanks, this helped me a lot.

I have been following links provided by i2hsu in a prior posting to wikipedia entries and have been working on Cantors Diagional theory and was not getting it. Your example helped me understand the reasoning.

I also am not sure I buy the theory, but I think I understand it better after reading your post.

Based on Cantor's diagonal argument and the arguments and examples given there, the results of the manipulation results in a supposedly new number, one that was not originally in the listing of 'all numbers in the interval.'

Is there not a logical problem with finding a NEW number betweeen two boundaries that is not in a listing of ALL NUMBERS between two boundaries?

What this gives me is a sequence that is guaranteed to be different than every f(n) sequence, because the number in position n is different.

I don't agree. If your f(n) really does give every possible value between the two boundaries, then any number generated by your manipulations WILL be in the set generated by f(n) - BY DEFINITION of 'every possible value'.

I maintain that f(n), where n ranges over ALL the positive integers, if it gives all the numbers between 0 and 1 then you are not able to maipulate the values generated to get a value NOT in the listing but still between 0 and 1. If you can, then your function is not valid or it would have generated the value.

If the functions you describe in your post are guaranteed to give a binary fraction (a zero, followed by a decimal point [binary point?] followed by any number of zeros or ones in every possible combination) and give ALL the possible combinations, then as long as your manipulation gives either a one or a zero you will always wind up with a number in the original list, no matter which digit you flip.

Chose a binary fraction between 0.0000000 and 0.1111111. Chose a position x such that x is between 1 and 7. Whatever the bit in position x is, flip it to the other state (1 -> 0, 0 -> 1). the result will always be a value that is already in the series.

I chose 1010101. Any bit you should chose to flip would give a result that is in the defined range.

1) 0.1010101

1) 0.0010101
2) 0.1110101
3) 0.1000101
4) 0.1011101
5) 0.1010001
6) 0.1010111
7) 0.1010100

I may be guilty of muddy thinking, missing something, or not using the terms in a way that is understood by those in the field,, but if your f(n) is supposed to give EVERY POSSIBLE number between two boundaries, but does not give the number you obtain when you perform Cantor's diagonal argument, then your f(n) is flawed in that it did not give every possible number.

This would seem to me to eliminate the contridiction claimed in Cantor's argument, rendering the claim that some infinities are larger that others false.

Re:What is special about prime numbers?

[SillySlashdotName]

I have been thinking about this, and think there is a problem with the logic.

Which set is larger, the set of all positive integers, or the set of all EVEN positive integers?

The sets are the same size.

Take all the positive integers, multiply their value by 2 and you have all the positive EVEN integers. Therefore there is a 1-1 correspondence between the members of the first set and the members of the second set, so they are the same size.

Because of this, a (the set of all positive integers, even or odd) is a superset of b (the set of all even positive integers) but a IS NOT larger than b.

Interesting that c (the set of all odd positive integers) is also exactly as large as a, which gives (the set of all even positive integers PLUS the set of all odd positive integers gives the set of all positive integers) b + c = a, but the size of b = the size of a and the size of c = the size of a, therefore the size of a + the size of a = the size of a!

Re:What is special about prime numbers?

[SillySlashdotName]

I appreciate the patience shown by respondents and the willingness to educate a layperson in the given field, a field that can be very difficult!

Thanks for the links - mathworld is very 'information dense', I am more the wikipedia speed.

I will say, though, that I need more education in the area, as Cantor's diagonal argument does not convince me.

Given the interval between 0 and 1, create a function that maps the positive integers to each of the real numbers between 0 and 1. Now do Cantor's diagonal procedure. Either you will get a number that is on the list generated by the function, or the function is faulty as it did not generate the number you arrived at.

The list of all possible real numbers between 0 and 1 would consist of a zero followed by a decimal point, followed by all possible combinations of the digits 0 through 9. I maintain it is not possible to then 'twiddle' one of the digits and arrive at a combination of the digits 0 through 9 that is not already in the set of "all possible combinations of digits 0 through 9."

Cantor's argument says it is possible to find a combination of digits consisting of the numbers 0 through 9 that is not in "all possible combinations of the digits 0 through 9." I have a logical problem with that.

Specifically, using the example on wikipedia, if we "enumerate all numbers in this interval as a sequence" then all numbers between 0.4444...443 and 0.5555...556 are in our list (Zero followed by an infinite string of fours, followed by a three through zero followed by a decimal point followed by an infinite string of fives followed by a 6, giving ALL POSSIBLE COMBINATIONS OF 4s AND 5s). If there is a number between these two numbers not on our list, then we have not "enumerated all numbers in this interval" as required.

I then maintain that, no matter what combination of manipulations done to any other string of digits, as long as a number consisting of a zero followed by a decimal point, followed by any combination of 4s and 5s results, the number WILL be on our list, directly contradicting the statement "However, because of the way we have chosen 4's and 5's as digits in step (6), x differs in the nth decimal place from rn, so x is not in the sequence ( r1, r2, r3, ... ). "

Therefore, "This sequence is therefore not an enumeration of the set of all reals in the interval [0,1]. This is a contradiction." is false.

Re:What is special about prime numbers?

[i2hsu]

>>multiply their value by 2

You've just put the set under a transformation... so you're actually ending up with a different set (ie. the set of all positive integers)

I think miskatonic alumnus has posted a pretty nice reply here: http://slashdot.org/comments.pl?sid=129086&thresho ld=1&commentsort=0&tid=156&mode=thread&cid=1078491 0

Although I'm not too sure how much these links and replies help you, I do hope they at least help a bit. =)

Re:What is special about prime numbers?

[SillySlashdotName]

Sure you can. Give me any real number between 1 and 2. Write it down on one of these infinite number of pieces of paper. Put that piece of paper in one of these infinite number of buckets. Repeat for all the real number between 1 and 2 without duplicating any.

The bolded sentence is the problem.
You need to be able to specify a way to determine the n'th real number you are going to choose.

I still don't see it.

You seem to be saying it is hard to find a function to determine the real numbers, so therefore the set of real numbers is not countable. I am saying that if you gave me every possible real number - however obtained, guessed, calculated, made up on the spot - those numbers could be assigned to a 'positive integer set' bucket in a 1-1 relationship and are therefore 'countably infinite' and so the set of real numbers is the same size as the set of positive integers.

As I see it, the only way there can be an infinity that is larger than another is if the elements of one set of infinity can not be assigned to another set in a 1-1 correspondence.

Not only can't you find a neat and tidy function that you can write down, but you can prove that it isn't possible for one to exist.

AH HA! A new direction for my investigation! THANK YOU!

As I have posted before, though, Cantor's method using the diagonal does not prove the uncountability to me, as a paradox is created when you claim you have listed all the numbers then claim you find a new number that is not listed. Both can not be true, so either not all the numbers were listed in the beginning or the number 'found' IS on the original list.

I have taken up enough time from everyone, so, while I will monitor the thread, I will not be posting further.

Thanks to all who attempted to educate, it is appreciated!

Re:What is special about prime numbers?

[nebaz]

Basically this entire thing comes down to a proof by contradiction. The general logic in that claim goes something like this
1) Let's assume f(n) for all 1,2,3... infinity contains all the possible values for my set
2) I can show that this is not true, by coming up with a member of the set which is not f(n) for any n.
You may say "bullshit", it's one of the f(n)'s.
Then I'll say "ok, which one is it"
Then you'll say, f(1085), for example.
Then I'll say, no it's not, because the 1085th "sequence" (or digit or however this is done) of f(1085) is 0, but the 1085th "Sequence" of my new element is 1. They can't be the same.

By the way we generated our "new member" it will not be equal to f(n) for any n because the nth "digit" will be different.

What that means is that either
1) f(n) encompasses all the members of my set (which I have claimed, but I have shown that my new number is different than every f(n))
or 2) f(n) actually does NOT encompass all of my set

The second possibility is what we have to deal with here. That means that we can't generate an f(n) that covers all the values of our second set, which is exactly the point. NO SUCH f(n) can be defined.

This is a general concept of proof by contradiction. We want to prove "X is false". We do so by assuming X is true, then coming up with something like 1+1=3. If X being true leads to 1+1=3 it can't be true, and thus we have proved X is false.

"Levels of infinity" is admittedly a very weird concept, and I had a hard time believing/understanding it when I first encountered it too, but I hope this helps.

Re:What is special about prime numbers?

[djcapelis]

1*prime

Now after doing the impossible, it's time for breakfast.

Re:What is special about prime numbers?

[miskatonic alumnus]

It is truly amazing how little mathematics people understand. The extended reals are not the same as the hyperreals. I said what I meant. Try again.

Re:What is special about prime numbers?

[SillySlashdotName]

I had said I was not going to continue posting on this thread, but you are picking at a point I would like more clarificatiion on.

1) Let's assume f(n) for all 1,2,3... infinity contains all the possible values for my set

Ok.

2) I can show that this is not true, by coming up with a member of the set which is not f(n) for any n.

You lost me.

If f(n) where n is in the positive integers maps to ALL POSSIBLE MEMBERS OF YOUR SET then you can not possibly create, devise, make up, calculate, or otherwise have a number in your set that is not mapped using f(n), otherwise you have a number in your set that is not a member of the set of all the possible numbers in your set. A contradiction. Of course, a contradiction means the original premis is false, so you would have proved your point. Or would you...?

I guess my point is that, if I have all the possible members in your set in one of my positive integer buckets, then any manipulation you can do to any single member or group of members of the set will result in a number that is in the set in one of my infinite buckets.

If you do Cantor's diagonal argument and come up with a number that is a valid member of the set of possible numbers in the set, then, by defining the buckets as holding 'all possible numbers in the set' any number you arrive at that is a valid number is going to be in the set. It has to be, if it is a valid member of the set!

You may say "bullshit", it's one of the f(n)'s.
Then I'll say "ok, which one is it"
Then you'll say, f(1085), for example.
Then I'll say, no it's not, because the 1085th "sequence" (or digit or however this is done) of f(1085) is 0, but the 1085th "Sequence" of my new element is 1. They can't be the same.
By the way we generated our "new member" it will not be equal to f(n) for any n because the nth "digit" will be different.

Interesting, but leads to a paradox I think.

create a function on x where x ranges over the positive integers such that every integer maps to itself. f(n) = n.

f(1) = 1 and f(f(1)) = 1
f(2) = 2 and f(f(2)) = 2
f(3) = 3 and f(f(3)) = 3
. .
. .
f(x) = x and f(f(x)) = x

Do you agree that the function, when applied to the (infinitely large) range of positive integers will give an infinitely large set, and that every integer in the set will, when put through the function give itself as a result, and that every result can be mapped 1-1 to the set of positive intergers? If any of my assumptions or intentions is not correct, then my whole thought is not correct.

We can now list the numbers resulting from the application of the function to the positive integers, pad the results on the left with zeros to make all the entries in the list the same length, and apply Cantor's diagonal argument.

This will result in a number, and because the function is f(number) = number, the entry that maps to the number found in the diagonalization must be arrived at when run through the f(x) = x function.

But you are stating that your number is different than my number, even though my number IS your number.

We have a contradiction.

The definition of a countable infinity is one that can be mapped on a 1-1 basis to the counting number which are the positive integers. Cantor's diagonal argument shows that the set of positive integers CAN NOT BE MAPPED to the set of positive integers! I.e., the set is larger than itself!

Congratulations, you have just proved that a countable infinity is not countable.

Whoops, THAT is a contradiciton!

So either Cantor's diagonal argument proves that the set of real numbers is not countable and so is larger than the set of positive integers, or the diagonal argument proves that BOTH sets, the real numbers and the positive integers, are uncountable and therefore may be the same size after all, or the argument proves nothing at all.

Re:What is special about prime numbers?

[SillySlashdotName]

The "famous proof of Cantor" you refer to, is that the diagonal argument or another proof?

If it is the diagonal argument, can you help me to understand why it does not also prove that the set of positive integers is not uncountably infinite, even though there exists a 1-1 relationship with the members of the set of positive integers and the definition of a countable infinity I found states that a countable infinity is one with a 1-1 correspondence with the positive integers?

The setup is this:

Create a function f such that f(x) = x, i.e., f(1) = 1 and f(f(1)) = 1, f(2) = 2 and f(f(2)) = 2, etc.

Apply this function to each of the positive integers, with the results being a new set WITH EXACTLY THE SAME ELEMENTS as the set of positive integers. Because the set of positive integers is countably infinite, the new set should be also countably infinite unless I am missing something.

List the elements of the result set one to a line and pad the left with zeros to make the lines all the same length.

Apply Cantor's diagonal argument to the listing created above, resulting in a number i. My understanding is that i is claimed to be different in the ith place from any number in the result set which means we have determined a number in the set of f(n) = n where f(i) != i.

Based on Cantor's argument being a proof that the set of real numbers is not countably infinite, haven't we just proven that the countably infinite set of positive integers are not countably infinite ( a != a)?

Have I divided by zero or some other basic error here, and if so where?

Re:What is special about prime numbers?

[Darby]

The list of all possible real numbers between 0 and 1 would consist of a zero followed by a decimal point, followed by all possible combinations of the digits 0 through 9. I maintain it is not possible to then 'twiddle' one of the digits and arrive at a combination of the digits 0 through 9 that is not already in the set of "all possible combinations of digits 0 through 9."

Cantor's argument says it is possible to find a combination of digits consisting of the numbers 0 through 9 that is not in "all possible combinations of the digits 0 through 9." I have a logical problem with that.


The thing is that you haven't come up with "all possible combinations of digits 0 through 9." after a decimal point. That *is* the interval [0,1] What you've come up with is a map from the natural numbers 1,2,3.... into [0,1]. That is what enumerating means. Enumerating doesn't necessarilly mean that you have listed all of them.

The trick to the diagonal proof relies completely on the fact that everything you deal with in the proof is countably infinite i.e. it's the "littlest infinity", which, granted, you still haven't agreed that such a thing even makes sense.

But the fact that you have an enumerated list is what allows you to find a real number not on that list. While there are an infinite number of numbers in your list, it's trivial to point out the 10th, the millionth, the 250 to the googol to the googol to the googolth number you have listed since that is what an enumeration is.

So if the initial assumption makes sense then every real number is in your list in a specific place. There are infinitely many, but every one exists at some specific *finite* place in the list. So when you create your new number by changing one digit from each number in the list, it truly does not exist in the list.
If it did exist in the list, then it would exist in one and only one specific location in that list. So ask yourself which position in the list could it possibly occupy?
Not the first, because it's first digit is different. Not the hundredth, not the trillionth, and so on and so on and so on.

As I have posted before, though, Cantor's method using the diagonal does not prove the uncountability to me, as a paradox is created when you claim you have listed all the numbers then claim you find a new number that is not listed. Both can not be true, so either not all the numbers were listed in the beginning or the number 'found' IS on the original list.

This is almost true, but you don't just claim that you have listed all the numbers, you claim something even stronger. You claim that you have listed them *by number* i.e. the first, the second etc. This is what makes it different.
So it's true that you claim to have listed them all in order and then demonstrate that you have found one that isn't in the list. This isn't a parodox though, it's a contradiction. Reaching this contradiction shows you that your initial assumption, that the reals are countable, was false.

To really get this, I think there are 2 things that you really need to understand and accept.
One is the idea of proof by contradiction. i.e. assume what you want to prove is not true. If this leads you to a contradiction, then what you assumed is false, and what you originally wanted to prove is therefore true.
The second is why the new number that you created can not possibly be in the list. If it were, then there would exist a finite number, n, that it's mapped to by. i.e. it's in bucket # n.
But by the very nature of the way the number was constructed, it can't be in bucket n because it's a different number in the nth decimal place. The fact that n could be any natural number at all and it isn't a specific one proves it for all natural numbers, hence there isn't a natural number that maps to our new one.

I guess one more thing that might help is to realise that while any statement proven mathematically *is* absolute truth, it's only absolute truth within a very specific un

Re:What is special about prime numbers?

[miskatonic alumnus]

The positive integers are countable because f(x)=x is a bijection from the positive integers to the positive integers. Therefore, they are not uncountable.

As for the Cantor argument you present, I take it you mean the entries in the list are sequences of integers with only finitely many nonzero entries --- for example, (...,0,0,3,2,7) would represent the number 327. Now, these sequences are in bijective correspondence with the positive integers. Here, diagonalization will produce a "number" that will have infinitely many nonzero entries, and therefore does not correspond to an integer since there are no integers with infinitely many digits. This "number" was not in the list, but that doesn't violate the assumption that all naturals were enumerated, since the result doesn't belong in the list anyway.

Re:What is special about prime numbers?

[nebaz]

Interesting, but leads to a paradox I think.

create a function on x where x ranges over the positive integers such that every integer maps to itself. f(n) = n.

f(1) = 1 and f(f(1)) = 1
f(2) = 2 and f(f(2)) = 2
f(3) = 3 and f(f(3)) = 3
. .
. .
f(x) = x and f(f(x)) = x

Do you agree that the function, when applied to the (infinitely large) range of positive integers will give an infinitely large set, and that every integer in the set will, when put through the function give itself as a result, and that every result can be mapped 1-1 to the set of positive intergers? If any of my assumptions or intentions is not correct, then my whole thought is not correct.

We can now list the numbers resulting from the application of the function to the positive integers, pad the results on the left with zeros to make all the entries in the list the same length, and apply Cantor's diagonal argument.

This will result in a number, and because the function is f(number) = number, the entry that maps to the number found in the diagonalization must be arrived at when run through the f(x) = x function.

Ok, there are two things here. First, you can not "pad to the left" to make all the numbers of equal length. For any finite set of numbers, it can be done, because there is a maximum number of digits. If you pad with an INFINITE number of zeros on each, I suppose they would be the same length, but then you are dealing with numbers with an infinite number of digits. Natural numbers never have an "infinite" number of digits (for example the number 111...... forever is NOT a natural number). Natural numbers have can be arbitrarily large, but finite. If you had an infinite number of zeros before every number, your new number (assuming you take "digit 1" of 000.........1, and "digit 2" of 000........2, etc, something other than zero for each digit would give you an infinite sequence of digits, but not a natural number.

In fact, it IS the case that the set of infinite sequences of digits is uncountable, but the crux of the matter here I think is understanding the difference between "infinite" and "finite, but arbitrarily large".

Hope this helps.

Re:What is special about prime numbers?

[SillySlashdotName]

Thank you.

Re:What is special about prime numbers?

[yourmom16]

You're right that two sets can have different sizes, but your explanation is completely wrong. For instance the set of even natural numbers is a subset of the set of natural numbers, but they are the same size because one can be obtained from the other by renaming it's elements.

"FUN with Prime Numbers"

[noisymime]

I find that title so hard to appreciate, maybe I'm just not as big a geek as i thought.

Re:"FUN with Prime Numbers"

[wwahammy]

I've never found prime numbers to be fun at all. Derivatives on the other hand....

Re:"FUN with Prime Numbers"

[Anonymous Coward]

You can find the gradient of my curve any day, if you know what I mean.

Complaint about article

[comwiz56]

Yes, this article is very informative and interesting, but I have one complaint:

The source code is often organized in confusing and/or excessively complicated ways. There are also non-standard typedefs.

Re:Complaint about article

[shamilton]

The article feels like it was written for the sole purpose of showing off the author's knowledge. Perhaps I'm just hyper-sensitive to that...

Re:Complaint about article

[Anonymous Coward]

The article feels like it was written for the sole purpose of showing off the author's knowledge. Perhaps I'm just hyper-sensitive to that...

To what, the author's knowledge? ;-)

Re:Complaint about article

[Anonymous Coward]

like the grandparent was written solely for the ipod spam.

Nice disclaimer

[cmcguffin]

> User assumes all risk and responsibility for any outcome.

I sure hope that doesn't include responsibility for brining his web server to its knees. I feel so guilty!

Re:Nice disclaimer

[Anonymous Coward]

I sure hope that doesn't include responsibility for brining his web server to its knees.

Yeah, brining seems a bit harsh. Couldn't we just link to it as usual?

An oxymoron

[Engineer Andy]

Fun, prime numbers, in the same sentence without some means of not connecting them in a positve light?

What manner of masochism is this page peddling in the name of fun?

This can't be good

[Anonymous Coward]

This sounds like one of those topics in high school where if you sounded interested you were written a raincheck for an after school beating by the rugby team.

Re:This can't be good

[Lord Kano]

This sounds like one of those topics in high school where if you sounded interested you were written a raincheck for an after school beating by the rugby team.

My standing advice for all school-aged geeks. Pick one jock that you think you can beat and pound the shit out of him whenever he gives you crap.

The rest of them will see how humiliated their comrade was and they will move on to easier targets. Sure, they could probably beat you, but they're not going to take the chance.

LK

Re:This can't be good

[nova20]

Pick one jock that you think you can beat...

that's a bad assumption to make in this crowd.

Re:This can't be good

[nova20]

This sounds like one of those topics in high school where if you sounded interested you were written a raincheck for an after school beating by the rugby team.

That's a badge of honor, dude. I'd put that on my resume under "Experience" -- beat up 25 times in high school for being a "geek" or "nerd"

Re:This can't be good

[Lord Kano]

that's a bad assumption to make in this crowd.

It worked for me.

LK

Quick!

[Primotech]

What's the first prime number?

Mersenne

[Madcapjack]

Aren't most of the really large prime numbers only Mersenne primes?

Re:Mersenne

[back_pages]

Aren't most of the really large prime numbers only Mersenne primes?

Rather, most of the Mersenne numbers are prime, and most of them are large. That doesn't begin to scratch the surface of most large prime numbers though.

Re:Mersenne

[mvdw]

No.

Re:Mersenne

[scoser]

The probability of finding a Mersenne number that is prime is much better than just choosing a random number to check for primality, which makes it easier to find large primes if you just hunt through the Mersenne numbers.

Re:Mersenne

[Anonymous Coward]

Hmm no. The odds are about the same. The advantage is that checking a Mersenne prime for primality is incomparably faster than checking a random sequence of digits of the same length.

Re:Mersenne

[dtfinch]

Not exactly. We know that 2^n-1 can only be prime if n is also prime (if I remember correctly). So while numbers in the form 2^n-1 generally may not have a signigifantly higher chance of being prime (I don't know), we can choose values of n that are easily 20x as likely to give us a prime number than if we used randomly chosen odd numbers.

Re:Mersenne

[acidblood]

Rather, most of the Mersenne numbers are prime

Wrong. There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known), and only 41 of these are Mersenne exponents.

Re:Mersenne

[back_pages]

Rather, most of the Mersenne numbers are prime

Wrong. There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known), and only 41 of these are Mersenne exponents.

Read what I typed, then read what you typed.

If I were wrong, then most of the Mersenne numbers would be composite. You have suggested that most of the large prime numbers are not Mersenne numbers, which is an unrelated concept, and substantiates my original post.

Re:Mersenne

[Anonymous Coward]

The point with Mersenne numbers is that it is easy to find out if a mersenne number is prime or not were as with other numbers that large (5+ million digit numbers) it is hard to tell weather or not they are prime.

Re:Mersenne

[acidblood]

If I were wrong, then most of the Mersenne numbers would be composite.

Do you have reading comprehension problems? Or is it just logic that escapes you? If only 41 primes up to 24,036,583 correspond to exponents of Mersenne primes, then the remaining 1.5 million or so primes up to 24,036,583 correspond to exponents of, you guessed it, Mersenne composites. I'd say that a compositeness ratio of 99.997% would indicate that `most' Mersenne numbers are composite.

You have suggested that most of the large prime numbers are not Mersenne numbers, which is an unrelated concept

I can only suggest you to heed your own advice.

Re:Mersenne

[ponds]

then the remaining 1.5 million or so primes up to 24,036,583 correspond to exponents of, you guessed it, Mersenne composites.

What the hell are you talking about? Prime numbers can not be composite. A prime number is by definition a number which is not composite.
What the guy that you're arguing with is saying is that the 1.5 million or so primes are not mersenne numbers, not that they are mersenne composites.

Don't make fun of the people that you're arguing with unless you're pretty sure you know what you are talking about -- It's alot funnier when you get owned if you talk alot of shit first.

Re:Mersenne

[Anonymous Coward]

"There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known)"

key word here is exponent. You might want to read http://en.wikipedia.org/wiki/Mersenne_prime. acidblood is correct.

Re:Mersenne

[acidblood]

I'd venture to say I know what I'm talking about. One can't publish a paper about large-scale distributed primality proofs without knowing these basics. Here's a sample of my work. Now don't get me wrong, I'm not trying to sound like a smart-ass, but I'm not going to let someone question my knowledge in this field (which I have studied for years) and remain quiet.

Now it seems people here are not familiar with the terminology associated with Mersennes, so I'll give a crash course.

A Mersenne number M_n is of the form 2^n - 1. If 2^n - 1 is prime, then M_n is a Mersenne prime. If 2^n - 1 is composite, then M_n is a Mersenne composite. The integer n in this expression is called the exponent. When I talk about `exponents of Mersenne composites', I'm refering to some prime n for which M_n = 2^n - 1 is composite.

Now if 2^n - 1 is prime, then n must be prime, but the converse is not always true, the smallest counterexample being 2^11 - 1 = 2047 = 23*89. Turns out that for prime exponents n = 24,036,583, only in 41 cases is 2^n - 1 actually prime. A list of these cases can be found here. For the other 1,509,222 prime values of n = 24,036,583, 2^n - 1 is composite. This translates to a compositeness ratio of 99.9973%.

I hope everything is clearer now.

Re:Mersenne

[acidblood]

Sorry, forgot to link to the list of Mersenne primes: click here

Re:Mersenne

[Anonymous Coward]

Nothing like a math thread to prove time and again that Slashdot is populated with drooling imbeciles who award karma points to the slightest misinformation.

Re: Mersenne

[Omniscient Ferret]

The largest primes known are Mersenne primes. There are primality tests for Mersennes that are far faster than any tests for other numbers. There are still far more other primes at that size - the most recently found Mersenne prime is over seven million digits long.

Re:Mersenne

[daniel_mcl]

Yeah. I think what somebody was trying to repeat thirdhand is that most *known* large primes are Mersenne primes; this is because we have effective, distributable algorithms to factor Mersenne numbers, while there are no such algorithms to determine whether an arbitrary number of comparable size is prime.

Re:Mersenne

[leifbk]

Not exactly. We know that 2^n-1 can only be prime if n is also prime (if I remember correctly). So while numbers in the form 2^n-1 generally may not have a significantly higher chance of being prime (I don't know), we can choose values of n that are easily 20x as likely to give us a prime number than if we used randomly chosen odd numbers.

The real reason why discovered Mersenne primes are way bigger than any other known primes, is because of the special algorithm for finding them. This is known as the Lucas-Lehmer test (google for it). It isn't feasible to run a brute-force trial factoring for numbers approaching 10 million digits. For a number on the form (2^P)-1 where P is a prime, the Lucas-Lehmer test requires only P iterations of the basic algorithm. It also works especially well for numbers on the form (2^P)-1, because the computer can get away with a lot of simple bit-shifting instead of costlier math operations in terms of CPU cycles.

I've done Lucas-Lehmer testing for the Great Internet Mersenne Prime Search for half a year now, and am currently running it on five different machines. The chances of actually finding a huge prime number are probably much less than of winning big-time in Lotto, but I for one think this is kind of fun.

Re:Mersenne

[TwistedSquare]

I'm afraid we're going to have to revoke your slashdot user account. Understanding a subject area properly and trying to correct people on matters other than spelling and grammar is not permitted.

Re:Mersenne

[Anonymous Coward]

Most of the Mersenne numbers are not prime. The ratio of prime Mersenne numbers to Mersenne numbers is less than the ratio of prime numbers to natural numbers, because if N is not prime, 2^N - 1 has a factor of 2^P - 1 where P|N (e.g. 2^3-1 = 7 divides 2^9-1 = 511), but if N is prime, 2^N - 1 can still have a factor.

Most of the large known primes are Mersenne primes because there are efficient algorithms based on the bit length of the prime (rather than its magnitude) to detect primality for such numbers. There are certainly more large primes than that, by the known distribution of primes.

Re:Mersenne

[Anonymous Coward]

Actually you have communications problems, my friend. What you meant to say, and what you said, were completely different things. I quote:

There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known), and only 41 of these are Mersenne exponents

This actually makes no fucking sense at all.

The largest Meresenne exponent known is greater than 100,000, but represents a prime of magnitude 2^100,000 - 1. There are more than 1.5 million primes between 1 and 2^100,000 - 1.

I take it you mean that 2^24,036,583 - 1 is known to be prime. Perhaps it is, but we have not checked every Mersenne number from 1 to 24,036,583. There are 41 known Mersenne primes in that range, but there may be many more unknown primes.

The guy is still wrong, as I explain in relation to his post, but you should fucking calm down with the "reading comprehension problems" when you can't write maths worth a damn.

Re:Mersenne

[Anonymous Coward]

Replying to myself to augment the post.

An example of a Mersenne number for which N is prime but the Mersenne number is not is N = 31. I have calculated this factor, which unfortunately the margin is too small to contain.

Re:Mersenne

[Finuvir]

What the hell are you spouting? How can a prime number be a Mersenne composite?

Re:Mersenne

[Anonymous Coward]

You're wrong.

Re:Mersenne

[fatphil]

Yves Gallot's GFN (generalised Fermat Number) search, and my GEFN (generalised Eisenstein Fermat Number) search, are both as efficient when it comes to the primality tests. If anything, our tests might be more efficient, as our DWTs are simpler than Mersenne's IBDWT. Both of our forms are definitely more efficient than Mersennes, as we can _presieve_ ours to massively reduce the number of lengthy tests that we need to do.

The only reason GIMPS (great internet mersenne prime search) has the top ?4 primes at the moment is because they have 1000x as much CPU power as Yves' GFN search, and 10000x as much CPU as my GEFN search.

With Percival's generalised DWT algorithm, those searching for Proth/Riesel forms (k*2^n+/-1) with very small k also have a similarly efficient primality tests.

The age of Mersennes is only not over yet because of the fact that they have such a head start. They will be caught up with over time when other projects get similar quantities of CPU power.

FP.

Re: Mersenne

[fatphil]

There are equally fast tests for Generalised Fermat Numbers and Generalised Eisenstein Fermat Numbers. It's just that this was only realised 4 years ago (GFNs, by Yves Gallot), and 18 months ago (GEFNs, by me). Their popularity has yet to catch on, and GIMPS's Mersennes have an enormous head start and huge user-base. However, it's no longer a question of efficiency.

Re:Mersenne

[bloggins02]

What the hell are you spouting? How can a prime number be a Mersenne composite?

Hello? Hello!!!??

He said this:

then the remaining 1.5 million or so primes up to 24,036,583 correspond to EXPONENTS OF, you guessed it, Mersenne composites.

Re:Mersenne

[Anonymous Coward]

I can only suggest that you head your own advice.

I suggest you read your own post again to see what's missing... maybe you should say what you want to say instead of making half a point so you don't look like so much of an idiot in the future.

Re:Mersenne

[boodaman]

I love a good smackdown.

Re:Mersenne

[Madcapjack]

Yeah. I think what somebody was trying to repeat thirdhand is that most *known* large primes are Mersenne primes;

Yeah, actually, that is what I meant in my original post- I meant the known primes-- that the largest primes that we know are Mersenne because they're easier to discover/verify than non-Mersenne primes.

Re:Mersenne

[Anonymous Coward]

There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known), and only 41 of these are Mersenne exponents.

This made perfect sense to me... I'm not sure what you think you read up there, but it's perfectly valid mathematically. Are you quite certain you're not guilty of communication problems yourself?

The largest Mersenne number (M_n) that is currently known prime has exponent n=24,036,583, and there are 1.5 million primes up to that exponent. The only Mersenne numbers M_n that have a possibility of being prime are those where the exponent n is prime, so the number of primes up to 24,036,583 are the set of exponents that need to be checked, which is about 1.5 million as he said. Hence the ratio 41 Mersenne primes and ~1.5 million Mersenne composites. No, we have not checked every exponent in that range, but we don't need to.

a test

[Lord Ender]

If this gets you really excited, you know you are the truest form of nerd.

Re:a test

[Lord Ender]

Which is to say, I think this is really cool.

Re:a test

[dtfinch]

I wasn't all that excited, only because I wrote my own several years back. He did go a couple steps further and work around the memory problem with paging though, which I had never tried. I was limited by my ram.

If I don't print or store the primes, I can find all the primes under 2 billion in 2 minutes on my 2.4ghz celeron, since after about 46k all it's doing is reading a bit array of what is and isn't prime. But adding a printf slows it down considerably.

Re:a test

[zedmelon]

Sorry, you admitted in public that you use a celeron instead of the required AMD processor. If you do not redeem yourself by immediately bashing microsoft, the RIAA or SCO while supplying illegal software downloads and praising Linux--by flavor, naturally--you may be permanently banned from Slashdot.

Note that if your post is not written in 1337 $p34|<, your 3 in 1d20 chance of being banned anyway will be raised to 13.

Haxxor. AOL sux. BSD is dead. Beowulf.

;)

Re:a test

[dtfinch]

Sorry, you admitted in public that you use a celeron instead of the required AMD processor.

I'll go ahead and say more than I need to here, in part because I have nothing better to do, or maybe because of my ADD, since the former is a lie.

Yes, I'm cheap. Low income. Student budget. No scholarships.

It's actually a Dell Dimension 2400n. Shipped with no operating system, it was the cheapest they had. I chose to get 512mb ram, an 80gb hd, a 17" monitor (also the cheapest they had), and a dvd drive. No CD burner, but I already have one elsewhere.

The graphics chipset is an integrated Intel i845GV. I'm sure the GV stands for Great Value, because as expected, it's not only about 1/20th as fast as the middle end 3D cards, it's about 1/3th as fast as its low end integrated competitors. Add to that the Linux driver's buggy, encouraging me to use software rendering. I managed to speed up mesa to make some games quite playable at a severe cost to quality, like bzflag, but I think I forgot to back it up when I last wiped the hard disk.

My cheap system is currently running Ubuntu 4.10. After editing /etc/apt/sources.list to add some extra repositories, I find it very palatable. Other distributions I've installed on it include Slackware 10, Mandrake 9, Suse 9, Fedora Core 2, and CentOS 3.

My older system is an eMachine eTower 500ix. It has a 500mhz celeron, 256mb ram, and an 80gb hd. And it has a 64mb ATI Radeon 7500 and a 52x cd burner, both of which I'll probably move to my newer piece of crap one of these days, if I don't just buy a better system. On it I have Windows XP Professional and Visual Studio.NET, both of which were given to me for free for being a student. But not surprisingly, VS.NET started having problems at about the same time the next version came out, so now if I program with .NET I use SharpDevelop. I keep both systems side by side on my desktop, though most days I don't even turn the Windows PC on.

I buy my games about 3-4 years after they hit the market, when they find their way into the $10 or less racks. I got Quake II for $1.42 on sale at Office Depot and Quake III for $9.95 at WalMart, not that I've played either in the past few months.

But I'm not entirely cheap. I probably spend around 5-10% of my income on open source related donations. Among that, $60 to GrokLaw to fight SCO fud. And probably 95% of my music collection is stuff I've bought, mostly Weird Al. Also Tom Lehrer, the Beatles, and Ozzy. Some of it as a result of sampling on Kazaa and deciding to buy the CD.

Re:a test

[pboulang]

If I don't print or store the primes, I can find all the primes under 2 billion in 2 minutes on my 2.4ghz celeron, since after about 46k all it's doing is reading a bit array of what is and isn't prime. But adding a printf slows it down considerably.

Interesting.. If I don't print or store them, I can do it in .00000001 seconds.. plus, the program I do that with is only 4 bytes long, and is cross platform!

Re:a test

[zedmelon]

Whoah, man... sorry.

I almost didn't post because it was offtopic and frankly not very funny, but I did anyway, probably because I have ADD too. All I was doing was making an off-color remark on the groupthink at /. and wouldn't have been surpised at getting no reply at all.

Your site is interesting, I've bookmarked it and will return.

That's really cool that you spend so much on donations. I try to do what I can. Yes, that's a pretty common statement, but I'll bet I spend a higher percentage than the average slashdotter. I see a lot of similarities here, like the music. Well, I don't care much for Ozzy, but Weird Al is one of my faves. Oh, and I gave up on trying to go back to school years ago. You know, I've never even heard of Ubuntu (opens a Google tab)... I like the meaning. No wonder it sounded African.

Wow. I really like that definition.

I remember rekindling a love for Worms2 upon finding it for $9.95 and thinking it criminal to sell it so cheaply. You've got me beat with the $1.42 Q2. I don't play much q3 anymore either, but even if the two copies (Windows and Linux versions) I bought had cost 3x as much, it'd still be the best "bang for buck" game I've ever owned. I've pumped FAR too many hours into it.

I actually own Celerons myself. I don't recall all the stats anymore; when one box dies, the surviving parts go to a box/pile/corner, and redistribute when I upgrade (ahh, I remember the days before becoming a Dad...upgrades came more than 1 per 3 years). I never throw anything away; that's how I'm building my armada ;)

I lucked out on the latest, the company where my friend worked was getting rid of machines and gave him two Dell Poweredge 2400 dual proc boxes, and he gave one to me after upgrading the 600s to 933 Celerons. I don't have any spare RAM, so it's stuck at 512. I just got it a couple days ago and haven't installed anything yet. Maybe I'll try Ubuntu.

BTW, you made your saving throw. ;)

Interesting code

[icekillis]

Reminds me, here's code to generate prime numbers: (earlier thread)
http://www.de.ioccc.org/2004/vik2.c

to cheat: http://www.de.ioccc.org/2004/vik2.hint
I didn't link them on purpose

And when

[Anonymous Coward]

And when we finally find a perfect algorithm, we can use it to...

uh

find more numbers.

chosing typesafety over speed?

[Anonymous Coward]

So the macros knock the time down from 4.49 to 4.15 seconds -- less than a 10% reduction. In my opinion, that's not enough benefit to give up the robustness and typechecking of functions.

I never thought that I'd see a C programmer type something like that.

Names of/Links to better algorithms?

[Anonymous Coward]

Can anyone point me towards some of the superior algorithms referred to in the summary?

of course, djb has the fastest way!

[Anonymous Coward]

see http://cr.yp.to/primegen.html

primegen is a small, fast library to generate prime numbers in order. It generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.
primegen can generate primes up to 1000000000000000, although it is not optimized for primes past 32 bits. It uses the Sieve of Atkin instead of the traditional Sieve of Eratosthenes.

This begs the question

[Anonymous Coward]

What's the 1,716,050,470th prime?

Re:This begs the question

[YGingras]

What's the 1,716,050,470th prime?

The 1,716,050,470th prime is 40,100,000,093.

Find out more on the Nth Prime Page.

Re:This begs the question

[notthe9]

What's the 1,716,050,470th prime?

The 40,100,000,093rd prime is 1,068,942,961,417.

Re:This begs the question

[bertas28]

This somehow reminds me of a series of memorandum I came across in Paradox, a magazine published by the Melbourne Uni Math Society (MUMS).

It consists of a bunch of proofs that there is no largest prime - the list of proofs is entitled "15 good reasons why Pure Mathematics is not taught to first year students." My favourites are:
Proof by example:
"Let x be the largest prime. Then x=91 but 91+6=97 which is prime. Therefore 91 cannot be the largest prime number. Therefore there is no largest prime."

Proof by intuition:
"Prime numbers are integers that can be divided by themselves only; prime numbers are odd with the exception of 2. By intuition as n->infinity, there will always be an odd number cannot be divided by another number besides itself."

Proof by experimental data:
"Suppose n is the highest prime. Then 2n-1 is also prime. But 2n-1>n so there is no highest prime. (Check: 2*2-1=3, 2*3-1=5, 2*5-1=11, 2*11-1=23, so true.)"

But the greatest of them all:
Proof by having no idea what a prime is:
"Say the largest prime is x, then 2x is also a prime since the statement is true for all natural numbers."

Go to http://www.ms.unimelb.edu.au/~paradox/archive/ for the magazine, these proofs appeared in issue 2 of 2002.

Re:This begs the question

[Piquan]

Go to http://www.ms.unimelb.edu.au/~paradox/archive/ for the magazine, these proofs appeared in issue 2 of 2002.

2002 (Editor: Norman Do)
Issue 1 (currently unavailable)
Issue 2 (currently unavailable)
Issue 3 (currently unavailable)

The author isn't a lightweight ...

[xmas2003]

While the prime number page is a bit odd (obligatory half-hearted pun), the author is Steve Litt who wrote Samba Unleashed ... plus there's already 40+ posts on the article, yet his web site is still pretty snappy despite the /. crowd ...

BTW, the first bazillion prime numbers HAVE been calculated, so for those /.'ers with spare CPU cycles, consider something perhaps more worthwhile such as Folding@HOME

Re:The author isn't a lightweight ...

[magefile]

If you get it from the F@H folks themselves, you don't have to run Windows, either (the parent's link is to a page about the Google Toolbar).

Re:The author isn't a lightweight ...

[bob beta]

It's a fairly light page, so it can probably take tons of 'hits' without loading his server down that badly. What it needs for a proper slashdotting is a few MPEGs of some dude lecturing on Prime Numbers.

Re:The author isn't a lightweight ...

[oojah]

Good plan. We could do we some more people on the team.

Just because the linked page talks about the google toolbar doesn't mean you can't use Linux and support us as well.

Cheers,

Roger

Encryption

[sbszine]

Read Penn Jillette's great explanation for details.

Re:Encryption

[Anonymous Coward]

Yeah, but that's an example of them being useful. It doesn't really make them esthetically "interesting".

Re:Encryption

[sbszine]

Yeah, but that's an example of them being useful. It doesn't really make them esthetically "interesting".

In that case I refer you to the fundamental theorum of arithmetic, which I think is pretty interesting.

Re:Encryption

[Lord Kano]

Penn is a cool ass man.

I had no idea of how deep he was until I saw him on Politically Incorrect.

LK

Re:Encryption

[God! Awful 2]

Read Penn Jillette's great explanation for details.

Okay, that's funny in a sort of Penn Jillette/Dave Barry kind of way. But that explanation would only make sense to someone who already understood the math!

-a

Re:Encryption

[maxwell demon]

Or to the Riemann zeta function, which gives the interesting relation:

The sum over all positive integer n of 1/n^s is the same as the product over all prime numbers p of 1/(1-p^-s).

Mere Mortals

[Wingie]

Slashdot, the place in which godhood is defined by how many prime numbers you can find in an hour and a half.

Fun with slashdotted servers...

[douglips]

Coralized link

Hah!

[Anonymous Coward]

So much for SSL!:)

Prime Resource

[d3m057h3n35]

Here's a nice, fun little resource for those interested in prime numbers. Actually, it's pretty large and exhaustive: The Prime Pages. Make sure to check out Prime Curios!; fascinating stuff.

Slashdotted

[Anonymous Coward]

Story posted at 10:30PM. Time now is...10:47PM. The site has been slashdotted. 17 minutes. I guess that's an ok time before the slashdot effect sets in.

Have some more fun with primes

[pestilence4hr]

A very fast segmented sieve (to find primes in an arbitrary range) can be found here, by Tomás Oliveira e Silva.

Of tangential interest is his Goldbach conjecture verification project. You can download his client and contribute to the project. He's shooting for 10^18...

Re:Have some more fun with primes

[gr8_phk]

A very fast segmented sieve

From reading the description but not the code, it sounds very similar to a method I devised about a year ago. The stuff in the /. article is very poor in comparison and a perfect example of premature optimization - with all those bit fields... Oddly, my algorithm doesn't really seive for primes, it actually factors every number in the range (except for prime powers) and is still fast.

superior algorithm

[Anonymous Coward]

djb:

see http://cr.yp.to/primegen.html

primegen is a small, fast library to generate prime numbers in order. It generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.
primegen can generate primes up to 1000000000000000, although it is not optimized for primes past 32 bits. It uses the Sieve of Atkin instead of the traditional Sieve of Eratosthenes.

the factor command in Unix/Linux

[3770]

There is a command in many unices and Linux called factor.

If you want to be a true geek you can try it on your friends phone numbers and find out if it is a prime.

Then, the next time you talk, inform them that their phone number is a prime, or tell them of their phone numbers prime factorization, and enjoy watching them think that you are a super geek and a super genius.

For even better effect, pretend to count in your head before you tell them this.

Re:the factor command in Unix/Linux

[0racle]

You don't really have friends do you.

Re:the factor command in Unix/Linux

[3770]

Not among humans. And they are the only ones with phones.

This is why I'm sharing this with the rest of you so that someone can use it.

Re:the factor command in Unix/Linux

[notthe9]

I wrote a program the other day which informed me my phone number was not the sum of two squared primes. My roommate found this somewhat interesting.

Re:the factor command in Unix/Linux

[bob beta]

If you want to be a true geek, you run factor against all the spare quartz crystals and oscillator blocks in your junkbox, to see which ones factor down to useful frequencies. 'A multiple of 9600 baud, hmmm....'

Re:the factor command in Unix/Linux

[Keifer]

Ooooooooooo!
Diiiiiiiiiiiss!

Re:the factor command in Unix/Linux

[themoodykid]

Hey, your user id is 560838. Thinking . . . thinking . . .

IT'S NOT PRIME!

Re:the factor command in Unix/Linux

[Anonymous Coward]

He got SERVED!!@!!!!!

Re:the factor command in Unix/Linux

[Anonymous Coward]

A true geek would never be such a phony. A nerd might. But geeks have skills. You should at least be able to get rid of all the factors below 10 in your head or, failing that, on paper and pencil. There are easy rules here and here. Once you've gotten rid of those, maybe it'd be acceptable to use factor. Better to write your own program; it's not hard.

Re:the factor command in Unix/Linux

[Anonymous Coward]

If I had mod points, you'd get them.. I giggled at that..

And now I'm waiting 15 seconds..

Re:the factor command in Unix/Linux

[ankhank]

Rats, it's apparently not included in OSX.

Re:the factor command in Unix/Linux

[Anonymous Coward]

BSDs also have /usr/games/primes, which I often use to find prime numbers.

Re:the factor command in Unix/Linux

[Liquid Len]

Oh, thanks a lot, buddy... With Thunderbird 1.0 released yesterday, and now this /usr/bin/factor thingy which I hadn't heard of...
There goes my productivity.

Re:the factor command in Unix/Linux

[ceeam]

Wow, both my home and cell numbers are prime (slashdot id OTOH is not quite). I wonder what's the probability of that?

Re:the factor command in Unix/Linux

[big ben bullet]

That was alot of thinking for conluding a number that ends with an 8 is not a prime...

Most of my friend would consider me kinda stupid if I did that....

Re:the factor command in Unix/Linux

[Johnno74]

If I want to prove I'm a true geek, I tell my friends I read slashdot...

Re:the factor command in Unix/Linux

[Anonymous Coward]

for a good prime, call...

Re:the factor command in Unix/Linux

[jhagler]

Jenny

Re:the factor command in Unix/Linux

[AxelBoldt]

By the prime number theorem, the probability that a given 7-digit number is prime is about 1/ln(10^8), which is roughly 5%. So the probability that two randomly picked numbers is prime is about 0.25%.

Obligatory...

[Anonymous Coward]

...more like... Nerdular Nerdence!

Fat lot of good...

[buckeyeguy]

...it'll do those poor people stuck in the Cube.

Yes, but...

[Anonymous Coward]

... can these "prime numbers" run Linux?

Oh, that works on your friends, on /. on the...

[3770]

Oh, that works to make your friends think you are a geek.

On /. on the other hand I suggest that you reply to my parent post, informing the world that you already knew of this puny little command and then proceed to talk about some _really_ obscure Linux command that only works on Slackware for the s/390 distro.

Gaps between primes

[tbjw]

From the article:

who can be sure that there aren't two consecutive primes somewhere that are more than 65536 apart

Let's recall elementary number theory:

65537! + 2 = 2 * 3 * ... * 65537 + 2 = 2 * (3 * ... * 65537 + 1)
65537! + 3 = 2 * 3 * ... * 65537 + 3 = 3 * (2* 4 * ... * 65537 + 1)
...

65537! + 65537 = 2* 3 * ... * 65536 * 65537 + 65537 = 65537(65536!+1)

So the 65536 consecutive numbers 65537! +2 , ..., 65537! + 65537 are all nonprime (the first is divisible by 2, the second by 3, the thrid by 4 etc). Since we also know that there are infinitely many primes, there must be a prime greater than 65537! + 65537. The biggest prime less than 65537! + 2 and the least prime bigger than 65537! + 65537 are consecutive primes which are at least 65536 apart.

Of course, 65537! is a massive number, which is unlikely to crop up in these calculations. There may be other sufficiently large gaps between primes among smaller numbers.
Consider, for instance, the method above applied with 5 in the place of 65536. We see that {6! +2, ..., 6! + 5} ={722, 723, 724, 725, 726} are all nonprime, but also 24, 25, 26, 27, 28 are 5 consecutive nonprime numbers.
For where we can expect large 'prime-free' gaps, I'll defer to any number theorist.

Re:Gaps between primes

[complete loony]

RTFA, He then suggests putting a zero flag in the array to signify that the next number is > 65K apart, and a 64 bit number is required.

Re:Gaps between primes

[boky]

Something I remember from high-school:
We had to prove that every prime, except for 1,2 and 3 takes the form:
(6k+1) or (6k-1)
We have proven the point.

So, all primes > 3 are subset of this group.

If you extend this to be a bit more abstract, you come to the conclusion:

If you number all primes from 1 on with p1...pn and your last found prime with pk, than you can safely say that all following primes *MUST* be a subgroup of:

p[1]*p[2]*...*p[k] +/- (p[1],p[2],...,p[k-1])

This is somewhere between the array and brute force method described in the article because you increase the step as you go and the multiplier can be just multiplied with the last found prime in each iteration. The downside being, that you still need to check if the number is prime by deviding it with all prime number found so far which are less than sqrt(n).

This also shows possible gaps between primes.

Re:Gaps between primes

[Anonymous Coward]

Um, That's just a reformulation of Eratosthenes sieve. 2300 years too late to be news.

Re:Gaps between primes

[lildogie]

BZZZT!

Saying X+2 and X+3, where X > 0, are both prime has to be wrong.

One of these numbers is even. The only even prime is 2.

IANAM, but neither is tbjw, I'll wager (nor the five people who modded this post up).

Re:Gaps between primes

[Anonymous Coward]

um, he's calling those numbers nonprime, not prime. bzzzt, youre wrong.

Re:Gaps between primes

[tbjw]

Actually, I am a mathematician of sorts (grad student), but not a number theorist.

If you read my post closely, you'd see that I claimed N! + 2 and N! + 3 were both nonprime (provided N > 2), not that they were prime as you somehow understood.

Re:Gaps between primes

[Nevyn]

Tbjw said "X+2 and X+3 are both non prime, where X is a factorial greater than 3" this being because the factorial has to start with 2x and 3x (if X is divisible by Y, then X+Y is also divisible by Y).

Fun With...

[FunWithHeadlines]

"Fun With Prime Numbers"?! Hey! That infringes upon Fun With Headlines my intellectual property! I'll sue!

Naaaah. I'll let them get away with it by leaving this blatant advertising instead.

(Hint to the clue-challenged: I'm joking. I am not in favor of IP as a concept, which is why I give my feeble jokes away for free, which is about twice what they're worth)

Re:Fun With...

[icekillis]

I believe I calculated the first million primes way before this article did. Are they infringing on my IP? what are my legal posibilities? This guy wrote a book, might be for some good cash.

Re:Fun With...

[FunWithHeadlines]

You and me, we'll form a class action suit. Profit, baby!

PI

[Anonymous Coward]

i fear... i might end up taking a drill to my head.

Re:Pi

[pkhuong]

After seeing Plouffe's inverter, calculating digits of Pi doesn't seem as interesting. One can easily calculate the nth (hex) digit of Pi in constant time, without any FP...

Re:Pi

[fatphil]

Your statement is false.

And given that the majority of the computational transistors on your CPU are in the FPU unit why the heck would you want to waste those transistors by not using them?

FP.

Re:Pi

[pkhuong]

http://www-2.cs.cmu.edu/~adamchik/articles/pi/pi.h tm

"The discoverers sought such a formula because they were aware that it could be used to compute the nth digit of Pi (in base 16), without computing any prior digits. This goes completely against conventional wisdom, and totally eliminates high-precision requirements from a computation of, say, the billionth hexadecimal digit!"

And braino on my part: the advantage is that you CAN use FP, without having to use arbitrary precision math.

Still, by your logic, we should add integers on the FPU instead of the ALU, right? Integer operations are still faster.

whats the big deal with primes?

[bunburyist]

Whats so great about prime numbers? why do they need really big ones? can't they just use small ones? ...why is there an expiry date on bottled water? why oh why!!?

That's nice, but...

[gibs]

Can someone tell me again what the point of this is?

Re:That's nice, but...

[Anonymous Coward]

Well, just look at that shameless banner right below the title on that page... I must admit I am impressed.

Prime post!

[Anonymous Coward]

Factor this!

Re:Prime post!

[Anonymous Coward]

10773554: 2 11 31 15797

FP?

[Anonymous Coward]

Viva Guatemala!

fp

[Anonymous Coward]

gay fp

Number of factors

[Anonymous Coward]

w00t fr1st p0st!!! ;-)

Seriously though, the article doesn't use anything more complicated than the Sieve of Eratosthenes to work out prime numbers - it just writes a list of prime numbers up to n to a file, then uses that to figure out a list of primes up to n^2.

It's still quite cool, though. It checks 40 billion numbers in 3 hours - about 10000 seconds. That means 4 million clock cycles per number - which does seem to be fairly high, considering that half of those numbers will be even, a further sixth will be divisible by 3 (and odd), and so on. None of them will have a factor of more than 200000.

I wonder if fiddling around with bit patterns (taking out sequences of the number being tested against in the number being tested) would speed it up.

Thats neat but...

[SkankinMonkey]

Does this really have any practical use? I remember DeCSS had something to do with decoding using prime numbers, but other than something like that, what will this actually achieve?

Re:Thats neat but...

[fatphil]

DeCSS has nothing to do with prime numbers.

DeCSS was a simple shift-register-based stream cypher.
Likewise DES, AES, RC4, MD5, and stuff like that are nothing to do with prime numbers.

RSA, Diffie-Hellman, El-Gamal - they are to do with prime numbers (i.e. they are based on number-theoretic properties of prime numbers).

Now a couple of years ago some loon who calls himself FatPhil decided to encode the DeCSS program as an archivable prime number, simply so that it could be officially archived somewhere. However, that was basically just a prank - hiding illegal programs in legal numbers.

FP.

first post

[Anonymous Coward]

is my uid a prime number?? Oh wait....

mmm

[Anonymous Coward]

what's the deal with finding the last or the biggest prime number? is it useful for something or what?

The largest known prime is...

[stevok]

2^24036583-1, which contains over 7.2 million digits.

The linked .txt file is 7.1 MB, so it probably will take a while. The Google cache doesn't do the number justice. In fact, the cached number is divisible by 2...

Prime Numbers for cash!

[kuzb]

If you're interested in running a distributed.net-like application with the chance to make some money using your CPU cycles to help find prime numbers, have a look at here. They give some good information about what prime numbers are, and what they're good for.

good lord

[Anonymous Coward]

first post already!

cool

[Anonymous Coward]

cool

Not slashdotted when I went there...

[cmpalmer]

Either he's got a good server, or no one cared enough to look.

That's the ultimate insult -- making the front page of Slashdot, then *not* getting Slashdotted as a result...

Re:Not slashdotted when I went there...

[Anonymous Coward]

Its a plain, static, html page. Doesnt generate much load.

Its when someones php (or worse ASP) driven blog gets posted here that it melts the server.

fpfpfpfpfpfp

[Anonymous Coward]

i have fun with your mom

1st

[Anonymous Coward]

1 is prime is it not?

Re:1st

[Anonymous Coward]

It is not, you fuckhead. Now go swallow some horse cum while being buttfucked by Bin Laden while smelling Bush's rectum, you fucktard. I hope your testicles turn into your eyeballs. I hope are surrounded by 1 million sluts, and have your penis cut off before you get to them. Bitch. Bitch. I need a hug.

College memories

[Anonymous Coward]

I'm dating myself, but this reminds me of a computer science class (late 80s) where we used the Sieve of Eratosthenes to find primes. Had fun writing it on a VAX 8550 and then porting it to our lightning fast 80286 10MHz PCs...

http://mathworld.wolfram.com/SieveofEratosthenes .h tml

Re:College memories

[Anonymous Coward]

I'm dating myself...

Well that applies to many of the slashdot crowd - you don't need to trumpet the fact that you have no girlfriend.

hrmmmm

[Anonymous Coward]

hrmmmmm...interesting

A Favorite Benchmark

[bob beta]

Prime number generating and factoring programs have been one of my favorite 'kick the tires' tests for any new hardware. This goes way back to early times for me, back to when the only programmable device I could own (back in the 70's) was a programmable calculator. It's still something I throw together and run on about anything programmable I acquire. I've even thrown a routine together for my ancient Tandy PC-8 Pocket Computer. Not sure what speed it runs, but it's gotta be a small fraction of a megahertz. Not sure how the old TI SR-56 I started out with in 1977 would rate.

More on that

[pablodiazgutierrez]

Here is way more than you could probably want to know about primes. And I would add an uninteresting linguistic fact: Primo is the Spanish word for prime, which also means 'cousin', which also means 'naive', in a pretty widespread slang over here. That gives any high school math class a new twist :).

L33t

[tepples]

31337 is still prime.

Fun with primes?

[The Master Control P]

How about when you're on the vintage mainframe level in Tron 2.0, ask some random program to calculate the seventh even prime number. When he segfaults, you get access to the directory containing Tron Legacy. Just don't ask yourself that question...

Imagine...

[NiTr|c]

The author was definately imagining a beowulf cluster of prime number solvers.

/.ed

[Bs15]

This site probably won't last long, heres google's cache:
http://66.102.7.104/search?q=cache:3EXdsF5PiA4J:ww w.troubleshooters.com/codecorn/primenumbers/primen umbers.htm+&hl=en/

Reminds me of the ACM office...

[ari_j]

One day, we were hanging around in the ACM chapter office and someone was working on his PC. He asked how big he should make some partition because he just didn't feel like deciding, and someone said "How about a nice, even 5 gigs?"

After a few seconds had passed, somebody pointed out: "Wait...not only is 5 not even ... it's prime!"

Re:Reminds me of the ACM office...

[Anonymous Coward]

Then did someone else point out, that by either definition of gig any number of them IS an even number?

Re:Reminds me of the ACM office...

[ari_j]

The original question was "How many gigs should I make this partition?" so that was an irrelevant concern. Of course, on the same day we had a discussion about number systems with a fractional base, so I think we may have missed the forest for the trees on that observation even if it would've fit. ;)

frist

[Anonymous Coward]

psot

Hm. It might just be a coincidence

[Anonymous Coward]

that he's looking for work.

i need to one up him so I can get away with plugging myself..

First post and where's millar rabin test?

[Anonymous Coward]

I was looking at the article, and I realised there was no mention for fermat's or millar rabin, which I thought was used for bigger scale applications.

But anyways, great article, although the code could be better in terms of style, its just me though i think.

Re:First post and where's millar rabin test?

[Anonymous Coward]

You are thinking of primality testing not prime generation.

Mmmm Primes...

[Anonymous Coward]

My java implementation of the sieve finds the first primes in 10 million in under a second. Just found that interesting, same cpu as this guy but Mobile athlon (its my laptop) and has only 512 ram but for such a low range this shouldnt matter.

Thanks

[PuppiesOnAcid]

Thanks to whoever found this article. It was a "prime" find!

*chortle*

Re:Thanks

[Anonymous Coward]

Your comment id is prime.

First shitting bear post!

[imag0]

Now, who can forget the Prime Number Shitting Bear?

Re:First shitting bear post!

[Anonymous Coward]

I'm amazed it took this long to get posted.

Pi

[TheApocalypse]

Everybody knows that calculating Pi is a better way to get chicks.

NSA Approved

[Anonymous Coward]

The primes generated using these algorithms are officially sanctioned by the NSA.

Happy encrypting, everyone.

And quit trying to overload Echelon, would ya?

sorry but.

[Anonymous Coward]

aparently no one cares.

Re:sorry but.

[Anonymous Coward]

10773689 is prime.

Interesting

[Anonymous Coward]

I've always thought it was cool to see different ways of doing things with programming.

Improvement

[acidblood]

Blockquoth the FA's author, regarding how to store a list of primes:

Keeping it in an array is simplest, but one must declare the array before finding primes. How big do you declare it.

Have a look here for a pretty tight upper bound on the number of primes up to a given number. Using an array, instead of a linked list, would probably lead to a small speed improvement on his code.

He could also use an std::vector from C++. As far as I can tell it's pretty easy to resize.

Re:Improvement

[man_ls]

Using the more granular control of C's malloc functions, it seems to me you could force a linked list type deal to be allocated in contigious memory, then use pointer arithmatic (i.e. arrays) to access it.

I may be totally wrong on this, however.

Re:Improvement

[Tobias Luetke]

I'm pretty sure a std::deque would be in order. Deque is a linked list of arrays with the same interface of a vector.

vector would be a bad choice because on resize it has to copy over the content of the entire old array into the new one, linked list is a bad choice because for each stored number you need another pointer to the next. Deque combines the both so that on resize it just creates a new array and links it to the old.

Re:Improvement

[Anonymous Coward]

What implementation of deque uses a linked list of arrays? All the ones I know use a regular array with stuff put on both ends.

frist psot

[Anonymous Coward]

first post

Re:A better use?

[benna]

encryption.

Benchmarking?

[Man in Spandex]

Is it these kind of algorithms that the makers of benchmark tools to stresstest cpu's? I'm assuming thats what Prime95 does since its called PRIME but I could be wrong and I might be. Anybody to correct me?

hey

[Anonymous Coward]

first post yall

vcic for life

just in case you're interested......

[Anonymous Coward]

startspam: If you want to buy primenumbers.com just send an email to info at 013 dot com. Cheers! endspam

fp

[Anonymous Coward]

frist psot?

Re:A better use?

[Anonymous Coward]

Why not put those CPU cycles to good use with something like Folding@Home?

Or, better yet, UT2004.

Obfuscation at it's best!

[Anonymous Coward]

I'd like to nominate the entries in this article, individually or as a whole, for the 2005 IOCCC. See how he was able to completely obscure his algorithms by using an absurdly outmoded language? Why, it's almost impossible to separate the content from the micromanagement of memory! And what the hell is with that brace style? It does a great job of making it totally unclear how blocks are organized!

(Am I trolling? Just being sarcastic? Genuinely irritated by his lame coding style? Who knows!)

How to do it?

[Anonymous Coward]

Nnnnnnnnah, isn't it?

FP Bitches.

Prime numbers in bad music...

[Kenja]

"One is the loneliest number that you'll ever do Two can be as bad as one, its the loneliest number since the number one"

Reminds me of...

[constandinos]

My Holloween Costume!

I marked up a sweatshirt with a bunch of random prime numbers and, dum roll please, I WAS the 'Indivisible Man'.

Tada.
~tel0p

If you think primes are boring...

[rubee]

take a class in abtract algebra, generally the first class in higher, proof-oriented mathematics. Primes have strong relevance in group theory (which is in itself relevant to quantum mechanics), which leads to rings and fields (widely applicable in linear algebra, analysis), which leads to other advanced topics.

Re:If you think primes are boring...

[suwain_2]

I'm somewhat uncertain how to interpret your "If you think primes are boring..." remark.

I think I know what you meant, but I think I like the literal "If you think primes are boring... take a class in abstract algebra" better. ;)

Re:If you think primes are boring...

[Anonymous Coward]

Go ahead take the abstract algebra class to remove all ambiguity.

Worked for me...

Not as much fun as

[Snoe]

The Prime Number Shitting Bear. Watching a console window spit out prime numbers might do it for the geeks, but everyone can loves the prime number shitting bear.

Re:Not as much fun as

[Anonymous Coward]

I've left the window open since I first read this comment when I got to work. After 4.5 hours its now at:

PRIMESTATS
Prime now:
200257
Prime count:
18005
Prime density:
9%
Uptime: 04:32

Gonna let it go til I leave to go home :)

Re:Not as much fun as

[Anonymous Coward]

Shouldn't that be PRIMESHATS?

Ouch, that hurt.

IOCCC

[Trejkaz]

Is the IOCCC entry one of the methods mentioned? :-p

Execution speed could definitely be improved...

[ivec]

In the bit array version, the following simple change would most likely improve performance by a consequent factor:

The bit shift and bit mask values should be compile-time constants, e.g.:
enum {
bytesPerInt = sizeof(unsigned)*8 ,
bpiShift =(bytesPerInt==16 ? 4 :
bytesPerInt==32 ? 5 :
bytesPerInt==64 ? 6 :
bytesPerInt==128 ? 7 :
0/*->error*/ ),
bpiMask = (1<<bpiShift)-1
};
This will allow the compiler to generate more efficient/hardcoded masking & shifting instructions.

Next, it is pointless to store/test even numbers inside the array - you could nearly double speed here, and simply shift down the array indices by one extra bit.

Similarly, it is easy enough to avoid testing multiples of 3, by alternating between increments of 2 and 4 times the prime number being tested.

Of course, much more can be done (even while maintaining the current level of code portability), but these are the obvious steps I would take to speed-up the presented bit-array method (paged or not).

It is the standard Symbian OS style

[Anonymous Coward]

So I presume that the Brits are either jealous of American programmers or are retarded.

One does not preclude the other, of course.

Re:It is the standard Symbian OS style

[Anonymous Coward]

And it's pretty close to the Wind River indentation style -- unfortunately. Eych.

Yeah

[skazatmebaby]

From the deluge of comments this story has had, perhaps there's been too much fun goin' down...

You forget your algorithm analysis

[Anonymous Coward]

Big O(n/2) is equivalent to Big O(n), so with your suggestion of removing all even numbers results in no speed up at all.

Re:You forget your algorithm analysis

[spuzzzzzzz]

Um, yes, of course. If you double the speed of something, it doesn't have any effect.
\end{sarcasm}

It doesn't change how well the algorithm scales, but it does speed up the algorithm.

Re:You forget your algorithm analysis

[Anonymous Coward]

Maybe you should look for a faster algorithm before you try to optimize the given one.

This is actually the MOST important thing to do!

[Theovon]

For those who scoff at this kind of stuff, we have to keep in mind that it's this sort of tinkering that results in some of the most amazingly useful and interesting stuff later.

I have one lament, which is that his code formatting (indenting) got munged, making it really hard to read the code. I'm really tired, so I just couldn't manage to read through all the C code. I hope he fixes the page so that I can read it more easily later.

Variable structure for the lazy?

[crimson30]

We could keep the list three ways:

1. In an array
2. On disk
3. In a linked list

I'm pretty rusty on programming and haven't done anything in years, but I'm wondering: is there anything new in the way of some sort of a structure that meets arrays and linked lists halfway? Sort of a dynamic array with the flexibility of linked lists and ease of arrays?

Re:Variable structure for the lazy?

[pkhuong]

Well, depending on the architecture and the languages, linked lists can be easy :)

http://en.wikipedia.org/wiki/VList

"In computer science, the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based (or singly-linked) linked lists.

Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference. Like singly-linked or cons-based lists, they are persistent, and elements can be added to or removed from the front in constant time. Length can also be found in O(log n) time."

"The underlying structure of a VList can be seen as a singly-linked list of arrays whose sizes decrease geometrically; in its simplest form, the first contains the first half of the elements in the list, the next the first half of the remainder, and so on."

For some reason, the article affirms that the VList is immutable.

Re:Variable structure for the lazy?

[addaon]

They're immutable (from reading the article, not previous knowledge) in the sense that "adding" an element really consists of creating a new vlist with the old vlist as its tail; references to the old ones can continue to be used unchanged, and will see an unmutated list.

Re:Variable structure for the lazy?

[pkhuong]

It doesn't have to be though. It's just like a normal array wrt mutability, afaics.

Better Implementation

[jkleint]

As mentioned, DJB's primegen is much faster. Even his Sieve of Eratosthenes implementation will do the primes up to a billion in 1.38 seconds on a 2.4 GHz P4, which is roughly 100x faster than this guy's "all primes below 100 million in less than 13 seconds" (although he doesn't specify on what machine). There's no reason to be using huge memory "pages," you can sieve up to N with any size interval you want (like say, the size of your L1 d-cache) using only Sqrt(N) memory for the primes up to Sqrt(N).

Re:Better Implementation

[Anonymous Coward]

I thought the article was just an advertisement for his consulting services(especially considering that he submitted it himself). I don't really think he was attempting to actually implement a fast algorithm.

Re:Better Implementation

[Anonymous Coward]

Def'ly, since he hid not-that-hard math in ugly c code without formating. Looks so sofistikated

Yet Another Prime Program

[Nynaeve]

I am really surprised the author never mentions wheel factorization. It makes the task even easier.
Here is my favorite program. It includes a 64-bit version.

Re:Yet Another Prime Program

[yuriismaster]

You know that page sure looks like this "Semantic Web" that our friend komar exampled... ;)

my code

[MyDixieWrecked]

this is something I wrote a while back to optimize my friend's prime finder he wrote to learn perl (I ported it to C and sped it up a LOT, although mine still sucks).

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
unsigned long long maxprimes = atoll(argv[1]);

printf("calculating %ld primes...\n", maxprimes);

unsigned long long value = 1; //the last prime
unsigned long long count = 0; //the count of primes found

unsigned long long i = 0;

for(count = 0; count < maxprimes; value += 2) {
for (i = 3; i <= (value >> 1); i += 2) {
if (!(value % i)) {
break;
}
}

if (i > (value >> 1)) {
count += 1;
printf("%ld is prime\n", value);
}
}

printf("Found %ld primes!\n\n", count);
}

Re:my code

[Billly Gates]

Unsigned long long?

Is this 64-bit?

Re:my code

[MyDixieWrecked]

yeah, but it works fine on my G4 and my P3, but not my G3, I dunno. it used to just be an unsigned long, but the linked site used long longs, so I switched it. ;)

I just RTFA...

[acidblood]

...and I'm going to list a few improvements here that I think the author missed.

In one of the early programs, the author had the idea of skipping all even numbers, which are of course divisible by 2. In the next program he found out how he could skip numbers divisible by 3. One can make a systematic method out of that -- in the literature it's known as adding a wheel to the sieve of Erathostenes. Thing is, he implemented the sieve of Erathostenes foregoing this improvement he had implemented earlier. This leads to a big improvement: when using a wheel with the first four primes 2,3,5,7, there are only 48 residue classes out of 210 = 2*3*5*7 possible that are not divisible by any of these four primes. In practice this means that, for each 210 numbers you'd consider, the sieve would only need be applied in 48 of them. That's a gain of 4.375. One can make a gain of nearly 5 using a wheel of the first five primes, but it begins to get complicated.

Another improvement would be to make the program cache-friendly. He sort of did this, down one level of the memory hierarchy, by paging the data to disk -- now he only needed to realize that, just as memory is much faster than disk, cache memory is faster than main memory. I've developed a sieve employing this optimization and it pays off indeed. This is considered a basic technique in the realm of high-performance computing. (The NFSNET, see my sig, uses a sieve including this and other optimizations, for instance).

I might get flamed for this, but he should consider assembly programming. There aren't many applications where assembly will pay off so handsomely as this one, and the `core' of the sieve is very small, so only a few lines of assembly are needed. Vector integer instructions, such as MMX and the integer instructions of SSE2, can be employed to very good advantage here. My sieve program also included this, and it gives a real nice boost -- and only about 25 lines of assembly were used, the rest was C.

Lastly there's the issue of representing the output. He stored the primes on disk by writing their values. A little compression can be realized in this representation: for instance he's printing out the primes in decimal, while hexadecimal would be more space-efficient. And instead of printing out the ASCII characters from 0 to 9, A to F, he could use a binary representation and read them through an hex dump -- that saves half the space, as a byte is used to store two hexadecimal digits instead of one.

A perfectly good representation that could save a lot of space (8 times, to be precise) would be a bitmap, which he used on some of his programs. That's where you represent primality or lack of it by setting and clearing bits of an integer. It's pretty easy to determine a prime from a bitmap value, so this representation is just as good as the previous one. One could also use the wheel idea I explained before to save even more space: a concrete example would be that for each block of 210 numbers, one needs only bitmaps for 48 of them, as the rest are divisible by the first four primes. In this example a savings of 4.375 would be realized. Of course, all these ideas would require special readers programs, instead of just opening up the files in a text editor -- a small price to pay for such a large space savings.

But in case only sequential reading of the primes is desired, there is an even more efficient representation: just write out the prime gaps, i.e. the difference between consecutive primes. One bit can be saved by realizing that, other than 3 - 2, all prime gaps are even, so one can just store the prime gap divided by two. One could really nitpick and point out that 0 is an impossible prime gap, so one could subtract two from all gaps, but this gain is too small to be worth the hassle. According to Thomas Nicely (incidentally the guy who discovered the bug on the Pentium FPU during his studies on computational number theory), one could store the prime gaps of all

Re:I just RTFA...

[coyote-san]

You overlooked another key optimization - no number can have prime factors larger than sqrt(N). You don't need to bother computing any of the intermediate primes. With a 210-into-48 encoding you can quickly determine primality of any 32-bit number with a precomputed block of only 2k! This is such a small buffer that you could easily bootstrap it the first time the function is called - you can bootstrap the process by hardcoding nothing more than the first 6 bytes.

This raises an interesting question - is it faster to load precomputed blocks from disk or to regenerate it in the L1 cache? One buffer would hold the first block, a second buffer would hold the 2nd-Nth block computed on demand, and a third buffer would hold the target block that's being updated by each successive block.

Re:I just RTFA...

[anethema]

If you're so worried about disk space, convert the bitmap to a png. More computationally intensive, but MUCH greater disk savings. Depends what you're concerned about.

Re:I just RTFA...

[Anonymous Coward]

Do you know any good C/C++ algorithms for:

uintmax_t prevprime(uintmax_t x);
uintmax_t nextprime(uintmax_t x);

where prevprime returns the prime number = x?

I'm looking for something that:

doesn't use any floating arithmetic unless you can prove their algorithm will never fail on any input

no dynamic memory used during runtime

a small fixed amount of stack variables

can use a small static LUT preferbly < 4K

no recursion except tail recursion (and no use of tail recursion to get by the dynamic memory constraint) unless the recursion has an upper bound of log2(UINTMAX_MAX)+1

doesn't depend on the value of UINTMAX_MAX and will work on any machine with just a recompile. I'm willing to relax this constraint if you only have one that works on 64bit integers.

It's undefined what happens if you do prevprime(x) for x 2 and nextprime(x) for all x's that will generate a primer larger than can fit in the number of bits.

Re: I just RTFA...

[Omniscient Ferret]

Another improvement would be to make the program cache-friendly. He sort of did this, down one level of the memory hierarchy, by paging the data to disk -- now he only needed to realize that, just as memory is much faster than disk, cache memory is faster than main memory.

Some of the programs sieved into smaller pages, which could fit into caches. He noted that page sizes of a million worked well for him, but he thought it might have to do with directory access with a large number of files.

Re:I just RTFA...

[BigBadDude]

check this one out:

http://cvs.sourceforge.net/viewcvs.py/buddy/budd y/ src/prime.c?view=markup

(there are zillions more, but this page was the one that i had in memory)

Re: I just RTFA...

[Omniscient Ferret]

That's where you represent primality or lack of it by setting and clearing bits of an integer.
Working out the mask for those bit operations can take enough time to cancel out the space benefits. I think you could optimize the different masks & their steppings.

... there is an even more efficient representation: just write out the prime gaps, i.e. the difference between consecutive primes.
I tried this, but I don't know where that program is now. I used 0 as an escape code, allowing me to either note the next delta in hex, or else the current number, to detect errors. I only did this for output, though.

I could see that being effective for the trial factor prime number table, too.

Oh, and the nfsnet thing that's your homepage is cool.

There's a primes program in (uh, on Debian) the bsdgames package; if memory serves, it does the wheel thing suggested.

A suggestion for the article:
If the trial factor prime number table gets big enough to swap (either out of cache, or out to disk), just segment the trial factors too.

This is something I've given a lot of thought to; I've been interested in prime numbers since I was a kid. I've thought about making CDs or DVDs full of primes.

Re:I just RTFA...

[Anonymous Coward]

oh no, probabilistic primality testing.

Re:I just RTFA...

[acidblood]

The GMP library uses a probabilistic algorithm as documented here. This is not as bad as it sounds. For instance, Dan Bernstein suggests in this paper a probabilistic procedure which consists of some trial factoring, a strong probable prime test and a Lucas test. Quoting him:

There is no known example of a composite number p that slips past all of these tests; I'm confident that nobody will ever find one by accident.

Of course, if you absolutely have to be sure that you're dealing with a prime, you could use a probabilistic algorithm to sieve for probable primes, then apply the n-1 test to obtain a primality certificate for your probable prime (which then becomes a certified prime with 0% probability of being composite). Of course this would be a bit costly, but for small integers the n-1 test is hard to beat -- ECPP and APR-CL have just too much overhead at this range. But I'm pretty sure your application, whatever it is, can live with the small probability that a PrP is composite.

Re:I just RTFA...

[Anonymous Coward]

I really, really hope you're joking...

Re:I just RTFA...

[gotan]

Another idea would be to leave out even numbers altogether. This could be done with some simple shift-operations and maybe a one-off in some places.

I don't know how that "wheel" is efficiently implemented, but a simple way of doing it might be just initialisation with that 210 bits in a periodic manner (or 105 if you just consider odd numbers), or, to avoid bit-operations, with the first 210 bytes. Since the low primes result in the most bit-operations that'd already help a lot.

Re:I just RTFA...

[johntromp]

Covering 30 numbers per byte and precomputing all the bit-indices, one arrives at: http://www.cwi.nl/~tromp/pearls.html#sieve

Re:I just RTFA...

[Anonymous Coward]

I think that you think that he thinks about JPG, which is usually lossy format, but I think you should think about him thinking about PNG, which iss lossless format, I think.

Re:I just RTFA...

[The_REAL_DZA]

Ok, as soon as you mentioned storing the ongoing results in a bitmap I started wondering about what pretty patterns (if any; it sounds like the distribution of "1" bits would be so sparse that the picture would be mostly "0"'s; black...) might be derived from wrapping the string of Prime/NotPrime bits across a bitmap "window" of various "widths"...

Great. I wasn't having enough trouble forcing myself to set up those WinXPSP2 machines gathering dust in the lab... ;-)

Re:I just RTFA...

[antispam_ben]

I think that you think that he thinks about JPG, which is usually lossy format, but I think you should think about him thinking about PNG, which iss lossless

The bitmap formats discussed for storing primes is an earlier meaning of the word (before the .bmp picture file format), simply a long string of 1's and 0's where the 1's represent the presence of something (in this case that the number represented at that bit number is prime) or 0 for its absence (that the number is composite).

Yes, I suppose you could convert it to a .bmp file format and then convert that to a .png which I presume is a lossless compression format. However, primes represented in binary forms such as a bitmap tend to be no more compressible than random numbers by their nature, so running such a file through a data compression algorithm won't get you much compression.

IOW, Fugetaboutit.

It RAISES the question. NO begging is involved :D

[Anonymous Coward]

From here:

"Dear Evan: You may have already addressed this question, but I'd like to hear your opinion on one of my pet peeves. "To beg the question" does not mean anything even remotely similar to "to lead us inexorably to the question" or "causes us inevitably to ask the question." It means to assume an answer to an unstated question or premise. It was used correctly on a recent episode of "The X-Files" when Mulder and Scully were discussing what was purported to be an alien autopsy. The exchange goes something like this: "Mulder: What is that green fluid? Scully: Blood? Mulder: It's widely held that aliens don't have blood. It must some unknown autopsy apparatus. Scully: That begs the question that it's an autopsy, let alone one of an alien." See what I mean? -- Michael Raynor, via the Internet.

I say, your question gives me a marvelous idea. Would you mind writing this column while I nip off to the Bahamas for a month or two? It's really not hard at all -- you just look things up in four or five hundred dictionaries and pick the answer that seems most plausible. I've found that you can usually fill the first paragraph of your answer with silly banter, anyway.

Regarding your question, I do see what you mean. Incidentally, if people on television have begun using proper English, perhaps it's time for me to buy a TV. I have never seen "The X Files," but if what you describe is typical dialog, the scriptwriters must be holding an English major hostage -- they did indeed use "beg the question" correctly. It does not mean "raises the question," or that the question itself begs like Oliver Twist ("Please, Sir, may I have an answer?"). It means to bypass or avoid an essential question, but to proceed as if it had already been answered. The Latin name for this sort of thing is "petitio principii," by the way. In your example, to discuss the color of alien blood sidesteps (or "begs") the rather essential question of whether there are such things as aliens in the first place. Similarly, my offer to you "begs the question" of whether I can afford to go to the Bahamas for a month or two in the first place, which I can't, so I'm afraid the deal's off."

Time to get back to earning my $100,000 ticket to a lifetime of burger-flipping.

Fun with C

[SirShadowlord]

Okay, could somebody explain to me (who hasn't touched C in about 10 years), a couple things about this code.

First, what's with the %ull format specifier in sprintf - is that even a valid format specifier?

Next, why subtract 2 from your buffer length when printing?

Finally, why bother with the "printprime" and sprintf function altogether - is there anything wrong with:

if (prime) printf("%llu\n",candidate);

Okay, this is kind of nitpicking, but I'm clearly missing something obvious here...

Re:Fun with C

[Jeremy Erwin]

First, what's with the %ull format specifier in sprintf - is that even a valid format specifier?

Next, why subtract 2 from your buffer length when printing?

Finally, why bother with the "printprime" and sprintf function altogether - is there anything wrong with:
if (prime) printf("%llu\n",candidate);
Hmm. Perhaps I didn't get much sleep when I typed^W pasted the code into emacs and compiled it on my powermac, but it seems that that piece of code ensures that only x86 machines can properly run the code. All the program did was output a long list of zeros.

I did try converting the program into C++, but massive slowdowns ensued. The eternal dilemma-- correctness or speed.

Give it up; this battle is a lost cause.

[Anonymous Coward]

Mainstream language usage determines the accepted meanings of words and phrases. This phrase is used incorrectly by millions of people (myself included). It is only a matter of time before the dictionary is updated. It's nice to see the X-Files mentioned, though. Such a great show (until season 7). Now it's just a filler for late nite slots on TNT. So sad.

Re:Give it up; this battle is a lost cause.

[Anonymous Coward]

Actually, I looked up the actual X-Files quote, and they used it incorrectly too. :D

Re:Give it up; this battle is a lost cause.

[Bastard of Subhumani]

Mainstream language usage determines the accepted meanings of words and phrases.

Would a "mainstream belief" in the earth being flat determine geographical or geological fact?

I put it to you, sir, that it would not.

Re:Give it up; this battle is a lost cause.

[BJH]

If the primary existence of the Earth was as a collective consensus among humans, yes.

You're comparing apples and oranges here. Language does not exist as an objective reality; it relies entirely upon the internal representation of that language shared between its speakers. If in the future nobody understood that language, it would no longer "exist" in any meaningful sense, whereas the Earth exists independently of the internal reality any human (or other being) holds to be true.

In other words, the only way a language can be said to exist is as a "mainstream belief" of its speakers. So, you lose.

Re:Give it up; this battle is a lost cause.

[Anonymous Coward]

phrases mean what the mainstream thinks it believes. Currently you and I and most others think that "the earth is flat" is a statement positing that the earth is planar rather than spherical.

In five hundred years, it might mean "the pie is shapeless". If you were plunked down there by a time machine, I hardly think you'd start trying to get people to change their minds about the meaning.

To put it another way, go out and start telling people "I'm gay" when you in fact mean "I'm happy". Gay no longer means happy in the traditional sense. It's a pity, but these things happen.

"Begs the question", in its original Logicians sense, is a terrible phrase which deserves to die. If you mean "that's circular reasoning", why not just say so? Anyway, it's always screamingly clear from the context which was meant, so why worry about it?

Re:Give it up; this battle is a lost cause.

[Anonymous Coward]

"Begs the question", in its original Logicians sense, is a terrible phrase which deserves to die. If you mean "that's circular reasoning", why not just say so?

The phrase "begs the question" does not appear in the post you're replying to. Which begs the question of whether you're an idiot or just clumsy.

Re:Give it up; this battle is a lost cause.

[Bastard of Subhumani]

If the primary existence of the Earth was as a collective consensus among humans, yes.

And if my aunt had balls she'd be my uncle.

You're comparing apples and oranges here.

And every argument you make is hypothetical.

Language does not exist as an objective reality

No matter how many people use "it's" as a posessive - sorry other people, I'm sure you do - it isn't correct. It matters not one iota if it becomes the accepted standard in the 2037 OED, here and now it is wrong. Period.

So, you lose.

You presume to lecture us on logic and/or metaphysics then resort to proof by assertion. What will you delight us with next? Perhaps an ad-hominem, it's what I'd expect from a stupid twat like you.

Re:Give it up; this battle is a lost cause.

[BJH]

If you don't understand an argument, just say so. It'll make you look better than resorting to infantile insults.

I agree with this post.

[Anonymous Coward]

Sincerely,
John Ashcroft (retired)

Well I'm ZERO!

[Anonymous Coward]

Hey none of you buggers would be anywhere without me! Without Zero, 10000 would just be 1-nothing-nothing-nothing-nothing. w00t!

Re:Fun!

[Anonymous Coward]

Cool, that's the Prime time, baby! Yeehaw, your mom's a virgin.....oh...wait...

Re:A better use?

[eclectro]

Excuse my ignorance, but what are extremely large primes used for?

Obviously to get a date with a hot chic so you can impress her with the math you know.

Re:This is actually the MOST important thing to do

[Domini]

Actually the code indentation problem is only present on my system in the OS X Safari browser... I tried Camino, and presto, it works right!

Even IE for Mac seems to do the indentation 'right' (But not pronounced enough).

Safari seems to do the layout totally haphazardly! The code is really unreadable... I was sure more people here would have noted that, but seemingly not many people use Safari.

Tip: Use Camino... it's really a lot faster and seems to work for more sites.

also doesn't make sense

[Trepidity]

Shouldn't any decent optimizing compiler (gcc?) inline those commonly-called functions anyway?

Re:also doesn't make sense

[nicolas.e]

Or even without a decent compiler, he could declare the functions "inline".

Oh my!

[davew2040]

"There are faster algorithms on the net, but these algorithms are within the reach of mere mortals and are fully explained."

Well jeebus Mildred!!

can someone

[Anonymous Coward]

convert this to c# for me?

Prime numbers and why we like them

[DemiserJ]

As a few people have enquired but nobody's answered . . . Prime numbers are useful for a few things but the one I know a bit about is encryption and digital signatures. Most modern day (digital) encryption algorithms use large prime numbers because of their various properties. By using modular arithmetic and prime numbers as keys, strong encryptions can be formed because prime numbers are very hard to factorise. (They use large numbers don't forget) You'll probably find that a lot of the digital encryptions and signatures that you use on your computer either by compressing (and encrypting) files, using https, certificates of authority as well as others will use prime number theory as part of their algorithm. Hope this was some help.

Public Key Encryption

[AT]

Prime numbers are used in public key encryption. This type of encryption relies on having a function that is easy to generate, but very difficult to reverse. Factorization of large numbers is exactly the function that is used in practice: the prime factors of a large number can easily be multiplied together to get an even larger number, but getting those prime factors back from the giant number is hard. In fact, as the giant number size increases linearly, the time to calculate the factors increases exponentially (using the best known algorithms).

That's their usefulness

[Anonymous Coward]

But where is their beauty? Like was mentioned before, fibonacci shows up all over the place, pi is at the core of almost everything, and you can't take a look at anything without visualizing the Golden Mean.

The use of prime numbers in encryption is fine and dandy, but no more complex than using something simple like Blowfish which is essentially a one-time pad. A thing's application does not establish its beauty.

There was a post above that pointed to a pictograph of primes plotted in a spiral manner in which diagonal streaks were visible, but that seems a wee bit contrived. Primes seem to be an interesting property of numbers, but they do not seem to have a natural "manifestation" which would grant them beauty.

Re:That's their usefulness

[d34thm0nk3y]

Beauty is truly in the eye of the beholder. Are fractals beutiful because of the interesting properties of the DE that creates them or because they make pretty pictures?

How to prove that all odd numbers are prime

[dargaud]

"It was mentioned on CNN that the new prime number discovered recently is four times bigger than the previous record." --John Blasik

"You know what seems odd to me? Numbers that aren't divisible by two." --Michael Wolf.

"I don't get even, I get odder."

How to prove that all odd numbers are prime? Well, this problem has different solutions whether you are a:

• Mathematician: 1 is prime, 3 is prime, 5 is prime, 7 is prime, and by induction we have that all the odd integers are prime.
• Physicist: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is an experimental error...
• Engineer: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime...
• Chemist: 1 prime, 3 prime, 5 prime... hey, let's publish!
• Modern physicist using renormalization: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is ... 9/3 is prime, 11 is prime, 13 is prime, 15 is ... 15/3 is prime, 17 is prime, 19 is prime, 21 is ... 21/3 is prime...
• Quantum Physicist: All numbers are equally prime and non-prime until observed.
• Professor: 1 is prime, 3 is prime, 5 is prime, 7 is prime, and the rest are left as an exercise for the student.
• Confused Undergraduate: Let p be any prime number larger than 2. Then p is not divisible by 2, so p is odd. QED
• Measure nontheorist: There are exactly as many odd numbers as primes (Euclid, Cantor), and exactly one even prime (namely 2), so there must be exactly one odd nonprime (namely 1).
• Cosmologist: 1 is prime, yes it is true....
• Computer Scientist: 1 is prime, 10 is prime, 11 is prime, 101 is prime...
• Programmer: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 will be fixed in the next release, ...
• C programmer: 01 is prime, 03 is prime, 05 is prime, 07 is prime, 09 is really 011 which everyone knows is prime, ...
• BASIC programmer: What's a prime?
• COBOL programmer: What's an odd number?
• Windows programmer: 1 is prime. Wait...
• Mac programmer: Now why would anyone want to know about that? That's not user friendly. You don't worry about it, we'll take care of it for you.
• Bill Gates: 1. No one will ever need any more than 1.
• ZX-81 Computer Programmer: 1 is prime, 3 is prime, Out of Memory.
• Pentium owner: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 8.9999978 is prime...
• GNU programmer: % prime
  usage: prime [-nV] [--quiet] [--silent] [--version] [-e script] --catenate --concatenate | c --create | d --diff --compare | r --append | t --list | u --update | x -extract --get [ --atime-preserve ] [ -b, --block-size N ] [ -B, --read-full-blocks ] [ -C, --directory DIR ] [--checkpoint ] [ -f, --file [HOSTNAME:]F ] [ --force-local ] [ -F, --info-script F --new-volume-script F ] [-G, --incremental ] [ -g, --listed-incremental F ] [ -h, --dereference ] [ -i, --ignore-zeros ] [ --ignore-failed-read ] [ -k, --keep-old-files ] [ -K, --starting-file F ] [ -l, --one-file-system ] [ -L, --tape-length N ] [ -m, --modification-time ] [ -M, --multi-volume ] [ -N, --after-date DATE, --newer DATE ] [ -o, --old-archive, --portability ] [ -O, --to-stdout ] [ -p, --same-permissions, --preserve-permissions ] [ -P, --absolute-paths ] [ --preserve ] [ -R, --record-number ] [ [-f script-file] [--expression=script] [--file=script-file] [file...]
  prime: you must specify exactly one of the r, c, t, x, or d options
  For more information, type "prime --help''
• Unix programmer: 1 is prime, 3 is prime, 5 is prime, 7 is prime, ...
  Segmentation fault, Core dumped.
• Computer programmer: 1 is prime, 3 is prime, 5 is prime

Re:How to prove that all odd numbers are prime

[Anonymous Coward]

Not to ruin a good joke, but I thought that 1 is not a prime?
(Doesn't it start with 2?)

Some mathematician confirm please :)

Re:How to prove that all odd numbers are prime

[shobadobs]

Yeah, all those people seem to be under the delusion that one is prime... The number one is neither prime nor composite though (you'd think the mathematician in the joke would know that).

Re:How to prove that all odd numbers are prime

[enbody]

Funny post!

Note, however, that 1 is not a prime. Citation: According to wikipepdia: "The number 1 is neither prime nor composite;"

Re:How to prove that all odd numbers are prime

[Morosoph]

Indeed. Besides, if 1 were prime, the fundamental theorem of arithmetic would be false.

Re:How to prove that all odd numbers are prime

[Kynde]

Yeah, all those people seem to be under the delusion that one is prime... The number one is neither prime nor composite though (you'd think the mathematician in the joke would know that).

Actually, 1 not being a prime is more of a consensus than a mathematical fact.

Primes could be defined so that 1 is also a prime, it's just that way too many theorems we have these days would need to be refined to deal with 1 properly (starting with the fundamental theorem of arithmetics). Which is almost the same as to say, things are easier when 1 is not regarded a prime. But that doesn't imply that 1 is not a prime.

One could argue that it would be more practical if a positive interger would either be a composite or a prime. Because positive integers now split into three classes: Primes, composites and 1. Meaning that negating prime theorems for composites require special handling with 1.

Now, I wouldn't go telling anyone that 1 is a prime. But I'd be lieing if tried to claim that I remember to include it as an option when I'm assuming a number to be a prime when I've discovered that it's not a composite. Moreover, I must admit that, deep down, I do think of it as prime. It's just that the consensus is to leave it out of the equations, just like when we hop from N to Z+, to make things a little bit easier.

Re:How to prove that all odd numbers are prime

[koogydelbbog]

> ZX-81 Computer Programmer: 1 is prime, 3 is prime, Out of Memory.

using INT PI rather than "3" will save you a couple of bytes if memory is tight (because all numbers in sinclair basic had a 6 byte overhead on top of their length whereas INT PI is just two 8-bit tokens)

see also:
http://slashdot.org/comments.pl?sid=105859& cid=901 6933

Re:How to prove that all odd numbers are prime

[Anonymous Coward]

1 is not prime by definition. You could consider 1 prime, but then you'd have a different concept that wasn't "prime." (though very close)

Re:How to prove that all odd numbers are prime

[starglider29a]

• Rocket Scientist: Built-in hold at 31... 29, 23, 19, 17, 13, 11, Ignition Sequence Start, 5, Main Engine Thrust Nominal, SRB Ignite

Re:How to prove that all odd numbers are prime

[Kynde]

1 is not prime by definition. You could consider 1 prime, but then you'd have a different concept that wasn't "prime." (though very close)

Excuse me?

Sadly you're just an ac, because now I'll never get to hear what this "primeness" would be that 1 is so close to. Your comment really is just an insult to either me or you, and I'm guessing you didn't mean it either way so I'm assuming it's you. Thenagain, you may have had a hunch you were on thin ice, posting as ac the way you did.

Re:How to prove that all odd numbers are prime

[trilliwig]

Hm, I guess you could say it's a matter of consensus that 1 is not prime, but it really is the most useful classification. If you must put 1 into a box, you can call it a unit, because this provides the most logical extension to general number fields where the integers can be classified into one of {zero, units, primes, composites}. http://www.utm.edu/research/rimes/notes/faq/one.ht ml goes into more detail.

Re:How to prove that all odd numbers are prime

[trilliwig]

Nuts, the correct link is http://www.utm.edu/research/primes/notes/faq/one.h tml

Re:How to prove that all odd numbers are prime

[Chris_Jefferson]

One of the quickest definitions of prime is "A number divisable only by 1 and itself.". 1 satisfies this.

Now you know (if you ever read this..)

Chris

Re:How to prove that all odd numbers are prime

[Kynde]

One of the quickest definitions of prime is "A number divisable only by 1 and itself.". 1 satisfies this.

Well, that post of mine was iself a reply to a reply to my post. Having read that you might have understood me better.

That won't work. Unless you change the forementioned huge amount of theorems, starting from the fundamental theorem of arithemitcs.

The most commonly used definition is "a prime has exactly two factors. Itself and one." Therfore 1 is not a prime. 1 not being a prime, simplifies numerous theorems. (e.g. the fundamental theorem of arithmetics, which states "Any positive integer can be represented in exactly one way as a product of primes." If 1 was a defined to be a prime that would have to modified. It can be done, but the consesus these days is that it's just easier to define 1 not to be a prime.

more prime numbers

[mikkom]

Here is some more fun with prime numbers: "Prime number shitting bear"

Re:more prime numbers

[Anonymous Coward]

Didn't someone once use a similar script, but lay its output on a {non-ursine} picture that will be rather familiar to seasoned Slashdot users?

stupid html formatting

[Anonymous Coward]

where prevprime returns the prime number <= x and nextprime returns the prime number >= x.

2 + 2 does = 5

[judowillreturns]

Let x = y
Multiply both sides by x:
x^2 = xy
Subtract y^2:
x^2 - y^2 = xy - y^2
Now we can factorise. The left side is done using the difference of two squares method, the right is a simple factorisation.
(x + y)(x - y) = y(x - y)
Now we can cancel out (x - y) i.e. divide both sides by this:
x + y = y

So if x = y, then x + y = 2y
Therefore:
2y = y

Give y an arbitary value, e.g. 1:
2 = 1

We can also set y to the power of 0 on both sides, also giving us
2 = 1

IANAM (I am not a mathematician, nor a great speller).

*Sanity note: Yes, there IS a flaw with this, how long will it take /. to figure out high school maths?

Re:2 + 2 does = 5

[IdntUnknwn]

In the interest of not spoiling it for anyone who has not already figured it out, all I will say is that the problem is in the 4th step (including the step x=y).

Re:2 + 2 does = 5

[IdntUnknwn]

Well that was unclear :P I mean the problem occurs when you divide by (x - y)

Re:2 + 2 does = 5

[Anonymous Coward]

how long will it take /. to figure out high school maths?

Well, considering this joke is posted EVERY SINGLE FUCKING TIME there's anything remotely math related on this site, I doubt it will take long at all.

Why don't you post the women=evil joke too? I'm sure we haven't heard that one too much either.

Re:2 + 2 does = 5

[Anonymous Coward]

Sure, it is just like black holes: "when god divides by zero"

ummm

[Anonymous Coward]

Ok, i'm dumb... What good is knowing all these numbers???

all odd nembers = 3 are prime: proof

[Edie O'Teditor]

Asked to prove that all odd numbers >= 3 are prime the students responded as follows:

• Mathemetician: 3 is, 5, is 7 is, so by induction they all are.
• Physicist: 3 OK, 5, OK, 7 OK, 9 ... mmm (crosses it out and writes "experimental error" beside it), 11, 13, 15 (see 9) ... OK ...
• Engineer: 3, 5, 7, 9, 11, 13, 15 ... seems OK to me!

Weird behaviour...

[c0p0n]

...since says to me something about a forbidden 503, which is a prime number...

Re:Weird behaviour...

[Anonymous Coward]

403 is Forbidden, which is not prime.

Sorry? What sort of first years?

[N Monkey]

the list of proofs is entitled "15 good reasons why Pure Mathematics is not taught to first year students."

Do you think they just mean arts students?!!

I'm sure we (i.e science students) had no problems with simple proofs of that nature in our first year pure maths subjects. (shrug)

Re:Sorry? What sort of first years?

[Anonymous Coward]

No, they were most likely speaking about science and engineering students in particular.

you are missing the point

[dominux]

a very very small number of large primes are Mersenne numbers, a very very small number of Mersenne numbers are prime. The point with the Mersenne numbers is that there are slightly more likely to be prime than a random large number and more importantly various mathematical tricks can be used to test a mersenne number for primality so they are quicker and easier to test than other numbers. These are the reasons why it is valid to say that most very large discovered primes are Mersenne numbers

Re:A better use?

[maxwell demon]

To get a story at slashdot, of course.

Of course there are also some less important uses in programs like pgp or ssh ...

litt

[Anonymous Coward]

this give obviously loves his own name very much. he uses it under *every* heading of the page..

Oxymoron

[j4ck50n]

"Fun" with "Prime Numbers"...cmon.

You missed one

[wowbagger]

You missed one:
Slashdot:

• New prime number 11 found posted by Hemos
• Conservatives hide evidence of new prime number to confound encryption posted by Michael
• 9's primeness stolen by Republicans posted by Timothy
• Primeness in a post-9 world posted by Jon Katz
• New prime number 2 higher than 9 found posted by CmdrTaco

Alternately adding 2 and 4

[ajs318]

This was the method I used in my first attempt to write a prime-number generator. I figured that any positive integer can be written as 6n, 6n+1, 6n+2, 6n+3, 6n+4 or 6n+5 where n is an integer; and furthermore, 6n, 6n+2 and 6n+4 are definitely even, while 6n+3 is definitely a multiple of three. So we only need to try 6n+1 and 6n+5 to see if they are primes. Also, the smallest prime factor of a non-prime number must be smaller than or equal to its square root; so you don't need to try every known prime for divisibility. Rather than do a square root, though, I squared the testing_factor and compared it with the prime_candidate. This is quicker for small prime_candidates; but, as the list of known primes {and thus testing_factors} grows, eventually the many multiplications will start to take longer than one square root evaluation. The crossover point actually is a system-by-system variable, since it depends on FPU performance.

I subsequently worked out that any list of primes stopping one shy of a product of primes-so-far {6, 30, 210, 2310 ..... } can be used, with very slight modification, as a sort of pre-sieve to eliminate things that are never going to be primes. For instance, looking at 30n+m, the "potential primes" are 30n+1, 30n+7, 30n+11, 30n+13, 30n+17, 30n+19, 30n+23 and 30n+29. {The primes smaller than 30 are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29; see how we simply have excluded everything which is a factor of 30, and included 1.} This list is good up to and including 209 {210 = 2 * 3 * 5 * 7} beyond which a new list will apply going something like 210n+1, 210n+11, 210n+13 ..... }

Now this is beginning to look like a recursive process! Mind, we're getting longer and longer lists as the density of primes is getting smaller. Hmm ..... I think I might have to go and investigate .....

Re:Alternately adding 2 and 4

[antispam_ben]

It appears you may be reinventing The Wheel. (I always wanted to say that, sorry...) That article discusses using the wheel for factorization, but it can also be used for compact storage of primes in a bit array. For example, a bitmap corresponding to only odd numbers would be a "wheel size" of two. If you also drop every bit divisible by three, you have a "wheel size" of six.

Surf around that site (http://primepages.org/), there's lots of good info there.

Try this out obfuscated

[jlcooke]

http://jlcooke.ca/oclug/oprimes.c

Obligatory Gentoo comment

[Anonymous Coward]

Considering this occurred on an $800 commodity box running standard Mandrake 10 Linux with X running along with several other programs, I'm impressed.

Now if he had been running this on a Gentoo box with the -mspeedyprimecalcs flag...

Re:Obligatory Gentoo comment

[Anonymous Coward]

> running this on a Gentoo box with the -mspeedyprimecalcs flag...

... he'd still be compiling his program.

MOD PARENT DOWN

[Anonymous Coward]

+4 Informative for useless b1tching that isn't even correct?

Java examples?

[tedgyz]

Anybody have Java equivalents of these toy programs? I want to play in my native tongue.

Re:Java examples?

[Anonymous Coward]

If you build it, they will download.

Or, perhaps open up your browser, and type in http://www.google.com

In that place to type in "stuff," try entering in Java Primes

Primes may be good for Extreme Encryption

[VernonNemitz]

The algorithm still needs to be proved. Everything you need to know about the proposal is here.

Score 6, Informative

[p3d0]

Thanks for the interesting post. I wish there were more here like yours.

Re: prime error codes

[Anonymous Coward]

401 Unauthorized

The creators of a Web page may want only certain people have access to that page. You should only retry the request if you know that you have authorization.

409 Conflict

The request could not be completed due to a conflict with the current state of the resource. This code is only allowed in situations where it is expected that the user might be able to resolve the conflict and resubmit the request.

503 Service Unavailable

The server is currently unable to handle the request due to a temporary overloading or maintenance of the server. The implication is that this is a temporary condition which will be alleviated after some delay. If known, the length of the delay may be indicated in a Retry-After header. If no Retry-After is given, you should handle the response as it would for a 500 response.

From this it follows...

[Otto]

therefore the average information content of a single prime is obviously zero

From this it follows that the entire information content of all the primes is also zero, and anybody you may meet who thinks differently is merely the product of a deranged imagination.

For extremly large values of 2

[mrnick]

2+2=5

*For extremly large values of 2

Eliminate More Redundant Checks

[CarbonRing]

There are a couple of easy improvements that can be made to Mr. Litt's program that I haven't seen mentioned.

When removing multiples of a new prime p, you don't need to test the even multiples of p, 2 already did that for you. This cuts your work in half.

Although less asymptotically beneficial, you can start with p^2 since the lower multiples of p have already been done in previous passes.

Encoding of successive prime differences

[antispam_ben]

Check out my page below, with some non-guaranteed C code (compiles with Borland C++ 4.5 compiler). Using a full 8 bits to store prime gaps is rather inefficient, I do the same with almost half the number of bits. Since the vast majority of prime differences for primes less than 2^32 is less than 30, the differences can be stored as one of 30/2=15 numbers, and thus stored in four bits. I only use 15 values available in 4 bits to represent gaps from 2 to 30, and use the 16th for an escape code to mean the next 4 bits represents a gap value of 16 through 30 (or something like that - read the webpage, read the code documentation for whatever you can get out of it, I wrote this last century...).

http://mindspring.com/~benbradley/number_theory.ht ml

I did a little more work since writing the webpage. Using four bits for gap storage appears to be the most compact up to 2^32, but not too far above that (I forget where), five-bit gaps become more compact. Writing code to pack and unpack five-bit gaps is, of course, left as an exercise for the student.

(btw [sneaking in metadiscussion], for some odd reason, I now have excellent karma, and my posts sart out at +2, which I can presumably prevent by checking the "No Karma Bonus" box. Why would I ever want to do that?)