mersenneforum.org Factoring 3^(k*2^n) +/- 1 numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2019-04-10, 09:22 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 25×32 Posts Factoring 3^(k*2^n) +/- 1 numbers Random musings of last night and this morning. As many on the forum are well aware, I discovered a PRP this time last year which, due to my inexperience and lack of awareness around the subject, is practically unprovable due to the difficulty in factoring N+/-1. It was 3504206+2. N+1 and N-1 both have a number of algebraic factors which are either too small to be useful or too large to be factorable. Moving onto new concepts, ideas and projects, the following has been rattling around in my brain for a while: Assume a search for primes in $3^{n}-2$, N+1 would therefore be $3^{n}-1$ As we know, $a^{2k}-1\equiv(a^k+1)(a^k-1)$ and so if n is even then $3^{n}-2\equiv(3^{n/2}+1)(3^{n/2}-1)$ giving two factors. This is fine, but largely useless if n is large as the factors are huge and still require factorising. However, if the exponent is a power of 2, this can be done repeatedly: $3^{2^n}-1\equiv(3^{2^0}-1)(3^{2^1}+1)(3^{2^2}+1)(3^{2^3}+1)[...](3^{2^{n-2}}+1)(3^{2^{n-1}}+1)$ Giving n (usually composite) factors, increasing in value exponentially. Obviously none of this is groundbreaking, I'm just filling in the background information to my musings. My question - the bit I think instinctively is 'no' but I can't work out for sure - is whether these algebraic factors of very specific $3^{k*2{n}}-1$ would make a search for $3^{k*2{n}}-2$ primes at all viable, or whether the factoring of the factors would be still an absurdly gargantuan task. All of the identified factors would be of very specific forms. Furthermore, leading on from that: is there any feasibility in a prime-searching project which looks for PRPs of the form $b^{k*2{n}}-2$ and then distributes factoring work of the PRP+1?
 2019-04-10, 11:02 #2 paulunderwood     Sep 2002 Database er0rr 1110010011002 Posts Code: ? k=1;for(n=1,32,print([n,ceil(2^n*log(3^(k))/log(10))])) [1, 1] [2, 2] [3, 4] [4, 8] [5, 16] [6, 31] [7, 62] [8, 123] [9, 245] [10, 489] [11, 978] [12, 1955] [13, 3909] [14, 7818] [15, 15635] [16, 31269] [17, 62538] [18, 125075] [19, 250149] [20, 500298] [21, 1000596] [22, 2001192] [23, 4002384] [24, 8004767] [25, 16009533] [26, 32019066] [27, 64038131] [28, 128076262] [29, 256152524] [30, 512305047] [31, 1024610093] [32, 2049220186] For each k these numbers' number of digits grow very quickly -- so you won't have many to test. Then there is the problem of finding actual PRPs for this double exponent -- a similar problem to the rarity of Fermat prime numbers. Code: ? forstep(k=1,14,2,for(n=1,13,if(ispseudoprime(3^(k*2^n)-2),print([n,k])))) [1, 1] [2, 1] [1, 3] [1, 11]
 2019-04-10, 11:08 #3 axn     Jun 2003 10011010110112 Posts You're looking at two coinciding rare events 1) b^N-2 is prp 2) b^N-1 is sufficiently (about 28%? at minimum) factored. You may find that no such (b,N) exists within currently testable ranges. EDIT:- There will be plenty of small (b,N), but probably none that is large enough (say, to enter T5K). Last fiddled with by axn on 2019-04-10 at 11:09
2019-04-10, 11:52   #4
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts

I might be going mad but I can't find the edit button on the first post. Maybe you can't edit the lead post in a thread? Anyway, there's a mistake. Maybe a mod could edit it and delete this post?

Quote:
 Originally Posted by lukerichards $3^{2^n}-1\equiv(3^{2^0}-1)(3^{2^1}+1)(3^{2^2}+1)(3^{2^3}+1)[...](3^{2^{n-2}}+1)(3^{2^{n-1}}+1)$

Quote:
 Originally Posted by lukerichards $3^{2^n}-1\equiv(3^{2^0}-1)(3^{2^0}+1)(3^{2^1}+1)(3^{2^2}+1)(3^{2^3}+1)[...](3^{2^{n-2}}+1)(3^{2^{n-1}}+1)$

2019-04-10, 11:56   #5
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts

Quote:
 Originally Posted by paulunderwood For each k these numbers' number of digits grow very quickly -- so you won't have many to test.
Understood - but that at least makes the problem relatively finite (limited by computing power and time), which at least gives bounds for reasonable investigation.

Also worth noting that there are lots of Ks that could be used. I think any prime k should give a unique exponent. Some kind of ratio between k and n would rule out candidates where n is not large enough to give sufficient algebraic factors.

 2019-04-10, 13:23 #6 axn     Jun 2003 115338 Posts 014224 has the known list of 3^n-2 primes. 051783 has the known list of 3^n+2 primes. These are rather small sets. You can see how many such numbers have the qualities that you look for. PS:- Why is the OEIS tag trying to add an "A" ?
2019-04-10, 14:00   #7
DukeBG

Mar 2018

3·43 Posts

Quote:
 Originally Posted by axn 014224 has the known list of 3^n-2 primes. 051783 has the known list of 3^n+2 primes. These are rather small sets. You can see how many such numbers have the qualities that you look for.
If you look closely at the second page, you'll probably recognize the name Luke W. Richards..

2019-04-10, 14:37   #8
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts

Quote:
 Originally Posted by DukeBG If you look closely at the second page, you'll probably recognize the name Luke W. Richards..
Indeed, I've tested (or sieved) all n up to 1,300,000 for 3n+2 while someone else has tested n up to 1,000,000 for 3n-2.

I also have a database of about 1,000,000 primes, p, and the first n for which they divide 3n-2, coupled with their multiplicative orders of p modulo 3, which saves time on a lot of PRP tests.

 Similar Threads Thread Thread Starter Forum Replies Last Post arbooker Factoring 209 2019-10-14 14:43 paulunderwood Miscellaneous Math 18 2017-08-27 14:56 ShridharRasal Factoring 10 2008-03-20 17:17 jasong Factoring 27 2006-03-21 02:47 Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 07:58.

Thu May 6 07:58:50 UTC 2021 up 28 days, 2:39, 0 users, load averages: 1.55, 1.72, 1.78