Goldbachin konjektuuri

[Harrastelija]

Goldbachin konjektuuri esitettiin vuonna 1742 ja se kuuluu: kaikki parilliset luvut suuremmat kuin 2 voidaan esittää kahden alkuluvun summana. Testaan lukua 1000000000000000000 freepascal kielisellä ohjelmalla. Ohjelma on pyörinyt nyt kauan aikaa, eikä vieläkään ole löytänyt kahta alkulukua. Yleensä kaksi alkulukua löytyvät pian. Ois se hienoa tehdä historiaa ja löytää vastaesimerkki, mikä kumoaa konjektuurin Vuonna 2013, eräs tutkimus, joka käytti erittäin suurta laskentatehoa, tutki Goldbachin konjektuuria kaikilla parillisilla luvuilla alle 4×10^18 eli välttämättä lukua 1000000000000000000 eli lukua 10E+19 ei olla vielä tutkittu.

program GoldbachExample;
uses
bigdecimalmath;

function IsPrime(n: BigDecimal): Boolean;
var
i, num: BigDecimal;
begin
IsPrime := True;
num := Sqrt(n);
i := 2;
while i <= num do
begin
if (n mod i) = 0 then
begin
IsPrime := False;
Exit;
end;
i := i + 1;
end;
end;

procedure GoldbachSum(n: BigDecimal);
var
x, y: BigDecimal;
found: Boolean;
begin
found := False;
x := 2;
while x <= n div 2 do
begin
if IsPrime(x) then
begin
y := n - x;
if IsPrime(y) then
begin
WriteLn(BigDecimalToStr(n), ' = ', BigDecimalToStr(x), ' + ', BigDecimalToStr(y));
found := True;
Break;
end;
end;
x := x + 1;
end;
if not found then
WriteLn('No Goldbach sum found for ', BigDecimalToStr(n));
end;

var
numberToCheck: BigDecimal;
begin
numberToCheck := 1000000000000000000;
GoldbachSum(numberToCheck);
end.

[QS]

Tämän tulosjoukko on { 999999999999999989 , 11 }

[Disputator]

Goldbachin konjektuuri esitettiin vuonna 1742 ja se kuuluu: kaikki parilliset luvut suuremmat kuin 2 voidaan esittää kahden alkuluvun summana. Testaan lukua 1000000000000000000 freepascal kielisellä ohjelmalla.
...

Ihan jees puuhastelua . Vähän kuitenkin täytyy antaa negatiivista palautetta ohjelmointikielen valinnasta, sillä Pascal on kai nykypäivän ohjelmointia osaavien osaamislistalla jossain paikalla 100+ eli noin 0,002% koodareista ymmärtää Pascalin sielunelämää tarkemmin. Pascal koodi jää ainakin multa tarkastamatta, koska en viitsi opetella Pascalia vastatakseni netissä johonkin ja luultavasti moni muukin ajattelee niin. Siksi:

Nykyään jengi koodaa jollain Pythonilla, C:llä, C++lla Javalla tms. Kaikissa noissa on olemassa kirjastoja erilaiseen harrastelijan numeronmurskaukseen.

[Eusa]

Tässä uusi idea tuottaa Golbachin alkulukupareja. Pdf-tiedosto on nopeasti idean pohjalta kyhätty tekele, jota lähden täsmentelemään. Empiiriset tulokset vakuuttavat kyllä, että oikeilla jäljillä ollaan.

Goldbach-1-2-adic-sym.pdf

(270.36 KiB) Tiedosto ladattu 93 kertaa

Ajatus on siis poistaa seulalla tietysti kaikki n:n sisältämä p-adisuus symmetrisesti molempiin suuntiin sekä riippuen parillisuudesta, viereisiä lähimpiä parillisia lukuja origoina pitäen Eratostheneen seulalla poistaa vielä loppuja n:lle suhteellisen alkuluvun suhteen p-adisuuksia pois myös molempiin suuntiin. Rakenne on symmetrinen ja johtaa siihen, että jaollisuustäytteisyyden täydentymiseksi muodostuu vähintään yksi 2-jäseninen n:n p-adisuuden "sukulais"rengas (n-d, n+d), jossa totaalihuuhtoutumisen tilanteessa parillisen n:n kahta puolen on pakosti alkulukukaksoset (d=1) tai n ollessa pariton, se on itse alkuluku (d=0) ja (n, n) on menetelmän antama eräs Goldbach-ratkaisu.

