# Just some prime number fun

• Feb 25th 2013, 06:33 PM
jamix
Just some prime number fun
Define a list of $2^k$ consecutive integers that has the property that every prime number from $2$ 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 $2^4$
(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 $2$ to $64$ divide into at least one term in the list.
• Feb 26th 2013, 12:25 AM
russ123
Re: Just some prime number fun
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.
• Feb 26th 2013, 06:50 AM
jamix
Re: Just some prime number fun
Quote:

Originally Posted by russ123
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.

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?
• Feb 26th 2013, 03:41 PM
Mouhaha
Re: Just some prime number fun
Quote:

Originally Posted by jamix
Define a list of $2^k$ consecutive integers that has the property that every prime number from $2$ 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 $2^4$
(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 $2$ to $64$ divide into at least one term in the list.

Which number of 143,144,145,146 is divided by 7?
• Feb 26th 2013, 07:36 PM
jamix
Re: Just some prime number fun
Quote:

Originally Posted by Mouhaha
Which number of 143,144,145,146 is divided by 7?

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.
• Feb 26th 2013, 10:24 PM
russ123
Re: Just some prime number fun
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)
• Feb 27th 2013, 05:31 AM
Mouhaha
Re: Just some prime number fun
10-11-12-13-14 ?

or 11-12-13-14-15?
• Feb 27th 2013, 05:33 AM
Mouhaha
Re: Just some prime number fun
Maybe smallest and shortest list of consecutive numbers
• Feb 27th 2013, 06:35 AM
jamix
Re: Just some prime number fun
Quote:

Originally Posted by russ123
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 $f(x) = (x)(x+1)(x+2)(x+3)(x+4)(x+5)(x+6)(x+7)$

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 $x$ such that $f(x) \equiv 0 mod (N)$

.................................................. ........

Mouhaha

Your examples have 5 consecutive integers. For order-2, you can only have 4 consecutive integers.
• Feb 27th 2013, 07:25 AM
russ123
Re: Just some prime number fun
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.
• Mar 1st 2013, 08:29 AM
Mouhaha
Re: Just some prime number fun
Quote:

Originally Posted by jamix
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 $f(x) = (x)(x+1)(x+2)(x+3)(x+4)(x+5)(x+6)(x+7)$

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 $x$ such that $f(x) \equiv 0 mod (N)$

.................................................. ........

Mouhaha

Your examples have 5 consecutive integers. For order-2, you can only have 4 consecutive integers.

The best way I think is to solve :
x mod (11)<=8
x mod (13 <=8
x mod (17)<=8
.......
x mod (61)<=8

Look at the sequence 88,89,90,91.
If you take x=92 you will find that :
92 mod (5)=2
92 mod (7)=1
92 mod (11)=4
92 mod (13) =1

all are <=4
• Mar 2nd 2013, 07:38 AM
jamix
Re: Just some prime number fun
Quote:

Originally Posted by Mouhaha
The best way I think is to solve :
x mod (11)<=8
x mod (13 <=8
x mod (17)<=8
.......
x mod (61)<=8

Look at the sequence 88,89,90,91.
If you take x=92 you will find that :
92 mod (5)=2
92 mod (7)=1
92 mod (11)=4
92 mod (13) =1

all are <=4

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 :)