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
P
est(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.

***

 Records   |  Conjectures  |  Problems  |  Puzzles