--- Jack Brennen <

jb@...> wrote:

> Phil Carmody wrote:

> > Is this not entirely naive?

> >

> > Pseudocode:

> > Fix a.

> > Find all values for wlog b such that b|f(a)

> > For each one find all values of wlog c such that c|f(b)

> > Check if a|f(c)

> > If so, you're done.

>

> Naive would be:

>

> forprime(c=2,LIMIT,forprime(b=2,c,forprime(a=2,b,...)));

I can do more naive than that:

for(c=2,LIMIT,isp=1;for(d=1,sqrt(c),if(c%d==0,isp=0;break));if(isp,...)

I don't think my script used anything more smart than the knowledge that f(x)

was a cyclotomic polynomial, so that factors were 6n+1. However, it would only

be 2x slower if it didn't assume that; and 2x 0s is 0s. Everything else was

straight out of the problem definition, modulo the assumption you mention

below.

> Either your pseudocode won't find all solutions

That's one of the things that makes it naive. It only looks for the 3-way

cyclic relationship of factors.

>, or you

> have some knowledge that there exists no pair (x,y) with:

>

> x|f(y) AND y|f(x)

>

> Is that known, or easy to prove?

I know off-hand of neither examples, nor a reason why they shouldn't exist.

A naive script found none below a million (lowest).

I guess that this 2-way relation will be much easier to take mathematics to

than the 3-way, so perhaps a proof exists if someone, off-list lurkers

included, is prepared to look for it.

I suspect if any proof exists, then a reductio ad absurdam one exists.

Wild Wild Handwaving follows:

Assume:

<a,b> is a solution, meaning

(P1) a | b^2-b+1

(P2) b | a^2-a+1

(P3) a<b, a minimal, b minimal for that a

Deduce:

(D1 from P1) kb = a^2-a+1

(D2 from D1) b = (a^2-a+1)/k

(D3 from D2) a | 1/k^2*a^4 - 2/k^2*a^3 + ((3-k)/k^2)*a^2 + ((k-2)/k^2)*a +

((k^2-k+1)/k^2)

(D4 from D3) a | a^4 - 2*a^3 + (3-k)*a^2 + (k-2)*a + (k^2-k+1)

(D5 from D4) a | k^2-k+1

(D6 from D1) k | a^2-a+1

(D7 from D1) kb < a^2

(D8 from D7,P3) k < a

(D9) So <k,a> is a solution violating the minimality of a.

Therefore our assumptions were false.

Quod Erat Demolition.

> (Although absent such knowledge, fixing your pseudocode to

> check for such cases would be easy.)

>

> Comparing the top-down to bottom-up search method... I guess

> I liked the top-down because it doesn't require factoring, only

> modular square roots modulo a prime. I suppose that if one were

> searching for solutions with ~200 digits, top-down might be the

> best way to make progress. But in the range where the one known

> solution falls, the bottom-up method is probably the better way.

The roots only method has merit certainly.

Bottom up, it might be possible to limit factorisation by some bound, I don't

know. For an exhaustive search, the second term should be trivial to factor,

but the third might take many seconds. Not good if you want to do millions.

So, have you found a 2nd answer yet ;-)

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________

Food fight? Enjoy some healthy debate

in the Yahoo! Answers Food & Drink Q&A.

http://answers.yahoo.com/dir/?link=list&sid=396545367