 Prime numbers and primality testing

 Restricted Group,
 1109 members
Two large consecutive smooth numbers
Expand Messages
 0 Attachment
N=43623575184339996059537425773119366447006380455838\
696504055889999185302903791148393125043181272726633463298672436846034128
and N+1, both are "smooth", i.e both factor entirely into primes<=9168769.
Can you do better (i.e. make N larger, and the max prime smaller)? 0 Attachment
> N=43623575184339996059537425773119366447006380455838\
Heuristically, log(max_N) is nearly proportional to sqrt(max_prime).
> 696504055889999185302903791148393125043181272726633463298672436846034128
>
> and N+1, both are "smooth", i.e both factor entirely into primes<=9168769.
>
> Can you do better (i.e. make N larger, and the max prime smaller)?
So, with p < 9168769, one can find N with more than 5000 digits.
But that's a hard puzzle, really. An easier puzzle is still to be solved:
http://tech.groups.yahoo.com/group/primenumbers/message/23659> Puzzle: find a chain of 13 consecutive psmooth integers,
Best regards,
> starting at N, with log(N)/log(p) greater than
>
> log(8559986129664)/log(58393) = 2.71328
Andrey 0 Attachment
 On Sat, 3/3/12, WarrenS <warren.wds@...> wrote:> N=43623575184339996059537425773119366447006380455838\
Calling Doctor Broadhurst for suggestion of the best metric by which to evaluate such records. A simple log doesn't necessarily tell the whole tale at all.
> 696504055889999185302903791148393125043181272726633463298672436846034128
>
> and N+1, both are "smooth", i.e both factor entirely into
> primes<=9168769.
Be warned, Warren  Dr. B is sitting on a corpus of algebraic formulae such that p(x) and p(x)+1 have algebraic factorisations, which makes smoothness measurably (I was going to say immeasurably, and then realised the stupidity of such a word choice) more likely.
I'll not play this game, as I have an appointment with 21 farmers in Lithuania (otherwise known as the biggest brewery crawl yet...)
Phil 0 Attachment
 In primenumbers@yahoogroups.com,
Phil Carmody <thefatphil@...> wrote:
> B is sitting on a corpus of algebraic formulae such that p(x)
Those don't seem to be of immediate help, Phil.
> and p(x)+1 have algebraic factorisations
Warren knows about ProuhetTarryEscott and
has set a puzzle that goes deeper than that.
I pass.
David 0 Attachment
 In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:
> Warren knows about ProuhetTarryEscott and
Oh well, I guess that, having been set up by Phil,
> has set a puzzle that goes deeper than that.
>
> I pass.
I ought not to pass. A quick coding of my favourite
PTE identity seemed to leave a significant computational
load for PariGP. I am willing to let that code run
for a few hours, without taking the effort to tune it.
David 0 Attachment
 In primenumbers@yahoogroups.com,
