mersenneforum.org The hunt for the largest Carmichael numbers has begun ... some 20+ years ago
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2023-05-20, 18:43 #1 Neptune     "Martin Hopf" Jul 2022 Solar System 101 Posts The hunt for the largest Carmichael numbers has begun ... some 20+ years ago ... right here - right now! These numbers were introduced by the namesake as "absolute pseudoprimes". Isn't that a reason, to pay more attention on them? Don't be blinded by big Carmichael numbers with many factors, as these are always easy to construct. Concentrate on Carmichael numbers with few factors. Let's say less than a dozen or a hundred. The largest Carmichael number with 3 factors currently is (unless otherwise stated): 3-C11219 It's construction-method: Code: { x=vecprod(primes(80))/2; /* product of first 79 odd primes */ /* choose 'i' such that 'p' and 'q' are primes */ i = 74218118677881697744516449513018846424418844889229; m = (x*i-1)^13/4; p = 6*m+1; q = 12*m+1; r = (p*q-1)/(5*7*11*13)+1; c = p*q*r; /* todo: ECPP-certificates for 'p,q' and 'r' */ } /* diagnostic follows */ ispseudoprime([p,q,r]) [1, 1, 1] /* from now on 'p,q,r' are titled as strong probable primes! */ /* isc(C) returns '1' if the product of all primes in vector 'C' is a Carmichael number. */ isc(C)={vecprod(C)%lcm(C-vector(#C,x,1))==1}; isc([p,q,r]) 1 #digits(c) 11219 Still need to prove the primality of p,q and r. Any one can help with providing an ECPP-certificate? Last fiddled with by Neptune on 2023-05-20 at 19:04
2023-05-20, 19:33   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

23·71 Posts

Quote:
 Originally Posted by Neptune ... right here - right now! The largest Carmichael number with 3 factors currently is (unless otherwise stated): 3-C11219
That would be too trivial, maybe that could be the record in another century.

Quote:
 Originally Posted by Neptune Still need to prove the primality of p,q and r. Any one can help with providing an ECPP-certificate?
I would suggest to search in a form, where p-1,q-1,r-1 number's factorization is known.

 2023-05-20, 19:53 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×13×17×23 Posts A version of (R. Gerbicz') polysieve will find much larger numbers in a very short time. Or one can make a prototype (as some people say) "on their knee". For example: Step 1: sieve for CC len 2 in base 2; these are conveniently already a pair of 6k+1 and 12k+1 right away (where k=2m). Step 2: either sieve the result with triple leading coefficient - or run pfgw -f on triple leading coefficient and then recover the underlying CC pairs, and done. Or one can modify NewPGen - but it only compiles on ancient 32-bit configured machines and with GCC version <=3. I used to do that for the quad forms that I liked, but now I am not sure even AWS has 32-bit OS images.
2023-05-21, 02:01   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

23·71 Posts

Quote:
 Originally Posted by Neptune The largest Carmichael number with 3 factors currently is (unless otherwise stated): 3-C11219
Well, I know it is a trivial reference, larger records are:
https://mathworld.wolfram.com/CarmichaelNumber.html
And found not any better. If there is one, then they not mentioned this 60351 digits number.

 2023-05-21, 07:11 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 236668 Posts NMBRTHRY list is searchable Some hits over different years: 3-Carmichael number with 61072 digits https://listserv.nodak.edu/cgi-bin/w...MBRTHRY&P=R458 4-Carmichael number with 30366 digits https://listserv.nodak.edu/cgi-bin/w...=NMBRTHRY&P=R2 5-Carmichael number with 14241 digits https://listserv.nodak.edu/cgi-bin/w...MBRTHRY&P=R747 6-Carmichael number with 20961 digits https://listserv.nodak.edu/cgi-bin/w...NMBRTHRY&P=R29 7-Carmichael number with 3773 digits https://listserv.nodak.edu/cgi-bin/w...MBRTHRY&P=R564 8-Carmichael number with 16432 digits https://listserv.nodak.edu/cgi-bin/w...MBRTHRY&P=R574 9-Carmichael number with 11310 digits https://listserv.nodak.edu/cgi-bin/w...MBRTHRY&P=R564 19-Carmichael number with 23707 digits https://listserv.nodak.edu/cgi-bin/w...MBRTHRY&P=R527
2023-05-21, 20:07   #6
Neptune

"Martin Hopf"
Jul 2022
Solar System

101 Posts

Quote:
 Originally Posted by Batalov NMBRTHRY list is searchable Some hits over different years...
Thank you for the list!

I see, my modest 11k-digit 3-Carmichael number comes a bit late as D. Broadhurst already had a 60k-digit in 2002.

Better for me at the moment to hold on with the Erdős method:
99-Carmichael number with 23415 digits 99-C23415.

2023-05-21, 21:28   #7
paulunderwood

Sep 2002
Database er0rr

466610 Posts

Quote:
 Originally Posted by Neptune Better for me at the moment to hold on with the Erdős method: 99-Carmichael number with 23415 digits 99-C23415.
Factors factored out and reported to FactorDB

2023-05-25, 18:00   #8
Neptune

"Martin Hopf"
Jul 2022
Solar System

101 Posts

Quote:
 Originally Posted by Neptune Still need to prove the primality of p,q and r. Any one can help with providing an ECPP-certificate?
An unknown user worked out the ECPP-certificates for p and r between May 22/23 and uploaded them to factordb.com. Many thanks for your efforts!
Together with the successful N+1 test for q, which I missed completely, 3-C11219 is now a proven Carmichael number.

Quote:
 Originally Posted by R. Gerbicz I would suggest to search in a form, where p-1,q-1,r-1 number's factorization is known.
I agree with this. For larger Carmichael numbers, we cannot afford to spend more time on the ECPP of the factors than constructing the former.
With my current method the factors of p-1 can be handled quite well. My new record:

81-Carmichael number with 23883 digits: 81-C23883

Last fiddled with by Neptune on 2023-05-25 at 18:27

2023-05-25, 20:36   #9
paulunderwood

Sep 2002
Database er0rr

110728 Posts

Quote:
 Originally Posted by Neptune An unknown user worked out the ECPP-certificates for p and r between May 22/23 and uploaded them to factordb.com. Many thanks for your efforts! Together with the successful N+1 test for q, which I missed completely, 3-C11219 is now a proven Carmichael number.
'twas I
Quote:
 I agree with this. For larger Carmichael numbers, we cannot afford to spend more time on the ECPP of the factors than constructing the former.
Surely a job Serge+Ryan to tackle.

Quote:
 With my current method the factors of p-1 can be handled quite well. My new record: 81-Carmichael number with 23883 digits: 81-C23883
Factored for FactorDB

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Number Theory Discussion Group 14 2018-12-02 09:27 devarajkandadai Number Theory Discussion Group 1 2018-07-30 03:44 devarajkandadai Number Theory Discussion Group 14 2017-11-15 15:00 devarajkandadai Number Theory Discussion Group 0 2017-07-09 05:07 devarajkandadai Math 1 2004-09-16 06:06

All times are UTC. The time now is 13:24.

Sun May 28 13:24:23 UTC 2023 up 283 days, 10:52, 0 users, load averages: 1.29, 1.35, 1.31

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.

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