Find a sequence of numbers

I need to solve task, there is a condition:

There is a a sequence of 17 consecutive natural numbers starting with N. For any number a of this sequence there is another number b from this sequence, such that GCD (a, b)> 1. Find the minimal N with this condition.

I use this code

for i in range(2, 100000000):
    not_division = 0
    lst = list(range(i, i+17))
    #print(lst)
    for j in lst:
        counter = 0
        for k in lst[1:]:
            if gcd_iterative(j, k) > 1 and gcd_iterative(j, k) != k:
                counter += 1

        if counter == 0:
            not_division += 1
            #print('%s have no delimiter' % j)
    if not_division == 0:
        print('%s SUCCESS' % str(lst))

But there is no sequence. What am I doing wrong?

Solution

I would try to tackle this with a less brute-force approach.

Some thought experiment first. Every other number will have the factor 2 in common. For the remaining 8 or 9, you need more factors. So for example you could have a factor of 3 common to some of them. Then another factor, and so on, e.g.:

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
* 3 * * 3 * * 3 * * 3 * * 3 * * 3
* * * 5 * * * * 5 * * * * 5 * * *
          ^       ^   ^       ^

So now do this in a more systematic way. Consider all prime factors smaller than 17. Try each combination of those, and for each combination each possible offset (but only those with at least 2 occurrences in the sequence). See which of these lead to a situation where every number has at least one partner. Then find the corresponding sequence using the Chinese remainder theorem.

Actually there are only 2 candidates:

 2  *  2  *  2  *  2  *  2  *  2  *  2  *  2  *  2
 3  *  *  3  *  *  3  *  *  3  *  *  3  *  *  3  *
 *  5  *  *  *  *  5  *  *  *  *  5  *  *  *  *  5
 7  *  *  *  *  *  *  7  *  *  *  *  *  *  7  *  *
 *  *  *  *  * 11  *  *  *  *  *  *  *  *  *  * 11
13  *  *  *  *  *  *  *  *  *  *  *  * 13  *  *  *

which is characterized by the first number x satisfying these constraints:

x mod 2 = 0
x mod 3 = 0
x mod 5 = 4
x mod 7 = 0
x mod 11 = 6
x mod 13 = 0
⇒ x mod 30030 = 2184

(computed using Sage function crt) and the mirror image of the above

 2  *  2  *  2  *  2  *  2  *  2  *  2  *  2  *  2
 *  3  *  *  3  *  *  3  *  *  3  *  *  3  *  *  3
 5  *  *  *  *  5  *  *  *  *  5  *  *  *  *  5  *
 *  *  7  *  *  *  *  *  *  7  *  *  *  *  *  *  7
11  *  *  *  *  *  *  *  *  *  * 11  *  *  *  *  *
 *  *  * 13  *  *  *  *  *  *  *  *  *  *  *  * 13

characterized by

y mod 2 = 0
y mod 3 = 1
y mod 5 = 0
y mod 7 = 5
y mod 11 = 0
y mod 13 = 10
⇒ y mod 30030 = 7810

which is greater, so 2184 … 2200 is the first sequence satisfying your requirements:

2184 = 2³ × 3 × 7 × 13
2185 = 5 × 19 × 23
2186 = 2 × 1093
2187 = 3⁷
2188 = 2² × 547
2189 = 11 × 199
2190 = 2 × 3 × 5 × 73
2191 = 7 × 313
2192 = 2⁴ × 137
2193 = 3 × 17 × 43
2194 = 2 × 1097
2195 = 5 × 439
2196 = 2² × 3² × 61
2197 = 13³
2198 = 2 × 7 × 157
2199 = 3 × 733
2200 = 2³ × 5² × 11

Which should be in range for your loop. Actually it should have been enough to loop up to 30030, the product of the primes up to 17. So if your loop really did finish, but miss this sequence, then there must be a mistake somewhere and knowing the sequence might help you debug that.