Browse Groups

• Does anyone know of a prime of the form n^4+4 (or of a search for one)? n must be odd, divisible by 5, ... CC
Message 1 of 11 , Jan 26, 2007
View Source
Does anyone know of a prime of the form n^4+4 (or of a search for one)?
n must be odd, divisible by 5, ...

CC
• ... Naive would be: forprime(c=2,LIMIT,forprime(b=2,c,forprime(a=2,b,...))); Either your pseudocode won t find all solutions, or you have some knowledge that
Message 1 of 11 , Jan 27, 2007
View Source
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,...)));

Either your pseudocode won't find all solutions, 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?

(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.
• ... 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
Message 1 of 11 , Jan 28, 2007
View Source
--- 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.
• ... From: thefatphil@yahoo.co.uk To: primenumbers@yahoogroups.com Sent: Sun, 28 Jan 2007 11.45AM Subject: Re: [PrimeNumbers] Re: abc|f(a)f(b)f(c) (was n^4+4)
Message 1 of 11 , Jan 28, 2007
View Source
----Original Message-----
From: thefatphil@...
Sent: Sun, 28 Jan 2007 11.45AM
Subject: Re: [PrimeNumbers] Re: abc|f(a)f(b)f(c) (was n^4+4)
>>, 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).

There is none below 200M (lowest).

-Mike Oakes

PS I posted to this thread a purported proof, via "Reply" on the
primenumbers website, nearly 3 hours ago.
It has neither appeared on the website nor in my inbox.
Don't postings there ever get mailed out to the list??

I now notice that the default recipient for "Reply" is the poster,
rather than the list.
This is odd.

Could you forward my reply of 3 hours ago to the list please, Phil, as
I don't have it any more either?
Thx
• ... n^4+4 = (n^2+2n+2)(n^2-2n+2) so the only possible primes are when either factor is 1, i.e. n=1 Richard
Message 1 of 11 , Jan 29, 2007
View Source
>From: "Chris Caldwell" <caldwell@...>
>Date: Fri, 26 Jan 2007 09:54:53 -0600
>
>Does anyone know of a prime of the form n^4+4 (or of a search for one)?
>n must be odd, divisible by 5, ...
>
>CC

n^4+4 = (n^2+2n+2)(n^2-2n+2) so the only possible primes are when either
factor is 1, i.e. n=1

Richard

_________________________________________________________________
Get Hotmail, News, Sport and Entertainment from MSN on your mobile.
http://www.msn.txt4content.com/
• ... If a,b,c are not required to be primes, then there are many solutions. If a f(a)=931=7^2*19 b=133=7*19 =
Message 1 of 11 , Jan 31, 2007
View Source
--- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...>
wrote:
>
> Let f(x)=x^2-x+1.
> Find 2 triplets, {a,b,c}, of primes
> such that abc|f(a)f(b)f(c).
>

If a,b,c are not required to be primes, then there are many solutions.

If a<b<c, the one with minimum a is:
a=31 => f(a)=931=7^2*19
b=133=7*19 => f(b)=17557=97*181
c=181 => f(c)=32581=31*1051

-Mike Oakes
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.