Note a number with exactly k prime
factors, counting repetitions, is called a k-almost prime. The On-Line
Encyclopedia of Integer Sequences (EIS) has sequences for the start
value in the smallest sets setting a new record for the number of
consecutive k-almost primes for small k. The sequence numbers for k = 3,
4, 5, 6, 7 are A067813 (7), A067814 (15), A067820 (8), A067821 (5),
A067822 (4) with the current record size in parentheses. The theoretical
maximal size for k is 2^k-1 since every 2^k number has k 2's as prime
factors.
1. Can you extend the Tables shown
above?
I have confirmed the existing
values.
I have only found one extension,
for K=6 with repetitions:
The start value in the smallest set
of 6 consecutive 6-almost primes is 4,843,161,124. This beats the EIS
record (A067821).
I found no set of 7 consecutive
7-almost primes below 320 billion. The first set with 5 numbers starts
at 15,605,704,374. The first with 6 numbers starts at 242,576,758,750.
These are both EIS records (A067822). 7 numbers seems considerably
harder but I wanted to find some solution. I used the Miracl big integer
library and searched for a non-minimal set with 6 small chosen prime
factors in each of the 7 numbers. I used modulo arithmetic to ensure
these factors and then trial factored and prp tested the 7 cofactors
until they were simultaneously primes. After 350 million attempts,
around the expectation, I found a solution starting at the 36-digit
6406046204123130430300895880515890624.
With a similar method and 12
billion attempts I found 8 consecutive 8-almost primes with 52 digits
starting at: x = 2964449574354034208097486674428289322182221197109370
The small chosen factors can be
seen in the prime factorizations:
x =
2*5*17^5*208785080071727942186958734184378379103122441
x+1 =
3*11^6*557784833893956461391485940822489191205236737
x+2 =
2^2*19^5*299306446789287727196841349480401361393690357
x+3 =
7^7*3599629374973783042412462584744560177406912811
x+4 =
2*3*13^5*1330687432994981594992582980031174536095132953
x+5 =
5^7*37944954551731637863647829432682103323932431323
x+6 =
2^7*23159762299640892250761614643971010329548603102417
x+7 =
3^7*1355486773824432651164831584100726713389218654371
I have not even attempted to find
the smallest solution. It seems hard.
By the way, I have previously found
the smallest solutions for 5-almost primes for 9, 10, 11, 12 consecutive
numbers: 2674685524, 10077383364, 21117216104, 393370860205. These are
all EIS records (A067820) and I will soon submit them along with the
partial solutions for this puzzle.
I found no extensions to the table
without repetitions.
I tried for K=6 but only found many
sets with 5 consecutive numbers. The smallest starts at 45,212,320,502
and I have searched to 563 billion. I quickly modified an old program
but I am not sure it is exhaustive for this purpose...
One day after he added:
I finally found 6 consecutive numbers with 6 prime
factors, not counting repetitions, starting at 626804494291:
626804494291 = 23*29*83*97*151*773
626804494292 = 2*2*47*59*101*131*4271
626804494293 = 3*61*127*191*337*419
626804494294 = 2*11*19*71*197*107209
626804494295 = 5*7*7*41*79*443*1783
626804494296 = 2*2*2*3*31*37*107*212801
I think this is the smallest solution but don't
guarantee it. When this solution first eluded me, I searched for a
big solution with the same method as I used for 7 7-almost primes and 8
8-almost primes. In a few minutes running I found a 46-digit solution
starting at: 3647131239451640984080894089331004699693395490
I never attempted the smallest solution for K=7.
I only searched for 7 BIG consecutive numbers with
7 prime factors, not counting repetitions. I had bad luck but after 1.87
billion attempts I found a 72-digit solution when I statistically should
have found 3 or 4. It starts at:
x=151993490505870691152585084549639083745786795351538879922474718559486680
I placed all primes below 152 in the prime
factorizations:
x = 2^3*3^2*5*83*89*97*
589227020851740454045942000170414403068805572308690648622811717
x+1 = 7*13*17*61*149*151*
71588229911992679251455843995968200407607018933452288766015757
x+2 = 2*31*37*47*137*139*
74028397744827522773279336715586517697799565324786508237289843
x+3 = 3*19*41*53*127*131*
73759062830373046536742968812696003175519353677408737111229019
x+4 = 2^2*29*43*67*79*101*
57000055171617667420537588018975565411093878996616918313940201
x+5 = 5*11*23*59*71*73*
392917382844295104275200689014375288041229023634459921615246857
x+6 = 2*3*103*107*109*113*
186615535093289321161099939216519567603044070563449505573592333
I will not attempt K=8 without counting
repetitions.
2. Can you find a triplet of
consecutive titanic integers (digits=>1000,
each) all having 3 prime factors,
a) counting repetitions, b) without counting repetitions?
I wanted a simultaneous solution
with and without counting repetitions, i.e. a solution without
repetitions. I found one with 1015 digits: x = 1848973165.....4372465653
I searched solutions on the form: x = a*b*c, x+1 = 2*7*d, x+2 = 3*5*e
Here a, b, c are primes chosen to
ensure:
x+1 has factors 2 and 7. x+2 has
factors 3 and 5.
x+1 and x+2 have no other small
factors (below 810).
x-1 and x+3 have at least 3 small
factors each.
The last is necessary since the
table for K=1 indicates that a solution is not allowed to be extendable
to the previous or next number. I know of no feasible way to determine
whether a titanic composite number is 3-almost prime if zero or one
factor is known.
I first computed sets of probable
primes around 338 digits and then tried different combinations of these
for a, b and c until the cofactors (x+1)/14 and (x+2)/15 were both
probable primes. I used a C program with Miracl and tested 30000 a,b,c
combinations in 80 minutes to find a solution around the expected time:
a = (339 digits chosen to satisfy
modulo conditions) =
1418845789815194177008153943513281697526261316184221913167427349283990\
6460876131870899786524877509789171760202550593485313828967983234288801\
8036966059425501526186690715788522168517373744622106007972312294677483\
0090909674153882439063625059359342071470879614881090597549135091109249\
69460187569862088688412392616783141901416611035121998707653
b = 466*810#*420+1 (338 digits)
c = 1104*810#*420+1 (339 digits)
810# is the product of all primes
below 810.
Primo proved the primes a, b, c, d,
e - actually b and c have easily provable forms but it takes Primo less
than 1 minute.
3. Redo 2 for gigantic integers
(digits=>10000, each).
I have not attempted this.
The probability of a d-digit number
being prime is O(d).
A probabilistic primality test on d
digits takes around O(d^2) time. The complexity of finding two
simultaneous primes around d digits is then
O(d*d*d^2) = O(d^4). A simple
algorithm for the given problem would look for 3 primes and have
complexity O(d^5). A gigantic solution is around 10000 times harder than
a titanic solution with my algorithm. I doubt there is anything
asymptotically faster with currently known methods of finding primes. I
expect it would take me 6 months with some optimizations to my current
program. Efficient trial factoring will only change the constants in the
complexity. Proving the probable primes would take decades with Primo
unless a method to search for solutions with easily provable prime
factors can be found.
I could probably find a 3000-digit
solution in a day or two. I would have if the puzzle asked for it but
not this much bigger.
