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.
ex;
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.
Admittedly I haven't figured out the answer myself yet, but my "knee-jerk" response, is that there must be something wrong with your code......
SOME THOUGHTS........
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?
Thanks for pointing out my mistake. Clearly none as 7 divides 70 + 70 = 140, so the next would be 147.
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)
I don't know python, but upon further thought I believe the answer to be well over 10 million. I don't think it can be found via a "brute-force" search since the number could be very very large......Is your algorithm a brute-force approach (ie checks in ascending order every single set of 8 consecutive integers)???
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
.................................................. ........
Mouhaha
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.
Yes I believe the best method is similar to this, however instead of choosing x and seeing if it has this desired property, we would "create x" via the Chinese Remainder Theorem (CRM), by going through the 8^14 choices we have for picking remainders <- 8 among these 14 primes and then use (CRM) to tell us x.....However as 8^14 > 1 billion, this search would be too time consuming for most programs to complete.
As you you enjoy programming, perhaps you'll enjoy this other prime number problem I'm about to post on the Number Theory forum