"WarrenS" <warren.wds@...> wrote:
> N=43623575184339996059537425773119366447006380455838\
but might, less coyly and more helpfully, have written
> 696504055889999185302903791148393125043181272726633463298672436846034128
{m=67440294559676054016000;y=1094090867210^2;
N=(y11^4)*(y35^2)*(y47^2)*(y94^2)*(y146^2)*(y148^2)/m1;}
in the more explicit manner of
http://physics.open.ac.uk/~dbroadhu/cpte.pdf
David 0 Attachment
On 3/4/2012 7:59 AM, primenumbers@yahoogroups.com wrote:> 1a. Two large consecutive smooth numbers
e = limit(n> infinity) (1+1/n)^n
> Posted by: "WarrenS"warren.wds@... warren_d_smith31
> Date: Sat Mar 3, 2012 9:19 am ((PST))
>
> N=43623575184339996059537425773119366447006380455838\
> 696504055889999185302903791148393125043181272726633463298672436846034128
>
> and N+1, both are "smooth", i.e both factor entirely into primes<=9168769.
>
> Can you do better (i.e. make N larger, and the max prime smaller)?
>
ln((n+1)/n) = ln(1 + 1/n)
ln( (1+1/n)^n) is, for large n, approximately equal to 1.
ln((1+1/n)^n) = n ln(1+1/n)
ln(1+1/n) = approximately (1/n) for large n.
Find solutions to k1 ln(2) + k2 ln(3) + k3 ln(5) + .... < 1/n for
target large values of n.
Minimize k1 ln(2) + k2 ln(3) + k3 ln(5) + .... where some of the k's
are required to be positive, and some negative.
k1 ln(2) + k2 ln(3) is approximately 0
k1 ln(2) = approximately  k2 ln(3)
k1/k2 = approximately ln(3)/ln(2)
One of k1, k2 is positive. The other is negative.
It seems straight forward to calculate the coefficients k1, k2, ,k3, etc
which minimizes this sum for given sets of primes,
2,3,5,etc.
From that minimum value of the sum for given sets of primes,
calculate n = int(1/minimum) as an upper bound for the n which applies.
Kermit Rose 0 Attachment
On 3/4/2012 7:59 AM, primenumbers@yahoogroups.com wrote:> 1c. Re: Two large consecutive smooth numbers
To construct quadratics,
> Posted by: "Phil Carmody"thefatphil@... thefatphil
> Date: Sat Mar 3, 2012 3:03 pm ((PST))
>
> Calling Doctor Broadhurst for suggestion of the best metric by which to evaluate such records. A simple log doesn't necessarily tell the whole tale at all.
>
> Be warned, Warren  Dr. B is sitting on a corpus of algebraic formulae such that p(x) and p(x)+1 have algebraic factorisations, which makes smoothness measurably (I was going to say immeasurably, and then realised the stupidity of such a word choice) more likely.
>
> I'll not play this game, as I have an appointment with 21 farmers in Lithuania (otherwise known as the biggest brewery crawl yet...)
>
> Phil
x^2  b x + c and x^2  b x + c + 1 which are both factorisable,
we look for integers b, k1, k2 such that
c = k1 * (bk1)
and
c+1 = k2 * (bk2)
1*3 = 3; 2 * 2 = 4
x^2  4 x + 3 = (x1)*(x3)
x^2  4 x + 4 = (x2)^2
2 * 4 = 8; 3 * 3 = 9
x^2  6 x + 8 = (x2)*(x4)
x^2  6 x + 9 = (x3)^2 which is really the same as the first example
translated by 1.
I will guess that maybe the only quadratic polynomial solutions are
translations of the first example.
Cubic polynomial solutions should be more prolific.
Kermit 0 Attachment
Hi kermit,
The quadratic case simply corresponds to a 3tuple
of smooth {Q, Q+1, Q+2} inferring a pair at
{(Q+1)^2  1, (Q+1)^2}
We are aiming for more massive "power boosting".
cf: ProuhetTarryEscott problem.
Warrens SMODA II document has a good list of
known cases for polynomials to orders up to 10,
and I believe he has found pairs using a 12th degree
poly.
Cheers!
________________________________
From: Kermit Rose <kermit@...>
To: primenumbers@yahoogroups.com
Sent: Monday, 5 March 2012, 1:59
Subject: [PrimeNumbers] Re: Two large consecutive smooth numbers
> I will guess that maybe the only quadratic polynomial solutions are
Cubic polynomial solutions should be more prolific.
> translations of the first example.
Kermit
[Nontext portions of this message have been removed] 0 Attachment
Jim White & I have been trying to construct these things because they are grist for my
new factoring algorithm SMODA. That was one example of our output. Although we can break (and have broken) that record, I could only make N have about 30% more digits before
my current program would get very slow or self destruct.
If you have new approaches, and can break that record using them, great.
The PTE approach Broadhurst & Carmody were hinting at, is what I am using now for the
largest ones, so that's not a new idea unless you know something I do not about it.
If you are interested in donating computer time to this effort, intel last 10 years,
unix variant, ok to run weeks at a time in background, then
email warren.wds AT gmail.com.
Thank you. 0 Attachment
 In primenumbers@yahoogroups.com,
"WarrenS" <warren.wds@...> wrote:
> N=43623575184339996059537425773119366447006380455838\
Yes. Let
> 696504055889999185302903791148393125043181272726633463298672436846034128
> and N+1, both are "smooth", i.e both factor entirely into
> primes <= 9168769.
> Can you do better (i.e. make N larger, and the max prime smaller)?
{f(y)=
(y^211^4)*(y^235^2)*(y^247^2)*
(y^294^2)*(y^2146^2)*(y^2148^2)/
67440294559676054016000  1;}
With N = f(1210851834572),
we find that N*(N+1) is 5205793smooth.
With N = f(1606741747790),
we find that N*(N+1) is 8686687smooth.
David 0 Attachment
 In primenumbers@yahoogroups.com,
"WarrenS" <warren.wds@...> wrote:
> Jim White & I have been trying to construct these things
I have not been following this in detail, but I gained the impression
> because they are grist for my new factoring algorithm SMODA.
that Warren's original advert was far too optimistic and that now
his heuristic for oracular factorization has escalated from
exp(log(N)^(1/3+o(1))) to the far less encouraging
exp(log(N)^(2/3+o(1))) as the time to construct a database.
Is this a fair summary of the setback?
David 0 Attachment
 In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:>
