| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Note 1020.30� discusses Carmichael numbers, since the interesting number
1729 is also a Carmichael number. They deserve their own topic.
N-1
A Carmichael number is a positive integer N satisfying A = 1 (mod N)
for all A relatively prime to N. The first few are:
561, 1105, 1729, 2465, 2821
In the "big primes list" I came across a method for generating
Carmichael numbers, sort of. At least it's faster than a linear search.
I think. Here's the extract:
n# = 2*3*5*7*...*p The product of the primes <= n, sometimes
called "prime-factorial" or "primorial".
M(k,n) = (1/4)*(k*47#/2 -1)^n : When 6M+1, 12M+1 and Y are all
Y(k,n,s) = 18*M(k,n)(4*M(k,n)+1)/s+1 : prime for the same k and n, their
: product is a Carmichael Number.
John
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1898.1 | AUSSIE::GARSON | achtentachtig kacheltjes | Thu Sep 29 1994 23:23 | 40 | |
re .0
>since the interesting number 1729
Yes, interestingly the taxi in which I came to work this morning was
number 1729. (-:
> n# = 2*3*5*7*...*p The product of the primes <= n, sometimes
> called "prime-factorial" or "primorial".
>
> M(k,n) = (1/4)*(k*47#/2 -1)^n : When 6M+1, 12M+1 and Y are all
> Y(k,n,s) = 18*M(k,n)(4*M(k,n)+1)/s+1 : prime for the same k and n, their
> : product is a Carmichael Number.
Just to make sure that I have this straight.
Choose k and n arbitrarily
1 / k * 47# \n
M = - �| ------- - 1 |
4 \ 2 /
Choose s arbitrarily
18M(4M+1)
Y = --------- + 1
s
If 6M+1, 12M+1 and Y are all prime then ...
I assume that you are asserting this without proof. It isn't obvious to
me.
Given that k, n and s are chosen arbitrarily (right?) does the
antecedent usually hold?
It looks to me that k must be odd, to make M an integer. Likewise is it
assumed that s must divide 18M(4M+1)?
| |||||
| 1898.2 | Equations look right to me | VMSDEV::HALLYB | Fish have no concept of fire | Fri Sep 30 1994 12:13 | 13 |
All good questions; I have no answers. Presumably you could ask the
list compiler for further reference.
> It looks to me that k must be odd, to make M an integer.
Other way around, right? k has to be even. Since there appear to be no
restrictions on s, I would assume any value that divides 18M(4M+1) is OK.
In the "1729" note the observation was made that a lot of Carmichael
numbers appear to be products of 3 or more factors. Sounds like a good
Knuth [HM50] level conjecture, supported at least partly here.
John
| |||||
| 1898.3 | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Fri Sep 30 1994 14:07 | 5 | |
Actually, I think Knuth proves in the exercises just after
presenting probabilistic primality checking programs that
Carmichael numbers do have at least three factors.
Dan
| |||||
| 1898.4 | check? | AUSSIE::GARSON | achtentachtig kacheltjes | Tue Oct 04 1994 00:11 | 21 |
re .2
>> It looks to me that k must be odd, to make M an integer.
>
> Other way around, right? k has to be even.
Assuming I copied the formula correctly...
1 / k * 47# \n
M = - �| ------- - 1 |
4 \ 2 /
If k is even then k/2 is an integer. 47# is even. So the product is
even. Subtract one and it's odd. Raise it to a power. It's still odd.
So 4 doesn't divide it.
Suppose k is odd. 47# is even but is only divided by 2 once. So 47#/2
is odd. So the product is odd. Subtract one and it's even. Raise to a
power and it stays even. If n >= 2 then there is certainly no problem
in the power being divisible by 4. For n = 1 it is left as an EFTR to
determine what additional constraints if any apply to k.
| |||||
| 1898.5 | It was a bad week | VMSDEV::HALLYB | Fish have no concept of fire | Tue Oct 04 1994 09:40 | 1 |
Yes, that's right. | |||||
| 1898.6 | AUSSIE::GARSON | achtentachtig kacheltjes | Sat Oct 21 1995 04:58 | 4 | |
re .*
Apparently some time in 1994 it was proven that there are infinitely
many Carmichael numbers.
| |||||