---

Hej

Jeg har en lap papir med en formel, der skulle give alle primtal - og kun
give primtal.
Der er 27 variable, man kan vælge frit, og alle ikke negative
funktionsværdier er primtal.

Desværre har jeg ikke noteret de nærmere kriterier - er der nogen der kender
disse, eller evt. en formel med færre variable.
Er der nogen der også kan oplyse, hvem der har fundet denne lidt
komplicerede formel. Jeg mener, at man startede ude med mange flere variable
omkring 75.

Formlen er :

F(a, b, c, ..., z) =
(k+2)[ 1 - { (wz+h+j-q)^2 + ((gk+2g+k+1)(h+j) + h -z)^2 + (16(k+1)^3 (k+2)
(n+1)^2 + 1 - f^2)^2 + (2n+p+q+z-e)^2 + (e^3 (e+2)(a+1)^2 + 1 - o^2)^2 +
((a^2-1) y^2 + 1 - x^2)^2 + (16 r^2 y^4 (a^2 - 1) + 1 - u^2 )^2 + (((a+ u^2
(u^2-a))^2 -1) (n+4dy)^2 +1 - (x+cu)^2)^2 + ((a^2 -1) L^2 +1 - m^2 )^2 + (ai
+ k + 1 - L - i)^2 + (n + L +v -y)^2 + (p + L (a-n-1) + b (2an + 2a - n^2 -
2n -2) - m)^2 + (q + y(a-p-1) + s(2ap + 2a - p^2 -2p -2) - x)^2 + (z + p L
(a-p) + t (2ap - p^2 - 1) - pm)^2 }]

--
Hilsen
Regnar Simonsen

---

"Regnar Simonsen" <regnar.simo@image.dk> skrev i en meddelelse news:HgmF9.46840$HU.3162643@news010.worldonline.dk...
> Hej
>
> Jeg har en lap papir med en formel, der skulle give alle primtal - og kun
> give primtal.
> Der er 27 variable, man kan vælge frit, og alle ikke negative
> funktionsværdier er primtal.
>
a-z er 26 bogstaver. (k+2)*[et tal] vil aldrig være et primtal.

Mvh
Martin

---

[Martin Larsen]

| a-z er 26 bogstaver. (k+2)*[et tal] vil aldrig være et primtal.

Å jo da! Hvis du ser etter, er eneste mulighet for at [et tal] i
formelen skal være positivt, er at det er = 1. Da kan jo gjerne (k+2)
være prim, hvis k=9 for eksempel.

SA
--
Stein Arild Strømme +47 55584825, +47 95801887
Universitetet i Bergen Fax: +47 55589672
Matematisk institutt www.mi.uib.no/~stromme
Johs Brunsg 12, N-5008 BERGEN stromme@mi.uib.no

---

"Stein A. Stromme" <stromme@mi.uib.no> skrev i en meddelelse news:ww3cpl3a6i.fsf@eliud.mi.uib.no...
> [Martin Larsen]
>
> | a-z er 26 bogstaver. (k+2)*[et tal] vil aldrig være et primtal.
>
> Å jo da! Hvis du ser etter, er eneste mulighet for at [et tal] i
> formelen skal være positivt, er at det er = 1. Da kan jo gjerne (k+2)
> være prim, hvis k=9 for eksempel.
>
Ja , jeg overvejede at skrive undtagelsesvis i stedet for aldrig - men jeg
tænkte at det var der ingen der ville kværulere over. Du kan jo også
finde løsninger med rationelle tal og bla bla.

Mvh
Martin

---

---

Hej

Jeg takker for links, der bekræfter, at formlen for primtal eksisterer og er
lavet at Jones, Sato, Wada og Wiens i 1976.
I artiklen nævnes, at formlen med 26 variable (jeg skrev vist 27) kan
reduceres til en formel med 10 variable (men at denne endnu ikke er fundet).

Men jeg forstår overhovedet ikke formlen.
Der står, at alle ikke negative funktionsværdier er primtal, og at alle
primtal vil kunne udtrykkes som en kombination af de 26 variable.
Alle variable er ikke negative hele tal - det er det, der er mystisk; for
formlen kan skrives :
F(a, b, c, ...z) = (k+2) { 1 - A^2 - B^2 - ... }
Hvis A, B, C osv. er >=1 vil F altid være 0 eller negativ - hvordan kan man
så få en positiv værdi ??

Hvis de variable kan antage ikke negative rationelle værdier (dvs. brøker),
kan jeg godt se nogle muligheder - men det er ikke det der står i artiklen.

Er der i øvrigt nogen, der bare kan finde et eneste primtal med formlen ???

