You just invented a very obfuscated way to compute Eulers's Totient (pari: eulerphi) function, or what? :razz:

[QUOTE=LaurV;611746]You just invented a very obfuscated way to compute Eulers's Totient (pari: eulerphi) function, or what? :razz:[/QUOTE]


If you are referring to post #66


To search for possible remainders q (modulo bW), proceed as described in post [URL="https://www.mersenneforum.org/showpost.php?p=611621&postcount=54"]#54[/URL]:

Set bW=2*p*k then k=bW/2/p=PrimesBaseProd=2*p1*p2*...*pn

if q is a possible factor

q=1+2*p*k1=RW[i]+bW*j with 0<=i<nR possibile remainder RW[i] = q (modulo bW)

then k1=(RW[i]-1)/2/p+(bW/2/p)*j with (RW[i]-1)/2/p = k1 (modulo bW/2/p) = k1 (mod k)

so if k=0(mod 4) then bW=0(mod 8) to speed up the search it is possible to evaluate only p=1(mod 4) or p=3(mod 4) cases in fact if r is a remainders then it must be r=1(mod 8) or r=7(mod 8):

for 0 <= a < k/4

r=1+8*p*a

and

r=1+2*p+8*p*a if p%4=3 or r=1+6*p+8*p*a if p%4=1

from these remainders you have to remove those that have factors in common with bW

so since r=1(mod 2*p) if p1=2 remove those are divisible by p2,...,pn


Note that as mentioned in a previous post the value of nR depends on n_PB:

nR=2 if n_PB = 1, nR=4 if n_PB = 2, nR=16 if n_PB = 3, nR=96 if n_PB = 4 and nR=960 if n_PB = 5

and if you have no memory problems you can add prime numbers > 11 in PrimesBase and increase n_PB although I don't know if there are any advantages in terms of speed.

In reference to your question in #67 the eulerphi function maybe allows you to calculate nR but I am interested in the possible remainders so you can use q = RW[i] + bW * j.


For example it is possible to calculate the vector v used in [URL="https://www.mersenneforum.org/showpost.php?p=319334&postcount=35"]Trial factoring, part 2 of 3[/URL] simply by setting n_PB=2 and adding this piece of code


[CODE]
std::vector<int64_t> v;
v.push_back((RW[1]-1)/2/P);
for (int64_t i=2;i<nR;i++)
v.push_back((RW[i]-1)/2/P-(RW[i-1]-1)/2/P);
v.push_back(PrimesBaseProd-(RW[nR-1]-1)/2/P);

[/CODE]

[QUOTE=User140242;611737]In my opinion the result highlighted post #62 does not allow to exclude factors that are not possible in fact for example if k=16 and p=5 mod 12 it is also necessary to exclude the factors k2%12=1=16-15 and k2%12=9=16-7...[/CODE][/QUOTE]
Post #62 is concerned with arbitrary primes [I]p[/I], placing additional conditions on [I]p[/I] gives further refinements indeed.

[QUOTE=Dobri;611773]Post #62 is concerned with arbitrary primes [I]p[/I], placing additional conditions on [I]p[/I] gives further refinements indeed.[/QUOTE]You disregarded the careful explanation in [url=https://www.mersenneforum.org/showpost.php?p=611260&postcount=42]this post[/url] and reference to more explanation in [url=https://www.mersenneforum.org/showpost.php?p=611265&postcount=45]this post[/url], and continued to do unnecessary computations

[quote=Dobri;611321]However, the cases for k = 12m + 8 and 12m + 11 still need a theoretical interpretation.
I do not have a counterexample with p mod 6 = 5 that would result in a prime q = 2kp + 1 for k = 12m + 8 or 12m + 11 that divides 2p - 1.
Currently, I am checking the known prime factors in the GIMPS database for a counterexample.
Such a counterexample with p mod 6 = 5 could be rare or does not exist.[/quote]In other words, you were searching the entire GIMPS database for prime factors q of Mersenne numbers with exponent p == 5 (mod 6) for which q is divisible by 3.

