--- On Fri, 3/15/13, djbroadhurst <

d.broadhurst@...> wrote:

> "paulunderwooduk" <paulunderwood@...> wrote:

>

> > Presumably, it is a Carmichael number

>

> http://arxiv.org/pdf/1203.6664.pdf

>

> > We have constructed a Carmichael number with 10,333,229,505 prime factors

Yeah, but you can't believe everything they say, as they also say

"""

Current records for Carmichael numbers with many prime factors

go to Loh and Niebuhr [9] at 1101518 prime factors and an

unpublished computation by the ﬁrst two authors at 19565300

prime factors.

"""

Pah! I'm pretty sure that MJOS & I announced out record-breaking Carmichaels either here (or on NMBRTHRY?) whenever it was (8-10 years ago?). I've got to admit, it was too easy and mathematically boring (just a simple big-steps-baby-steps discrete logarithm) so we didn't bother wasting time pushing the limit as far as the algorithm (and storage capacity for the table of small primes) would go - that would just be handle-turning.

Hmm, even google can't find that - but I ain't senile, I do remember doing it! I still have the code and and some early runs on my machine:

$ ls -al mjos/mjos.txt

-rw-r----- 1 phil phil 4439 Nov 30 2002 mjos/mjos.txt

$ ls -al mjos/known/car24.tbz

-rw-r--r-- 1 phil phil 4768781 May 20 2004 mjos/known/car24.tbz

$ bunzip2 < $! | wc -l

1521430

That's bigger than the Loh one, at least, and confirms the timescale I was thinking about (the .tbz was almost certainly created by me when cleaning up after the files were no longer current). I don't think Markku-Juhani ever gave me the output of his larger runs (he had access to his uni cluster), so they're lost. But I as I have the code, I could recreate them, they nearly double in size with each step. More

However, 10,333,229,505 is a truly momentous, I cannot imagine how many more doublings of our problem size would be necessary to reach that far. Even hundreds of millions of small primes would have been pushing the limits of any single machine I have access to today.

So this is almost certainly a serious algorithmic breakthrough, and not just handle-turning. I shall give it a more thorough read tomorrow.

Phil

--

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]