Jeg paster lige formlen fra artiklen igen :

F =
(k+2){1 - [wz + h + j - q]2 - [(gk + 2g + k + 1)(h + j) + h - z]2 -[2n + p
+ q + z - e]2

-[16(k + 1)3(k + 2)(n + 1)2 + 1 - f2]2 - [e3(e + 2)(a + 1)2 + 1 - o2]2 -
[(a2 - 1)y2 + 1 - x2]2


-[16r2y4(a2 - 1) + 1 - u2]2 - [((a + u2(u2 - a))2 - 1) (n + 4dy)2 + 1 - (x +
cu)2]2 - [n + l + v - y]2


-[(a2 - 1)l2 + 1 - m2]2 - [ai + k + 1 - l - i]2 - [p + l(a - n - 1) + b(2an
+ 2a - n2 - 2n - 2) - m]2


-[q + y(a - p - 1) + s(2ap + 2a - p2 - 2p - 2) - x]2 -[z + pl(a - p) +
t(2ap - p2 - 1) - pm]2}


Hilsen
Regnar Simonsen

---

"Regnar Simonsen" <regnar.simo@image.dk> skrev i en meddelelse news:hpwF9.47530$HU.3238532@news010.worldonline.dk...
>
> Alle variable er ikke negative hele tal - det er det, der er mystisk; for
> formlen kan skrives :
> F(a, b, c, ...z) = (k+2) { 1 - A^2 - B^2 - ... }
> Hvis A, B, C osv. er >=1 vil F altid være 0 eller negativ - hvordan kan man
> så få en positiv værdi ??

A^2 etc skal alle være 0.

(Stein var på rette spor)
Mvh
Martin

---

Scripsit "Martin Larsen" <mlarsen@post7.tele.dk>
> "Regnar Simonsen" <regnar.simo@image.dk> skrev

> > Alle variable er ikke negative hele tal - det er det, der er mystisk; for
> > formlen kan skrives :
> > F(a, b, c, ...z) = (k+2) { 1 - A^2 - B^2 - ... }
> > Hvis A, B, C osv. er >=1 vil F altid være 0 eller negativ - hvordan kan man
> > så få en positiv værdi ??

> A^2 etc skal alle være 0.

Aha!

Det vil sige at det "underliggende" indhold i formlen er at man kan
vise at (k+2) er et primtal ved at angive et certifikat bestående af
25 tal a,b,...,j,l,...,z som sammen med k opfylder hver af ligningerne
A=0, B=0,...

Intuitivt må man så forvente at nogen af tallene i certifikatet i
almindelighed er eksponentielt meget større end k.

--
Henning Makholm "Nej, hvor er vi altså heldige! Længe
leve vor Buxgører Sansibar Bastelvel!"

---

Henning Makholm wrote:
>
> > > Alle variable er ikke negative hele tal - det er det, der er mystisk; for
> > > formlen kan skrives :
> > > F(a, b, c, ...z) = (k+2) { 1 - A^2 - B^2 - ... }
> > > Hvis A, B, C osv. er >=1 vil F altid være 0 eller negativ - hvordan kan man
> > > så få en positiv værdi ??
>
> > A^2 etc skal alle være 0.
>
> Aha!
>
> Det vil sige at det "underliggende" indhold i formlen er at man kan
> vise at (k+2) er et primtal ved at angive et certifikat bestående af
> 25 tal a,b,...,j,l,...,z som sammen med k opfylder hver af ligningerne
> A=0, B=0,...

Lige netop. Som Weisstein skriver:

http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

»it is really a set of Diophantine equations in disguise«.

For at skære ud i pap: Polynomiet kan kun give en positiv værdi
hvis indholdet i den store tuborgparentes er +1, hvilket netop
sker hvis alle de firkantede parenteser giver nul. Værdien af
polynomiet er da (k+2)·1=k+2, og k+2 vil da være et primtal. Og
ethvert primtal kan fremkomme på denne måde.

Og åbenbart (som andre har nævnt) kan man nøjes med 9 ubekendte i
stedet for de 25 ubekendte (a til z fraregnet k) der er i formlen.
Det betyder at man kan lave et polynomium i kun 10 variable der har
samme egenskab som det oprindelige polynomium.

En anden taktik er at mindske *graden* af polynomiet, og her mener
jeg at man kan komme ned på et fjerdegradspolynomium. Men så skal
man bruge flere variable end de 26.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

> For at skære ud i pap: Polynomiet kan kun give en positiv værdi
> hvis indholdet i den store tuborgparentes er +1, hvilket netop
> sker hvis alle de firkantede parenteser giver nul. Værdien af
> polynomiet er da (k+2)·1=k+2, og k+2 vil da være et primtal. Og
> ethvert primtal kan fremkomme på denne måde.

