"I am experimenting with heuristic sieves."
 

2[B][SUP]1277[/SUP][/B] - 1 = 1 + 2⋅3⋅5⋅23⋅59⋅89⋅233⋅397⋅683⋅1103⋅[B]1277[/B]⋅2089⋅2113⋅18503⋅64439⋅181193⋅3033169⋅107367629⋅...
[URL="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem"]https://en.wikipedia.org/wiki/Fermat%27s_little_theorem[/URL]

[QUOTE=Dobri;586724]2[B][SUP]1277[/SUP][/B] - 1 = 1 + 2⋅3⋅5⋅23⋅59⋅89⋅233⋅397⋅683⋅1103⋅[B]1277[/B]⋅2089⋅2113⋅18503⋅64439⋅181193⋅3033169⋅107367629⋅...
[URL="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem"]https://en.wikipedia.org/wiki/Fermat%27s_little_theorem[/URL][/QUOTE]
Trolling much?

What does it have to do with anything?

[QUOTE=Batalov;586734]What does it have to do with anything?[/QUOTE]
I am experimenting with heuristic sieves. One of the heuristics attempts to use the known small factors of 2[SUP]p-1[/SUP]-1.
Interestingly, in the case of [I]p[/I] = 1277, there is a plenty of factors of 2[SUP]p-1[/SUP]-1.

