Alkulukuparittelut

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 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.

Lue lisää

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ä.

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 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.

Lue lisää

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 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])

Lue lisää

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 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.

Lue lisää

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öä .

.

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

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ä