Problems & Puzzles: Puzzles

Puzzle 371. A052215 This interesting sequence (A052215) asks for the smallest pairs of consecutive numbers, n & n+1 such that each of them is composed exactly for k distinct primes. Currently there are known only 10 terms: 2, 14, 230, 7314, 378014, 11243154, 965009045, 65893166030, 5702759516090, 605247139068494 14                             15 2*7 3*5                                   230                           231 2*5*23 3*7*11                           7,314                        7,315 2*3*23*53 5*7*11*19                             378,014                    378,015 2*7*13*31*67 3*5*11*29*79                       11,243,154                11,243,155 2*3*13*17*61*139 5*7*11*19*29*53                       965,009,045              965,009,046 5*7*11*13*23*83*101 2*3*17*29*41*73*109                  65,893,166,030         65,893,166,031 2*5*17*19*43*67*73*97 3*7*11*29*31*41*71*109             5,702,759,516,090     5,702,759,516,091 2*5*7*13*31*37*131*179*233 3*11*17*19*23*47*67*83*89          605,247,139,068,494 605,247,139,068,495 2*13*17*23*31*41*43*67*71*229 3*5*7*11*37*47*53*89*193*331 Q1. Find one more solution. I have extended this game to triplets. The sequence goes like this: 33, 1309, 203433, 16467033,... for 2, 3, 4, 5 ... distinct prime factors. For example: 16467033 3*11*17*149*197 16467034 2*19*23*83*227 16467035 5*13*37*41*167 Q2. Extend the sequence.

---

Contributions to Q2 came from Farideh Firoozbakht, Igor Schein & Jacques Tramu.

***

Farideh wrote:

All terms of the sequence are of the form 4k+1 because, If n isn't of the

form 4k+1 then 4 divides one of the three numbers n, n+1 & n+2 , so that

number isn't square free and according to the definition of the sequence n

isn't in the sequence.

 

Next term is 1990586013 and we have:

 

1990586013=3*13*29*67*109*241

1990586014=2*23*37*43*59*461

1990586015=5*11*17*19*89*1259

***

Igor wrote:

k=6 {n=1990586013, n+1, n+2}
k=7 {n=41704979953, n+1, n+2}
k=8 {n=851066388303493, n+1, n+2}

Let's call the largest prime divisor of a number its height. I loop
over k-tuples of primes while increasing the height. For each
candidate C I look at C+1, C+2, C-1 and C-2 to see if they're
square-free and if their omega is also k. This way I am guaranteed to
hit the smallest-height member of the triple before the other two,
which generally results in finding a solution sooner. Every time I
find a (possibly non-minimal) solution, I continue in the same
fashion, but this time I first check if a candidate C is a member of a
smaller solutions then the already found one, before looking at C +/-
1, C +/- 2.

This approach as it is unfortunately doesn't guarantee the minimal
solution.
 

***

Jacques wrote:

LG:6, 1 990 586 013  

LG:7,  41 704 979 953

-- 41704979953 = 7* 13 *29 *41* 47* 59 *139
-- 41704979954 = 2 *11 *23 *31* 83* 103* 311
-- 41704979955 = 3* 5 *17 *19* 109* 157* 503

***

Fred Schneider wrote, on 16/9/6:

11 Solution:

78971815814237709=3*11*17*23*29*31*41*43*71*137*397
78971815814237710=2*5*7*13*19*47*59*113*157*227*409

