## Newly found discovery - neat factorizations

Expand Messages
• 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
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.
• 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
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.
• 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
"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.

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?

--- 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.
• ... 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
>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
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.

> "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.
>
> 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?
>
>
>
>
> --- 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