Problems & Puzzles: Puzzles

Puzzle 585. 37677869739 Perhaps you already know that 37677869739 is the smallest starting integer of a set of 24 consecutive integers such that each one is divisible by a distinct prime chosen from among the first 24 primes. As a matter of fact this is reported in A083129 Q. Can you extend this table?

---

Contributions came from Giovanni Resta, J. K. Andersen, Robert D Mohr & Jan van Delden

***

Giovanni wrote:

My results (obtained with running times ranging from 6 seconds to 16 hours) are for n from 25 to 32.
Below each number there is the sequence of primes which divides
the numbers in the interval. That is, if the sequence is
{7,11,19,...} then n is divisible by 7, n+1 by 11, n+2 by 19 and so on.
(I also checked the previous terms in the sequence)

25 29035604208
{3,67,5,47,71,11,31,59,89,53,2,73,37,13,97,17,19,23,79,7,29,41,43,83,61}

26 216718364268
{73,47,61,23,2,53,3,5,29,97,13,101,43,19,7,41,67,59,79,31,71,89,83,11,17,37}

27 216718364267
{103,73,47,61,23,2,53,3,5,29,97,13,101,43,19,7,41,67,59,79,31,71,89,83,11,17,37}

28 20410184278342
{71,79,19,5,29,31,103,17,23,61,11,107,13,47,3,83,7,101,89,73,43,41,2,67,37,97,59,53}

29 20410184278341
{109,71,79,19,5,29,31,103,17,23,61,11,107,13,47,3,83,7,101,89,73,43,41,2,67,37,97,59,53}

30 38673118336735
{29,13,79,2,47,83,41,17,11,61,5,89,73,67,3,101,107,97,113,103,23,53,31,19,37,71,59,7,43,109}

31 38673118336735
{29,13,79,2,47,83,41,17,127,61,5,89,73,67,3,101,107,97,113,103,23,53,31,19,37,71,59,7,43,109,11}

32 897980683551921
{17,37,89,7,19,79,29,73,131,43,97,127,103,59,5,31,113,107,13,2,11,3,53,67,71,23,61,109,47,101,41,83}

***

J. K. Andersen wrote:

25:     29035604208
26:    216718364268
27:    216718364267
28:  20410184278342
29:  20410184278341

***

Robert wrote:

For n=25, the fist integer for the lowest sequence is 29035604208.

***

Jan wrote:

The PARI program (on SLOANE’s) suggests the Chinese remainder theorem is used upon all permutations of a list of n residues i, i=0..n-1, and the primes p[1]..p[n].
The minimum value of these results is the sought value. As n increases this takes a lot of computing time.

I decided to “just run through” the numbers N (and hopefully hit on a solution before trying n! numbers). To speed up the search I matched the primes in descending order.

 

The routine should match numbers N+offset with the offset in [0..n-1].

It is therefore convenient to define the residue as  (–N) mod p[k] which should equal a possible offset if p[k]>=N.

 

In step I, the routine tries to match the primes p[k]>=N. Increasing N if the residue does not match the interval [0..n-1] or if residues are equal for two primes used.
[For n=26 the first increase is about 41.8 and the second is 20.2 <used much less frequently>]

 

In step II, a list of possible (not assigned) offsets has to be computed for each prime p[k]<n based on the residue. Run through the p[k], if  there is just 1 offset for p[k] remaining assign it to p[k] and try p[k+1]<p[k], if there is none, proceed to N+1 and start over. Repeat this check until hopefully all residues are assigned. <There is no garantee all offsets can be assigned this way, but it proves to do the job, untill now..>.

 

25 29035604208

26 216718364268

27 216718364267

 

For n=26 the assigned offsets and primes are (in the order found by the routine):

Offsets: I) [11,9,21,22,18,0,20,16,2,17,5,1,12,15,25,19,8]             II)[3,13,23,7,24,10,14,6,4]
Primes: I) [101,97,89,83,79,73,71,67,61,59,53,47,43,41,37,31,29] II)[23,19,11,5,17,13,7,3,2]

 

The found values for N/(average increase) are much smaller than n!. But again, no guarantee that this is true in general.

 

A theoretically justified (large) lowerbound could speed up this search...

***

---