 mersenneforum.org Mersenne Numbers Known from Number Practice to Be Composite
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2022-08-19, 15:22 #67 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 1011310 Posts You just invented a very obfuscated way to compute Eulers's Totient (pari: eulerphi) function, or what?    2022-08-19, 15:29   #68
User140242

Jul 2022

22×13 Posts Quote:
 Originally Posted by LaurV 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   2022-08-19, 17:31 #69 User140242   Jul 2022 22×13 Posts 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 v; v.push_back((RW-1)/2/P); for (int64_t i=2;i 2022-08-20, 05:26   #70
Dobri

"Καλός"
May 2018

3×112 Posts Quote:
 Originally Posted by User140242 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.   2022-08-21, 12:56   #71
Dr Sardonicus

Feb 2017
Nowhere

25·11·17 Posts Quote:
 Originally Posted by Dobri 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 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.   2022-08-22, 12:03   #72
Dobri

"Καλός"
May 2018

3·112 Posts Quote:
 Originally Posted by Dr Sardonicus 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.   2022-08-23, 01:14 #73 Dobri   "Καλός" May 2018 3·112 Posts 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   2022-08-23, 06:43   #74
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3·3,371 Posts Quote:
 Originally Posted by Dr Sardonicus 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....    2022-08-23, 06:55   #75
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

278116 Posts Quote:
 Originally Posted by Dobri 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   2022-08-23, 12:34 #76 Dr Sardonicus   Feb 2017 Nowhere 25·11·17 Posts 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   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Viliam Furik Number Theory Discussion Group 22 2020-12-08 14:45 TheGuardian GPU Computing 25 2019-05-09 21:53 jshort Factoring 9 2019-04-09 16:34 wildrabbitt Math 120 2016-09-29 21:52 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

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.

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