# Thread: Just some prime number fun

1. ## Just some prime number fun

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

2. ## 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.

3. ## Re: Just some prime number fun

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?

4. ## Re: Just some prime number fun

Originally Posted by jamix
Define a list of $\displaystyle 2^k$ consecutive integers that has the property that every prime number from $\displaystyle 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 $\displaystyle 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 $\displaystyle 2$ to $\displaystyle 64$ divide into at least one term in the list.
Which number of 143,144,145,146 is divided by 7?

5. ## Re: Just some prime number fun

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.

6. ## 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
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)

7. ## Re: Just some prime number fun

10-11-12-13-14 ?

or 11-12-13-14-15?

8. ## Re: Just some prime number fun

Maybe smallest and shortest list of consecutive numbers

9. ## Re: Just some prime number fun

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

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

Mouhaha

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

10. ## 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.

11. ## Re: Just some prime number fun

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 $\displaystyle 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 $\displaystyle x$ such that $\displaystyle 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

12. ## Re: Just some prime number fun

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