Suurta alkulukua etsimään

[Harrastelija]

Haastan kaikki ohjelmoijat itse tehdyllä ohjelmalla löytämään ison alkuluvun. Itse löysin alkuluvun 2249999999999999981

Ensin Erasthoneen seulalla tein totuusarvoisen taulukon 1.5 miljardia pienemmistä alkuluvuista ja sen taulukon avulla tutkin lukuja 1.5*1.5 miljardista alaspäin.

Koodi: Valitse kaikki

Program Alkuluku;
uses math,sysutils,DateUtils,bigdecimalmath;
CONST maxind = 1500000000; {lasketaan 1,5 miljardia pienemmät alkuluvut}
VAR	  taulukko	: ARRAY[1..maxind] OF BOOLEAN;

	lkm, luku:	qword;	
	ind:	longint;
	neliojuuri	:	Float;
	ehdokas,apuri: qword;
function onalkuluku(luku:qword):boolean;
var indeksi: Longword;
	onse: boolean;
begin
	if (luku mod 2) = 0 then onse:=false else
		begin
			indeksi:=3;
			onse:=true;
			while (indeksi <= Sqrt(luku)) and (onse=true) do
				begin
					if taulukko[indeksi] then
					begin
						if (luku mod indeksi) = 0 then 
							begin onse:=false; 
							writeln(indeksi); 
						end;
					end;	
					indeksi:=indeksi+2;
			end;
		end;
	onalkuluku:=onse;
end;
begin
	lkm:=maxind;
	neliojuuri:= Sqrt(lkm);
	for ind:=2 to maxind do taulukko[ind]:=true; {oletetaan kaikki alkuluvuiksi}
	taulukko[1]:= false;
	luku:=2;
	ind:=luku;
	while ind<=lkm do {poistetaan 2:n monikerrat}
		begin
			taulukko[ind]:= false; 
			ind:=ind+2; 
		end;
	while (luku < neliojuuri) do
		begin
			while (taulukko[luku] = false) and (luku < neliojuuri) do 
			{etsitään seuraava alkuluku}
				luku:=luku + 1;
			ind:=luku + luku;
			while ind < lkm do {poistetaan sen monikerrat}
				begin
					taulukko[ind]:= false;
					ind:=ind+luku;
				end;
			luku:= luku + 1;
		end;
	taulukko[2]:= true;
	{Nyt on taulukoitu miljardia pienemmät alkuluvut. 
	 Tulostetaan sataa pienemmät kokeeksi.}
	for ind:=1 to 100 do 
			if taulukko[ind]=true then writeln (ind);
	//Tutkitaan ehdokaslukuja
	apuri:=1;
	while apuri < 100 do
		begin
			ehdokas:=maxind*maxind-apuri;
			if onalkuluku(ehdokas) then 
				begin
					writeln(ehdokas,' on alkuluku.') 
				end	
					else writeln(ehdokas,' ei ole alkuluku.');
			apuri:=apuri+2;
		end;
end.

[Eusa]

753791360294117621597426470588235616628676470588233478500000000000003833.

Siinäpä esimerkki.

[Harrastelija]

Mikäli ao. koodini toimisi oikein, niin sain selville, että Mersennen luku 2^1499997953 - 1 on alkuluku. Mersennen lukujen, jotka ovat muotoa 2^p-1, alkuluvullisuutta tutkitaan niin sanotulla Lucas Lehmerin testillä. En kuitenkaan luule, että koodini toimisi oikein, sillä vuonna 2016 suurin tunnettu alkuluku oli 2^74207281-1.

Mutta en tiedä mitä siinä on väärin - se toimii ainakin pienillä luvuilla.

Koodi: Valitse kaikki

Program Alkuluku;
uses math,sysutils,DateUtils,bigdecimalmath;
CONST maxind = 1500000000; {lasketaan 1,5 miljardia pienemmät alkuluvut}
VAR	  taulukko	: ARRAY[1..maxind] OF BOOLEAN;
	lkm, luku:	qword;
	ind:	longint;
	neliojuuri	:	Float;
function LucasLehmerTest(p: Integer): Boolean;
var
  s, mersenne: Int64;
  i: Integer;
begin
  if p = 2 then
  begin
    LucasLehmerTest := True;
    Exit;
  end;
  s := 4;
  mersenne := Int64(1) shl p - 1;
  for i := 3 to p do
    s := (s * s - 2) mod mersenne;
  LucasLehmerTest := s = 0;
end;

procedure tulostaMersenne(pot: Int64);
var tulostaluku: bigdecimal;
	indeksi: Int64;
