- 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--- 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 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. >As far as I understand, sieve methods

Correct.

>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

Not exactly.

>list of primes, then you could take a long list of integers and

>trial divide against a list of small primes

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.