A question about primes of a particular form

[enzocreti]

The numbers pg(k) are so defined:


pg(k)=(2^k-1)*10^m+2^(k-1)-1.
where m is the number of decimal digits of 2^(k-1)-1.
So for example pg(2)=(3*10)+2-1=31
pg(3)=7*10+3=73.
pg(4)=157


In other words pg(k) is obteined by concatenating the decimal digits of 2^k - 1 and 2^(k-1) - 1.


With Pfgw i found that up to k=21.000, the k's such that (pg(k)+11)/42 is a prime are these:


3
6
12
36
105
156
336
2286
4272
4427
11979
20076


so for example (pg(3)+11)/42 is a prime. I wonder why there is only one case out of 12, thqat is pg(4427) in which k=4427 is NOT a multiple of 3. In all other cases k=3,6,12,36,105,156,336,2286,4272,11979,20076 k is a multiple of 3.

[enzocreti]

can a k of the form 3s+1 exist such that (pg(k)+11)/42 is prime? where s is some positive integer.

[enzocreti]

I found other k's leading to a prime (yet multiples of 3)


29343, 29988, 30405

[Batalov]

Originally Posted by enzocreti

can a k of the form 3s+1 exist such that (pg(k)+11)/42 is prime? where s is some positive integer.

How about k=100?
You are simply doing it wrong.

[axn]

Originally Posted by Batalov

How about k=100?
You are simply doing it wrong.

pg(100)+11 is not divisible by 42. So...

[enzocreti]

Originally Posted by Batalov

How about k=100?
You are simply doing it wrong.

for k=100, (pg(100)+11)/42 is NOT prime

[Batalov]

Originally Posted by enzocreti

With Pfgw i found that

When a person claims that that they found "with Pfgw", they imply integer division.

pfgw divides.

Examples:
pfgw -N -k -q"8/3"
8/3 is trivially prime!: 2

pfgw -N -k -q"(1267650600228229401496703205375633825300114114700748351602687+11)/42"
(1267650600228229401496703205375633825300114114700748351602687+11)/42 is 3-PRP!


cat > help
71419
1108537
782395429
131693398271

pfgw -N -k -hhelp -t -q"((2^100-1)*10^30+2^99-1+11)/42"
Primality testing ((2^100-1)*10^30+2^99-1+11)/42 [N-1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file help
Running N-1 test using base 2
((2^100-1)*10^30+2^99-1+11)/42 is prime! (0.0144s+0.0005s)

[Batalov]

If one uses "division only when it divides", then the answer is very trivial.
It has nothing to do with primality, only with divisibility of pg(k)+11 by 42.

Define: m = 2^k-1 - 1, d = ceil(log₁₀m), and then pg(k) = (2*m+1)*10^d+m.
Now, consider k and d separately.
When does 2 | pg(k)+11? Answer: for all k and d.
When does 3 | pg(k)+11? Answer: for all k and d.
When does 7 | pg(k)+11? Answer: if(d%6 == 1) { for all k } else {only for k = multiple of 3}.
Do the homework. See that the above three statements are true.

Now, d%6 == 1 is true only for ~1/6 of all k and 1/3 of these k's are a multiple of 3.
So, the k :: 3|k have a ~ 6:1 times better odds to produce a prime than the other k (considering the primality is an essentially random function wrt k, d)


For k = 4427, d = 1333 which is 1 (mod 6), indeed.

[Dr Sardonicus]

A slightly different approach: As Batalov showed, 6|(pg(k) + 11) always. For 7, we have:

If 3|k then Mod(2^k - 1, 7) = 0 and Mod(2^(k-1) - 1, 7) = 3, so Mod(pg(k),7) = 3 for any m.

If 3 does not divide k, the fact that 10 is a primitive root (mod 7) comes into play. In each case, there will only be one residue class of Mod(m, 6) that makes Mod(pg(k),7) = 3.

If k == 1 (mod 3) then Mod(2^(k-1) - 1, 7) = 0 and Mod(2^k - 1, 7) = 1, so Mod(pg(k), 7) = Mod(10^m, 7). This is 3 when Mod(m, 6) = 1.

If k == 2 (mod 3) then we have Mod(pg(k), 7) = Mod(3*10^m + 1, 7), which is again 3 when Mod(m,6) = 1.

Of the 18 possible pairs (Mod(k,3), Mod(m, 6)) then, the 6 pairs with Mod(k,3) = 0 , the pair (Mod(k,3) = 1, Mod(m,6) = 1), and the pair (Mod(k,3) = 2, Mod(m,6) = 1) allow Mod(pw(k), 7) = 3.

For the remaining ten pairs, Mod(pg(k), 7) is not 3.

So, pg(k) + 4 is divisible by 7 about 6 times as often for 3|k as for k == 1 (mod 3), and about 6 times as often as for k == 2 (mod 3). A numerical check up to k = 10000 confirms this:

? c0=0;c1=0;c2=0;a=log(2)/log(10);f=a;m=1;for(i=1,10000,e1=i%3;e2=m%6;if(e1==0,c0++);if(e1==1&&e2==1,c1++);if(e1==2&&e2==1,c2++);f+=a;if(f>1,f--;m++));print(c0" "c1" "c2)
3333 556 557

[Dr Sardonicus]

I fouled up. I want m to be the number of decimal digits of 2^(i-1) - 1, not 2^i - 1. I should have initialized i at 2, not 1. (Or left i initialized at 1, initialized f at 0, and had a value pg(1) = 10.)

? c0=0;c1=0;c2=0;a=log(2)/log(10);f=a;m=1;for(i=2,10000,e1=i%3;e2=m%6;if(e1==0,c0++);if(e1==1&&e2==1,c1++);if(e1==2&&e2==1,c2++);f+=a;if(f>1,f--;m++));print(c0" "c1" "c2)
3333 556 556

While I was at it, I ran the numbers out farther, to 100,000 an 300,000:

? c0=0;c1=0;c2=0;a=log(2)/log(10);f=a;m=1;for(i=2,100000,e1=i%3;e2=m%6;if(e1==0,c0++);if(e1==1&&e2==1,c1++);if(e1==2&&e2==1,c2++);f+=a;if(f>1,f--;m++));print(c0" "c1" "c2)
33333 5556 5556

? c0=0;c1=0;c2=0;a=log(2)/log(10);f=a;m=1;for(i=2,300000,e1=i%3;e2=m%6;if(e1==0,c0++);if(e1==1&&e2==1,c1++);if(e1==2&&e2==1,c2++);f+=a;if(f>1,f--;m++));print(c0" "c1" "c2)
100000 16666 16668

(EDIT: I'm sure e1 and e2 can be computed more expeditiously.)

[enzocreti]

pg(k) numbers are so defined:


pg(k)=(2^k-1)*10^d+2^(k-1)-1, where d is the number of decimal digits of 2^(k-1)-1. In other words they are numbers obtained by the concatenation of two consecutive Mersenne numbers. Examples are 12763 and 157.
Now I consider when pg(k) is prime and k is congruent to 7 mod 10.
The values I found are k=7,67,360787. It seems that if pg(k) is prime and k is congruent to 7 mod 10, then k is also congruent to 1 (mod 6). Is there any Mathematical reason? Could exist a pg(k) prime with k congruent to 7 mod 10 and k NOT congruent to 1 mod 6? And all the pg(k) which are primes with k congruent to 7 mod 10, are all of the form 900s+163?