- --- On Fri, 3/15/13, djbroadhurst <d.broadhurst@...> wrote:
> "paulunderwooduk" <paulunderwood@...> wrote:

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

>

> > 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

"""

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] - --- In primenumbers@yahoogroups.com,

Phil Carmody <thefatphil@...> wrote:

> I'm pretty sure that MJOS & I announced out record-breaking

http://tech.groups.yahoo.com/group/primenumbers/message/11058

> Carmichaels either here (or on NMBRTHRY?) whenever it was

> (8-10 years ago?).

David - --- On Fri, 3/15/13, djbroadhurst <d.broadhurst@...> wrote:
> Phil Carmody <thefatphil@...> wrote:

Wow, if it was 200 times larger, then we did push it all the way to its limits. I'd forgotten that Markku-Juhani had done that, I don't have his logs. He did have access to part of what was once the 7th largest machine in the world when he was found that. A bit of a rewrite (we'd need more than 32 bits) would have been necessary to go any further. 6 Moore's Law doublings does indicate that a 6-billion factor Carmichael should be possible with the same algorithm on a cluster in 2013. With more-distributed computing, perhaps even more. The long boring bit that grows at O(n) is embarassingly parallel, and the "clever" bit (what Loh overlooked) only grows at O(sqrt(n)).

> > I'm pretty sure that MJOS & I announced out record-breaking

> > Carmichaels either here (or on NMBRTHRY?) whenever it was

> > (8-10 years ago?).

>

> http://tech.groups.yahoo.com/group/primenumbers/message/11058

Phil