Problems & Puzzles:
Puzzles
Puzzle 171. Perfect &
Carmichael numbers
Here is a new puzzle suggested by Frank Ellerman. This new
puzzle is based in the fact that Carmichael and
Perfect numbers are
related the following way:
If e(n) is the n-th
perfect number, and we
find a(n) so that
a(n) * e(n) * d(n) + 1
is prime for all proper divisors d(n) of e(n), then the product of these
primes is a Carmichael number
Examples:
For e(1)=6 the proper divisors d(1) are 1+2+3 (=6), and for a(1)=1
we get 3 primes 1*6*1+1=7, 1*6*2+1=13, 1*6*3+1=19. The product 7*13*19
is then (necessarily) a 3-Carmichael number. BTW,
a(1)= 1 corresponds to EIS A046025(1).
For e(2)=28 the 5 divisors d(2) are 1+2+4+7+14 (=28), and with
a(2)=2136 we get 5 primes 2136*28*d(2)+1, the product is again
necessarily a 5-Carmichael number: 599966117492747584686619009. BTW a(2)=
2136 corresponds to EIS A067199(1).
Frank questions:
1. Find the least a(3) for e(3) =
496
2. Find the least a(4) for e(4) = 8128
My questions:
4. Find the least a(2) for e(2)=28
such that the 5-Carmichael number produced by the
product of the five primes is Titanic
5. Redo the exercise 4. trying to
beat the 3-Carmichael number world
record
(10,200 digits, 1998,
Harvey Dubner)
[See Note below]
Solution:
Note to question 5 (added the 26/3/2002)
Phil Carmody notices that the question 5 is
improper because:
a) The current 3-Carmichael record is now the product
of three primes, 7106, 7107 & 14206 digits each, found by him
the 13/3/2002.
b) Is improper to ask to beat a 3-Carmichael record
with a 5-Carmichael number; if question 5 is a redo of
question 4, and question 4 is to find a large 5-Carmichael number, then
the proper question should be with this number to beat the current
5-Carmichael record (a 4271-digit number), gotten by David Broadhurst
the 1/3/2002.
According with all this, the new question 5 is:
5. Redo the exercise 4. trying to
beat the 5-Carmichael number world
record
(4271 digits, 1/3/2002, David Broadhurst)
It should be noted that the Carmody's and the Broadhurst's
Carmichael records are not produced following the
Perfect-Carmichael-numbers-link, but another wider than this.
While questions 4 & 5 must be
responded with numbers keeping this Perfect-Carmichael-numbers-link
following the spirit of the original Ellerman puzzle-proposal.
***
Felice Russo wrote (15/4/2002):
Only to inform you that for three weeks I worked on the item 1 of
puzzle 171. Up to a(3)=233754853 no Carmichael number has been found.
***
Jim Fougeron wrote (3/5/2002):
Here is the answer for #1 on puzzle 171.
the least a(3) for e(3)=496 which generates a 9-Carmichael is
13494274080.
(13494274080*496+1)*(13494274080*496*2+1)*
(13494274080*496*4+1)*(13494274080*496*8+1)*
(13494274080*496*16+1)*(13494274080*496*31+1)*
(13494274080*496*62+1)*(13494274080*496*124+1)*
(13494274080*496*248+1)=
16315768534164504503768899887255535481340474863295853498430\
22397649864136156162979036439091121153232606890925336730106\
285793281
I am well on my way to finding the next smallest (over 30 billion right
now) The CPU time used (once I got tired of using APSieve
and wasting hours of time on disk I/O), was just over 30 minutes. I did
this with nothing more than a modified sieve of Eratosthenes (9
simultaneous modular sieves over the same range of numbers). The sieve
factors out all values which any of the 9 candidates have a factor less
than 202291. I had found 24 of these factored sets, and the 25th had all
values prime. I have found over 40 candidates since then, but none have
had all values prime.
This was actually not too difficult of a puzzle, once it is simply
looked at as a 9 step sieve.
***
One day after Jim wrote again now about the solution to question 4:
Puzzle #171 question # 4, the solution is:
Preliminary: find the minimal a(2)=a_t which creates a titanic
Carmichael candididate. This happens at a(2)
=594263089026802941591263784280977080604417821967468784755725941\
253423450335870970593488721652558694467988150597534378269455689\
231232542934932434749577886907217889818742359930075809118799528\
942424753 (call a_t from here on)
This is the first a(2) value which generates a titanic candidate for a
Carmichael. From this point, I incremented a_t until a value produced
primes for all 5 required factors. This happened at a_t + 43216624217. The
value a_t+43216624217 is the minimal titanic Carmichael for the perfect
number 28. The expression (which can be directly fed into PFGW) is:
((594263089026802941591263784280977080604417821967468784755725941\
253423450335870970593488721652558694467988150597534378269455689\
231232542934932434749577886907217889818742359930075809118799528\
942424753+43216624217)*28+1)* \
((594263089026802941591263784280977080604417821967468784755725941\
253423450335870970593488721652558694467988150597534378269455689\
231232542934932434749577886907217889818742359930075809118799528\
942424753+43216624217)*28*2+1)* \
((594263089026802941591263784280977080604417821967468784755725941\
253423450335870970593488721652558694467988150597534378269455689\
231232542934932434749577886907217889818742359930075809118799528\
942424753+43216624217)*28*4+1)* \
((594263089026802941591263784280977080604417821967468784755725941\
253423450335870970593488721652558694467988150597534378269455689\
231232542934932434749577886907217889818742359930075809118799528\
942424753+43216624217)*28*7+1)* \
((594263089026802941591263784280977080604417821967468784755725941\
253423450335870970593488721652558694467988150597534378269455689\
231232542934932434749577886907217889818742359930075809118799528\
942424753+43216624217)*28*14+1)
or the number in decimal:
100000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000036\
361524899585703333707005642179808477392838840459547852127527332\
336031439714058905338106405767651340557826903965715665403665254\
253414215340381354801982306773813962506472027985205398801510515\
926767130737664809842730556554838557972669327691098215297557812\
819591617009393912252696778606415095204880404379098458757684049\
723086085044267236727426422512691268116239357680873750349620481\
354558822804500744096481002831815774474204216472917962473515085\
743445948395330942972140089196170068091335788555462700844609776\
734449126501610579679486321282192014679210024370885643251124726\
717852786417038979438128955977655145375423106528833469040464228\
179654616043982071367451353994268057016596242675683193689772291\
187911158676858782140376043475913444392756879878874612038401668\
8199078106542047410157447996575683249525837908454550881
which is a 1000 digit 5-Charmichael. This number was found with a
custom written 5-way modular sieve, and 5-prp test built in. Total run
time was about 5 hours of Athlon 750.
***
For the question 2, Phil Carmody wrote
(11/5/2002):
Jim wanted to see how fast my gensv could tackle puzzle
171, and so I ran it for 7 minutes on my alpha, and got the following:
k=216818853118725
ptest(k*8128+1), 1
ptest(k*8128*2+1), 1
ptest(k*8128*4+1), 1
ptest(k*8128*8+1),1
ptest(k*8128*16+1), 1
ptest(k*8128*32+1), 1
ptest(k*8128*64+1), 1
ptest(k*8128*127+1),1
ptest(k*8128*254+1),1
Pest(k*8128*508+1), 1
ptest(k*8128*1016+1),1
ptest(k*8128*2032+1),1
ptest(k*8128*4064+1),1
The numbers aren't proved prime, but have passed 2 different fermat tests
and 10 MR tests each. It took 40 minutes to verify
the minimality, as with gensv it tests numbers out of order so you've got to
wait for a block to complete. I'm not going to
tackle the 17-term problem, as 17 gets a bit hard.
***
|
