Problems & Puzzles: Puzzles

 Puzzle 641. Cunningham Chains of semiprimes. Emmanuel Vantieghem sent the following nice puzzle: Inspired by Cunningham chains, let's consider sequences of semiprimes, s(1), s(2), ... such that  s(i+1) = 2 s(i) + 1  for  i = 1, 2, ... To ensure that the sequence is not part of a bigger such sequence, we restrict our attention to sequences for which (s(1)-1)/2  is not semiprime. Example :  1157, 2315, 4631, 9263, 18527, 37055, 74111, 148223, 296447. This sequence terminates at  296447  since  2*296447 +1 = 5*19*79*79  is not semiprime.   Q1. Prove that all such chains terminate.   I made a search for all  s(1) < 10^8  and the longest chain was this one: 2681669, 5363339, 10726679, 21453359, 42906719, 85813439, 171626879, 343253759, 686507519, 1373015039, 2746030079, 5492060159, 10984120319, 21968240639 (14 terms)   Q2. can you find longer chains ?

Contributions came from Hakan Summakoglu & J. K. Andersen

***

Hakan wrote:

Q2: My largest chain starting with the semiprime 121360769.

121360769, 242721539, 485443079, 970886159, 1941772319, 3883544639, 7767089279, 15534178559, 31068357119, 62136714239, 124273428479, 248546856959, 497093713919, 994187427839, 1988374855679  (15 terms)

***

Jens wrote:

Q2. There is a chain with 16 terms starting at 969870257.

***

Emmanuel vantieghem wrote (June 15, 2012)

Q1. First, observe that any sequence  ( a(i) )  (i = 1, 2, ... )  with  a(i+1) = 2 a(i)+1 is allways of the form

(2^m) k - 1,  (2^(m+1)) k - 1,  (2^(m+2)) k - 1, ...

for some odd  k  and some  m >= 0.

Next, let an odd term  N = (2^n)k - 1  of that sequence has  w  prime divisors (counted with multiplicity).  If  u  is a positive natural number such that  2^u === 1 mod N (for instance, take  u = EulerPhi(N)), then  (2^(n+u))k - 1  is a term of the sequence which is divisible by  N  and strictly bigger than  N.  Thus, its number of prime factors is > w.

As a consequence, there cannot be an infinite such sequence of only semiprimes.

Q2. This is my longest chain (17 semiprimes) :

9932943134 = 2*4966471567

19865886269 = 29*685030561

39731772539 = 107*371324977

79463545079 = 251*316587829

158927090159 = 389*408552931

317854180319 = 13*24450321563

635708360639 = 11*57791669149

1271416721279 = 19*66916669541

2542833442559 = 71*35814555529

5085666885119 = 1013563*5017613

10171333770239 = 383*26557007233

20342667540479 = 2600569*7822391

40685335080959 = 139*292700252381

81370670161919 = 67*1214487614357

162741340323839 = 37*4398414603347

325482680647679 = 14057*23154491047

650965361295359 = 11*59178669208669

***

 Records   |  Conjectures  |  Problems  |  Puzzles

 Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.