mersenneforum.org  

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

Reply
 
Thread Tools
Old 2022-08-19, 15:22   #67
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

1011310 Posts
Default

You just invented a very obfuscated way to compute Eulers's Totient (pari: eulerphi) function, or what?
LaurV is online now   Reply With Quote
Old 2022-08-19, 15:29   #68
User140242
 
Jul 2022

22×13 Posts
Default

Quote:
Originally Posted by LaurV View Post
You just invented a very obfuscated way to compute Eulers's Totient (pari: eulerphi) function, or what?

If you are referring to post #66


To search for possible remainders q (modulo bW), proceed as described in post #54:

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.

Last fiddled with by User140242 on 2022-08-19 at 15:34
User140242 is offline   Reply With Quote
Old 2022-08-19, 17:31   #69
User140242
 
Jul 2022

22×13 Posts
Default

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 Trial factoring, part 2 of 3 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);
User140242 is offline   Reply With Quote
Old 2022-08-20, 05:26   #70
Dobri
 
"Καλός"
May 2018

3×112 Posts
Default

Quote:
Originally Posted by User140242 View Post
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]
Post #62 is concerned with arbitrary primes p, placing additional conditions on p gives further refinements indeed.
Dobri is offline   Reply With Quote
Old 2022-08-21, 12:56   #71
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

25·11·17 Posts
Default

Quote:
Originally Posted by Dobri View Post
Post #62 is concerned with arbitrary primes p, placing additional conditions on p gives further refinements indeed.
You disregarded the careful explanation in this post and reference to more explanation in this post, and continued to do unnecessary computations

Quote:
Originally Posted by Dobri View Post
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.
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 this post 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.
Dr Sardonicus is offline   Reply With Quote
Old 2022-08-22, 12:03   #72
Dobri
 
"Καλός"
May 2018

3·112 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
You disregarded the careful explanation in this post and reference to more explanation in this post, 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 this post 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.
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 in error (for instance, see https://en.wikipedia.org/wiki/Integer_overflow) give a prime.
Dobri is offline   Reply With Quote
Old 2022-08-23, 01:14   #73
Dobri
 
"Καλός"
May 2018

3·112 Posts
Default

Examples of the first Mersenne numbers for which there are three consecutive factors for a given value of k3 with k3 = k2 + k1 are:
- M1527857 with factors {21389999, 12222857, 9167143}. Here 7 = 4 + 3.
- M159541 with factors {3509903, 2552657, 957247}. Here 11 = 8 + 3.

Last fiddled with by Dobri on 2022-08-23 at 01:29
Dobri is offline   Reply With Quote
Old 2022-08-23, 06:43   #74
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

3·3,371 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
You disregarded the careful explanation in this post and reference to more explanation in this post, 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 this post 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.

The last paragraph is priceless....
LaurV is online now   Reply With Quote
Old 2022-08-23, 06:55   #75
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

278116 Posts
Default

Quote:
Originally Posted by Dobri View Post
Examples of the first Mersenne numbers for which there are three consecutive factors for a given value of k3 with k3 = k2 + k1 are:
- M1527857 with factors {21389999, 12222857, 9167143}. Here 7 = 4 + 3.
- M159541 with factors {3509903, 2552657, 957247}. Here 11 = 8 + 3.
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

Last fiddled with by LaurV on 2022-08-23 at 06:58
LaurV is online now   Reply With Quote
Old 2022-08-23, 12:34   #76
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

25·11·17 Posts
Default

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 108. 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 108 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 < 107 are

1527857 9167143 12222857 21389999
1684937 10109623 13479497 23589119
3524537 21147223 28196297 49343519
6317357 37904143 50538857 88442999
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Repeating residues in LL tests of composite Mersenne numbers Viliam Furik Number Theory Discussion Group 22 2020-12-08 14:45
Mersenne number with exponent 333333367 is composite TheGuardian GPU Computing 25 2019-05-09 21:53
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 06:09.


Fri Sep 30 06:09:28 UTC 2022 up 43 days, 3:38, 0 users, load averages: 0.77, 0.95, 0.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