Selvfølgelig.

Men er der så nogen, der har fundet bare en kombination af de 25 variable,
som gør A=B=C= ... =0, og derved danner et primtal vha formlen.
Den skal jo immervæk give samtlige primtal, så det skulle vel ikke så svært
at finde bare et !

--
Hilsen
Regnar Simonsen

---

Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>

> En anden taktik er at mindske *graden* af polynomiet, og her mener
> jeg at man kan komme ned på et fjerdegradspolynomium.

Det kan ihvertfald gøres rent systematisk: man indfører en ny variabel
for hvert led i en af de oprindelige ligninger, og så sørger man for
at den får den rigtige værdi ved at lave én hjælpeligning
pr. multiplikation i leddet. Det giver en række andengradsligninger i
en masse variable - når man så kvadrerer hver af dem for at få et
polynomium ender man med fjerde grad.

--
Henning Makholm "That's okay. I'm hoping to convince the
millions of open-minded people like Hrunkner Unnerby."

---

Henning Makholm <henning@makholm.net> writes:

> Det vil sige at det "underliggende" indhold i formlen er at man kan
> vise at (k+2) er et primtal ved at angive et certifikat bestående af
> 25 tal a,b,...,j,l,...,z som sammen med k opfylder hver af ligningerne
> A=0, B=0,...

God pointe.

> Intuitivt må man så forvente at nogen af tallene i certifikatet i
> almindelighed er eksponentielt meget større end k.

Intuitionen lyder rimelig.

Hvis alle tallene i certifikatet var begrænset af et polynomium i k,
så kunne man prøve alle kombinationerne af 25 tal igennem i polynomiel
tid (p(k)^25 * beregningen af den store sum). Det ville placere
Primality-problemet i P, hvor vi indtil nu kun ved at det er i NP (og
coNP).

Men, man kan jo håbe at det er i P :)

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

Lasse Reichstein Nielsen <lrn@hotpop.com> writes:

> Hvis alle tallene i certifikatet var begrænset af et polynomium i k,
> så kunne man prøve alle kombinationerne af 25 tal igennem i polynomiel
> tid (p(k)^25 * beregningen af den store sum). Det ville placere
> Primality-problemet i P, hvor vi indtil nu kun ved at det er i NP (og
> coNP).

I august måned i år, udgav Manindra Agrawal, Neeraj Kayal og Nitin
Saxena en artkel hvor de viser at PRIME faktisk ligger i P.

Jeg fandt artiklen på nettet, men jeg har ikke adressen.

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

Henrik Christian Grove <grove@sslug.dk> writes:

> I august måned i år, udgav Manindra Agrawal, Neeraj Kayal og Nitin
> Saxena en artkel hvor de viser at PRIME faktisk ligger i P.

Whoa. Stort! Tak for det.

> Jeg fandt artiklen på nettet, men jeg har ikke adressen.

Du gav information nok til at det var første hit på google. :)
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

Henrik Christian Grove wrote:
>
> > Hvis alle tallene i certifikatet var begrænset af et polynomium i k,
> > så kunne man prøve alle kombinationerne af 25 tal igennem i polynomiel
> > tid (p(k)^25 * beregningen af den store sum). Det ville placere
> > Primality-problemet i P, hvor vi indtil nu kun ved at det er i NP (og
> > coNP).
>
> I august måned i år, udgav Manindra Agrawal, Neeraj Kayal og Nitin
> Saxena en artkel hvor de viser at PRIME faktisk ligger i P.

Der var jo også en tråd om det her i gruppen:

news:3D5CFE03.ECC48DDD@jeppesn.dk
http://groups.google.com/groups?ie=UTF-8&oe=UTF-8&as_umsgid=3D5CFE03.ECC48DDD%40jeppesn.dk

Men det polynomium vi diskuterer i denne tråd, er vist ganske uegnet til
at finde primtal med. Hvis man bare vælger variablene a til z på må og
få, er det højst usandsynligt at polynomiets værdi bliver positiv.

Men én eller anden kan jo skrive et program der tester om der er nogen
positive værdier når variablene a til z løber mellem fx 0 og 9 (det
giver sølle 10^26 = 100 kvadrillioner værdier at teste).

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen
> Men det polynomium vi diskuterer i denne tråd, er vist ganske uegnet til
> at finde primtal med. Hvis man bare vælger variablene a til z på må og
> få, er det højst usandsynligt at polynomiets værdi bliver positiv.
> Men én eller anden kan jo skrive et program der tester om der er nogen
> positive værdier når variablene a til z løber mellem fx 0 og 9 (det
> giver sølle 10^26 = 100 kvadrillioner værdier at teste).

