Sums of all Squares

[lavalamp]

Ah, I snagged the stable binary for windows, I guess there's only a 32 bit version for that.

I would quite like a forbigprime loop. Are you saying then that while 64bit pari can generate more primes, you can't use them in a regular forprime loop?

Incidentally, do you know why the limit is 4,294,965,247 and not 4,294,967,295? Those last 93 primes before 2^32-1 could be vitally important!

[CRGreathouse]

Originally Posted by lavalamp

Ah, I snagged the stable binary for windows, I guess there's only a 32 bit version for that.

Right. The mingw project that the Windows version of Pari/GP is built on is strictly 32-bit. There is a mingw64 fork, but the last time I used it there were serious problems with it. I've heard that it's better now, but I haven't tried recently.

Originally Posted by lavalamp

Are you saying then that while 64bit pari can generate more primes, you can't use them in a regular forprime loop?

No, forprime can go as high as primelimit, and 64-bit Pari can handle more primes than you could fit in memory. I did the calculations up to 10^10 using forprime normally.

But it would often be convenient to loop over more primes than you can fit in memory. For example, there's no way I could fit the primes to 10^12 in memory, but I'd like to check the conjecture up to that point.

Originally Posted by lavalamp

Incidentally, do you know why the limit is 4,294,965,247 and not 4,294,967,295? Those last 93 primes before 2^32-1 could be vitally important!

The implementation leaves free space of about 2000, as I recall, so there is room for status and whatnot in the word.

[CRGreathouse]

Originally Posted by lavalamp

I would quite like a forbigprime loop.

Likewise -- I wanted one enough that I sat down and wrote one. But there are still fencepost errors, and also a few things I'd like to optimize before I send it out.

The version I have right now is reasonably efficient for long intervals (forprime(p=a,b, ...) with b - a >> sqrt(b) or so) but inefficient for small intervals. It would be very easy to write a function to handle short intervals (sieve out tiny primes then test with ispseudoprime), so I might break the code into four parts:

forprime
forbigprime
forsmallprime
forthinprime

where the existing forprime would move to forsmallprime, the new code would go into forbigprime (and maybe also new code in forbigprime_word*), forthinprime would be the near-trivial code for handling short intervals, and forprime would handle errors and decide which function to use.

I don't think these would be exposed to GP; it would probably be best to let users remain ignorant of the different workings. There are some sticking points, though.

First, it's usually good to warn the user if they try to exceed primelimit. If you want to loop over the primes up to 100 million, just calculate those primes, don't use forbigprime (which, by its nature, will be slower) and then throw them away!

Second, forprime currently allows code like

forprime(p=2,100,print1(p" ");if(p==3,p=80))

which changes the index midstream. My current version of bigprime doesn't handle this, and it would be very inefficient if it did.

One possibility would be to use a different function ("forbigprime") in GP, so users only use the appropriate function. This takes care of the above issues, but exposes more complexity to the user than is desirable.

Another would be to allow the index to change with forbigprime, but if it does just kick them into forthinprime.

Another would be to disallow changing the index entirely.

* which would handle cases where the upper limit is larger than primelimit but not larger than a word -- 2^32-1 or 2^64-1 on 32- and 64-bit, respectively.

[lavalamp]

This program is for use (ideally) by people who already know what they're doing, I don't see why these specific loops would need to be hidden. On a personal note, I would prefer knowing what code is going to do when I run it, rather than be unsure because I don't happen to know the current primelimit.

It would be possible to get the best of both worlds though, have a generic loop that can call whichever loop seems most appropriate, and the numerous specific loops for people who already know what they want, it only takes a few lines in the documentation.

If there's no way (or it is at least very hard) to make the forbigprime loop efficient AND able to jump around with the index, then it seems reasonable to deny the ability to change it, for that loop only.

[science_man_88]

Originally Posted by CRGreathouse

Likewise -- I wanted one enough that I sat down and wrote one. But there are still fencepost errors, and also a few things I'd like to optimize before I send it out.

The version I have right now is reasonably efficient for long intervals (forprime(p=a,b, ...) with b - a >> sqrt(b) or so) but inefficient for small intervals. It would be very easy to write a function to handle short intervals (sieve out tiny primes then test with ispseudoprime), so I might break the code into four parts:

forprime
forbigprime
forsmallprime
forthinprime

where the existing forprime would move to forsmallprime, the new code would go into forbigprime (and maybe also new code in forbigprime_word*), forthinprime would be the near-trivial code for handling short intervals, and forprime would handle errors and decide which function to use.

I don't think these would be exposed to GP; it would probably be best to let users remain ignorant of the different workings. There are some sticking points, though.

First, it's usually good to warn the user if they try to exceed primelimit. If you want to loop over the primes up to 100 million, just calculate those primes, don't use forbigprime (which, by its nature, will be slower) and then throw them away!

Second, forprime currently allows code like

forprime(p=2,100,print1(p" ");if(p==3,p=80))

which changes the index midstream. My current version of bigprime doesn't handle this, and it would be very inefficient if it did.

One possibility would be to use a different function ("forbigprime") in GP, so users only use the appropriate function. This takes care of the above issues, but exposes more complexity to the user than is desirable.

Another would be to allow the index to change with forbigprime, but if it does just kick them into forthinprime.

Another would be to disallow changing the index entirely.

* which would handle cases where the upper limit is larger than primelimit but not larger than a word -- 2^32-1 or 2^64-1 on 32- and 64-bit, respectively.

if theres a easy formula for calculating the distance between primes that doesn't use a random n in 6n I could see a way to extend it the way it is, but using a shift in vectors.

[lavalamp]

Well, not exactly, but sort of:
http://primes.utm.edu/notes/gaps.html

Trivia: this is where god lives.

[science_man_88]

Originally Posted by lavalamp

Well, not exactly, but sort of:
http://primes.utm.edu/notes/gaps.html

Trivia: this is where god lives.

well I've drowned lol.

[science_man_88]

given primes p and q<p we can show that the composites ruled out are q%((p^2-q^2)%q) mod q above p^2. but i can't take this any further.

[lavalamp]

Perhaps this then:
http://www.ieeta.pt/~tos/gaps.html

While you're at it could you explain what this means:

Originally Posted by science_man_88

if theres a easy formula for calculating the distance between primes that doesn't use a random n in 6n I could see a way to extend it the way it is, but using a shift in vectors.

[science_man_88]

Originally Posted by lavalamp

Perhaps this then:
http://www.ieeta.pt/~tos/gaps.html

While you're at it could you explain what this means:

I think I was thinking to find 6n+1 primes from a 6n+1 prime guessing random numbers that are multiples of 6.

[science_man_88]

Originally Posted by science_man_88

given primes p and q<p we can show that the composites ruled out are q%((p^2-q^2)%q) mod q above p^2. but i can't take this any further.

I forgot to mention p^2-q^2 can be made into 2* (the sum of the numbers (q-p)) -(p+q)