Priemgetal - n - priemgetal

[Onwetend]

het is opzich ook niet wereldschokkend, maar toch leuk.

maargoed welterusten. andere gegadigden kunnen zich melden (bij balie 4)

[JWvdVeer]

Zelf heb ik ook nog maar een stuk code geschreven, deze laat ik vannacht maar even het werk doen:

Code: Selecteer alles

<?php

error_reporting(E_ALL);

ini_set('display_errors', 1);

set_time_limit(3600);

setlocale(LC_TIME, 'Europe/Paris', 'nld');

date_default_timezone_set('Europe/Amsterdam');

$aiPrimes = Array(1, 2, 3);

$iLastPrime = 3;

$iCount = 2;

$iPrimer = 1;

while(true){

var_dump($iCount) & flush();

while($iLastPrime < (2 * $iCount)){

$fSqrt = sqrt(24 * $iPrimer++ + 1); # Voor ieder priemgetal p > 3, bestaat er een natuurlijk getal n zodat p² = 24n + 1.

if(fmod($fSqrt, 1)) continue;

$iCandidatePrime = intval($fSqrt);

if(abs(($iCandidatePrime % 6) - 3) != 2) continue; # Voor ieder priemgetal p > 3, bestaat er een natuurlijk getal n zodat p = 6n ± 1.

if(abs(($iCandidatePrime & 3) - 2) != 1) continue; # Voor ieder priemgetal p > 2, bestaat er een natuurlijk getal n zodat p = 4n ± 1.

$iSqrt = floor(sqrt($iCandidatePrime));

$iIndex = 1;

while($aiPrimes[$iIndex] <= $iSqrt) if(!($iCandidatePrime % $aiPrimes[$iIndex++])) continue 2;

$aiPrimes[] = ($iLastPrime = $iCandidatePrime);

}

$iIndex = count($aiPrimes);

while($aiPrimes[--$iIndex] >= $iCount){

if(in_array((-$aiPrimes[$iIndex] + (2 * $iCount)), $aiPrimes)){

++$iCount;

continue 2;

}

}

var_dump('Geldt niet voor '.$iCount);

break;

}

print_r($aiPrimes);

?>

Dan zie ik morgen wel wat er uit komt .

Gezien de snelheid waarmee het programma draait, vermoed ik dat er vaak per getal meerdere paren zijn. Zoals bijv. het getal 7 de paren (3,11) en (1, 13) heeft. Vandaar dat ik ook steeds sterker begin te vermoeden dat het bewijs ook vrij simplistisch moet zijn (al heb ik er zelf niet over nagedacht)

Het geldt in ieder geval op dit moment tot en met de 25,000. Dus we gaan het zien.

Nu duurt het op mijn laptop ongeveer 40s voor n=5000

In PHP heb ik hem al binnen de 10s zitten. Maar jij hebt er dan ook twee ongelooflijke for-loops inzitten. Mijn code overschrijven naar een andere taal zou waarschijnlijk ook nog veel schelen (is dat ik er op dit tijdstip geen tijd, laat staan zin, meer voor heb).

[ZVdP]

In PHP heb ik hem al binnen de 10s zitten. Maar jij hebt er dan ook twee ongelooflijke for-loops inzitten. Mijn code overschrijven naar een andere taal zou waarschijnlijk ook nog veel schelen (is dat ik er op dit tijdstip geen tijd, laat staan zin, meer voor heb).

Ik heb al een kleine optimalisatie gedaan ondertussen:

Door in mijn code 'limit/3' te vervangen door 'limit/i' wordt de rekentijd nog maar 190ms voor n=5000. En 20s voor n=50000

[JWvdVeer]