Så forsrå jeg bedre, at jeg ikke havde bid med de første 3 forsøg. Der er
vist et "bette nøk" endnu

Hilsen
Regnar Simonsen

---

In <Pine.GSO.4.21.0211281249340.28176-100000@dumbo.servers.ima.auc.dk> Michael Vittrup <vittrup@ima.auc.dk> writes:



>On Thu, 28 Nov 2002, Regnar Simonsen wrote:

>>Jeg har en lap papir med en formel, der skulle give alle primtal - og kun
>>give primtal.

>Her er der mere end en lap papir:

>http://www.math.snu.ac.kr/~mhkim/t-unsol.pdf

Jeg syntes jo nok at jeg havde set den formel før.
Keith Devlin: Mathematics: The New Golden Age side 146 og 147

Den er slutningen på et rimeligt spændende kapitel om Hilberts
tiende problem. Matyasevich viste på et tidspunkt at enhver
"listable" mængde har et tilhørende polynomium P med
heltalskoefficienter så et tal tilhører mængden, hvis
den tilhørende ligning P(k,y1,y2,y3,...yn) = 0 har en
heltallig løsning. Da primtallene er en "listable" mængde,
vidste man at der måtte findes et sådant polynomium, men
det tog "a considerable effort" for Jones, Sato, Wada og
Wiens at finde det 25'endegrads polynomium med 26 variable,
Regnar startede den her tråd med.

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:


> Jeg syntes jo nok at jeg havde set den formel før.
> Keith Devlin: Mathematics: The New Golden Age side 146 og 147
>
> Den er slutningen på et rimeligt spændende kapitel om Hilberts
> tiende problem. Matyasevich viste på et tidspunkt at enhver
> "listable" mængde har et tilhørende polynomium P med
> heltalskoefficienter så et tal tilhører mængden, hvis
> den tilhørende ligning P(k,y1,y2,y3,...yn) = 0 har en
> heltallig løsning. Da primtallene er en "listable" mængde,
> vidste man at der måtte findes et sådant polynomium, men
> det tog "a considerable effort" for Jones, Sato, Wada og
> Wiens at finde det 25'endegrads polynomium med 26 variable,
> Regnar startede den her tråd med.

Er "listable" her det samme som "recursively enumerable", "recursive"
eller noget helt andet?

   Torben

---

Torben Ægidius Mogensen wrote:

> Er "listable" her det samme som "recursively enumerable", "recursive"
> eller noget helt andet?

Jeg læser det som "tællelig".

-Claus

---

Claus Rasmussen <clr@cc-consult.dk> writes:

> Torben Ægidius Mogensen wrote:
>
> > Er "listable" her det samme som "recursively enumerable", "recursive"
> > eller noget helt andet?
>
> Jeg læser det som "tællelig".

Det tror jeg ikke på. Hvis der findes et polynomium, der kan afgøre
om et tal er med i en mængde eller ej (via heltallige rødder), så
findes der et program, der kan opremse mængden: Man opremser alle
N-dimensionale heltalsvektorer og tester for hver af dem, om det er en
rod i polynomiet. Dermed er problemet "recursively enumerable". Men
der findes tællelige mængder (f.eks. mængden af terminerende
programmer), som ikke er "recursively enumerable". Så spørgsmålet er
om der findes polynomier for alle "recursively enumerable" mængder,
eller om implikationen kun går den anden vej.

   Torben

---

In <w5y976xe2n.fsf@pc-032.diku.dk> torbenm@diku.dk (Torben Ægidius Mogensen) writes:

>Claus Rasmussen <clr@cc-consult.dk> writes:

>> Torben Ægidius Mogensen wrote:
>>
>> > Er "listable" her det samme som "recursively enumerable", "recursive"
>> > eller noget helt andet?
>>
>> Jeg læser det som "tællelig".

>Det tror jeg ikke på. Hvis der findes et polynomium, der kan afgøre
>om et tal er med i en mængde eller ej (via heltallige rødder), så
>findes der et program, der kan opremse mængden: Man opremser alle
>N-dimensionale heltalsvektorer og tester for hver af dem, om det er en
>rod i polynomiet. Dermed er problemet "recursively enumerable". Men
>der findes tællelige mængder (f.eks. mængden af terminerende
>programmer), som ikke er "recursively enumerable". Så spørgsmålet er
>om der findes polynomier for alle "recursively enumerable" mængder,
>eller om implikationen kun går den anden vej.

>   Torben

"listable" er her synonymt med "effectively enumerable".