[Eusa]

...viereisiä lähimpiä parillisia lukuja origoina pitäen Eratostheneen seulalla poistaa vielä loppuja n:lle suhteellisen alkuluvun suhteen p-adisuuksia pois myös molempiin suuntiin.

Tarkennus. Eratostheneen seulalla siis poistetaan lukujärjestelmän suhteiset p-adisuudet transitioina n:n suhteelliseen alkulukuun nähden - eikä pelkästään tuon luvun sisältämät p-adisuudet.

[Eusa]

Mod-symm-sieve.pdf

(209.69 KiB) Tiedosto ladattu 72 kertaa

Laajensin teoreeman koskemaan Goldbachin lisäksi alkulukukaksosten arvoitusta ja Riemannin hypoteesia. Yhteys on selvä. Paperissa on vielä avoimia loppuväitteitä tarkkaa todistelua vailla, mutta täytyy hieroa ne kuntoon ajan kanssa...

[Keckman]

Tuli ChatGPT:n avulla tehtyä todella nopea C-kielinen versio ohjelmasta. Se tulostaa alta aikayksikön:

1000000000000000000 = 11 + 999999999999999989

Process returned 0 (0x0) execution time : 0.153 s
Press any key to continue.

Koodi: Valitse kaikki

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

typedef uint64_t ull;

/* 128-bit välikertoimet (GCC/Clang tukee __int128) */
static ull modmul(ull a, ull b, ull mod) {
    __uint128_t res = (__uint128_t)a * b;
    return (ull)(res % mod);
}

static ull modpow(ull base, ull exp, ull mod) {
    ull result = 1;
    while (exp > 0) {
        if (exp & 1)
            result = modmul(result, base, mod);
        base = modmul(base, base, mod);
        exp >>= 1;
    }
    return result;
}

static bool miller_rabin(ull n) {
    if (n < 2) return false;

    /* Pienet alkuluvut */
    ull small_primes[] = {2,3,5,7,11,13,17,19,23,29,31,37};
    for (int i = 0; i < 12; i++) {
        if (n % small_primes[i] == 0)
            return n == small_primes[i];
    }

    /* Kirjoita n-1 = d * 2^s */
    ull d = n - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    /* Deterministiset testikannat 64-bit luvuille */
    ull bases[] = {2ULL, 325ULL, 9375ULL, 28178ULL,
                   450775ULL, 9780504ULL, 1795265022ULL};

    for (int i = 0; i < 7; i++) {
        ull a = bases[i] % n;
        if (a == 0) return true;

        ull x = modpow(a, d, n);
        if (x == 1 || x == n - 1)
            continue;

        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = modmul(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }

        if (composite)
            return false;
    }

    return true;
}

void goldbach_fast(ull n) {
    if (n <= 2 || (n % 2) != 0) {
        printf("Input must be even and > 2\n");
        return;
    }

    /* Tarkista ensin pieniä alkulukuja */
    ull small_primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
    int count = sizeof(small_primes)/sizeof(small_primes[0]);

    for (int i = 0; i < count; i++) {
        ull p = small_primes[i];
        if (p >= n) break;
        if (miller_rabin(n - p)) {
            printf("%llu = %llu + %llu\n", n, p, n - p);
            return;
        }
    }

    /* Sitten jatketaan parittomilla */
    for (ull p = 53; p < n/2; p += 2) {
        if (miller_rabin(p)) {
            if (miller_rabin(n - p)) {
                printf("%llu = %llu + %llu\n", n, p, n - p);
                return;
            }
        }
    }

    printf("No Goldbach sum found for %llu\n", n);
}

int main() {
    ull numberToCheck = 1000000000000000000ULL;
    goldbach_fast(numberToCheck);
    return 0;
}