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

***