begin
	tulostaluku:=2;
	indeksi:=1;
	while indeksi < pot do
		begin
			tulostaluku:=tulostaluku*2;
			indeksi:=indeksi+1;
		end;
	tulostaluku:=tulostaluku-1;
	writeln(BigDecimalToStr(tulostaluku));
end;


begin
	lkm:=maxind;
	neliojuuri:= Sqrt(lkm);
	for ind:=2 to maxind do taulukko[ind]:=true; {oletetaan kaikki alkuluvuiksi}
	taulukko[1]:= false;
	luku:=2;
	ind:=luku;
	while ind<=lkm do {poistetaan 2:n monikerrat}
		begin
			taulukko[ind]:= false;
			ind:=ind+2;
		end;
	while (luku < neliojuuri) do
		begin
			while (taulukko[luku] = false) and (luku < neliojuuri) do
			{etsitään seuraava alkuluku}
				luku:=luku + 1;
			ind:=luku + luku;
			while ind < lkm do {poistetaan sen monikerrat}
				begin
					taulukko[ind]:= false;
					ind:=ind+luku;
				end;
			luku:= luku + 1;
		end;
	taulukko[2]:= true;
	writeln('Taulukko valmis');
	//Nyt on taulukoitu 1.5 miljardia pienemmät alkuluvut.
	for ind:=(maxind-3000) to maxind do //tutkitaan lukuja 2^alkuluku LucasLehmerin testillä.
		if taulukko[ind] then
			begin
				if LucasLehmerTest(ind) then
					begin
				    	Writeln('2^', ind, ' - 1 on alkuluku.');
				    	tulostaMersenne(ind);
				    end;
			end;
end.

[Harrastelija]

753791360294117621597426470588235616628676470588233478500000000000003833.

Siinäpä esimerkki.

Koodi näytille!

[HuuHaata]

Onko olemassa todistus, jonka mukaan ei voi löytää mielivaltaisen suurta alkulukua osoittamalla, että sen täytyy sellainen olla? Vai eikö tuollaista osoittamista voi syystä x tehdä, ja tuollaisia "helppoja" alkulukuja ei ole.

Kysymys täysin miettimättä. Voisi tietysti jaksaa aloittaa GPT:llä.

[Harrastelija]

En ihan ymmärrä kysymystäsi, mutta eikö siitä, että alkulukuja on todistettu olevan ääretön määrä, seuraa, että on olemassa myös mielivaltaisen suuria alkulukuja?

[HuuHaata]

En ihan ymmärrä kysymystäsi, mutta eikö siitä, että alkulukuja on todistettu olevan ääretön määrä, seuraa, että on olemassa myös mielivaltaisen suuria alkulukuja?

Kyllä mutta siis ei ole olemassa alkulukugeneraattoria? Eli ongelmaa etsi suuri alkuluku ei voida minkään alkulukujen joukon suhteen yksinkertaistaa mallilla yleisesti pitäisi ajaa ohjelma, jolla noita etsitään joka hidastuu nopeasti, mutta nyt jotenkin jollain valinnalla algoritmi tulee merkittävästi nopeammaksi, kun käydään paljon vähemmän lukuja läpi tms.

Vastauksen täytynee olla, ettei mahdollista kun sitä ei ole tehty.

[Harrastelija]

Kyllä mutta siis ei ole olemassa alkulukugeneraattoria?

Ei tietenkään ole alkulukugeneraattotria. Alkulukualgoritmeja on, joista nopein taitaa olla käyttämäni Eratostheneen seula, mutta se on eri asia. https://fi.wikipedia.org/wiki/Eratostheneen_seula

[HuuHaata]

Kyllä mutta siis ei ole olemassa alkulukugeneraattoria?

Ei tietenkään ole alkulukugeneraattotria. Alkulukualgoritmeja on, joista nopein taitaa olla käyttämäni Eratostheneen seula, mutta se on eri asia. https://fi.wikipedia.org/wiki/Eratostheneen_seula

Miksi ei tietenkään?

Miksi ei voisi olla todistusta, että luvut mallia 3^n-1 ovat aina alkulukuja? Tai ainakin todennäköisemmin, kuin muut luvut. Ja tuon esimerkin tilalle luonnollisesti jotain monimutkaisempaa.

[Harrastelija]

Luulen itse, että väite "On olemassa alkulukugeneraattori" kuuluu sarjaan, jotka eivät ole todistettavissa ta kumottavissa. Gödelhän osoitti, että matemaattisten järjestelmien sisällä on tällaisia väittämiä, jotka eivät ole todistettavissa järjestelmän omilla aksioomilla.