Loading ...
Sorry, an error occurred while loading the content.

Record-setters for prime pair-concatenations of 4 cons. primes

Expand Messages
  • James Merickel
    Hi. This is my first post here. I m inquiring as to whether somebody might want to put a fair amount of power behind a search I m doing. I have the first
    Message 1 of 5 , Feb 5, 2011
    View Source
    • 0 Attachment
      Hi. This is my first post here. I'm inquiring as to whether somebody might want to put a fair amount of power behind a search I'm doing. I have the first cases of 4 consecutive primes such that there are 9 and 10 prime pair-concatenations (out of 12 possible). Using PARI/GP in one window with a program that rules out groupings that won't work on account of divisibility by 3 or 11 and uses the ispseudoprime function on a 2-year-old computer, it will take about a year to rule out 13-digit numbers for the 11/12 case. I will likely put almost all my computer's power behind the search in a month and for a month unless there is someone out there who can speed the search. The 9/12 and 10/12 record-setters have the nice feature that all 5 of the remaining numbers are semiprimes. And the 9/12 case was particularly cute because the 4 primes are of the form 100*Prime+3*prime(i), i=7 to 10. I'd like the 11/12 case just out of silly curiosity. It's possible
      a heuristic argument could be made for it being more-or-less-permanently out of reach, so having that as an alternative would also be satisfactory. If anybody can and wants to help, please let me know.
    • Phil Carmody
      ... Welcome ... Far from unlikely. What you ll probably find is that brain-power will be applied in order to reduce the amount of searching that needs to be
      Message 2 of 5 , Feb 6, 2011
      View Source
      • 0 Attachment
        --- On Sat, 2/5/11, James Merickel <merk7777777@...> wrote:
        > Hi.  This is my first post here.

        Welcome

        > I'm inquiring as to whether somebody might want
        > to put a fair amount of power behind a search I'm
        > doing.

        Far from unlikely. What you'll probably find is that brain-power will be applied in order to reduce the amount of searching that needs to be done.

        > I have the first cases of 4 consecutive primes

        That bit I get; mostly unambiguous, I presume you're hunting for subsequent cases?

        > such that there are 9 and 10 prime pair-concatenations (out
        > of 12 possible).

        That clause made no mention of the 4 consecutive primes, so how does it depend on them?

        Did you mean you are looking for:
        4 consecutive primes such that out of the 12 pairwise concatenations of those primes, 9 or 10 of them are themselves prime.

        > Using PARI/GP in one window with a
        > program that rules out groupings that won't work on account
        > of divisibility by 3 or 11 and uses the ispseudoprime
        > function on a 2-year-old computer, it will take about a year
        > to rule out 13-digit numbers for the 11/12 case. I
        > will likely put almost all my computer's power behind the
        > search in a month and for a month unless there is someone
        > out there who can speed the search.  The 9/12 and 10/12
        > record-setters have the nice feature that all 5 of the
        > remaining numbers are semiprimes. And the 9/12 case
        > was particularly cute because the 4 primes are of the form
        > 100*Prime+3*prime(i), i=7 to 10.  I'd like the 11/12
        > case just out of silly curiosity.  It's possible
        > a heuristic argument could be made for it being
        > more-or-less-permanently out of reach, so having that as an
        > alternative would also be satisfactory.  If anybody can
        > and wants to help, please let me know.

        If it's not impossible modulo small primes, it's almost certainly possible. I see no reason for any small prime to do that. 12 coincidences are fairly easy to find in general.

        If you restrict your search to the >10/12 case then the mod 3 filter will speed things up by a small constant factor, as you're basically looking for 4 consecutive primes with the same residue mod 3, no other combination works.

        Moving to a compiled language rather than GP should speed things up even more. I see no reason why such a search limit shouldn't be more than a week or so, less on a modern machine (which for me is anything less than 5 years old).

        Its entirely possible that this has already been on of Carlos Rivera's Prime Puzzles, so it's worth searching for the results you've already found, to see if anyone's already found them and more.

        Phil
      • thefatphil
        ... Doing both of the above, and starting a search about 10 hours ago on an old machine (a 2GHz G5), has pulled out a bunch of 9/12s already: ?
        Message 3 of 5 , Feb 7, 2011
        View Source
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...> wrote:
          > If you restrict your search to the >10/12 case then the mod 3 filter will speed things up by a small constant factor, as you're basically looking for 4 consecutive primes with the same residue mod 3, no other combination works.
          >
          > Moving to a compiled language rather than GP should speed things up even more. I see no reason why such a search limit shouldn't be more than a week or so, less on a modern machine (which for me is anything less than 5 years old).

          Doing both of the above, and starting a search about 10 hours ago on an old machine (a 2GHz G5), has pulled out a bunch of 9/12s already:

          ? test42(l,p)=local(t=10^l,q);for(i=1,4,for(j=1,4,if(i!=j,q=p[i]*t+p[j];print(i,j," ",q," ",isprime(q)))))
          ? test42(12,[140130997087, 140130997099, 140130997129, 140130997231])
          12 140130997087140130997099 1
          13 140130997087140130997129 1
          14 140130997087140130997231 1
          21 140130997099140130997087 1
          23 140130997099140130997129 1
          24 140130997099140130997231 1
          31 140130997129140130997087 1
          32 140130997129140130997099 0
          34 140130997129140130997231 0
          41 140130997231140130997087 1
          42 140130997231140130997099 1
          43 140130997231140130997129 0
          ? test42(12,[192736714403, 192736714451, 192736714517, 192736714559])
          12 192736714403192736714451 1
          13 192736714403192736714517 1
          14 192736714403192736714559 1
          21 192736714451192736714403 1
          23 192736714451192736714517 0
          24 192736714451192736714559 1
          31 192736714517192736714403 1
          32 192736714517192736714451 1
          34 192736714517192736714559 0
          41 192736714559192736714403 1
          42 192736714559192736714451 1
          43 192736714559192736714517 0
          ? test42(12,[274690345133, 274690345151, 274690345157, 274690345199])
          12 274690345133274690345151 1
          13 274690345133274690345157 1
          14 274690345133274690345199 1
          21 274690345151274690345133 1
          23 274690345151274690345157 0
          24 274690345151274690345199 0
          31 274690345157274690345133 1
          32 274690345157274690345151 1
          34 274690345157274690345199 1
          41 274690345199274690345133 1
          42 274690345199274690345151 1
          43 274690345199274690345157 0
          ? test42(12,[364949489699, 364949489717, 364949489741, 364949489819])
          12 364949489699364949489717 1
          13 364949489699364949489741 1
          14 364949489699364949489819 1
          21 364949489717364949489699 1
          23 364949489717364949489741 0
          24 364949489717364949489819 1
          31 364949489741364949489699 1
          32 364949489741364949489717 0
          34 364949489741364949489819 1
          41 364949489819364949489699 1
          42 364949489819364949489717 0
          43 364949489819364949489741 1
          ? test42(12, [410592133781, 410592133799, 410592133817, 410592133901])
          12 410592133781410592133799 1
          13 410592133781410592133817 0
          14 410592133781410592133901 0
          21 410592133799410592133781 1
          23 410592133799410592133817 1
          24 410592133799410592133901 1
          31 410592133817410592133781 1
          32 410592133817410592133799 1
          34 410592133817410592133901 1
          41 410592133901410592133781 1
          42 410592133901410592133799 1
          43 410592133901410592133817 0
          ? test42(12, [459357247429, 459357247441, 459357247471, 459357247483])
          12 459357247429459357247441 1
          13 459357247429459357247471 1
          14 459357247429459357247483 1
          21 459357247441459357247429 0
          23 459357247441459357247471 1
          24 459357247441459357247483 1
          31 459357247471459357247429 0
          32 459357247471459357247441 1
          34 459357247471459357247483 1
          41 459357247483459357247429 1
          42 459357247483459357247441 1
          43 459357247483459357247471 0

          I see no reason not to continue that until at least the next power of 10. Of course, it'll take quite a hit when it goes beyond that limit, as the density of primes will be measurably lower. I'll see how that affects things before deciding to commit to the next power of 10 after that.

          I can let you have my source code; it's pretty dumb, it just requires C, GMP, and a sieve library with a very simple interface.

          Phil
        • Phil Carmody
          ... Well, another 9 popped out quickly ... ? test42(12, [523545425101, 523545425113, 523545425197, 523545425233]) 12 523545425101523545425113 1 13
          Message 4 of 5 , Feb 7, 2011
          View Source
          • 0 Attachment
            Phil Carmody <thefatphil@...> wrote:
            > I see no reason not to continue that until at least the
            > next power of 10. Of course, it'll take quite a hit when it
            > goes beyond that limit, as the density of primes will be
            > measurably lower. I'll see how that affects things before
            > deciding to commit to the next power of 10 after that.

            Well, another 9 popped out quickly ...
            ? test42(12, [523545425101, 523545425113, 523545425197, 523545425233])
            12 523545425101523545425113 1
            13 523545425101523545425197 0
            14 523545425101523545425233 1
            21 523545425113523545425101 1
            23 523545425113523545425197 1
            24 523545425113523545425233 1
            31 523545425197523545425101 1
            32 523545425197523545425113 0
            34 523545425197523545425233 1
            41 523545425233523545425101 1
            42 523545425233523545425113 1
            43 523545425233523545425197 0

            But even better, a 10 has appeared:
            ? test42(12, [539423223413, 539423223431, 539423223497, 539423223509])
            12 539423223413539423223431 0
            13 539423223413539423223497 1
            14 539423223413539423223509 1
            21 539423223431539423223413 1
            23 539423223431539423223497 1
            24 539423223431539423223509 1
            31 539423223497539423223413 1
            32 539423223497539423223431 1
            34 539423223497539423223509 1
            41 539423223509539423223413 1
            42 539423223509539423223431 0
            43 539423223509539423223497 1

            In theory my search should have found all 10s, what did you find - perhaps my code has bugs if it doesn't find yours.

            Phil
          • Phil Carmody
            [bringing back on-list] ... Excellent. Double-checking is always good for both parties (and third parties who have to trust the results). ... With the current
            Message 5 of 5 , Feb 7, 2011
            View Source
            • 0 Attachment
              [bringing back on-list]

              --- On Mon, 2/7/11, James Merickel <merk7777777@...> wrote:
              > Hi, Phil.  What you have there
              > as the first 10/12 agrees with my curio at Prime Curios.

              Excellent. Double-checking is always good for both parties (and third parties who have to trust the results).

              > I thought the nice first 9/12 I described
              > would have been accepted, but only this 10/12 was. 
              > Your search is clearly around a full order of magnitude
              > faster than mine, and if you restricted it to searching for
              > 11/12 it would be faster still.

              With the current algorithm, there's no direct increase in restricting it to 11/12. I don't do any trial-division, I just test each concatenated number in turn (with GMP, so that it does some trial division). Most of the time it doesn't even get to the 10th number, so stopping once 10 is possible, but 11 is impossible, almost never happens. So no optimisation possible. That's what you get with rushed code using nothing but brute force.

              However, that's because my algorithm's a bit dumb. I should add a pre-sieving stage. If I do that, then firstly it should be a fair bit faster, and secondly capable of the optimisation you mention.

              > Unfortunately, I don't
              > think I have the programming software.  I could perhaps
              > download it to disk at the library in order to install it on
              > my computer, but I'm a little tied up with other things
              > right now. 

              An executable made by me won't help you. I use only linux, and my development machine is a PowerPC. My other development machine is ARM-based. I don't do PeeCees and Windoze at all. However, if I publish the code, others can certainly build it for you. When I last had a windows machine, I seem to remember "cygwin" being pretty handy, perhaps you could install that.

              Phil
            Your message has been successfully submitted and would be delivered to recipients shortly.