Date:         Sun, 15 Nov 1998 15:51:03 -0500
Reply-To:     Harvey Dubner <hdubner1@compuserve.com>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Harvey Dubner <hdubner1@compuserve.com>
Subject:      3-component Carmichael Numbers

Numbers of the form,

(6M+1)(12M+1)(18m+1)

are Carmichael numbers whenever all three components are prime.  This,
perhaps, is the best known family of Carmichael numbers.  Because of the
single parameter that appears in each of the components, the form of M can
be chosen so that prime proving is fast and easy.  Also, there are more
Carmichael numbers in this family than any other.  There is data indicating
that about 2.5% of all 3-component Carmichael numbers are of this form.

The smallest such Carnichael number is  7*13*19=1729.  I have recently found
the three largest such numbers (as far as I know).  They are of the form,

N=P_1*P_2*P_3  where   P_i=c*3003*k_i*10^b + 1,   k_i=1,2,3

             Times based on pentium/200 equivalent

b=exp  c=multiplier  digits  Estimated search time  actual time
__________________________________________________
1502    6948950     4538  131 computer-days    12 days  (lucky!!)
1308    19513527   3958    33 computer-days    36 days
1204    51412393   3647    23 computer-days    48 days


Note that each component of the number with 4538 digits has 1513 digits.
Finding 3 primes simultaneously of this size is not easy.

I also counted the number of such Carmichael numbers of this type up to
10^36.

----------------------------------------------------------------------------
3 component Carmichael numbers of the form
      C = (6M+1)(12M+1)(18M+1)

  n     Number of C's < 10^n
-----   ----------------------
3          0
4          1
5          1
6          2
7          2
8          3
9          7
10         10
11         16
12         27
13         45
14         77
15        133
16        234
17        415
18        746
19       1354
20       2480
21       4580
22       8519
23      15956
24      30069
25      56988
26     108570
27     207836
28     399638
29     771621
30    1495580
31    2909178
32    5677865
33   11116339
34   21828157
35   42670184
36   27940603

I know that Wilfrid Keller previously had counted up to 10^30 some years
ago.  The new, fast computers are wonderful.

Harvey Dubner





Date:         Mon, 23 Nov 1998 13:43:08 -0500
Reply-To:     Harvey Dubner <hdubner1@compuserve.com>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Harvey Dubner <hdubner1@compuserve.com>
Subject:      3-component Carmichael numbers-correction

On November 15, 1998, I posted a message which included the counts of the
number of Carmichael numbers of the form,

(6M+1)(12M+1)(18M+1) .

Unfortunately, the table had an error in the last entry, for n=36 (10^36).
Here is the corrected table including 3 additional entries.

Harvey Dubner
_______________________________________

3 component Carmichael numbers of the form
      C = (6M+1)(12M+1)(18M+1)

  n     C's < 10^n
-----   ------------
  3          0
  4          1
  5          1
  6          2
  7          2
  8          3
  9          7
 10         10
 11         16
 12         27
 13         45
 14         77
 15        133
 16        234
 17        415
 18        746
 19       1354
 20       2480
 21       4580
 22       8519
 23      15956
 24      30069
 25      56988
 26     108570
 27     207836
 28     399638
 29     771621
 30    1495580
 31    2909178
 32    5677865
 33   11116339
 34   21828157
 35   42670184
 36   84144873
 37  166369603
 38  318733896