PARI's commands

[science_man_88]

Originally Posted by CRGreathouse

Depends on what size primes you store and how you store them, naturally.

well if we encode it as characters for each digit it gets inefficient real quick (almost like BCD in ASM I think), I don't know the best way to encode them efficiently unless maybe we convert them to hex to take less room than the decimal and hex or another power of 2 base is easier for me to convert to binary(yes I've learned that part lol).

[CRGreathouse]

Originally Posted by science_man_88

well if we encode it as characters for each digit it gets inefficient real quick (almost like BCD in ASM I think), I don't know the best way to encode them efficiently unless maybe we convert them to hex to take less room than the decimal and hex or another power of 2 base is easier for me to convert to binary(yes I've learned that part lol).

So store them natively in binary, taking k bits to store (naturally!) a k-bit prime. You can even do better: store all but the last bit, unless the prime is 2, in which case store it as 0.

You'll need some way to delimit the primes, though.

[science_man_88]

Originally Posted by CRGreathouse

So store them natively in binary, taking k bits to store (naturally!) a k-bit prime. You can even do better: store all but the last bit, unless the prime is 2, in which case store it as 0.

You'll need some way to delimit the primes, though.

let me guess the last bit won't matter as it will always be one except when the decimal representation of the prime is 2. yeah what to separate them in storage with.

[CRGreathouse]

Originally Posted by science_man_88

let me guess the last bit won't matter as it will always be one except when the decimal representation of the prime is 2. yeah what to separate them in storage with.

One way would be to used fixed width. Store only 65-bit primes, so every 64 bits is a new prime. There are 412246861431389469 65-bit primes, so you shouldn't run out... unless you have more than 206123 TB.

You could even left-pad with 0s and include primes of up to 65 bits. This gives you 837903145466607212 to work with (and moves the storage for all of them to 418951 TB).

[science_man_88]

a=0;forallprime(1,2^100,p->a=a+1;if(ispower(p+1),print(ispower(p+1)","p","a)))

this can't be efficient

[CRGreathouse]

There are many more primes than (proper) powers, and as it happens ispower is a lot slower than isprime. So if you're able, set up the loop the other way: loop over powers and check the the primality of n-1.

This way you're checking something like 1.126 * 10¹⁵ numbers instead of 1.267 * 10³⁰.

Edit: 1125910730446094 instead of 1.856(1) * 10²⁸, assuming (wrongly) that you've precalculated primes up to 2¹⁰⁰.

[axn]

Originally Posted by CRGreathouse

There are many more primes than (proper) powers, and as it happens ispower is a lot slower than isprime. So if you're able, set up the loop the other way: loop over powers and check the the primality of n-1.

Two words. Algebraic factors. Zero clock cycles.

[CRGreathouse]

Originally Posted by axn

Two words. Algebraic factors. Zero clock cycles.

I was actually more interested in the general issue of looping over primes and powers than the specific one of finding primes one less than a power.

[science_man_88]

Originally Posted by axn

Two words. Algebraic factors. Zero clock cycles.

I can't even remember the think other than 2kp+1 that anyone told me lol.

[CRGreathouse]

The suggestion was that b - 1 is a factor of b^k - 1, so unless b = 2 this cannot be a prime. If b = 2 then you're just looking for Mersenne primes.

[science_man_88]

best I can do of summing up the LL test is:

s=2*y*(2*k*p+1) s=4*y*k*p+(2*y)

but this is useless obviously