- View Source--- In primenumbers@yahoogroups.com, <david.broadhurst@...> wrote:>But now, J-L, are you able to explain my comment:

>>> What is remarkable about this exercise is that it can be

>Can you quantify my suprise?

>> solved so quickly. Heuristically, that was not to be expected.

>

>

Well, I would say that for n >= 600, both algebraic factors are more than 415 digits and trial factoring them with pfgw up to 20000000 with -d option you may remove a 20000000-smooth composite factor of say 10 or 15 digits. This leave 2 factors of more than 400 digits. The "probability" for one such factor to be prime is roughly 1/l(10^400), that is about 0.001. So for both factors to be prime the probability is about 0.000001.

Am I right ?

Amicalement,

J-L - View SourceJean-Louis Carton wrote:

> So for both factors to be prime the probability is about 0.000001.

We seek complete factorization of both of the cofactors

25^k-4*5^k-1 and 25^k+4*5^k-1

for some k > 300, where each has more than

400 decimal digits. We had better avoid

the case k = 0 mod 3, where each cofactor

has an algebraic factorization, which is

here a distinct disadvantage.

Suppose that we sieve out primes to depth d

and hope for what is left to yield a

a pair of PRPs as here, with k = 304:

(25^304-4*5^304-1)/(2^2*11*29*1289*1759*9511*27851) is 3-PRP!

(25^304+4*5^304-1)/(2^2*1439*17390951) is 3-PRP!

The probability for success for a single value of k

coprime to 3 is of order

(exp(Euler)*log(p)/log(25))^2/k^2

Setting p = 2*10^7 and summing over /all/ k > 300,

the probability that Exercise 6 has /no/ solution is

exp(-2/3*(exp(Euler)*log(2*10^7)/log(25))^2/301) =~ 83%

In fact it has a solution almost immediately, at k = 304.

David - View Source
On Mon, 9/16/13, djbroadhurst wrote:

--- "djbroadhurst" <d.broadhurst@...> wrote:

> > Exercise 6: Find the complete factorization of F(n) for at

> > least one even integer n > 600.

> As far as I can tell, no-one (apart from the setter)

> yet solved Exercise 6, which can be done in less

> than 2 minutes, using OpenPFGW. What is remarkable

> about this exercise is that it can be solved so

> quickly. Heuristically, that was not to be expected.

But is that more or less remarkable than the expectation of

any one of Phil Taylor's darts landing in the region around

where it actually landed? You only chose that target after

the arrow had landed, I'm sure.

How many mathematical diversions have you looked at

via the medium of numerical computation? How many of

them would you expect to be remarkably easier than

expected to solve? Probably a non-zero answer. Don't

be surprised that one particular example was one.

Knowing what he's trying to say, even if he's not getting

it across clearly,

Phil

--

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani] - View Source
---In primenumbers@yahoogroups.com, <thefatphil@...> wrote:

> You only chose that target after

> the arrow had landed, I'm sure.It happened thus:

1) I determined to factorize F(n)=((n^2-9)/4)^2-5 for

n <= 300, completely. As later shown in "factordb", I succeeded.2) Meanwhile I ran OpenPFGW on n in [301,600], hoping for a

quick outlier and found none.3) I estimated the probability of an easily discoverable

completely factorization for n>600 and found it to be small.4) Recalling how I had once been caught out before by

a "probably no more" heuristic, I set a lone process running on

n in [601, 10000] so as not to be caught out again by Jens.5) When I later looked and pfgw.log, it had found a hit at

n=608.So yes, Phil, you are quite correct that the puzzle was set

after this finding. However the heuristic that I gave was

made prior to my discovery, else I would not have said that

I was surprised.The point that you are making (I think) is that I do such

expsriments often and only notice when the result is unexpected.

I don't tell folk about all the boring times when a negative

heuristic is borne out by a null result. That is the selectioneffect.

David

`(guilty of not boring folk with what is routine)`