Then, in [url=https://www.mersenneforum.org/showpost.php?p=611685&postcount=62]this post[/url] you proclaimed "exhaustive computations indicate" something that is obvious from the first formulas for k given in the first post linked to above.

So perhaps you can help me with a similar problem. I've run extensive computations, reducing battalions of supercomputers to molten slag, which indicate that no number greater than 5 which in decimal ends in 0, 2, 4, 5, 6, or 8, is prime. Of course, I have no idea why this could possibly be true.

[QUOTE=Dr Sardonicus;611816]You disregarded the careful explanation in [URL="https://www.mersenneforum.org/showpost.php?p=611260&postcount=42"]this post[/URL] and reference to more explanation in [URL="https://www.mersenneforum.org/showpost.php?p=611265&postcount=45"]this post[/URL], and continued to do unnecessary computations

In other words, you were searching the entire GIMPS database for prime factors q of Mersenne numbers with exponent p == 5 (mod 6) for which q is divisible by 3.

Then, in [URL="https://www.mersenneforum.org/showpost.php?p=611685&postcount=62"]this post[/URL] you proclaimed "exhaustive computations indicate" something that is obvious from the first formulas for k given in the first post linked to above.

So perhaps you can help me with a similar problem. I've run extensive computations, reducing battalions of supercomputers to molten slag, which indicate that no number greater than 5 which in decimal ends in 0, 2, 4, 5, 6, or 8, is prime. Of course, I have no idea why this could possibly be true.[/QUOTE]
One could have better read between the lines and understood that me "searching the entire GIMPS database" happened as much as someone else was "reducing battalions of supercomputers to molten slag".
It can be argued from the standpoint of hardware and software testing that there is no such thing as unnecessary computations though.
Running computation tests produces errors and soon or later one of the "battalions of supercomputers" would [U]in error[/U] (for instance, see [URL]https://en.wikipedia.org/wiki/Integer_overflow[/URL]) give a prime.

Examples of the first Mersenne numbers for which there are three consecutive factors for a given value of [I]k[/I][SUB]3[/SUB] with [I]k[/I][SUB]3[/SUB] = [I]k[/I][SUB]2[/SUB] + [I]k[/I][SUB]1[/SUB] are:
- M[M]1527857[/M] with factors {21389999, 12222857, 9167143}. Here 7 = 4 + 3.
- M[M]159541[/M] with factors {3509903, 2552657, 957247}. Here 11 = 8 + 3.

[QUOTE=Dr Sardonicus;611816]You disregarded the careful explanation in [URL="https://www.mersenneforum.org/showpost.php?p=611260&postcount=42"]this post[/URL] and reference to more explanation in [URL="https://www.mersenneforum.org/showpost.php?p=611265&postcount=45"]this post[/URL], and continued to do unnecessary computations

In other words, you were searching the entire GIMPS database for prime factors q of Mersenne numbers with exponent p == 5 (mod 6) for which q is divisible by 3.

Then, in [URL="https://www.mersenneforum.org/showpost.php?p=611685&postcount=62"]this post[/URL] you proclaimed "exhaustive computations indicate" something that is obvious from the first formulas for k given in the first post linked to above.

So perhaps you can help me with a similar problem. I've run extensive computations, reducing battalions of supercomputers to molten slag, which indicate that no number greater than 5 which in decimal ends in 0, 2, 4, 5, 6, or 8, is prime. Of course, I have no idea why this could possibly be true.[/QUOTE]
:goodposting: :tu:
The last paragraph is priceless.... :missingteeth:

[QUOTE=Dobri;611887]Examples of the first Mersenne numbers for which there are three consecutive factors for a given value of [I]k[/I][SUB]3[/SUB] with [I]k[/I][SUB]3[/SUB] = [I]k[/I][SUB]2[/SUB] + [I]k[/I][SUB]1[/SUB] are:
- M[M]1527857[/M] with factors {21389999, 12222857, 9167143}. Here 7 = 4 + 3.
- M[M]159541[/M] with factors {3509903, 2552657, 957247}. Here 11 = 8 + 3.[/QUOTE]
This is a clear example of Guy's Strong Law of Small Numbers. Pick enough small numbers, and you will find plenty of triplets (a, b, c) such as a=b+c.

I still have this "feeling" that mersenne factors and fermat factors have more chances to be also aliquot factors, compared with the other primes. If you think about, THERE IS a connection, because all those "drivers" are related to perfect numbers, which in turn are strong related to mersenne primes. If the drivers are persistent, guides are persistent (guide is a driver from which some factors were removed, so it is just a "partial" driver), then why the factors alone couldn't be persistent too? So, when I look to factorDB aliquot sequences and see the small primes that factor each terms, I have the tendency to only see 3, 5, 7, 17, 23, 47, 89, 223, 233, etc, and I have this "feeling" that there are more such primes than "the others" of comparable size, and they are also "persistent" (their chances to appear again and again from a term to the next seems higher) than the other primes that come and go. So, maybe you can try to "intensively test" all the aliquot factors in factorDB and see if they are indeed factors of some mersenne numbers in our range of interest? (i.e. under 1G exponents, or under 32 bits exponents more generally). That way, at least, you would use your energy in a more useful way, and maybe you get lucky and really find some huge factors there :razz:

One would expect q1 = 6*p + 1, q2 = 8*p + 1, and q3 = 14*p + 1 all to be prime for infinitely many p == 1 (mod 4). One would also expect 2 to be a 6th power residue (mod q1), 8th power residue (mod q2), and 14th-power residue (mod q3) for a positive proportion of such (q1, q2, q3). (My best guess at the "positive proportion" is 1/84.)

I checked for such p, q1, q2, q3 up to the limit p < 1.1 x 10[sup]8[/sup]. Up to that limit, there are 2383 p == 1 (mod 4) for which q1, q2, and q3 are all prime. Of these, there are 23 for which q1, q2, and q3 all divide 2^p - 1.

Thus, among p < 1.1 x 10[sup]8[/sup] the proportion of prime triples (q1, q2, q3) all dividing 2^p - 1 is a bit lower than 1/84.

The values p q1 q2 q3 with p < 10[sup]7[/sup] are

1527857 9167143 12222857 21389999
1684937 10109623 13479497 23589119
3524537 21147223 28196297 49343519
6317357 37904143 50538857 88442999