Problems & Puzzles: Puzzles

 Puzzle 710 6252893229398 & non-semiprimes The start of a record-breaking run of 173 consecutive integers (6252893229398-6252893229570) that are non-semiprimes. [Luhn] Q1. Can you find a larger record-breaking run?   Note: The real puzzle must take into account an update shown here: http://primes.utm.edu/curios/page.php?short=98189036755454 (Thank to Shyam Sunder Gupta)

Contributions came from Fred Schneider

***

Fred wrote:

It's easy to create a sequence of non-semi-primes of arbitrary length using the
the Chinese Remainder theorem.
Finding the minimum answer is a much more difficult problem.
This approach doesn't look for prime numbers.  It just finds a list of numbers
that is guaranteed to have at least three distinct prime factors.

Set up this system of equations to solve (note: how the consecutive primes are distributed):

0 mod 2 * 3 * 5
1 mod 7 * 11 * 13
2 mod 17 * 19 (already divisible by 2)
3 mod  23 * 29 (already divisible by 3)
4 mod 31 * 37 (already divisible by 2)
5 mod 41 * 43 (already divisible by 5)
6 mod 47       (already divisible by 2 and 3)
ETC

Similarly, you do a construction that found an arbitrary list of numbers where each had more than 10, 1000 or 1000000 distinct prime factors.

...

My idea could be refined quite a bit.  For instance, if the first number is a multiple of 4, it can't be a semi-prime.
Because, it must be 4 multiplied by some other number.  Keeping in mind we can do the following:

0 mod 2*2
1 mod 3*3
2 mod 5    (will be divisible by 2)
3 mod 7 * 11
4 (This  will be divisible by 2*2 and 3)
5 mod 13 * 17
6 mod 19 (this will be divisible by 2)
7 (This will be divisible by 3 and 5)
8 (This will be divisible by 2*2)

I'll try to find some time for this ...

...

Here's a solution for 250:

I created a set of equations and used the Chinese Remainder Theorem to find a set of
250 consecutive numbers that had at all have at least 3 prime factors.

It's a matter of distributing prime numbers along a set of n consecutive numbers and solving for "x" below
(Note how the primes 2 through 13 are distributed below)

x =  0 mod 2^2 (The first number is clearly multiple of 4 and greater than 4 if it's part of this solution set so it can't be a semi-prime).
x = -1 mod 3^2
x = -2 mod 5    (already divisible by 2, just include 5)
x = -3 mod 7^2
x = -4 (This will be divisible by 2^2 * 3, no need for this one to be in set of equations)
x = -5 mod 11^2
x = -6 mod 2 * 13 (already divisible by 2, just include 13)
x = -7 (This will be divisible by 3 * 5, no need for this one to be in set of equations)
x = -8 (This will be divisible by 2^2, no need for this one to be in set of equations)
ETC

-----------------------------------------------

It turned out that I needed to use primes 2 through 503 to create a system of 96 "necessary" equations and used the Chinese Remainder Theorem to find this solution:

x =
145588919617782819139657818570193901796722980344052442144636947492782113921572549361677077492
188414853163677542089291950571255518251205598326362705599991667882891323722551855754824221004
259402021853203720921200613571503408222769230710605591614200274480053946255270147804512543515
89478948
mod
349343760392597571262366683355847121573220014817366177145702534896441672521373733284542872972
190007417288572833315944102555171785806142662807096846939554867417632893214729052233037880772
038023602862340146234777805329509236693224222091230172718951656358062546854265839325382980338
15187220

So, none of the numbers between:
1455889196...89478948
and
1455889196...89479197
are semi-primes.

***

 Records   |  Conjectures  |  Problems  |  Puzzles