Consecutive numbers with counting prime factors
Jens Kruse Andersen
find more interesting.
Find n consecutive numbers with 1,2,...,n prime factors.
The smallest solution for n=3 is 61,62,63.
How big can you make n? You don't have to find the smallest solution.
Do you think there is an upper limit to n?
--
Jens Kruse Andersen
Dave Pettit
Spoiler...
s
p
o
i
l
e
r
s
p
a
c
e
I like this question - I ran a quick Access query and found that there
are 4 solutions for n=4 and the first number coming from the first
1,000 primes. One thing to note is that if the sequence for n=5 is
a1,a2,a3,a4,a5, then we necessarily have that a1>5, so that 2 divides
a2, 3 divides a3, and 4 divides a4. This would mean that a3/3 and
a4/4 would have to be products of two primes, a list of which would be
easy to construct if you already have a table of primes handy... This
also means that a5 is neither divisible by 2 nor 3, so that each of
the 5 prime factors must be 5 or more.
Anyway, the smallest solution I've found for n=4 is
193
194=2*97
195=3*5*13
196=2*2*7*7
Smallest for n=5 (as far I know) is
15121, 15122, 15123, 15124, 15125
I can't find one for n=6 with a1 less than the 10,000th prime.
Dave Pettit
Mark Lewis
> I can't find one for n=6 with a1 less than the 10,000th prime.
838561 = prime(66783)
838562 = 2.419281
838563 = 3.11.25411
838564 = 2.2.29.7229
838565 = 5.7.13.19.97
838566 = 2.3.3.3.53.293
None for n=7 up to 120,000,000
> One thing to note is that if the sequence for n=5 is a1,a2,a3,a4,a5,
> then we necessarily have that a1>5, so that
> 2 divides a2, 3 divides a3, and 4 divides a4.
So need:
(12i+1), 2(6i+1), 3{4i+1}, 2^2{3i+1},
with (prime) and {semiprime}.
--
Mark W. Lewis, North Somerset, UK
Mark Lewis
Looking specifically for numbers based on the LCM(i<=n) series 4->12,
6->60, 7->420, 8->840, 10->2520,... found n=7:
807905281 = prime(41531968)
807905282 = 2.403952641
807905283 = 3.15733.17117
807905284 = 2.2.1871.107951
807905285 = 5.11.43.211.1619
807905286 = 2.3.3.3.37.404357
807905287 = 7.7.7.7.29.41.283
Jens Kruse Andersen
Mark Lewis wrote:
> Looking specifically for numbers based on the LCM(i<=n) series 4->12,
> 6->60, 7->420, 8->840, 10->2520,... found n=7:
>
> 807905281 = prime(41531968)
> 807905282 = 2.403952641
> 807905283 = 3.15733.17117
> 807905284 = 2.2.1871.107951
> 807905285 = 5.11.43.211.1619
> 807905286 = 2.3.3.3.37.404357
> 807905287 = 7.7.7.7.29.41.283
Nice work. I had only searched to 100 million and found solutions up to n=6.
Is there an argument saying the 5th and 7th number are divisible by 5 and 7 or
is this just a guess?
I know I did not demand the smallest solution but anyway: Could there be
smaller solutions without this?
--
Jens Kruse Andersen
Mark Lewis
>> Looking specifically for numbers based on the LCM(i<=n) series
>> 4->12, 6->60, 7->420, 8->840, 10->2520,...
>
> I had only searched to 100 million and found solutions up to n=6.
Here is an n=8:
23066039641 = prime(1011077439) = 27459571.840 + 1
23066039642 = 2.11533019821
23066039643 = 3.3673.2093297
23066039644 = 2.2.317.18190883
23066039645 = 5.11.31.1759.7691
23066039646 = 2.3.3.13.1237.79687
23066039647 = 7.7.7.7.23.47.8887
23066039648 = 2.2.2.2.2.107.619.10883
> Is there an argument saying the 5th and 7th number are divisible by
> 5 and 7 or is this just a guess?
We need a 5 and a 7 somewhere in a sequence of 7+, so I thought they
might as well go at positions 5 and 7, thus I look for solutions
LCM(i<=n).k + i eg 840.k + i for n=8
> I know I did not demand the smallest solution but anyway: Could
> there be smaller solutions without this?
Sure.
Jens Kruse Andersen
> >> Looking specifically for numbers based on the LCM(i<=n) series
> >> 4->12, 6->60, 7->420, 8->840, 10->2520,...
>
> 23066039641 = prime(1011077439) = 27459571.840 + 1
> > Is there an argument saying the 5th and 7th number are divisible by
> > 5 and 7 or is this just a guess?
>
> We need a 5 and a 7 somewhere in a sequence of 7+, so I thought they
> might as well go at positions 5 and 7, thus I look for solutions
> LCM(i<=n).k + i eg 840.k + i for n=8
>
> > I know I did not demand the smallest solution but anyway: Could
> > there be smaller solutions without this?
>
> Sure.
I have made an exhaustive search below 100 billion.
I only list the first number in the solution sequences.
Assuming I have not made errors:
838561 is the smallest solution for n=7.
19896463921 is the smallest solution for n=8.
The smallest prime factor in the 7th term is 13.
Mark Lewis has only searched cases where it is 7 and he found the solution
23066039641.
All solutions below 100 billion for n=8:
19896463921, 23066039641, 43551724441, 44284925161, 66912729241, 72732659161.
No solutions for n=9.
--
Jens Kruse Andersen
Jens Kruse Andersen
> 838561 is the smallest solution for n=7.
The smallest for n=7 is 807905281.
The smallest solutions for n=1,2,3,4,5,6,7,8 begins with:
2, 3, 61, 193, 15121, 838561, 807905281, 19896463921.
Maybe this should be submitted to the On-Line Encyclopedia of Integer
Sequences.
I checked it was not there before my original post.
A solution for n=9 will have to be above 100 billion. I am currently searching
to 1000 billion.
The idea of my exhaustive search algorithm for n=7 and higher is:
The 7th term must be a product of 7 primes greater than 5. Generate all such
products and test if they are a solution for n=7, n=8 and n=9.
--
Jens Kruse Andersen
Jens Kruse Andersen
for n=8, I finally found a solution for n=9 starting at 7262366956993.
There were no solutions below 10^12 so I continued to 10^13. The search is not
complete and there may be smaller solutions above 10^12 - my search algorithm
jumps around.
The prime factorizations are:
7262366956993 = 7262366956993
7262366956994 = 2*3631183478497
7262366956995 = 3*5*484157797133
7262366956996 = 2*2*8663*209580023
7262366956997 = 29*29*439*2767*7109
7262366956998 = 2*3*17*19*4643*807097
7262366956999 = 7*7*11*37*73*283*17627
7262366957000 = 2*2*2*5*5*5*1571*4622767
7262366957001 = 3*3*3*3*13*23*109*233*11807
Note the smallest prime factor in the 5th number is as high as 29.
--
Jens Kruse Andersen
Rainer Rosenthal
Jens Kruse Andersen <jens...@NOSPAMget2net.dk> wrote
>
> 7262366956993 = 7262366956993
> 7262366956994 = 2*3631183478497
> 7262366956995 = 3*5*484157797133
> 7262366956996 = 2*2*8663*209580023
> 7262366956997 = 29*29*439*2767*7109
> 7262366956998 = 2*3*17*19*4643*807097
> 7262366956999 = 7*7*11*37*73*283*17627
> 7262366957000 = 2*2*2*5*5*5*1571*4622767
> 7262366957001 = 3*3*3*3*13*23*109*233*11807
>
> Note the smallest prime factor in the 5th number is as high as 29.
> --
Nice work, the NJAS archive waits for you!
Rainer Rosenthal
r.ros...@web.de
Jens Kruse Andersen
> Jens Kruse Andersen <jens...@NOSPAMget2net.dk> wrote
> >
> > The prime factorizations are:
> > 7262366956993 = 7262366956993
> > 7262366956994 = 2*3631183478497
> > 7262366956995 = 3*5*484157797133
> > 7262366956996 = 2*2*8663*209580023
> > 7262366956997 = 29*29*439*2767*7109
> > 7262366956998 = 2*3*17*19*4643*807097
> > 7262366956999 = 7*7*11*37*73*283*17627
> > 7262366957000 = 2*2*2*5*5*5*1571*4622767
> > 7262366957001 = 3*3*3*3*13*23*109*233*11807
>
Thanks. I don't want to submit the sequence until I know I have found the
smallest solution for n=9. I just found a smaller one:
6793633105561 = 6793633105561
6793633105562 = 2*3396816552781
6793633105563 = 3*3163*715948267
6793633105564 = 2*2*479*3545737529
6793633105565 = 5*19*191*1223*306139
6793633105566 = 2*3*17*563*2297*51503
6793633105567 = 7*7*11*163*179*419*1031
6793633105568 = 2*2*2*2*2*23*937*9851099
6793633105569 = 3*3*3*3*3*131*151*827*1709
Here the nth term is divisible by n.
The exhaustive search below this solution may take another week or more.
--
Jens Kruse Andersen
Rainer Rosenthal
Jens Kruse Andersen <jens...@NOSPAMget2net.dk> wrote
> Here the nth term is divisible by n.
That's funny.
> The exhaustive search below this solution may take
> another week or more.
Good luck. "Or more" means "up to 10^17 weeks" ? :-)
Regards
Rainer Rosenthal
r.ros...@web.de
Jim Dars
"Jens Kruse Andersen" <jens...@NOSPAMget2net.dk> wrote in message
news:sFa09.57$eA1....@news.get2net.dk...
Least there be any doubt, I'm sure most of this board follows your activity
with great interest --- it is exceptional. Jens, there is no other activity
because you're in a league that surpasses the ability of most other mortals.
For definition sake, does a 9 digit sequence contain many 8 digit sequences,
or must an 8 digit sequence be such that it cannot be expanded to 9?
Best wishes, Jim
Jens Kruse Andersen
Jim Dars wrote:
> Least there be any doubt, I'm sure most of this board follows your activity
> with great interest --- it is exceptional. Jens, there is no other activity
> because you're in a league that surpasses the ability of most other mortals.
Thanks, but my search program is really not that efficient. My titanic
semi-prime triplet does not make me a god although I appreciate your worship
:-)
With the encouragement from you and Rainer Rosenthal I will make some
optimizations and go for a solution with 10 numbers when I have the smallest
solution with 9. The current program might use years on n=10, considering it
has found more than 1000 solutions for n=8 but only 2 of them also worked for
n=9. As expected, they did not work for n=10.
Do others want to help and run my optimized and hopefully much faster program
on assigned ranges?
If so, I can probably make a version with an appropriate user interface in a
couple of days.
It will run in a dos-box under Windows.
If you find the first or the smallest n=10 solution with my program, we will
share the credit for the discovery and you will be immortalized - or at the
very least mentioned in the On-Line Encyclopedia of Integer Sequences.
I doubt I can write a program that will find an n=11 solution on current PC's.
There may not even be one with 64-bit numbers and that is what my C program
uses - I don't expect to reach 2^64.
> For definition sake, does a 9 digit sequence contain many 8 digit sequences,
> or must an 8 digit sequence be such that it cannot be expanded to 9?
By definition, any solution for n begins with a solution for all numbers
smaller than n. It usually takes a lot of solutions for n to find one that
also works for n+1.
My guess is however that there will be a smallest solution for n and n+1
simultaneously, i.e. the smallest solution for n can be expanded for some
value of n.
I also guess that there are solutions for all values of n, i.e. the sequence
of smallest solutions is infinite.
Now I only know it starts:
2, 3, 61, 193, 15121, 838561, 807905281, 19896463921, 6793633105561?, ???
The rounded ratio between successive terms is:
2, 20, 3, 78, 55, 963, 25, 341?, ???
--
Jens Kruse Andersen
Rainer Rosenthal
Jens Kruse Andersen <jens...@NOSPAMget2net.dk> wrote
> With the encouragement from you and Rainer Rosenthal
*hehe* but don't blame me, if you get insane :-)
I really wish you best luck and a lot of busy
helpers. May be you ask in sci.math for the help
of Phil Carmody and Jan Kristian Haugland, who
could give some interesting hints to fasten the
search. Please don't count on me - but I surely
appreciate your work and will like to see more
results. But please: it's only a game! Don't get
too excited (see above).
Friendly greetings
Rainer Rosenthal
r.ros...@web.de
Jens Kruse Andersen
The user interface still needs a little work before others can use it.
With the improved program I found the smallest solution for n=9 so far:
3059220303001 = 3059220303001
3059220303002 = 2*1529610151501
3059220303003 = 3*991*1029001111
3059220303004 = 2*2*29*26372588819
3059220303005 = 5*19*283*389*292517
3059220303006 = 2*3*7*151*3067*157279
3059220303007 = 11*17*37*47*79*193*617
3059220303008 = 2*2*2*2*2*109*757*1158613
3059220303009 = 3*3*3*3*3*3*13*157*2056081
3059220303010 = 2*5*388541*787361 :-(
No n=10 solution but that would have required extreme luck.
I have tested all numbers below this with 7 or 11 as a prime factor in the 7th
term.
This means that whatever the smallest solution is, it will not have the nth
term divisible by n.
--
Jens Kruse Andersen
Jens Kruse Andersen
> With the improved program I found the smallest solution for n=9 so far:
> 3059220303001 = 3059220303001
an interest.
I have completed the search to 10^13 without more solutions for n=9. The 3
solutions below 10^13 start at:
3059220303001, 6793633105561, 7262366956993.
I am now searching to 2*10^13 in hope of a solution for n=10 but it will
probably be bigger.
I found a new n=9 solution:
12058367740777 = 12058367740777
12058367740778 = 2*6029183870389
12058367740779 = 3*503*7990966031
12058367740780 = 2*2*5*602918387039
12058367740781 = 79*229*541*1103*1117
12058367740782 = 2*3*11*11*25523*650759
12058367740783 = 7*7*7*13*13*41*5073689
12058367740784 = 2*2*2*2*37*139*233*628921
12058367740785 = 3*3*5*23*29*61*113*167*349
No luck with n=10:
12058367740786 = 2*17*10111*35076439
Note the smallest prime factor is 79 for the 5th number.
The sequence of starting numbers of the smallest solutions for
n=1,2,3,4,5,6,7,8,9 is now complete and I will submit it to the On-Line
Encyclopedia of Integer Sequences. It may take a day or two before it is
accepted but here it is:
2, 3, 61, 193, 15121, 838561, 807905281, 19896463921, 3059220303001
The rounded ratios are:
2, 20, 3, 78, 55, 963, 25, 154
The ratios leading to the smallest solution for an even n is: 2, 3, 55, 25
Leading to odd n: 20, 78, 963, 154
I don't think it is a coincidence that the former are smaller. The nth number
in a solution sequence is even when n is it and there are more combinations
with exactly n prime factors when 2 can be one of them.
The 7th number has the toughest condition: 2, 3 and 5 can not be prime factors
(I use this is in my search).
The ratio to the n=7 solution is also the biggest: 963.
The 10th number can be divisible by 2 but not 2^2 or 3.
My guess is that the ratio to the smallest n=10 solution will be between 25
and 154.
I hope it is lower than this but I doubt it. I will probably need help to find
it in less than a month.
The 11th number in a solution sequence will have the same tough condition as
the 7th and I don't expect to find a solution for n=11. In some years I may
return to the problem with my 200 GHz Pentium IX :-)
"Rainer Rosenthal" wrote:
>*hehe* but don't blame me, if you get insane :-)
I'm not planning to make it my life mission and should I get insane, I will
not blame you - well, insane people are not reasonable, maybe I will anyway
:-)
--
Jens Kruse Andersen
Jens Kruse Andersen
Encyclopedia of Integer Sequences at www.research.att.com/~njas/sequences/
Here is the entry:
ID Number: A072875
Sequence: 2,3,61,193,15121,838561,807905281,19896463921,3059220303001
Name: Smallest start for a run of n consecutive numbers of which the i-th
has exactly i prime factors.
Comments: a(7) found by Mark W. Lewis. a(8) and a(9) found by Jens Kruse
Andersen.
Download search program (see alt.math.recreational thread) to
search for a(10) and be mentioned here.
Links: alt.math.recreational thread, Consecutive numbers with counting
prime factors
Example: a(3)=61 because 61(prime), 62(=2*31), 63(=3*3*7) has exactly
1, 2, 3 prime factors and this is the smallest solution
See also: Cf. A001222.
Keywords: hard,nice,nonn,new
Offset: 1
Author(s): Jens Kruse Andersen (jens...@NOSPAMget2net.dk), Jul 28 2002
I added NOSPAM in this post, my real e-mail is listed. Do spammers scan the
body of posts?
I wrote:
> I am now searching to 2*10^13 in hope of a solution for n=10 but it will
> probably be bigger.
There where 3 solutions for n=9 below 10^13 and 6 more below 2*10^13, but none
for n=10.
I am continuing from 2*10^13 to 5*10^13 along with a helper who requested my
program by e-mail - assuming he is actually running it. If you also want to
help then mail me (remove NOSPAM from address) or post a follow-up. Some
ranges requires a lot of memory, write how much you have available and I will
give you proper command-line parameters for a search assignment.
Sorry but I don't have a homepage, I will e-mail the 37 kB zipped DOS-box
program with instructions - it is easy to use.
--
Jens Kruse Andersen jens...@NOSPAMget2net.dk
Rainer Rosenthal
Jens Kruse Andersen <jens...@NOSPAMget2net.dk> wrote
> 5818684827160441 = 5818684827160441
> 5818684827160442 = 2*2909342413580221
> 5818684827160443 = 3*7*277080229864783
> 5818684827160444 = 2*2*2579*564044671109
> 5818684827160445 = 5*71*73*459421*488723
> 5818684827160446 = 2*3*97*1097*21011*433759
> 5818684827160447 = 11*29*43*47*59*1021*149827
> 5818684827160448 = 2*2*2*2*2*2*2*45458475212191
> 5818684827160449 = 3*3*3*3*3*3*23*80173*4328539
> 5818684827160450 = 2*5*5*7*7*19*19*89*89*830561
>
Very nice indeed.
Congratulations.
Rainer Rosenthal
r.ros...@web.de
Bob Harris
> 5818684827160441 = 5818684827160441
> 5818684827160442 = 2*2909342413580221
> 5818684827160443 = 3*7*277080229864783
> 5818684827160444 = 2*2*2579*564044671109
> 5818684827160445 = 5*71*73*459421*488723
> 5818684827160446 = 2*3*97*1097*21011*433759
> 5818684827160447 = 11*29*43*47*59*1021*149827
> 5818684827160448 = 2*2*2*2*2*2*2*45458475212191
> 5818684827160449 = 3*3*3*3*3*3*23*80173*4328539
> 5818684827160450 = 2*5*5*7*7*19*19*89*89*830561
ioi ioi ioi <---- three cheers for Jens!
> I spent a long time on this so bear with me if I make some possibly boring
> observations on the prime factorizations. ...
Those observations were not boring at all.
Bob H
Jens Kruse Andersen
Jim Dars wrote:
> To say that I'm impressed would be to unstate thens by a degree equal to
> your starting number raised to itself!!
Thanks a lot to Jim Dars, Rainer Rosenthal and Bob Harris.
It is great to have your work appreciated.
--
Jens Kruse Andersen
DIAMOND Mark R.
have you shown your program anywhere?) Since I haven't got the whole thread,
I hope that I'm not merely repeating someone else's hard work. Having read
through Jens observations I wondered if I could formalize at least one of
them. Like I say, someone might already have said this, in which case I
apologise ...
> > The i'th number is not always divisible by i - the 7th number is the
only
> > exception.
>
(a) The first number is obviously prime, so we'll call it P. It must be odd.
(For convenience, I call the consecutive numbers P, Q, R, S ...)
(b) the second number Q is even, and is either of the form 4n or 4n+2. If Q
were 4n = 2.2.n then it would have at least three factors, so it must be of
the form 4n+2 = 2.(2n+1) with 2n+1 a prime.
(c) The third number R could either be 1 mod 3, 2 mod 3 or divisible by
three. If R were 2 mod 3, then P would be 0 mod 3 which is impossible since
P is prime. If R were 1 mod 3, then Q would be 0 mod 3. We already know Q is
0 mod 2, which would make it 0 mod 6, which is impossible because it has
only 2 factors (see b above). So R is 0 mod 3.
(d) The fourth number S = Q+2 which means that it is of the form (4n+2)+2 =
4(n+1)=2.2.(n+1) which is divisible by 4, as observed
(e) The sixth number U (conveniently missing the difficult 5th!) is even and
0 mod 3 (follows from R being 0 mod 3), so U is 0 mod 6 as suspected.
So to summarize, P is prime and congruent to 1 mod 12 (follows from being 1
mod 3 [statement c] and 1 mod 4 [statement b]). 2n+1 as in (b) must be prime
and n+1 must have 2 prime factors ... of which presumably one is equal to 2.
I have no idea whether this makes sieving any easier, but it looks as if it
should. I'm currently playing around with what one can infer about the
status of P mod 5 and 7.
Mark
--
Mark R. Diamond
Phil Carmody
>
> As you may remember, I have been searching for 10 consecutive numbers of which
> the i'th has exactly i prime factors.
> No others ran my program but after numerous optimizations and 2 weeks of
> running, I finally found a 16-digit solution starting at
> 5,818,684,827,160,441.
Hi Jens!
If you'd like to share your source, then maybe I can find someone who'll be prepared to run it for a couple of weeks. (I have called in favours from friends, and many of them quite enjoy running code for me). There seems little reason to write the thing from scratch, and coordination and cooperation will be more fruitful than duplicated effort.
Phil
Jens Kruse Andersen
"DIAMOND Mark R." wrote:
> I've seen this very late, and am *amazed* at Jens success. (By the way Jens,
> have you shown your program anywhere?) Since I haven't got the whole thread,
> I hope that I'm not merely repeating someone else's hard work. Having read
> through Jens observations I wondered if I could formalize at least one of
> them. Like I say, someone might already have said this, in which case I
> apologise ...
Mark Lewis made observations like yours. My search program uses this and more.
The source code looks very messy and I have not made it public. I asked people
to run it to help find the solution with 10 numbers, but nobody ran it. That's
OK, after several optimizations I found the solution on my own and have
received many nice congratulations. The final version could have reached it in
3 days.
> > > The i'th number is not always divisible by i - the 7th number is the
> only
> > > exception.
This is taken out of context and relates to a specific solution. My search was
exhaustive, except for a few numbers I will test later.
> (a) The first number is obviously prime, so we'll call it P. It must be odd.
> (For convenience, I call the consecutive numbers P, Q, R, S ...)
> (b) the second number Q is even, and is either of the form 4n or 4n+2. If Q
> were 4n = 2.2.n then it would have at least three factors, so it must be of
> the form 4n+2 = 2.(2n+1) with 2n+1 a prime.
> (c) The third number R could either be 1 mod 3, 2 mod 3 or divisible by
> three. If R were 2 mod 3, then P would be 0 mod 3 which is impossible since
> P is prime. If R were 1 mod 3, then Q would be 0 mod 3. We already know Q is
> 0 mod 2, which would make it 0 mod 6, which is impossible because it has
> only 2 factors (see b above). So R is 0 mod 3.
> (d) The fourth number S = Q+2 which means that it is of the form (4n+2)+2 =
> 4(n+1)=2.2.(n+1) which is divisible by 4, as observed
> (e) The sixth number U (conveniently missing the difficult 5th!) is even and
> 0 mod 3 (follows from R being 0 mod 3), so U is 0 mod 6 as suspected.
>
> So to summarize, P is prime and congruent to 1 mod 12 (follows from being 1
> mod 3 [statement c] and 1 mod 4 [statement b]). 2n+1 as in (b) must be prime
> and n+1 must have 2 prime factors ... of which presumably one is equal to 2.
I don't see a reason to presume n+1 has 2 as prime factor. Many (most?)
solutions don't have this.
> I have no idea whether this makes sieving any easier, but it looks as if it
> should. I'm currently playing around with what one can infer about the
> status of P mod 5 and 7.
These observations can make sieving a little faster and I did use them.
However it was much more important to eliminate most numbers in advance and
then make an efficient sieve for bigger prime factors of which nothing is
known.
Simply using that n divides every nth number gave me the following form for
the sequence where x+i must have i prime factors:
x+1 = prime
x+2 = 2*prime
x+3 = 3*(2 primes)
x+4 = 2*2*(2 primes), primes<>3
x+5 = (5 primes), primes>=5
x+6 = 2*3*(4 primes), primes=3 or primes>=7
x+7 = (7 primes), primes>=7
x+8 = 2*2*(6 primes), primes<>3
x+9 = 3*(8 primes), primes<>7
x+10= 2*(9 primes), primes>=5
x+11= (11 primes), primes>=7
x+odd is odd and can obviously never have 2 as factor.
Most numbers can be eliminated in advance by first choosing the hardest of the
above conditions for the length of the sequence wanted. Then generate all
possibilities for that number by combining stored primes.
To look for a sequence of length 7, make all products of 7 primes>=7 and then
test the previous 6 conditions.
In my search for 10 consecutive numbers, I think more than 99.9% of the search
space was eliminated by starting with the 10th number equal to 2 times 9
primes>=5.
When sieving you can not only stop if one of the numbers (usually among the
first 4) have too many prime factors. You can also stop as soon as you know
one of the other numbers can't possibly have enough prime factors. Suppose
(x+9)/3 has factor 11 but no other factors below the 7th root of (x+9)/(3*11),
then stop.
Note that to see whether p divides any of the consecutive numbers, only one
modulo computation is needed. The modulo tells which number, if any, is
divisible by p.
I used Borland C++ 5.5 and my tests showed that it made very slow code for
64-bit divisions, which are not part of the IA32 instruction set. A separate
test showed they took 16 times longer than 32-bit divisions so I made a little
inline assembler to use the 64 by 32 bit division (limited to 32 bit result)
which is in IA32. It is amazing what a couple of assembler lines in a critical
place can do for efficiency.
Regardless of my optimizations, 11 consecutive numbers seems out of reach for
my program.
--
Jens Kruse Andersen
Jens Kruse Andersen
I wrote:
> > As you may remember, I have been searching for 10 consecutive numbers of
which
> > the i'th has exactly i prime factors.
> > No others ran my program but after numerous optimizations and 2 weeks of
> > running, I finally found a 16-digit solution starting at
> > 5,818,684,827,160,441.
Phil Carmody wrote:
> If you'd like to share your source, then maybe I can find someone who'll be
prepared to run it for a couple of weeks. (I have called in favours from
friends, and many of them quite enjoy running code for me). There seems little
reason to write the thing from scratch, and coordination and cooperation will
be more fruitful than duplicated effort.
Thanks for the offer but I don't think it is relevant now.
11 numbers seems extremely hard. The 11th number in a sequence must have all
11 prime factors>=7 and such numbers are very rare - the first is 7^11~=2
billion. My program uses 64-bit numbers and I expect the smallest solution
with 11 numbers is above 2^64 ~= 1.8*10^19. It would require a lot of
reprogramming and probably years of cpu-time to find a solution. Unless your
friends happen to have a super-computer, I will pass on this one.
Actually, for a targeted search at 11, the rarity of the 11th number is not so
critical except for the 64-bit limit, as my algorithm in another post may
show. It is more critical that the 10th number is also quite rare since I
can't find a way to "generate" this simultaneously with the 11th.
I have still not confirmed that my 10-number solution is the smallest (I
expect it is). This is a matter of taking time to rewrite some of my program.
It must handle cases where the 10th number has a prime factor above 5*10^8 - I
don't have ram to store more primes simultaneously. When the program is
rewritten, I can test the remaining numbers below the known solution in less
than a day without help.
I don't think there is much point in spending cpu-time computing bigger
solutions for 10 numbers.
--
Jens Kruse Andersen