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

Newly found discovery - neat factorizations

Expand Messages
  • jbrennen
    After over three days of CPU time, I found the first group of six consecutive integers whose prime factorizations have the same exact pattern of digit lengths
    Message 1 of 4 , Feb 9, 2004
    • 0 Attachment
      After over three days of CPU time, I found the first group of six
      consecutive integers whose prime factorizations have the same exact
      pattern of digit lengths (in base 10, of course).

      That may be a little confusing, so let me give the result, which
      should clear things up a bit:

      853173502025 == 5 * 5 * 13 * 2625149237
      853173502026 == 2 * 3 * 37 * 3843123883
      853173502027 == 7 * 7 * 11 * 1582882193
      853173502028 == 2 * 2 * 29 * 7354943983
      853173502029 == 3 * 3 * 59 * 1606729759
      853173502030 == 2 * 5 * 17 * 5018667659

      Each number is a one-digit-prime times a one-digit-prime times a
      two-digit prime times a ten-digit-prime. The actual pattern is
      not important, just the fact that six consecutive integers all
      share the same pattern.

      Smaller records include:

      (two consecutive numbers)
      2 == 2
      3 == 3

      (three consecutive numbers)
      85 == 5 * 17
      86 == 2 * 43
      87 == 3 * 29

      (four consecutive numbers)
      34172 == 2 * 2 * 8543
      34173 == 3 * 3 * 3797
      34174 == 2 * 7 * 2441
      34175 == 5 * 5 * 1367

      (five consecutive numbers)
      779930 == 2 * 5 * 23 * 3391
      779931 == 3 * 3 * 19 * 4561
      779932 == 2 * 2 * 73 * 2671
      779933 == 7 * 7 * 11 * 1447
      779934 == 2 * 3 * 43 * 3023


      Before somebody attempts to "best" this result by finding a group
      of seven consecutive integers with the same pattern, let me warn
      you... No such group exists. The proof is left to the reader. :)

      If anybody would like to find some more examples of six, perhaps
      to justify inclusion in the OEIS, note that the first integer of
      the six must be congruent to either 3770 or 84425 (mod 88200).
      My crude method of factoring every such group of six completely
      and then testing for compatibility could be greatly improved upon
      by using sieve methods.
    • Ken Davis
      Hi Jack, Interesting. Plus a proof left to the reader that I could actually do for once. Cheers Ken
      Message 2 of 4 , Feb 9, 2004
      • 0 Attachment
        Hi Jack,
        Interesting.
        Plus a "proof left to the reader" that I could actually do for once.
        Cheers
        Ken
        --- In primenumbers@yahoogroups.com, "jbrennen" <jack@b...> wrote:
        > After over three days of CPU time, I found the first group of six
        > consecutive integers whose prime factorizations have the same exact
        > pattern of digit lengths (in base 10, of course).
        >
        > That may be a little confusing, so let me give the result, which
        > should clear things up a bit:
        >
        > 853173502025 == 5 * 5 * 13 * 2625149237
        > 853173502026 == 2 * 3 * 37 * 3843123883
        > 853173502027 == 7 * 7 * 11 * 1582882193
        > 853173502028 == 2 * 2 * 29 * 7354943983
        > 853173502029 == 3 * 3 * 59 * 1606729759
        > 853173502030 == 2 * 5 * 17 * 5018667659
        >
        > Each number is a one-digit-prime times a one-digit-prime times a
        > two-digit prime times a ten-digit-prime. The actual pattern is
        > not important, just the fact that six consecutive integers all
        > share the same pattern.
        >
        > Smaller records include:
        >
        > (two consecutive numbers)
        > 2 == 2
        > 3 == 3
        >
        > (three consecutive numbers)
        > 85 == 5 * 17
        > 86 == 2 * 43
        > 87 == 3 * 29
        >
        > (four consecutive numbers)
        > 34172 == 2 * 2 * 8543
        > 34173 == 3 * 3 * 3797
        > 34174 == 2 * 7 * 2441
        > 34175 == 5 * 5 * 1367
        >
        > (five consecutive numbers)
        > 779930 == 2 * 5 * 23 * 3391
        > 779931 == 3 * 3 * 19 * 4561
        > 779932 == 2 * 2 * 73 * 2671
        > 779933 == 7 * 7 * 11 * 1447
        > 779934 == 2 * 3 * 43 * 3023
        >
        >
        > Before somebody attempts to "best" this result by finding a group
        > of seven consecutive integers with the same pattern, let me warn
        > you... No such group exists. The proof is left to the reader. :)
        >
        > If anybody would like to find some more examples of six, perhaps
        > to justify inclusion in the OEIS, note that the first integer of
        > the six must be congruent to either 3770 or 84425 (mod 88200).
        > My crude method of factoring every such group of six completely
        > and then testing for compatibility could be greatly improved upon
        > by using sieve methods.
      • Adam
        Sieve methods is something that confuses me about many posts to this group. It seems to be thrown around a lot, and sometimes I don t quite get it. As
        Message 3 of 4 , Feb 13, 2004
        • 0 Attachment
          "Sieve methods" is something that confuses me about many posts to
          this group. It seems to be thrown around a lot, and sometimes I
          don't quite "get it." As far as I understand, sieve methods
          generally are used (computationally) to sieve for useful candidates
          in a long list to generate a list of better candidates which are then
          laborously checked. For instance, if you were looking for a long
          list of primes, then you could take a long list of integers and trial
          divide against a list of small primes (e.g., make sure none of the
          numbers are even, divisible by 3, etc.), then PrP them to get a
          smaller list, then finally test for primality.

          What confuses me about this post, and previous ones that refer to
          sieveing, is how do you generate the "sieve concept"? Is there an
          automated process, or do you have figure out specific concepts re:
          sieveing first relevant to the particular problem?

          Adam



          --- In primenumbers@yahoogroups.com, "jbrennen" <jack@b...> wrote:
          > After over three days of CPU time, I found the first group of six
          > consecutive integers whose prime factorizations have the same exact
          > pattern of digit lengths (in base 10, of course).
          >
          > That may be a little confusing, so let me give the result, which
          > should clear things up a bit:
          >
          > 853173502025 == 5 * 5 * 13 * 2625149237
          > 853173502026 == 2 * 3 * 37 * 3843123883
          > 853173502027 == 7 * 7 * 11 * 1582882193
          > 853173502028 == 2 * 2 * 29 * 7354943983
          > 853173502029 == 3 * 3 * 59 * 1606729759
          > 853173502030 == 2 * 5 * 17 * 5018667659
          >
          > Each number is a one-digit-prime times a one-digit-prime times a
          > two-digit prime times a ten-digit-prime. The actual pattern is
          > not important, just the fact that six consecutive integers all
          > share the same pattern.
          >
          > Smaller records include:
          >
          > (two consecutive numbers)
          > 2 == 2
          > 3 == 3
          >
          > (three consecutive numbers)
          > 85 == 5 * 17
          > 86 == 2 * 43
          > 87 == 3 * 29
          >
          > (four consecutive numbers)
          > 34172 == 2 * 2 * 8543
          > 34173 == 3 * 3 * 3797
          > 34174 == 2 * 7 * 2441
          > 34175 == 5 * 5 * 1367
          >
          > (five consecutive numbers)
          > 779930 == 2 * 5 * 23 * 3391
          > 779931 == 3 * 3 * 19 * 4561
          > 779932 == 2 * 2 * 73 * 2671
          > 779933 == 7 * 7 * 11 * 1447
          > 779934 == 2 * 3 * 43 * 3023
          >
          >
          > Before somebody attempts to "best" this result by finding a group
          > of seven consecutive integers with the same pattern, let me warn
          > you... No such group exists. The proof is left to the reader. :)
          >
          > If anybody would like to find some more examples of six, perhaps
          > to justify inclusion in the OEIS, note that the first integer of
          > the six must be congruent to either 3770 or 84425 (mod 88200).
          > My crude method of factoring every such group of six completely
          > and then testing for compatibility could be greatly improved upon
          > by using sieve methods.
        • jim_fougeron
          ... Correct. ... Not exactly. This is the difference between a sieve and an iterative process like you list above (in the original post Jack was using an
          Message 4 of 4 , Feb 13, 2004
          • 0 Attachment
            >As far as I understand, sieve methods
            >generally are used (computationally) to sieve for useful candidates
            >in a long list to generate a list of better candidates which are
            >then laborously checked.

            Correct.

            >For instance, if you were looking for a long
            >list of primes, then you could take a long list of integers and
            >trial divide against a list of small primes

            Not exactly.

            This is the difference between a "sieve" and an iterative process
            like you list above (in the original post Jack was using an iterative
            process and not a sieve).

            In this trivial example, a list of numbers from 10000001 to 11000001
            will be searched for primes.
            Note, 10000001 to 11000001 are frequently MUCH larger, and may be
            certain forms of expressions, patterns, or other groupings which
            have certain arithmetic properties.

            Iterative process:
            Take 10000001 and see if 2, 3, 5, 7, 11, ... divides it. If not,
            then keep it for a longer test.
            Take 10000002 and see if 2, 3, 5, 7, 11, ... divides it. If not,
            then keep it for a longer test.
            Take 10000003 and see if 2, 3, 5, 7, 11, ... divides it. If not,
            then keep it for a longer test.
            ....
            When done, test whatever survived.

            Sieve process:
            Determine that 2 divides 10000001+1.
            Cross out that number, and every other number from that point on.
            Determine that 3 divides 10000001+1.
            Cross out that number and every third number from that point on.
            Determine that 5 divides 10000001+4.
            Cross out that number and every fifth number from that point on.
            ....
            Any value not "crossed-out" is tested.


            The difference between the 2 processes, is that the iterative process
            requires O(X*Y) time, while the sieve requires O(X) time [where X is
            the count of small prime factors, and Y is the number of candidate
            numbers.]


            In the sieve, we are assuming that division is a costly step (it
            is), and that "crossing out" candidates can be done much faster.
            We try to avoid division, by using the fact that if we know that
            N%p is 0, then (N+k*p)%p is also 0. We have thus removed 1/p of
            our candidates, without having to perform Y divisions. If we had
            10 candiates, we would only have to find the "starting" point for
            each factor prime once. If we have 10 million candidates, we still
            only have to find that starting point once. If using iterative
            division, then for 10 candidates, we perform division by a prime 10
            times, and for 10 million candidates, we perform 10 million
            divisions.


            The down side to a sieve, is that finding the starting point, is
            frequently very costly (more costly than divisision usually). Also,
            it is highly likely that there will be NO candidates (left) that have
            a factor of the prime we are searching for. Take for instance, if
            we had 10 canidates to start with. Using a sieve to factor them is
            not very useful. The simple iterative trial division is probably
            much faster in this case. However, if there were 10 million
            starting candidates, then using a sieve (even if the step of finding
            the starting point is 10 times more CPU intensive than a single
            division), is much faster, due to the number of candidates.

            Another "down side", is that not all expression forms "fit" into a
            sieve model. Searches such as the Mersenne prime search,
            unfortunately do not allow for a sieve to be used. Each candidate
            must stand on it's own, due to the types of numbers that divide each
            candidate, and an iterative process must be used. However there are
            many forms where a sieving process can be used.


            Not all "sieves" try to simply eliminate composites.

            In the search Jack listed, you might write a sieve to:

            have X number of "buckets".
            Each bucket capable of holding factors.
            Then perform a sieve where you place a 2 in the bucket #2 #4 #6 ...
            place a 3 in bucket #3 #6 #9 ....
            place a 5 in bucket #5 #10 #15 ...
            (in each step above, you would have to place as many 2's, 3's, or
            other factor as would "fit" into the bucket, i.e. the bucket #24
            would get 3 2's and 1 3)
            When done, throw out any bucket with too few, or too many factors.
            Then search for consecutive buckets.
            Then see if these consecutive bucket have factors of equal size.

            This would be considered a sieve (verses iterative process), due to
            not "trying" to fully work with each candidate number, but
            performing the work on the whole 'set' and then later observing the
            results. Note the above method, while it would work, is far from
            optimal, as it is testing values which could NEVER be a solution
            (note that the first integer of the six must be congruent to either
            3770 or 84425 (mod 88200).) Any sieve would have to work within
            those bounds, or end up being much slower than Jack's "crude" method.

            Jim.

            --- In primenumbers@yahoogroups.com, "Adam" <a_math_guy@y...> wrote:
            > "Sieve methods" is something that confuses me about many posts to
            > this group. It seems to be thrown around a lot, and sometimes I
            > don't quite "get it." As far as I understand, sieve methods
            > generally are used (computationally) to sieve for useful
            candidates
            > in a long list to generate a list of better candidates which are
            then
            > laborously checked. For instance, if you were looking for a long
            > list of primes, then you could take a long list of integers and
            trial
            > divide against a list of small primes (e.g., make sure none of the
            > numbers are even, divisible by 3, etc.), then PrP them to get a
            > smaller list, then finally test for primality.
            >
            > What confuses me about this post, and previous ones that refer to
            > sieveing, is how do you generate the "sieve concept"? Is there an
            > automated process, or do you have figure out specific concepts re:
            > sieveing first relevant to the particular problem?
            >
            > Adam
            >
            >
            >
            > --- In primenumbers@yahoogroups.com, "jbrennen" <jack@b...> wrote:
            > > After over three days of CPU time, I found the first group of six
            > > consecutive integers whose prime factorizations have the same
            exact
            > > pattern of digit lengths (in base 10, of course).
            > >
            > > That may be a little confusing, so let me give the result, which
            > > should clear things up a bit:
            > >
            > > 853173502025 == 5 * 5 * 13 * 2625149237
            > > 853173502026 == 2 * 3 * 37 * 3843123883
            > > 853173502027 == 7 * 7 * 11 * 1582882193
            > > 853173502028 == 2 * 2 * 29 * 7354943983
            > > 853173502029 == 3 * 3 * 59 * 1606729759
            > > 853173502030 == 2 * 5 * 17 * 5018667659
            > >
            > > Each number is a one-digit-prime times a one-digit-prime times a
            > > two-digit prime times a ten-digit-prime. The actual pattern is
            > > not important, just the fact that six consecutive integers all
            > > share the same pattern.
            > >
            > > Smaller records include:
            > >
            > > (two consecutive numbers)
            > > 2 == 2
            > > 3 == 3
            > >
            > > (three consecutive numbers)
            > > 85 == 5 * 17
            > > 86 == 2 * 43
            > > 87 == 3 * 29
            > >
            > > (four consecutive numbers)
            > > 34172 == 2 * 2 * 8543
            > > 34173 == 3 * 3 * 3797
            > > 34174 == 2 * 7 * 2441
            > > 34175 == 5 * 5 * 1367
            > >
            > > (five consecutive numbers)
            > > 779930 == 2 * 5 * 23 * 3391
            > > 779931 == 3 * 3 * 19 * 4561
            > > 779932 == 2 * 2 * 73 * 2671
            > > 779933 == 7 * 7 * 11 * 1447
            > > 779934 == 2 * 3 * 43 * 3023
            > >
            > >
            > > Before somebody attempts to "best" this result by finding a group
            > > of seven consecutive integers with the same pattern, let me warn
            > > you... No such group exists. The proof is left to the
            reader. :)
            > >
            > > If anybody would like to find some more examples of six, perhaps
            > > to justify inclusion in the OEIS, note that the first integer of
            > > the six must be congruent to either 3770 or 84425 (mod 88200).
            > > My crude method of factoring every such group of six completely
            > > and then testing for compatibility could be greatly improved upon
            > > by using sieve methods.
          Your message has been successfully submitted and would be delivered to recipients shortly.