mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-03-30, 10:34   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

56278 Posts
Default Suggestion for new sieving software

Sascha77 came up with this problem/puzzle:

http://www.mersenneforum.org/showpos...7&postcount=74

Which corresponds to: Does any factor of a mersenne number 2np+1 have n=k*p.

I checked all of GIMPS 33.5 million known factors and found 1 solution only:

http://www.mersenneforum.org/showpos...0&postcount=81

http://www.mersenneforum.org/showpos...6&postcount=83

so this like a new kind of Wieferich prime, just as rare.

So I wrote some programs and have been looking for other examples, but my programming skill is limited to C with GNU MP, so they are not super fast.

It would be very nice with an efficient siever like newpgen/srsieve for numbers of the form 2*k*p2+1, p prime (or k*p2+1 whichever is easier) over k and p intervals.

Maybe if people like Prime95/geoff/rogue/Jean Penné who has the skills finds this interesting and have the time :)

Last fiddled with by ATH on 2012-03-30 at 10:40
ATH is offline   Reply With Quote
Old 2012-03-30, 11:19   #2
wreck
 
wreck's Avatar
 
"Bo Chen"
Oct 2005
Wuhan,China

7·23 Posts
Default

I think there should be infinite solutions to this problem, though it is rare.
For any given p, Consider the minimum number of A (A>1) that satisfy
A^p = 1 (mod p^2)
maybe help.
wreck is offline   Reply With Quote
Old 2012-03-30, 14:58   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·3·739 Posts
Default

There are certainly an infinite amount of solutions for composite p, and composite factors 2*k*p^2+1, as for example p=28, 56, 100, 126, 140, 240, 256, 280, 312, 336, 364, 512, 624, 748 etc.

The factors are prime for the trivial p=32, 64, 128, but also for other which are not powers of 2, like for example p=678: we have 2^678-1 is divisible by the prime 10113049, which is 2*11*678^2+1.

Contrary, there are not many solutions for odd composite p either. The only one I found 339: 2^339-1 is divisible by the same prime, 10113049, which this time is 2*(11*4)*339^2+1, so k=44, considering that 678=2*339 (=2*3*113). But 2^113-1 does not have any factor f whose f-1 contain some square of 113.
LaurV is offline   Reply With Quote
Old 2012-04-04, 13:03   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by ATH View Post
Sascha77 came up with this problem/puzzle:

http://www.mersenneforum.org/showpos...7&postcount=74

Which corresponds to: Does any factor of a mersenne number 2np+1 have n=k*p.

I checked all of GIMPS 33.5 million known factors and found 1 solution only:

http://www.mersenneforum.org/showpos...0&postcount=81

http://www.mersenneforum.org/showpos...6&postcount=83

so this like a new kind of Wieferich prime, just as rare.

So I wrote some programs and have been looking for other examples, but my programming skill is limited to C with GNU MP, so they are not super fast.

It would be very nice with an efficient siever like newpgen/srsieve for numbers of the form 2*k*p2+1, p prime (or k*p2+1 whichever is easier) over k and p intervals.

Maybe if people like Prime95/geoff/rogue/Jean Penné who has the skills finds this interesting and have the time :)
here's an inefficient code to find them:

Code:
for(x=1,10000,for(k=1,x,if((2^x-1)%(2*k*x^2-1)==0,print(k","x))))
thought part of the slowness is because I don't break once I find one.

Last fiddled with by science_man_88 on 2012-04-04 at 13:08
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generalized Cullen/Woodall Sieving Software rogue And now for something completely different 13 2014-12-29 19:11
new sieving software Thomas11 Riesel Prime Search 81 2011-11-05 19:16
Suggestion henryzz Marin's Mersenne-aries 1 2009-04-14 10:33
Software suggestion: JuanTutors Software 25 2009-03-08 04:36
Sieving Software lavalamp Software 10 2007-10-20 23:07

All times are UTC. The time now is 22:39.

Sat Oct 24 22:39:58 UTC 2020 up 44 days, 19:50, 2 users, load averages: 1.72, 1.73, 1.90

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.