Een iets grotere optimalisatie gedaan (omgeschreven naar een andere taal, namelijk C#):

Code: Selecteer alles

/*

 * Gemaakt met SharpDevelop.

 * Gebruiker: Jan Willem

 * Datum: 7-8-2010

 * Tijd: 8:07

 * 

 * Dit sjabloon wijzigen: Extra | Opties |Coderen | Standaard kop bewerken.

 */

using System;

namespace Prime1

{

class Program

{

public static void Main(string[] args)

{

long[] aiPrimes = {1, 2, 3};

long iLastPrime = 3;

long iCount = 1;

long iPrimer = 1;

while(++iCount < (long) Math.Pow(2, 32)){

while(iLastPrime < (2 * iCount)){

double fSqrt = Math.Sqrt(24 * iPrimer++ + 1);

if(Math.IEEERemainder(fSqrt, 1) != 0) continue;

long iCandidatePrime = (long) fSqrt;

if(Math.Abs((sbyte) (iCandidatePrime % 6) - 3) != 2) continue;

if(Math.Abs((sbyte) (iCandidatePrime & 3) - 2) != 1) continue;

long iSqrt = (long) Math.Floor(Math.Sqrt(iCandidatePrime));

long iIndex = 1;

bool bDividable = false;

while(!bDividable && (aiPrimes[iIndex] <= iSqrt)){

if((iCandidatePrime % aiPrimes[iIndex++]) == 0) bDividable = true;

}

if(!bDividable){

iLastPrime = iCandidatePrime;

Array.Resize<long>(ref aiPrimes, aiPrimes.Length + 1);

aiPrimes[aiPrimes.Length - 1] = iLastPrime;

}

}

bool bNotFound = true;

long iPos = (long) aiPrimes.Length;

while(aiPrimes[--iPos] >= iCount){

long iRemainer = (-aiPrimes[iPos] + (2 *  iCount));

for(long iSIndex = 0; (bNotFound && (aiPrimes[iSIndex] <= iRemainer)); iSIndex++){

if(aiPrimes[iSIndex] == iRemainer){

Console.WriteLine(iCount.ToString() + ": " + iRemainer.ToString() + " + " + aiPrimes[iPos].ToString());

bNotFound = false;

}

}

}

if(bNotFound){

Console.WriteLine("Geldt niet voor " + iCount.ToString());

break;

}

}

}

}

}

En als je mij vertrouwd kun je ook de executable downloaden:

primer

(5 KiB) 78 keer gedownload

Je moet alleen de extensie even hernoemen naar .exe (en evt. voor de zekerheid nog virusscannen).

Command-line kun je hem dan uitvoeren als: prime.exe > "C:\prime.txt"

(kun je na afloop het resultaat terughalen).

Hij is iets minder snel dan ZVdP aangeeft, maar dat komt omdat deze oplossing ook dingen weergeeft. Als je zuivere rekentijd gebruikt zal het vergelijkbaar zijn.

[JVV]

Is dit niet hetzelfde als het Goldbach vermoeden? Maar dan anders geformuleerd.

Het vermoeden zegt dat elke even geheel getal groter dan 2 geschreven kan worden als een som van 2 priemgetallen.

Laten we een willekeurig even geheel getal N noemen (groter dan 2). Deze kan geschreven worden als de som van priemgetallen a en b. Daaruit volgt meteen dat;

N/2 precies tussen a en b in ligt.

[mcs51mc]

Is dit niet hetzelfde als het Goldbach vermoeden? Maar dan anders geformuleerd.

Het vermoeden zegt dat elke even geheel getal groter dan 2 geschreven kan worden als een som van 2 priemgetallen.

Laten we een willekeurig even geheel getal N noemen (groter dan 2). Deze kan geschreven worden als de som van priemgetallen a en b. Daaruit volgt meteen dat;

N/2 precies tussen a en b in ligt.

Neen omdat Goldbach enkel over even gehele getallen spreekt.

Onwetend zijn vermoeden is geldig voor alle gehele getallen > 1

Neem even 15, Goldbach zegt niets over 15 daar het oneven is

dan is 15 - 2 = 13 = priemgetal

en is 15 + 2 = 17 = priemgetal

[Rogier]

Ja. Voor mij wel. Maar vermoedelijk geen bewijs wat jullie zullen accepteren. Ik 'geloof' namelijk in een theorie die nogal afwijkt van de geaccepteerde theorieen. en beide onderbouwen elkander, ze passen precies in elkaar. dat is voor mij wel genoeg.

Dat is nu juist het fraaie van wiskunde: de meeste stellingen die waar zijn, kun je gewoon bewijzen, en de meeste stellingen die onwaar zijn kun je falsificeren. Dus geloof is helemaal niet nodig!

[Marko]

Neen omdat Goldbach enkel over even gehele getallen spreekt.

En als je die even getallen door 2 deelt, zoals JVV doet, kom je in de helft van de gevallen uit op een oneven getal.

Onwetend zijn vermoeden is geldig voor alle gehele getallen > 1

Andersom gesteld: Als je die getallen vermenigvuldigt met 2 kom je altijd op een even getal uit, waar het vermoeden van Goldbach voor geldt.

[JVV]

Neen omdat Goldbach enkel over even gehele getallen spreekt.

Onwetend zijn vermoeden is geldig voor alle gehele getallen > 1

Neem even 15, Goldbach zegt niets over 15 daar het oneven is

dan is 15 - 2 = 13 = priemgetal

en is 15 + 2 = 17 = priemgetal

Jawel

Ik zei dat N is even, dan is N/2 even of oneven.

In het voorbeeld van jou;

N/2 = 15

N/2 + 2 = 17

N/2 - 2 = 13

N = 30 = 13 + 17 (goldbach voorbeeld)

Ander voorbeeld;

N/2 = 16

N/2 + 13 = 29

N/2 - 13 = 3

N = 32 = 29 +3 (goldbach voorbeeld)

Ander voorbeeld;

N/2 = 17

N/2 + 12 = 29

N/2 - 12 = 5

N = 34 = 29 + 5 (goldbach voorbeeld)

Etc...

Dus toch het vermoeden van Goldbach

[Onwetend]

En dat vermoeden is nog niet bewezen?

[Rogier]

Het vermoeden van Goldbach is: voor even getallen n (zeg n=2k) bestaan er priemgetallen p en q zodat n=p+q.

De stelling van Onwetend is: voor ieder getal k bestaat er een getal m zodat k-m en k+m beide priem zijn. Dit volgt rechtstreeks uit de stelling van Goldbach met m=k-min(p,q).

Dus Onwetend, we zijn erg nieuwsgierig naar je bewijs!

Laat ik nog wel even de kanttekening maken dat het niet om priemgetallen gaat, maar om niet-deelbare getallen.

Wat is het verschil?

En dat vermoeden is nog niet bewezen?

Klopt!

[Onwetend]

Wat is het verschil?

Het verschil is het getal 1, dat doorgaans niet als priemgetal wordt gezien. Priemgetallen zouden alleen deelbaarzijn door 1 en door zichzelf, wat m.i. niet echt een goed argument is, maar desalniettemin wel de doorgaande wetenschappelijke opvatting.

Dus Onwetend, we zijn erg nieuwsgierig naar je bewijs!

ik zal een poging wagen binnenkort. Als iemand me nou even een goed voorbeeldje kan laten zien van het bewijs van een soortgelijke stelling, dan kan ik het brengen zoals verlangd wordt.

[mcs51mc]

Onwetend:

\(n+k=p1\)

\(n-k=p2\)

Goldbach:

\(p1+p2=N\)

Onwetend in Goldbach:

\(n+k+n-k=N\)

\(2*n=N\)

Eender welk getal n (formulering van Onwetend) maal 2 is een even getal N (formulering Goldbach).

Ander taalkundige formulering is wiskundig eigenlijk hetzelfde.

Onwetend en Goldbach zeggen dus hetzelfde maar een beetje anders

Van een zwart/wit gevlekte koe

zegt Onwetend dat ze wit is met zwarte vlekken terwijl

Goldbach zegt dat ze zwart is met witte vlekken

[Rogier]

ik zal een poging wagen binnenkort. Als iemand me nou even een goed voorbeeldje kan laten zien van het bewijs van een soortgelijke stelling, dan kan ik het brengen zoals verlangd wordt.

Zie bijvoorbeeld dit bewijs (van Euclides) voor het feit dat er oneindig veel priemgetallen zijn:

Beschouw een eindige verzameling van priemgetallen. Vermenigvuldig al deze priemgetallen met elkaar en tel 1 bij dit resultaat op (zie Euclides-getal). Het resulterende getal is nu niet deelbaar door een van de priemgetallen uit de eindige verzameling, waarmee wij begonnen zijn, dit omdat delen door een van deze priemgetallen altijd een rest van 1 geeft. Omdat alle niet-priemgetallen te schrijven zijn als een product van priemgetallen, is ofwel dit resulterende getal zelf een priemgetal ofwel moet er een priemgetal zijn, waardoor het resulterende getal deelbaar is, maar dat niet zit in de oorspronkelijke eindige verzameling van priemgetallen waarmee wij begonnen zijn. Hoe dan ook, is er dus tenminste nog een priemgetal, dat geen deel uitmaakte van de eindige verzameling, waarmee wij begonnen zijn. Dit argument is van toepassing ongeacht de eindige verzameling, waarmee wij deze redenering beginnen. Er bestaan dus altijd meer priemgetallen dan enig gegeven eindig getal.

Ik vrees dat je voor het bewijzen van het vermoeden van Goldbach wel ingewikkeldere "instrumenten" nodig hebt.

Maar enkel een ruwe schets van de gedachtengang die tot een echt bewijs kan leiden is wellicht ook al interessant.

[Harokie]

Joh, laten we er gewoon allen eerst een goede nacht over slapen .

Wellicht dat morgen die stelling er dan gewoon opeens uitrolt

Is het niet gewoon het priem k-tupel vermoeden wat jullie bespreken?

Kijk eens op http://www.kennislink.nl/publicaties/eindeloze-priemen