Aihe

Alkulukuparittelut

Anonyymi

Kuinka monella tavalla voidaan luvut 1, 2, ..., 2n asettaa pareihin siten että kunkin parin summa on alkuluku?

Esim jos n=3, niin on kolme paritusta:

(1, 2), (3, 4), (5, 6) <-- summat 3, 7 ja 11 alkulukuja
(1, 4), (2, 3), (5, 6) ------------- 5, 5 ja 11
(1, 6), (2, 5), (3, 4) -------------- 7, 7 ja 7

12

<50

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Anonyymi
    • Anonyymi

      Kannattaa laskea Pypyllä rekursiivisesti hiukan alkupäätä.

      pyp t.py
      3: 3
      4: 6
      5: 26
      6: 96
      7: 210
      8: 1106
      9: 3759
      10: 12577
      11: 74072
      12: 423884
      13: 2333828
      14: 16736611
      15: 99838851

      Google: 3,6,26,96,210,1106,3759,12577,74072,423884,2333828,16736611,99838851 oeis.org

      Taas eka osuma: https://oeis.org/A000341/internal

      Turha pohdiskella mitään likiarvokaavoja alkulukulaskuissa. Menevät kuitenkin pieleen hiukankin isommilla luvuilla. Ja jos eivät mene, niin menevät kuitenkin kun luvut kasvavat lisää. Fakta!

      Lista jatkuu:
      16: 630091746
      17: 4525325020
      18: 38848875650
      19: 342245714017
      20: 3335164762941
      21: 31315463942337
      22: 241353231085002
      23: 2350106537365732
      24: 17903852593938447
      25: 158065352670318614
      26: 1815064841856534244
      27: 20577063085601738871
      28: 276081763499377227299

      Kotikoneilla pääsee helposti n=20 saakka. Sitten pitää alkaa kikkailla ja kuluttaa kymmeniä tunteja ohjelmien optimointeihin.

      • Anonyymi

        Ei todellakaan mene pieleen ja ei ole turha! Jos vaikka lasketaan kaikkia parituksia eikä vain täydellisiä (ei tarvitse kaikkia lukuja parittaa vaan vain osa), niin tuon videon keinot antaa polynomi-aikaisen algoritmin, joka laskee lukumäärän suhteellisesti kuinka tarkasti vain halutaan (vaativuus tietenkin kasvaa, kun virhettä halutaan pienentää). Ja on siellä myöhemmissä videoissa sämpläys täydellisillekin, joten eiköhän tuo onnistu niillekin.

        Eikä tehtävällä sinänsä ole mitään tekemistä alkulukujen kanssa. Graafi on mitä se on ja kun se on muodostettu, niin alkuluvut voidaan unohtaa. Tietenkin graafi on kaksijakoinen, koska kahden eri luvun summa voi olla alkuluku vain jos toinen on parillinen ja toinen pariton. Ehkä jos jotain asymptoottisia juttuja kysytään, niin alkuluvut voivat tulla jotenkin peliin takaisin mukaan.


      • Anonyymi
        Anonyymi kirjoitti:

        Ei todellakaan mene pieleen ja ei ole turha! Jos vaikka lasketaan kaikkia parituksia eikä vain täydellisiä (ei tarvitse kaikkia lukuja parittaa vaan vain osa), niin tuon videon keinot antaa polynomi-aikaisen algoritmin, joka laskee lukumäärän suhteellisesti kuinka tarkasti vain halutaan (vaativuus tietenkin kasvaa, kun virhettä halutaan pienentää). Ja on siellä myöhemmissä videoissa sämpläys täydellisillekin, joten eiköhän tuo onnistu niillekin.

        Eikä tehtävällä sinänsä ole mitään tekemistä alkulukujen kanssa. Graafi on mitä se on ja kun se on muodostettu, niin alkuluvut voidaan unohtaa. Tietenkin graafi on kaksijakoinen, koska kahden eri luvun summa voi olla alkuluku vain jos toinen on parillinen ja toinen pariton. Ehkä jos jotain asymptoottisia juttuja kysytään, niin alkuluvut voivat tulla jotenkin peliin takaisin mukaan.

        Alkulukuvaatimus aiheuttaa sen, ettei löydy helppoa (tarkaa) kaavaa ja se hidastaa myös ohjemallisia ratkaisutapoja. Kokeile, niin huomaat kaiken.

        Esim. n=20 tehtävä voidaan laskea kaikkien mahdollisten 10+10 tapausten tulojen summana. Nopeuttaa valtavasti, vaikka 10 kpl voidaan valita 20:sta 184756 eri tavalla ja pitää laskea 2*184756 tapausten kaikki mahdolliset kombinaatiot. Ilman mitään optimointeja, sain laskettua tuon yhdellä ytimellä paljon alle 10 minuutissa. Ja tietysti oikein!

        Aloita n==10. Samalla opit paljon moniin muihinkin vastaaviin ongelmiin liittyviä ratkaisutapoja ja voi hyödyntää kouluissa opittuja matematiikan perussääntöjä. Joskus kymmeniä tai satoja vuosia sitten monia laskuja vain pohdiskeltiin teoreettisesti ja kehiteltiin kaikkea hauskaa ajanvietettä. Nykyisin lasketaan tarkasti ja tehdään esim. lääkkeitä ja rokotteita ja kaikkea muuta tarpeellista.

        Kaikesta voi laskea arvion sadalla tai tuhannella satunnaisotannalla. Pitää tietysti olla toimiva ohjelma, jolla nuo laskee. Samalla huomaa, että alku- ja loppupään lukuja pitää painottaa eri tavalla. Ja kun n kasvaa, niin alkuluvut harvenevat ja tulee lisää säätämistä.


    • Anonyymi

      Taulukko kannattaa kirjoittaa selkeämpään järjestykseen:

      (1, 2), (3, 4), (5, 6)
      (1, 4), (3, 2), (5, 6)
      (1, 6), (3, 4), (5, 2)

      Parittomat numerot ovat aina kiinteillä paikoillaan ja vain parilliset kombinoituvat. Ja jos lasketaan vain lukumäärää, mitään rivejä ei tietystikään edes tarvitse muodostaa.

      • Anonyymi

        Jos n on 20, mahdolliset parit parittomille luvuille ovat:

        1: 2 4 6 10 12 16 18 22 28 30 36 40
        3: 2 4 8 10 14 16 20 26 28 34 38 40
        5: 2 6 8 12 14 18 24 26 32 36 38
        7: 4 6 10 12 16 22 24 30 34 36 40
        9: 2 4 8 10 14 20 22 28 32 34 38
        11: 2 6 8 12 18 20 26 30 32 36
        13: 4 6 10 16 18 24 28 30 34 40
        15: 2 4 8 14 16 22 26 28 32 38
        17: 2 6 12 14 20 24 26 30 36
        19: 4 10 12 18 22 24 28 34 40
        21: 2 8 10 16 20 22 26 32 38 40
        23: 6 8 14 18 20 24 30 36 38
        25: 4 6 12 16 18 22 28 34 36
        27: 2 4 10 14 16 20 26 32 34 40
        29: 2 8 12 14 18 24 30 32 38
        31: 6 10 12 16 22 28 30 36 40
        33: 4 8 10 14 20 26 28 34 38 40
        35: 2 6 8 12 18 24 26 32 36 38
        37: 4 6 10 16 22 24 30 34 36
        39: 2 4 8 14 20 22 28 32 34 40

        Aluksi valitaan ensimmäiseltä riviltä ensimmäinen parillinen luku, sitten seuraavalta riviltä alusta alkaen seuraava valitsematon parillinen luku. Tuota toistetaan järjestyksessä kunnes päästään viimeisellä riville. Jos sieltä löytyy vapaa luku, saa pisteen. Ei voi löytyä kuin yksi eli turha hakea lisää. Maksimipistemmäärä on 3335164762941. Ei ole tuon vaikeampaa.

        Rivien järjestyksen saa alussa vaihtaa mieleisekseen. Ja jokaisen parillisen numeron voi vaikka jakaa kahdella tai korvata jollakin kirjaimella tai värillä. Saattaa olla jotain vaikutusta nopeuteen.

        Jos joku keksii toimivan (nopeuttavan) tavan poistaa valittu numero seuraavien rivien vaihtoehdoista, niin homma nopeutuu. Kannattaa tehdä esim. kolmannen rivin valinnan jälkeen aina automaattisesti eli laskea jäljellä olevat vaihtoehdot loppupäälle vasta silloin.


      • Anonyymi
        Anonyymi kirjoitti:

        Jos n on 20, mahdolliset parit parittomille luvuille ovat:

        1: 2 4 6 10 12 16 18 22 28 30 36 40
        3: 2 4 8 10 14 16 20 26 28 34 38 40
        5: 2 6 8 12 14 18 24 26 32 36 38
        7: 4 6 10 12 16 22 24 30 34 36 40
        9: 2 4 8 10 14 20 22 28 32 34 38
        11: 2 6 8 12 18 20 26 30 32 36
        13: 4 6 10 16 18 24 28 30 34 40
        15: 2 4 8 14 16 22 26 28 32 38
        17: 2 6 12 14 20 24 26 30 36
        19: 4 10 12 18 22 24 28 34 40
        21: 2 8 10 16 20 22 26 32 38 40
        23: 6 8 14 18 20 24 30 36 38
        25: 4 6 12 16 18 22 28 34 36
        27: 2 4 10 14 16 20 26 32 34 40
        29: 2 8 12 14 18 24 30 32 38
        31: 6 10 12 16 22 28 30 36 40
        33: 4 8 10 14 20 26 28 34 38 40
        35: 2 6 8 12 18 24 26 32 36 38
        37: 4 6 10 16 22 24 30 34 36
        39: 2 4 8 14 20 22 28 32 34 40

        Aluksi valitaan ensimmäiseltä riviltä ensimmäinen parillinen luku, sitten seuraavalta riviltä alusta alkaen seuraava valitsematon parillinen luku. Tuota toistetaan järjestyksessä kunnes päästään viimeisellä riville. Jos sieltä löytyy vapaa luku, saa pisteen. Ei voi löytyä kuin yksi eli turha hakea lisää. Maksimipistemmäärä on 3335164762941. Ei ole tuon vaikeampaa.

        Rivien järjestyksen saa alussa vaihtaa mieleisekseen. Ja jokaisen parillisen numeron voi vaikka jakaa kahdella tai korvata jollakin kirjaimella tai värillä. Saattaa olla jotain vaikutusta nopeuteen.

        Jos joku keksii toimivan (nopeuttavan) tavan poistaa valittu numero seuraavien rivien vaihtoehdoista, niin homma nopeutuu. Kannattaa tehdä esim. kolmannen rivin valinnan jälkeen aina automaattisesti eli laskea jäljellä olevat vaihtoehdot loppupäälle vasta silloin.

        Laskin n=24 esilasketuilla 6 pituisilla palikioilla. Aika tasan 20 min yhdellä ytimellä.

        Ja n=28 vastavasti esilasketuilla 7 pituisilla palikoilla onnistui 12,5 tunnissa kahdella ytimellä.

        Kokeilin myös n=32 laskentaa esilasketuilla 8 pituisilla palikoilla. Siihen tarvitaan 601080390 kpl 16 numeron valintaa 32:sta. Miljoonan ekan laskentaa meni aikaa yli 4 tuntia, joten ei kannattanut jatkaa. Pitää keksiä jotain optimointeja turhan laskennan vähentämiseksi. Peilikuvia ei varmasti löydy.

        Laskin vain joka 10000:n alkeistapauksen ja kerroin tuloksen 10000:lla:

        n=32: 5949500359473723221290000

        Vastaavasti vain joka 1000. alkeistapauksen laskenta:

        n=32: 5951515479469405986558000

        Pari kolme ensimmäistä numeroa ehkä oikein! Jälkimmäinen luultavsti lähempänä oikeata arvoa.

        Jokaisen 8 pituisen (ja muidenkin) palikan kombinaatioiden määrä on laskettava erikseen jokaisessa neljässä eri paikassa. ([1,3,..15], [17,...31], [33,...47], [49,...,63])


      • Anonyymi
        Anonyymi kirjoitti:

        Laskin n=24 esilasketuilla 6 pituisilla palikioilla. Aika tasan 20 min yhdellä ytimellä.

        Ja n=28 vastavasti esilasketuilla 7 pituisilla palikoilla onnistui 12,5 tunnissa kahdella ytimellä.

        Kokeilin myös n=32 laskentaa esilasketuilla 8 pituisilla palikoilla. Siihen tarvitaan 601080390 kpl 16 numeron valintaa 32:sta. Miljoonan ekan laskentaa meni aikaa yli 4 tuntia, joten ei kannattanut jatkaa. Pitää keksiä jotain optimointeja turhan laskennan vähentämiseksi. Peilikuvia ei varmasti löydy.

        Laskin vain joka 10000:n alkeistapauksen ja kerroin tuloksen 10000:lla:

        n=32: 5949500359473723221290000

        Vastaavasti vain joka 1000. alkeistapauksen laskenta:

        n=32: 5951515479469405986558000

        Pari kolme ensimmäistä numeroa ehkä oikein! Jälkimmäinen luultavsti lähempänä oikeata arvoa.

        Jokaisen 8 pituisen (ja muidenkin) palikan kombinaatioiden määrä on laskettava erikseen jokaisessa neljässä eri paikassa. ([1,3,..15], [17,...31], [33,...47], [49,...,63])

        Kun laskee ensimäisen valinnan ja sen komplementin kombinaatiot, voi samoilla tiedoilla laskea myös viimeisen valinnan (601080390.) jasen komplementin kombinaatiot. Yksi kertolasku ja summaus lisää. Aika puolituu, sillä valintoja tarvitsee tehdä vain puoliväliin saakka.

        Ensimmänen valinta on samalla viimeisen valinnnan komplementti ja viimeinen valinta on ensimmäisen valinnan komplementti. Sama juttu toisen ja kolmannen jne. kanssa.

        n=24 sujui 10m12s:ssa.

        Jotain kombinointiteorioista ymmärtävä matemaatikko löytäisi varmasti jotain muutakin yksinkertaista optimoimista.


      • Anonyymi
        Anonyymi kirjoitti:

        Kun laskee ensimäisen valinnan ja sen komplementin kombinaatiot, voi samoilla tiedoilla laskea myös viimeisen valinnan (601080390.) jasen komplementin kombinaatiot. Yksi kertolasku ja summaus lisää. Aika puolituu, sillä valintoja tarvitsee tehdä vain puoliväliin saakka.

        Ensimmänen valinta on samalla viimeisen valinnnan komplementti ja viimeinen valinta on ensimmäisen valinnan komplementti. Sama juttu toisen ja kolmannen jne. kanssa.

        n=24 sujui 10m12s:ssa.

        Jotain kombinointiteorioista ymmärtävä matemaatikko löytäisi varmasti jotain muutakin yksinkertaista optimoimista.

        Myös 8 luvun (tai 6,7) valinnassa 16:sta (12,14) voi hyödyntää samaa komplementtilistan ominaisuutta. Laskena-aika puolittui taas.

        Valinnat tapahtuvat yleiskäyttöisen indeksilistataulukon avulla. Kun siihen lisää rinnalle myös komplementilistan indeksit, nin komplementtilistankin saa muodostettua suoraan ilman hidasta laskentaa. Taas laskenta-aika enemmän kuin puolittui.

        Ja kun huomaa, ettei mitään listoja tarvitsekaan erikseen muodostaa, vaan kaiken tarvittavan osoitelaskennan saa suoritettua suoraan indeksoimalla kombinoitavaa 16 (tai 12,14) pituista listaa, niin kaikki nopeutuu.

        n=24 sujui 1m40s:ssa yhdellä ytimellä.
        n=28 sujui 1h44m:ssa yhdellä ytimellä.

        Myös n=32 laskenta nopeutui n. 20 kertaiseksi. Laskin joka sadannella alkeistapauksella:
        n=32: Noin 5952447841226087295866900

        Ehkä kolme ekaa numeroa oikein. Lasken tarkan arvon joskus, jos saan pienennettyä muistinkäyttöä .

        .


    • Anonyymi

      Lukuteoria on laskussa, koska tietojenkäsiyteluä se ei enää paljoa auta,
      Jos tietoturvaosaaminen sen takia nousee, siksi hakkerien taito samalla noysee

      • Anonyymi

        Harvinaisen idioottimainen valikoima sanoja epämääräisessä järjestyksessä. Jotain viisasta joku varmasti yritti sanoa jollakin kielellä.


      • Anonyymi
        Anonyymi kirjoitti:

        Harvinaisen idioottimainen valikoima sanoja epämääräisessä järjestyksessä. Jotain viisasta joku varmasti yritti sanoa jollakin kielellä.

        Tämä oli näin
        Jos tietoturvaosaaminen nousee, niin hakkerit pääsevät samoihin lähdeosaamisiin tietojenkäsittelyssä


    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Miksei työ kelpaa suomalaisille?

      Rakennus-, siivous-, ja hoiva-alakin täynnä ulkomaista työvoimaa ja kotimaiset vuosis kortistossa. Mistä moinen oikein johtuu. Ovatko korvaukset liia
      Maailman menoa
      424
      4974
    2. Talouselämä-julkaisu tykittää kovaa tekstiä Usan taloudesta

      "Joe Biden nousee velkaantuvan valejättiläisen johtoon – Yhdysvaltain budjettivajeet repeävät ja velkavuori kasvaa" https://www.talouselama.fi/uutis
      Maailman menoa
      103
      1880