--- In

primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:

>

> Excellent: post-hoc speed-ups are always welcome.

>

> Yet first credit should always go to the first

> discovery. Happily this also goes to you:

>

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

> > I have just finished a 1 GHz-yr investigation of this Conjecture

> > In every case but one, n was indeed a Carmichael number,

> > but for n = 507529 = 11*29*37*43, the conditions are satisfied

>

> a) To discover 1 non-Carmichael: 1 GHz-year (MO)

> b) To discover 6 more: less than 1 GHz-hour (DB)

> c) To recover all 7: less than 1 GHz-minute (MO)

>

> Which is the more meritorious?

>

> I incline to think : (a), by MO, at beginning of this process.

Thanks for that, David.

For c), I benefited from your Chinese hint: hereby gratefully acknowledged.

I think the best thing about a) was that it was truly exhaustive, in that it assumed no restriction on the number of factors of n; and as we have seen, the bulk of the time needed is for checking out semiprimes (even with your CRT improvement).

We can be certain that 507529 is a[1] for Neil's OEIS entry, when we get round to creating it.

But a[2] is currently not certain, as b) assumed no semiprime solution exists.

The algorithm in c) is almost linear in n_max, which is remarkable, isn't it.

I have run it up to n_max=10^10 so far, and found 89 non-Carmichaels.

The core of the lemma is one line of pari-GP code, but it's unproven. It was found "by inspection", after wrestling for some time with the following deep paper by Richard Pinch:

http://www.chalcedon.demon.co.uk/rgep/p20.pdf
[I can't remember, did you flag it in an earlier posting?]

The algorithm seems to work, and certainly gives those solutions, and only those, which your code gives, where they overlap.

I wonder if you can co-discover it?

(My turn to set a Puzzle:-)

Mike