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
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
Vastaukset 12
Vanhimmat
Voisiko tässä videossa: https://youtu.be/svi1j799i0A?t=1275 kerrottuja keinoja käyttää lukumäärän approksimatiiviseen laskemiseen?
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.
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ä.
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.
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])
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öä .
.
Lukuteoria on laskussa, koska tietojenkäsiyteluä se ei enää paljoa auta,
Jos tietoturvaosaaminen sen takia nousee, siksi hakkerien taito samalla noysee
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ä