[QUOTE=Dobri;586738]...Interestingly, in the case of [I]p[/I] = 1277, there is a plenty of factors of 2[SUP]p-1[/SUP]-1.[/QUOTE]
O RLY?
Ever heard of
x[SUP]2[/SUP]-1 = ... ? (write it out, don't be shy)
x[SUP]11[/SUP]-1 = ... ? (write it out)

There is so much "interesting" in the world to anyone who skipped all classes in the 7th grade.

[QUOTE=Batalov;586740]There is so much "interesting" in the world to anyone who skipped all classes in the 7th grade.[/QUOTE]
Obviously, it stems from the observation that 1276 = 4⋅11⋅29. You assume the worst in others.
One should not forget to be polite and respectful to the ones who attempt to communicate instead of posting uncivilized forcible content of provocative and insulting nature as only bullies do from the assumed position of power.
At least, I remember from kindergarten the basics of being kind to people.

[QUOTE=Dobri;586744]You assume the worst in others.[/QUOTE]
You, actually, appear to be assuming the worst in others.

I almost always apply [URL="https://en.wikipedia.org/wiki/Hanlon%27s_razor"]Hanlon's_razor[/URL]. My remark had nothing to do with you but with your argument.

Do you disagree with an illustrative argument that if a person cut all classes in school in the past, they will later in life find a lot of things interesting and even stunning? "A kilogram of led weighs the same as a kilogram of feathers! Who could have thought?!" You are arguing not with the presented argument, but with the "assumed" fact that it was "about you". It was not.

Whether you immediately project yourself in every sentence is entirely a matter of your choice. Your assumptions.

[QUOTE=Batalov;586745]My remark had nothing to do with you but with your argument.
[/QUOTE]
Same here. Only the first line of my previous response was concerned with your comment concerning the homogeneous version of the geometric sum formula.
The rest of said response was an illustrative argument.
As for razors, I do not use such tools. Sometimes, one could inadvertently 'cut' oneself while attempting to apply razors to others.

I can only add another illustrative vignette -

[I]Interestingly[/I] (c), [URL="http://factordb.com/index.php?query=2%5E1278-1"]2[SUP]1278[/SUP]-1 is fully factored[/URL]. But [I]how [/I]can that be [URL="http://factordb.com/index.php?query=2%5E1278-1-1"]without the help of factoring 2[SUP]1278[/SUP]-1-1[/URL], which is not factored at all beyond the trivial factor of 2? It is one of the two: 1. Wizardry! or 2. Factoring N-1 actually helps nothing to factor N; it is a red herring.

[QUOTE=Batalov;586753][I]Interestingly[/I] (c), [URL="http://factordb.com/index.php?query=2%5E1278-1"]2[SUP]1278[/SUP]-1 is fully factored[/URL]. But [I]how [/I]can that be [URL="http://factordb.com/index.php?query=2%5E1278-1-1"]without the help of factoring 2[SUP]1278[/SUP]-1-1[/URL], which is not factored at all beyond the trivial factor of 2? It is one of the two: 1. Wizardry! or 2. Factoring N-1 actually helps nothing to factor N; it is a red herring.[/QUOTE]
Or 3. The factors could be used indirectly in the design and testing of the heuristic sieve.
Every heuristic initially has an element of wizardry though.

[QUOTE=Dobri;586738]I am experimenting with heuristic sieves. One of the heuristics attempts to use the known small factors of 2[SUP]p-1[/SUP]-1.
<snip>[/QUOTE]A heuristic is an informed guess. Those offered seriously include the information on which they are based, what simplifying assumptions are being made, and a "plausibility argument" explaining how those principles and assumptions are being applied.

I see no indication that your "heuristic sieve" is informed by anything, or that it is anything other than phantasmagorical. You have provided no motivation for using factors of M[sub]p[/sub] - 1 in a sieve for trying to factor M[sub]p[/sub], and have given absolutely no indication of what set, if any, you might want to use them to sieve.

You are certainly not informed on the subject by what is available on this Forum.

The question of whether factoring M[sub]p[/sub] - 1 would help in factoring M[sub]p[/sub] was discussed on this very forum about a year ago, [url=https://www.mersenneforum.org/showthread.php?t=25836]here[/url]. It specifically mentions the exponent 1277. And, as of this posting, the thread title is still visible on the Mersenne Forum home page.

The short answer to the question is "No."

I conclude that you have either not bothered to avail yourself of the most basic facts concerning factors of M[sub]p[/sub] - or are deliberately disregarding them, in which case you are a troll.

[QUOTE=Batalov;586740]
x[SUP]2[/SUP]-1 = ... ? (write it out, don't be shy)
x[SUP]11[/SUP]-1 = ... ? (write it out)
[/QUOTE]
x[SUP]2[/SUP]-1 = (x - 1)(x +1)
x[SUP]3[/SUP]-1 = (x - 1)(x[SUP]2[/SUP] + x + 1)
x[SUP]3[/SUP]+1 = (x + 1)(x[SUP]2[/SUP] - x + 1)

x[SUP]6[/SUP]-1 = (x[SUP]3[/SUP]-1)(x[SUP]3[/SUP]+1)

x[SUP]11[/SUP]-1 = didn't get any Google Search results, but since there are answers for x[SUP]5[/SUP]-1 and x[SUP]5[/SUP]+1, the same patterns should be observable.

x[SUP]5[/SUP]-1 = (x - 1)(x[SUP]4[/SUP] + x[SUP]3[/SUP] + x[SUP]2[/SUP] + x + 1)
x[SUP]5[/SUP]+1 = (x + 1)(x[SUP]4[/SUP] - x[SUP]3[/SUP] + x[SUP]2[/SUP] - x + 1)

x[SUP]2p[/SUP]+1 = Maybe a prime
x[SUP]2p[/SUP]-1 = Always composite
x[SUP]2p±1[/SUP]+1 = Always composite
x[SUP]2p±1[/SUP]-1 = Always composite

[QUOTE=Dr Sardonicus;586759]The question of whether factoring M[sub]p[/sub] - 1 would help in factoring M[sub]p[/sub] was discussed on this very forum about a year ago, [url=https://www.mersenneforum.org/showthread.php?t=25836]here[/url]. It specifically mentions the exponent 1277. And, as of this posting, the thread title is still visible on the Mersenne Forum home page.
The short answer to the question is "No."[/QUOTE]
Thank you for providing a link to a previous thread, of which I was unaware about, discussing this matter.
I did not intend to create a separate thread or provide extensive details on a work in progress but rather to post a few hints and see if there are similar attempts for factorization of composite Mersenne numbers.
One heuristic scheme I am currently testing and modifying is to use the factors of 2[SUP]p-1[/SUP]-1 (which are obviously coprime with Mp) as a factor base in a version of the rational sieve and proceed in a series of iterations in potentially finding factors of Mp. As pointed out in a previous post, the factors of 2[SUP]p+1[/SUP]-1 are also known. This gives me an idea to attempt a hybrid rational sieve using a combined factor base.

[QUOTE=tuckerkao;586767]x[SUP]11[/SUP]-1 = didn't get any Google Search results, but since there are answers for x[SUP]5[/SUP]-1 and x[SUP]5[/SUP]+1, the same patterns should be observable.[/QUOTE]
[I]x[/I][SUP]11[/SUP] - 1 = ([I]x[/I] - 1)([I]x[/I][SUP]10[/SUP] + [I]x[/I][SUP]9[/SUP] + [I]x[/I][SUP]8[/SUP] + [I]x[/I][SUP]7[/SUP] + [I]x[/I][SUP]6[/SUP] + [I]x[/I][SUP]5[/SUP] + [I]x[/I][SUP]4[/SUP] + [I]x[/I][SUP]3[/SUP] + [I]x[/I][SUP]2[/SUP] + [I]x[/I] + 1)
[url]https://mathworld.wolfram.com/GeometricSeries.html[/url]
[url]https://www.wolframalpha.com/input/?i=x%5E11-1[/url]

2[SUP]2^n[/SUP] + 1 have the higher chance to be a prime.

I always wondering why nobody is testing 3[SUP]n[/SUP] - 2 or 3[SUP]n[/SUP] + 2.

[QUOTE=tuckerkao;586767]
...
x[SUP]2p±1[/SUP]-1 = Always composite[/QUOTE]

Nope. 2[SUP]2*2-1[/SUP] - 1 is 2[SUP]3[/SUP]-1, prime. 2[SUP]2*3-1[/SUP] - 1 is 2[SUP]5[/SUP]-1, prime. 2[SUP]2*3+1[/SUP] - 1 is 2[SUP]7[/SUP]-1, prime. 2[SUP]2*7-1[/SUP] - 1 is 2[SUP]13[/SUP]-1, prime.

[QUOTE=Viliam Furik;586774]Nope. 2[SUP]2*2-1[/SUP] - 1 is 2[SUP]3[/SUP]-1, prime. 2[SUP]2*3-1[/SUP] - 1 is 2[SUP]5[/SUP]-1, prime. 2[SUP]2*3+1[/SUP] - 1 is 2[SUP]7[/SUP]-1, prime. 2[SUP]2*7-1[/SUP] - 1 is 2[SUP]13[/SUP]-1, prime.[/QUOTE]
I think I've made the error by not knowing how to put the powers in 2 layers. For some reason SUP & /SUP doesn't work inside another SUP & /SUP bracket.

x[Sup]2^(p+1)[/Sup]-1 = Maybe a Prime
x[Sup]2^(p-1)[/Sup]-1 = Always composite, p > 3
x[Sup]2^p+1[/Sup]-1 = Always composite, p ≥ 3
x[Sup]2^p-1[/Sup]-1 = Maybe a Prime

[QUOTE=tuckerkao;586775]For some reason SUP & /SUP doesn't work inside another SUP & /SUP bracket.[/QUOTE]Nesting BB code used to work in the past, some older posts do that. But an "upgrade" sometime ago broke it. :down:

[QUOTE=tuckerkao;586767]<snip>
x[SUP]2p[/SUP]+1 = Maybe a prime
<snip>[/QUOTE]
Did you mean x[sup]2^p[/sup] + 1?

[QUOTE=Dobri;586768]Thank you for providing a link to a previous thread, of which I was unaware about, discussing this matter.
<snip>[/quote]So, you didn't even bother reading the thread titles listed on the Mersenne Forum home page.
[quote]One heuristic scheme I am currently testing and modifying is to use the factors of 2[SUP]p-1[/SUP]-1 (which are obviously coprime with Mp) as a factor base in a version of the rational sieve[/QUOTE]Good luck with that.

FWIW, for odd positive integers [B]a, b & n = a*b[/B], there are relationships between the factors of [B]n-1[/B] and factors of [B]n[/B] which can be used to make the solution-space for factors of [B]n[/B] smaller. However this reduction [B]may or may not be marginal[/B]. Unfortunately for large composites it often (but not always) is.
For example:
[B]GCD(a-1,n-1) == GCD(b-1,n-1)[/B]
always holds [B]true[/B].

Example:
[B]65341= 361*181 => gcd(65341-1, 361-1) == gcd(65341-1, 181-1) == 180 => 65341 == (2*180+1) * (1*180+1)
[/B]


Pari-GP code:
[CODE]

\\EDE-100-A Relevance of factors of n-1 to factors of n by Rashid Naimi 2021/8/29
\\ The following Pari-GP code shows that for odd positive integers a, b & n= a*b, GCD(a-1,n-1) == GCD(b-1,n-1)
runningN = 1
runningGcd = 1
theExp = 2 \\determines the upper range for both a & b
forstep(a=3,19^theExp ,2,{
forstep(b=3,19^theExp ,2,
n=a*b;
ag=gcd(a-1,n-1);
bg=gcd(b-1,n-1);
if(ag > runningGcd && !ispower(n),
runningN =n;
runningGcd =ag;
);
print("** ",n," >> ",ag);
if(ag != bg,
print("**** Counterexample ****");
next(19); \\\\ Halt RUN if a counterexample is found
);
);
})

print("***** ",runningN ," >> ",runningGcd );
factor(runningN)




[/CODE]

[QUOTE=Dr Sardonicus;586809]Did you mean x[sup]2^p[/sup] + 1?[/QUOTE]
That was what I meant to type in, but the script coding seemed to take the inner layer out, thus the entire expression looked like another equation.

[QUOTE=tuckerkao;586899][QUOTE=Dr Sardonicus;586809]Did you mean x[sup]2^p[/sup] + 1?[/QUOTE]That was what I meant to type in, but the script coding seemed to take the inner layer out, thus the entire expression looked like another equation.[/QUOTE]Yes, some bbcode tags inside of bbcode tags don't work.

I advise you to hit "Preview Post," and check the preview every time before you post a message. That way, you won't have to bother trying to remember which nested bbcode tags work and which ones don't. If any nested bbcodes are squirrelly, you'll see it in the preview window. You can then edit the message in the Message window (NOT the Preview window). You can check "Preview Message" repeatedly and edit repeatedly until it looks satisfactory, before you hit "Submit Reply."