This felt so much like a projecteuler problem I couldn't resist. I tried it with computer but failed. Searched all numbers up to ten million. Or maybe my code was wrong.
Define a list of consecutive integers that has the property that every prime number from to 2^(2k) divides into some term in the list, a composite list of order k.
The list of integers 143,144,145,146 would be composite list of order 2, since all the prime number up to (ie 2,3,5,7,11,13) divide at least one member of this list.
What is the smallest "composite list of order 3"? ie. Find the smallest 8 consecutive integers, such that all the prime numbers from to divide into at least one term in the list.
1) We need 8 consecutive numbers
2) The primes of interest are 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61. ......
Now any list of 8 consecutive integers is going to contain some that are divisible by 2,3,5 and 7. Thus we only need to consider the 14 primes 11,13,17,19,23,29,31,37,41,43,47,53,59 and 61.........
Another thought is that if "N" is the largest of these 8 consecutive integers, then "N mod (p)" for any of the 14 primes p, must be either 0 or some integer less than 8.
Any thoughts on how the Chinese Remainder Theorem might be used?
I believe the set of integers "88, 89, 90, 91" is an example of a "composite list of order 2". I suspect its the smallest of "order 2" as well, but I haven't checked this.
I didn't really double check or anything. If any of you know python you can look at it if you want.
Code:from time import clock begin = clock() def prime_comp_sieve(upper): """ returns list of len(upper) 0 for prime 1 for composite """ nums = [0 for n in range(upper)] p = 2 while p < int(pow(upper, 0.5) + 1): for d in xrange(p + p, upper, p): nums[d] = 1 while True: p += 1 if not nums[p]: break return nums nums = prime_comp_sieve(10**7) primes = [n for n, x in enumerate(nums[:65]) if x == 0][2:] all_comp_lists = [str(n) + ' ' if x == 1 else '*' for n, x in enumerate(nums)] all_comp_lists = [map(int, sub_list.split()) for sub_list in ''.join(all_comp_lists).split('*')] all_comp_lists = [sub_list for sub_list in all_comp_lists if len(sub_list) >= 8] for comp_list in all_comp_lists: for x in range(len(comp_list) - 7): sub_comp_list = comp_list[x:x+8] found_comp_list = True for p in primes: found_multiple = False for c in sub_comp_list: if c % p == 0: found_multiple = True break if not found_multiple: found_comp_list = False break if found_comp_list: print ','.join(map(str, comp_list)) break if found_comp_list: break print 'completed in: %s seconds' % int(clock() - begin)
One method which is likely to be a little more efficient than a "brute-force" one is to consider the polynomial
Suppose N = 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43 x 47 x 53 x 59 x 61
The question comes down to finding the smallest integer such that
Your examples have 5 consecutive integers. For order-2, you can only have 4 consecutive integers.
Yes it's brute force. It first finds all the sets of consecutive integers below ten million that are greater or equal to 8 in length and are all composite (all_comp_list). Then it goes through each one of the sets in ascending order (comp_list). For each set it considers all subsets of consecutive integers of length 8 in the (sub_comp_list) and checks if all primes up to 64 divide atleast one of the members in the sub_set.
I will think over about the polynomial you showed (should take me some days but I admit that might be a bit over my head. I don't have much math knowledge but hope to learn a bit from here.
As you you enjoy programming, perhaps you'll enjoy this other prime number problem I'm about to post on the Number Theory forum