Results 1 to 12 of 12

Math Help - Just some prime number fun

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2012
    From
    south africa
    Posts
    11

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Just some prime number fun

    Quote Originally Posted by russ123 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2012
    From
    Canada Ontario
    Posts
    43

    Re: Just some prime number fun

    Quote Originally Posted by jamix View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Just some prime number fun

    Quote Originally Posted by Mouhaha View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2012
    From
    south africa
    Posts
    11

    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)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Dec 2012
    From
    Canada Ontario
    Posts
    43

    Re: Just some prime number fun

    What about :
    10-11-12-13-14 ?

    or 11-12-13-14-15?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Dec 2012
    From
    Canada Ontario
    Posts
    43

    Re: Just some prime number fun

    Maybe smallest and shortest list of consecutive numbers
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Just some prime number fun

    Quote Originally Posted by russ123 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2012
    From
    south africa
    Posts
    11

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Dec 2012
    From
    Canada Ontario
    Posts
    43

    Re: Just some prime number fun

    Quote Originally Posted by jamix View Post
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jun 2008
    Posts
    148

    Re: Just some prime number fun

    Quote Originally Posted by Mouhaha View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 11:23 AM
  2. Is this a prime number??
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: April 25th 2011, 09:24 AM
  3. Prime number
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 28th 2009, 10:11 PM
  4. Replies: 1
    Last Post: September 2nd 2009, 08:31 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum