mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > enzocreti

Reply
 
Thread Tools
Old 2018-11-15, 08:15   #1
enzocreti
 
Mar 2018

1EA16 Posts
Default A question about primes of a particular form

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 is offline   Reply With Quote
Old 2018-11-15, 10:37   #2
enzocreti
 
Mar 2018

2×5×72 Posts
Default ...continues...

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

Last fiddled with by enzocreti on 2018-11-15 at 10:58
enzocreti is offline   Reply With Quote
Old 2018-11-16, 08:04   #3
enzocreti
 
Mar 2018

2×5×72 Posts
Default other k's found

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


29343, 29988, 30405
enzocreti is offline   Reply With Quote
Old 2018-11-16, 08:52   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

231816 Posts
Default

Quote:
Originally Posted by enzocreti View Post
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.
Batalov is offline   Reply With Quote
Old 2018-11-16, 09:24   #5
axn
 
axn's Avatar
 
Jun 2003

22×11×103 Posts
Default

Quote:
Originally Posted by Batalov View Post
How about k=100?
You are simply doing it wrong.
pg(100)+11 is not divisible by 42. So...
axn is offline   Reply With Quote
Old 2018-11-16, 10:51   #6
enzocreti
 
Mar 2018

2·5·72 Posts
Default k=100

Quote:
Originally Posted by Batalov View Post
How about k=100?
You are simply doing it wrong.
for k=100, (pg(100)+11)/42 is NOT prime
enzocreti is offline   Reply With Quote
Old 2018-11-16, 15:32   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

23·1,123 Posts
Default

Quote:
Originally Posted by enzocreti View Post
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 is offline   Reply With Quote
Old 2018-11-16, 20:54   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

231816 Posts
Cool

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 = 2k-1 - 1, d = ceil(log10m), 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)
\qed

For k = 4427, d = 1333 which is 1 (mod 6), indeed.
Batalov is offline   Reply With Quote
Old 2018-11-17, 01:00   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,011 Posts
Default

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 is offline   Reply With Quote
Old 2018-11-17, 13:21   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,011 Posts
Default

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.)

Last fiddled with by Dr Sardonicus on 2018-11-17 at 13:29
Dr Sardonicus is offline   Reply With Quote
Old 2018-11-19, 09:25   #11
enzocreti
 
Mar 2018

2·5·72 Posts
Default A question about pg primes whose exponent is congruent to 7 mod 10

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?
enzocreti is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primes of the form (b+-1)*b^n+-1 and b^n+-(b+-1) sweety439 sweety439 159 2020-02-12 07:55
Search primes of form 2*n^n ± 1 JeppeSN And now for something completely different 27 2018-04-12 14:20
Primes of the form n+-phi(n) carpetpool carpetpool 3 2017-01-26 01:29
Primes of the form a^(2^n)+b^(2^n) YuL Math 21 2012-10-23 11:06
Primes of the form 2.3^n+1 Dougy Math 8 2009-09-03 02:44

All times are UTC. The time now is 18:34.

Sat Mar 28 18:34:37 UTC 2020 up 3 days, 16:07, 2 users, load averages: 1.12, 1.46, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.