(I searched for all even numbers with max factor < 1500.  It may be minimal but I'm not positive)

12 Solution:

91710717175892025210=2*3*5*17*31*43*101*149*179*283*311*569
91710717175892025211=7*11*13*19*29*41*53*61*79*97*313*523

This is likely not the lowest solution but it narrows the search space to numbers < 10^20.

My method: I wrote a C program which computes an even number c with n factors and  attempt to factor c-1 and c+1 such that
either may have n factors.
For levels 1 to n-1, compute a set of modulus through some p and smaller modulus set for squared primes for each level
iterating through the primes through p and keep a running sum of the logs of the prime factors.  That way
there's no practical limit to the size of the solution sought and large number arithmetic is not needed.
At the final level, loop through the pth prime but only compute the modulus of the prime set only while c-1 or c+1 is a viable candidate.

Optimizing code:  Any n-factor solution must be > sqrt(product of the first 2n primes) = s  ***
and at level L, log(c) must be >= log(s)-(n-L)*log(p) otherwise it's wasted search
At the nth level, let's call "a" the product of the x factors found so far of either c-1 or c+1 through the mth prime.  It's only worthwhile
to keep searching if log(n)-log(a) > (n-numFactors)*log(prime(m+1)).
The "logs" are precomputed in an array and some rounding error is included in the calculations as is often necessary with floating math.

*** Similarly for trios, any n-factor solution must be > cube_root(product of the first 3n primes)

***

On Set. 20, 06, Fred wrote more on the same issue:

I updated my answer below.  I found a smaller number for "12" plus a smaller solution for the "8 trio" (Ivan's answer was not the minimal solution apparently).  Plus a 9-trio solution:
 

11 Solution:

78971815814237709=3*11*17*23*29*31*41*43*71*137*397
78971815814237710=2*5*7*13*19*47*59*113*157*227*409

(I searched  all 11-factor even numbers with max factor < 2000.  This is likely minimal but I'm not positive)

12 Solution:

22593106657425552170=2*5*13*23*43*47*61*67*79*139*227*367
22593106657425552171=3*7*11*19*29*59*71*97*101*131*137*241

I searched  all 12-factor even numbers with max factor < 500.  This is probably not the lowest solution.

My method: I wrote a C program which computes an even number c of the form 4g+2 with n factors and then attempts to factor c-1 and c+1 such that either may have n factors.
For levels 1 to n-1, it computes a set of modulus through some p and smaller modulus set for squared primes for each level, iterating through the primes through p and keep a running sum of the logs of the prime factors.  That way,
there's no practical limit to the size of the solution sought and large number arithmetic is not needed.
At the nth level, loop through the pth prime but only compute the modulus of the prime set only while c-1 or c+1 is a viable candidate.

Optimizing code:  Any n-factor solution must be > sqrt(product of the first 2n primes) = s 
and at level L, log(c) must be >= log(s)-(n-L)*log(p) otherwise it's a wasted search.  At the nth level, let's call "a" the product of the x factors found so far of either c-1 or c+1 through the mth prime.  It's only worthwhile
to keep searching if log(n)-log(a) > (n-numFactors)*log(prime(m+1)).
The "logs" are precomputed in an array and some "fuzziness" is included in the calculations as is often necessary with floating math to avoid missing any solutions.

The "11" and "12" solutions above are about 44 and 147 times their respective theoretical minimums.
 

===========================================================
 

I also found 4 smaller trio solutions for n=8.  The smallest one is:

162338633743713=3*7*17*29*149*241*283*1543
162338633743714=2*23*37*67*89*113*353*401
162338633743715=5*11*13*31*163*173*179*1451

This is the smallest answer where the max prime of the even (middle) number is < 1500 . 

Trio solution for n=9:
82730444975760153=3*11*13*17*23*239*677*1319*2311
82730444975760154=2*31*37*61*107*181*223*367*373
82730444975760155=5*7*43*59*73*89*97*491*3011

This is the smallest, answer where the max prime of the even (middle) number is < 500


My logic is the same as the pair logic except that:
1) The code only continues through the set of primes while c-1 AND c+1 are viable candidates.
2) The lower bound to any solution must be > cube_root(product of the first 3n primes). 

The "8" and "9" answers above is about 564 and 2869 times their respective theoretical minimums.  Note: The minimal 7 trio solution is only about 12 times the theoretical minimum.

***

Fred Schneider wrote (June,07):

8775662872958796813 = 3*23*29*31*37*113*163*191*479*2269
8775662872958796814 = 2*17*67*89*97*107*131*277*281*409
8775662872958796815 = 5*7*11*13*19*149*241*433*997*5953

***

 

---