mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-12-13, 23:36   #23
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·32·83 Posts
Default

Quote:
Originally Posted by chalsall View Post
So that suggests an optimization is possible.

Any success with that yet?
I will use the suggestions given on post #11, except the part "you can guess the i-th res: it will be around i*M/cnt," The values can be anywhere in the range 0<m<x.

For example if x1 = 2 (mod mr) and x2 = 3 (mod mr), it is clear that x1 = 2 (mod m) and x2 = 3 (mod m) and these values are a lot less than m1 * m2 * m3 * ... mn.
alpertron is offline   Reply With Quote
Old 2017-12-15, 16:46   #24
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by alpertron View Post
I have read that threorem S but it is not applicable to this problem, because that theorem works when the values are represented as (a1 mod m1, a2 mod m2, a3 mod m3, etc).

which can then be restated in the form of a line on the x,y plane. as y1=m1*x+a1; y2=m2*x+a2; y3=m3*x+a3 and looking for common natural number y co-ordinates amongst them is what CRT is doing. your main problem is you've turned it all into a non-linear form. edit: and as to your around claim it depends on what's meant by around as 1 pm is close to 12 pm even though 1 is not close to 12. your numeric sort of the positive values is just a sort on the y intercepts of the new lines.

Last fiddled with by science_man_88 on 2017-12-15 at 16:51
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Complexity of Chinese Remainder Theorem carpetpool Miscellaneous Math 4 2017-02-09 19:26
Basic Number Theory 6: functions and the Chinese Remainder Theorem Nick Number Theory Discussion Group 4 2016-10-31 22:26
Chinese Remainder Problem ShiningArcanine Math 2 2007-11-17 10:01
Implementing Chinese Remainder Theorem in C ShiningArcanine Software 3 2007-11-17 05:55
Card Sorting Probability TimSorbet Math 13 2007-01-13 15:31

All times are UTC. The time now is 08:56.


Mon Jan 30 08:56:39 UTC 2023 up 165 days, 6:25, 0 users, load averages: 1.05, 0.90, 0.89

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

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