well, yes and no. (And it wasn't a "setback" since I knew it all along.)
>
>
>  In primenumbers@yahoogroups.com,
> "WarrenS" <warren.wds@> wrote:
>
> > Jim White & I have been trying to construct these things
> > because they are grist for my new factoring algorithm SMODA.
>
> I have not been following this in detail, but I gained the impression
> that Warren's original advert was far too optimistic and that now
> his heuristic for oracular factorization has escalated from
> exp(log(N)^(1/3+o(1))) to the far less encouraging
> exp(log(N)^(2/3+o(1))) as the time to construct a database.
>
> Is this a fair summary of the setback?
(1) My factorization algorithm SMODA as far as I know still works and still runs in
exp(log(N)^(1/3+o(1))) time PROVIDED database ("oracle") is available for its use.
It is plausibly better under this proviso than quadratic sieve and number field sieve,
but that at present is unconfirmed.
(2) For the problem of computing the database, however, I only have
exp(log(N)^(2/3+o(1))) time algorithms for. However as we just saw, the o(1)
is fairly beneficial, since we can reach at least 400bitlong database entries on a single computer, indeed Broadhurst just found some database entries of that size
in a matter of a few hours  pretty fast turnaround! (His weren't as large as my
best records, but obviously Broadhurst has already built a search code comparable to or better than mine.) In fact I hope to release a preliminary database by me & Jim White, going up to 400bits, in a few more days to interested parties.
(3) You might say that (2) sort of demolishes (1), but that is debatable. The thing is,
the databasebuild is something that all factorers worldwide can do collaboratively and do only once. Therefore, it is not fair to judge this runtime on the same footing as the other runtime. I admit I'm not quite sure how to judge it, because it has been a fairly rare thing
in the world so far, to have oraclealgorithms that actually are useful.
It is conceivable that (2)'s theoretical runtime can be sped up, but at present, I haven't been able to. Furthermore, few or no experts have carefully examined either (1) or (2) yet so it remains possible I'm crazy and the whole thing is broken. I doubt that  I think any remaining errors are minor  I'm just giving you fair warning.
Warren D Smith 0 Attachment
Hard puzzle, really hard puzzle
We know also that, while max N might exist with ~5000
digits, his nearest psmooth neighbour pair might
well be hundreds of digits smaller.
What we don't know is which pairs N are "PTEcompatible",
ie can be found via some factoring
polynomial whose roots are all psmooth.
Any ideas on that issue would be useful
Jim White
________________________________
From: Andrey Kulsha <Andrey_601@...>
To: PrimeNumbers@...
Sent: Sunday, 4 March 2012, 9:53
Subject: Re: [PrimeNumbers] Two large consecutive smooth numbers
Heuristically, log(max_N) is nearly proportional to sqrt(max_prime).
So, with p < 9168769, one can find N with more than 5000 digits.
But that's a hard puzzle, really.
[Nontext portions of this message have been removed] 0 Attachment
Andrey's chain puzzle is interesting. Could it be
he already has found the maximum possible result
for chain length 13?
It's hard to see how that result can be beaten.
Some results with weights of 2.2 or more:
28246112570058, weight = 2.2053 (P = 1257251)
18911412089528, weight = 2.2077 (P = 1032307)
218381019281507, weight = 2.2410 (P = 2504167)
9288363679368, weight = 2.2480 (P = 587149)
3393509932556102, weight = 2.2536 (P = 7788997)
4532039198639948, weight = 2.2536 (P = 8856259)
4532039198639949, weight = 2.2536 (P = 8856259)
12469670986534198, weight = 2.2547 (P = 13762769)
10160468895884110, weight = 2.2592 (P = 12163843)
461881571558141, weight = 2.2615 (P = 3050603)
7909529450841510, weight = 2.2621 (P = 10669823)
211814723372355, weight = 2.2918 (P = 1782043)
430753934627814, weight = 2.4217 (P = 1103933)
Perhaps the 14chain at N = 4532039198639948 might
be a good result? What are the best known results
for 14 or longer chains?
________________________________
From: Andrey Kulsha <Andrey_601@...>
To: PrimeNumbers@...
Sent: Sunday, 4 March 2012, 9:53
Subject: Re: [PrimeNumbers] Two large consecutive smooth numbers
> Puzzle: find a chain of 13 consecutive psmooth integers,
Best regards,
> starting at N, with log(N)/log(p) greater than
>
> log(8559986129664)/log(58393) = 2.71328
Andrey
[Nontext portions of this message have been removed] 0 Attachment
> Andrey's chain puzzle is interesting. Could it
No, I think that log/log ratio has no limit.
> be he already has found the maximum possible
> result for chain length 13?
> Perhaps the 14chain at N = 4532039198639948
Brute force search yielded:
> might be a good result? What are the best known
> results for 14 or longer chains?
N = 505756884840 for 14chain
N = 285377140980 for 15chain
N = 32290958458 for 16chain
as listed in http://www.primefan.ru/stuff/math/maxs.xls
(there k+1 is chain length)
Best regards,
Andrey 0 Attachment
Andrey,
I can't use that file, I don't have XL. Any chance
of a text export? eg commaseparated fields
________________________________
From: Andrey Kulsha <Andrey_601@...>
To: PrimeNumbers@...
Sent: Tuesday, 6 March 2012, 6:28
Subject: [PrimeNumbers] Re: 13chains of consecutive smooth numbers
> Andrey's chain puzzle is interesting. Could it
No, I think that log/log ratio has no limit.
> be he already has found the maximum possible
> result for chain length 13?
> Perhaps the 14chain at N = 4532039198639948
Brute force search yielded:
> might be a good result? What are the best known
> results for 14 or longer chains?
N = 505756884840 for 14chain
N = 285377140980 for 15chain
N = 32290958458 for 16chain
as listed in http://www.primefan.ru/stuff/math/maxs.xls
(there k+1 is chain length)
Best regards,
Andrey
[Nontext portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.