pythonmath

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:

    (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

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

    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.