http://logic.pdmi.ras.ru/~yumat/Journal/H10history/H10histe.pdf

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

Claus Rasmussen wrote:
>
> > Er "listable" her det samme som "recursively enumerable", "recursive"
> > eller noget helt andet?
>
> Jeg læser det som "tællelig".

Jeg tror det er en egenskab ved visse delmængder af de naturlige tal.
Egenskaben betyder at der eksisterer et polynomium af den diskuterede
slags. På den tidligere refererede side

http://www.math.ucalgary.ca/~jpjones/abst1982.htm

er der noget der hedder »recursively enumerable« (forkortet r.e.), og
mon ikke det er det samme?

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>

[listable]

> Jeg tror det er en egenskab ved visse delmængder af de naturlige tal.
> Egenskaben betyder at der eksisterer et polynomium af den diskuterede
> slags.

Næppe - i så fald ville det resultat af Matyasevich som kai refererede
jo være ganske tomt.

> er der noget der hedder »recursively enumerable« (forkortet r.e.), og
> mon ikke det er det samme?

Jo, det er nok det "listable" er et (lidt utraditionelt) synonym for
her.

En delmængde af N er rekursivt opremselig (r.e.) hvis der findes et
program som (uden nogen inddata) udskriver alle mængdens elementer i
en eller anden rækkefølge (som programmet selv har lov til at
bestemme).

Alternativt: En mængde er r.e. hvis den er enten Ø eller billedmængden
for en eller anden beregnelig (total) funktion fra N til N.

Alternativt²: En mængde er r.e. hvis den er billedmængden for en eller
anden beregnelig partiel funktion fra N til N.

Opgave for den interesserede læser: Vis at de tre definitioner er
ækvivalente.

--
Henning Makholm "Y'know, I don't want to seem like one of those
hackneyed Jews that you see in heartwarming movies.
But at times like this, all I can say is 'Oy, gevalt!'"

---

Scripsit Henning Makholm <henning@makholm.net>

Hovsa:

> Alternativt²: En mængde er r.e. hvis den er billedmængden for en eller
> anden beregnelig partiel funktion fra N til N.

Alternativt³: En mængde er r.e. hvis den er den mængde af inddata for
hvilket et eller andet program standser.

> Opgave for den interesserede læser: Vis at de tre definitioner er
> ækvivalente.

s/tre/fire/

--
Henning Makholm "I didn't even know you *could* kill chocolate ice-cream!"

---

Henning Makholm wrote:

> En delmængde af N er rekursivt opremselig (r.e.) hvis der findes et
> program som (uden nogen inddata) udskriver alle mængdens elementer i
> en eller anden rækkefølge (som programmet selv har lov til at
> bestemme).

Hvad er forskellen på en opremselig mængde og en rekursivt opremselig
mængde ?

-Claus

---

Scripsit Claus Rasmussen <clr@cc-consult.dk>
> Henning Makholm wrote:

> > En delmængde af N er rekursivt opremselig (r.e.) hvis der findes et
> > program som (uden nogen inddata) udskriver alle mængdens elementer i
> > en eller anden rækkefølge (som programmet selv har lov til at
> > bestemme).

> Hvad er forskellen på en opremselig mængde og en rekursivt opremselig
> mængde ?

Jeg tror ikke jeg har set "enumerable" brugt alene. Der er nok for
stor risiko for forvekling med "denumerable", tællelig, som bare
betyder at der findes en eller anden - ikke nødvendigvis beregnelig -
injektiv funktion fra mængden til N.

--
Henning Makholm "... a specialist in the breakaway
oxidation phenomena of certain nuclear reactors."

---

Henning Makholm wrote:
>
> [listable]
>
> > Jeg tror det er en egenskab ved visse delmængder af de naturlige tal.
> > Egenskaben betyder at der eksisterer et polynomium af den diskuterede
> > slags.
>
> Næppe - i så fald ville det resultat af Matyasevich som kai refererede
> jo være ganske tomt.

Jeg ville have skrevet at egenskaben *implicerede* at et sådant poly-
nomium eksisterede, ikke at dette var definitionen.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen wrote:

> Claus Rasmussen wrote:
>>
>>> Er "listable" her det samme som "recursively enumerable", "recursive"
>>> eller noget helt andet?
>>
>> Jeg læser det som "tællelig".
>
> Jeg tror det er en egenskab ved visse delmængder af de naturlige tal.

Ja, det er der begrebet "tællelig" normalt bliver brugt. Men tællelig
er ensbetydende med enumerabel - hvis man kan opremse elementerne i en
mængde, så kan man også tælle dem. Eller hvad ?

-Claus