Mathematics jokes

bobbym · 2013-04-09 04:09:14

What is the way that you are generating yours and what are you using as a language?

Agnishom · 2013-04-09 04:21:10

Python(ya, its slow)
I am doing it this way

1. Load the previous list of primes(which I made six months ago)
2. Define the miller-rabin with k=7
3. Define the primality test which says whether or not a number is prime by checking whether it is divisible by all the primes which are in the list of primes upto the square root of the given number
4. Let n = the last prime in the list loaded
5. If n = 9999999999, terminate
6. Increment n by 1
7. If miller-rabin claims  n to be prime, proceed to 8, otherwise goto 5
8. If the real primality test claims n to be prime, proceed to 9, otherwise goto 5
9. Write n in the file, goto 5

bobbym · 2013-04-09 04:28:08

There are a couple of possible bottlenecks there.

First how fast is line 8? What method is being used?

Line 6, should be increment by 2.

Agnishom · 2013-04-09 04:30:49

Ya, thats a. Good point

For 8, reffer 3

bobbym · 2013-04-09 04:32:43

Two tests for primality are redundant.

Agnishom · 2013-04-09 04:39:15

But the Miller rabin is done at first so as to save time

bobbym · 2013-04-09 04:43:18

Yes but is it really saving time? I would totally go with the Miller - Rabin.

Agnishom · 2013-04-09 04:54:16

If you would totally go with the miller-rabin, then how would you be sure whether the number you're going through is prime or not?

bobbym · 2013-04-09 05:02:05

There are things that are almost certainly true. They are so rare as to be impossible.

Agnishom · 2013-04-09 05:10:42

bobbym wrote:

Okay, with k = 7 there was less than one chance in 16384 that it was making a mistake.

The risk is not worth it.
I am making a lot more primes than 16384

bobbym · 2013-04-09 05:17:48

Supposing you doubled k? What do you think will happen?

Agnishom · 2013-04-09 05:22:51

But still, what if I am one of those unlucky guys out of 100000000 who get a wrong result?

Agnishom · 2013-04-09 05:27:55

By the way, last day at 12:30 at night I told Alokananda that her phone number is the sum of two primes. Than I told her that there are more than 113274 ways of representing that

She was perhaps shocked and said something which translates like "You do such things at night? Are you mad?"
Then she said, "Had it been any other girl, you would have driven them mad. Only because I am Alokananda, I am still not mad"

bobbym · 2013-04-09 05:29:06

If you chose k = 14 then and if you generated 250 000 000 primes you should expect to only have 1 false prime in the list!

If you chose k = 21 you would need to generate 4 billion primes to expect to have 1 wrong!

But still, what if I am one of those unlucky guys

Do you know that you take a gamble like that everyday? You do not get unlucky.

Isn't it better to generate your list knowing there is an extremely tiny chance that one of them is false rather than generating no list that is perfect!

Agnishom · 2013-04-09 05:36:11

If I choose k=22, how much time would it take to complete upto 9999999999(10 digits)?

bobbym · 2013-04-09 05:42:57

how much time would it take to complete

That is another question. Right now we are dealing with mathematics and Agnishom's mind.

I would use k = 24 and it is extremely unlikely that there will be a false prime in your list.
Anyways, there are ways to now make sure there are no errors.

Agnishom · 2013-04-09 05:52:45

What are they?

bobbym · 2013-04-09 05:55:10

There are 455052511 primes less than 10 000 000 000. Your list is checked to see if it has that many, then you know there are no errors!

Now we can get to your last line which is possibly another error.

Agnishom · 2013-04-09 07:47:55

Error? Its my loop!

bobbym · 2013-04-09 07:50:26

Excuse me, I meant 9.

Do you understand what I am saying about generating the primes?

Agnishom · 2013-04-09 07:52:45

9 says Write n to file, goto 5

bobbym · 2013-04-09 07:53:40

Okay, hold that for a second. Are you clear why you need only one test? Miller - Rabin will be enough?

Agnishom · 2013-04-09 07:59:14

Ya because at last we can check whether it has the required number of primes or not. And moreover, the number of primes can be less but NEVER more because if it says that a number is composite it definately is

bobbym · 2013-04-09 08:02:44

Okay, so we have sped it up already because you are no longer using trial division, which is slow.

Let's talk about the list itself. 455 million primes is a very, very big list. There is no list like that on the internet and for good reason. It is going to be a gigabyte or more.

Agnishom · 2013-04-09 08:04:37

Okay! A gigabite?

That's quite huge

Last edited by Agnishom (2013-04-09 08:05:04)

Math Is Fun Forum

#126 2013-04-09 04:09:14

Re: Mathematics jokes

#127 2013-04-09 04:21:10

Re: Mathematics jokes

#128 2013-04-09 04:28:08

Re: Mathematics jokes

#129 2013-04-09 04:30:49

Re: Mathematics jokes

#130 2013-04-09 04:32:43

Re: Mathematics jokes

#131 2013-04-09 04:39:15

Re: Mathematics jokes

#132 2013-04-09 04:43:18

Re: Mathematics jokes

#133 2013-04-09 04:54:16

Re: Mathematics jokes

#134 2013-04-09 05:02:05

Re: Mathematics jokes

#135 2013-04-09 05:10:42

Re: Mathematics jokes

#136 2013-04-09 05:17:48

Re: Mathematics jokes

#137 2013-04-09 05:22:51

Re: Mathematics jokes

#138 2013-04-09 05:27:55

Re: Mathematics jokes

#139 2013-04-09 05:29:06

Re: Mathematics jokes

#140 2013-04-09 05:36:11

Re: Mathematics jokes

#141 2013-04-09 05:42:57

Re: Mathematics jokes

#142 2013-04-09 05:52:45

Re: Mathematics jokes

#143 2013-04-09 05:55:10

Re: Mathematics jokes

#144 2013-04-09 07:47:55

Re: Mathematics jokes

#145 2013-04-09 07:50:26

Re: Mathematics jokes

#146 2013-04-09 07:52:45

Re: Mathematics jokes

#147 2013-04-09 07:53:40

Re: Mathematics jokes

#148 2013-04-09 07:59:14

Re: Mathematics jokes

#149 2013-04-09 08:02:44

Re: Mathematics jokes

#150 2013-04-09 08:04:37

Re: Mathematics jokes

Board footer