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

26 216718364268

27 216718364267

28 20410184278342

29 20410184278341

30 38673118336735

31 38673118336735

32 897980683551921


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...


Records   |  Conjectures  |  Problems  |  Puzzles