Primes from powers of 2 strings.

[Batalov]

n=270, a prp11150 - attached.

[Batalov]

a prp15046 (n=314)

[axn]

Originally Posted by retina

swapsies, even <---> odd.

Indeed. I was, of course, referring to the number of terms. Yeah, that's the ticket.

[science_man_88]

well one thing the amount of primes depends on is how many permutations that end in 1 there are. since 1=2^0 we can use n! to figure out how many permutations there are of the remaining elements. as for if they are prime I haven't got that far.

[CRGreathouse]

Originally Posted by science_man_88

well one thing the amount of primes depends on is how many permutations that end in 1 there are. since 1=2^0 we can use n! to figure out how many permutations there are of the remaining elements. as for if they are prime I haven't got that far.

I discuss this in post #16. There are (n-1)! permutations that result in a number coprime to 10, making the 'chance' that an individual number is prime about 2.5 times more likely than a standard number that size, which is ~ 1/log(2^(n^2)). Thus the expected number of primes is something like 2.5 * n! / log 2 / n^3.

[science_man_88]

Originally Posted by CRGreathouse

I discuss this in post #16. There are (n-1)! permutations that result in a number coprime to 10, making the 'chance' that an individual number is prime about 2.5 times more likely than a standard number that size, which is ~ 1/log(2^(n^2)). Thus the expected number of primes is something like 2.5 * n! / log 2 / n^3.

couldn't we use PARI for small ones ? the hard part in my eyes is making sure we do every permutation without recording them as we go.

[retina]

Originally Posted by CRGreathouse

The numbers are something like n²/2 + O(n) bits long and there are (n-1)! ways to order them with the 1 in the rightmost position. The 'chance' that one would be prime is about 2.5 log 2 / n², so the expected number of primes is very large -- superexponential.

I don't understand why it is (n-1)!. Is it not n!. We exclude 2^0 then that leaves n sets of numbers to permute, 2^1 to 2^n.

[science_man_88]

(13:29)>p2=vector(100,n,sumdigits(2^n))
%21 = [2, 4, 8, 7, 5, 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7, 5, 1, 2, 4,
(15:12)>x6=vector(100,x,sumdigits(6*x+1))
%22 = [7, 4, 1, 7, 4, 1, 7, 4, 1, 7, 4, 1, 7, 4, 1, 7, 4, 1, 7, 4, 1, 7, 4, 1, 7, 4, 1, 7, 4, 1, 7, 4,
(15:12)>x6=vector(100,x,sumdigits(6*x-1))
%23 = [5, 2, 8, 5, 2, 8, 5, 2, 8, 5, 2, 8, 5, 2, 8, 5, 2, 8, 5, 2, 8, 5, 2, 8, 5, 2, 8, 5, 2, 8, 5, 2,

adding 1 as the first in p2 we can show that only indexes 2x+1 starting at the 1 added in can have possible primes.

1 fits into the 1,2,4,5,7,8
1+2=3 doesn't fit in
1+2+4 = 7 fits
1+2+4+8 = 15(1+5) = 6 doesn't
1+2+4+8+7 = 22(2+2) = 4 fits
1+2+4+8+7+5 = 27 = 0 doesn't

the pattern repeats.

[CRGreathouse]

Originally Posted by retina

I don't understand why it is (n-1)!. Is it not n!. We exclude 2^0 then that leaves n sets of numbers to permute, 2^1 to 2^n.

It's all in how you count it: is #88 2^0 through 2^88 or 2^0 through 2^87? The conversion to the other convention is obvious.

[CRGreathouse]

Originally Posted by science_man_88

couldn't we use PARI for small ones ? the hard part in my eyes is making sure we do every permutation without recording them as we go.

I used it to get this thing started, with

try(n)=my(t);n--;for(k=1,n!,if(ispseudoprime(t=glue(round(2^numtoperm(n,k)))*10+1),return(t)))

I didn't try to find any large values with this, though -- PARI's not well-suited to probable-prime testing numbers beyond 1000-2000 digits.

[Batalov]

I used perl to manipulate strings (pregenerated with BigInt), sans '1'. With an array of strings, just swap two random strings at a time, concat (with '1' at end) and pipe into pfgw. Just my 2c.