Järjestykset siten että vierekkäisten summa aina alkuluku

Olet tehnyt koodissa virheen. Kun n = 6, hyväksyttyjä järjestyksiä on vain 8 ja kun n = 7, niitä on 16.

Jos aloittaja haluaisi vain yksittäistapauksia, hän olisi laittanut keskustelun Ohjelmointi-palstalle. Matematiikan tehtävänä tässä on ratkaista yleinen sääntö, jonka mukaan vastaus löytyy.

Anonyymi kirjoitti:

Olet tehnyt koodissa virheen. Kun n = 6, hyväksyttyjä järjestyksiä on vain 8 ja kun n = 7, niitä on 16.

n = 6
1 4 3 2 5 6
1 6 5 2 3 4
2 3 4 1 6 5
2 5 6 1 4 3
3 2 5 6 1 4
3 4 1 2 5 6
3 4 1 6 5 2
4 1 6 5 2 3
4 3 2 1 6 5
4 3 2 5 6 1
5 2 3 4 1 6
5 6 1 2 3 4
5 6 1 4 3 2
6 1 4 3 2 5
6 5 2 1 4 3
6 5 2 3 4 1

Missä virhe? Vai oletko sinä taas se palstan ikioma sählääjäharjoittelija ja toisten syyttäjä?

Anonyymi kirjoitti:

Jos aloittaja haluaisi vain yksittäistapauksia, hän olisi laittanut keskustelun Ohjelmointi-palstalle. Matematiikan tehtävänä tässä on ratkaista yleinen sääntö, jonka mukaan vastaus löytyy.

Lue lisää

Taas selittelet omiasi ja luulet jotain. Esitä se ratkaisu tai ole hiljaa.

Jokanen matematiikkaa hiukankin opiskellut tietää, ettei alkulukujen kanssa pelatessa löydy koskaan mitään yleissääntöä.

10: 1328
11: 2144

Kohta alkaa selittely. Ja selitysten korjaaminen ja ...

Taulukoin n = 21 arvolla kaikki alkulukuun päättyvät vaihtoehdot seuraaviksi luvuiksi. Laskentaan meni aikaa n. 36 min.

21: 675603568

Laskeaa mikä on tulos n = 22 arvolla. Aikaa menee luultavasti pari kome tuntia. Tai vähemmän, jos osaatte optimoida paremmin.

Laskettujen arvojen avulla saattaa olla mahdollista kehittää joku likiarvokaava.

Anonyymi kirjoitti:

Taulukoin n = 21 arvolla kaikki alkulukuun päättyvät vaihtoehdot seuraaviksi luvuiksi. Laskentaan meni aikaa n. 36 min.

21: 675603568

Laskeaa mikä on tulos n = 22 arvolla. Aikaa menee luultavasti pari kome tuntia. Tai vähemmän, jos osaatte optimoida paremmin.

Laskettujen arvojen avulla saattaa olla mahdollista kehittää joku likiarvokaava.

Lue lisää

Laitoin Googleen pelkästään luvun 675603568.

Ensimmäinen hakutulos yllätti jälleen taas:

https://oeis.org/A103839

Eli vanhoja kaikille tuttuja Hamiltonian paths.

Jos laskee vain lukumäärää, niin ei tarvitse muodostaa listaa numeroiden järjestyksestä tulostusta tms. varten. Riittää vain tietää mikä on viimeisin numero ja katsoa indeksoitavasta taulukosta onko seuraava numeroehdokas vapaana ja pitää kirjaa lukujonon pituudesta. Nopeuttaa valtavasti rekursiivista ohjelmaa. Ei lainkaan hitaita listaoperaatioita. Seuraava luku muodostaa automaattisesti alkuluvun. Ei tarvitse tarkistaa mitään.

Sain kaikki lukumäärät laakista oikein n = 22 asti. Viimeinen kesti 1h50m. Tuon jälkeen alkaa hidastua.

Kopsasin oeis.org:sta oikeat lukumäärät:
20: 241559918
21: 675603568
22: 8723487720
23: 22850057800
24: 285146572432
25: 859834538938
26: 8276479696196
27: 32343039694056
28: 429691823372130

Viimeisten isojen lukumäärien laskeminen vaatii aikaa ja rinnakkaislaskentaa tai jotain älykästä tapaa turhan laskennan minimoimiseksi. Pelkkä laskurin askeltaminenkin 430 biljoonaa kertaa kestää useita päiviä.

Anonyymi kirjoitti:

Jos laskee vain lukumäärää, niin ei tarvitse muodostaa listaa numeroiden järjestyksestä tulostusta tms. varten. Riittää vain tietää mikä on viimeisin numero ja katsoa indeksoitavasta taulukosta onko seuraava numeroehdokas vapaana ja pitää kirjaa lukujonon pituudesta. Nopeuttaa valtavasti rekursiivista ohjelmaa. Ei lainkaan hitaita listaoperaatioita. Seuraava luku muodostaa automaattisesti alkuluvun. Ei tarvitse tarkistaa mitään.

Sain kaikki lukumäärät laakista oikein n = 22 asti. Viimeinen kesti 1h50m. Tuon jälkeen alkaa hidastua.

Kopsasin oeis.org:sta oikeat lukumäärät:
20: 241559918
21: 675603568
22: 8723487720
23: 22850057800
24: 285146572432
25: 859834538938
26: 8276479696196
27: 32343039694056
28: 429691823372130

Viimeisten isojen lukumäärien laskeminen vaatii aikaa ja rinnakkaislaskentaa tai jotain älykästä tapaa turhan laskennan minimoimiseksi. Pelkkä laskurin askeltaminenkin 430 biljoonaa kertaa kestää useita päiviä.

Lue lisää

Laskennan saa helposti paljon alle kymmenysosaan tarkastelemalla hiukan muodostettujen lukujonojen alkuosaa. Suurin osa on tehtävän kannalta matemaattisesti täysin samoja. Siis sama luku viimeisenä ja kaikki muut luvut keskenään samoja, mutta eri järjestyksessä. Riittää laskea loppuun asti aina vain yksi noista ja kertoa tulos samanlaisten määrällä.

Jos n on paljon yli 20, tehtävä kannattaa jakaa kahteen eri vaiheeseen. Ensin muodostetaan kaikki lailliset 10 tai 12 luvun pituiset alkuosat. Muodosteaan alkukuosasta lista, jossa viimeinen luku on erillään ensimmäisenä ja sen jälkeen suurusjärjestykseen lajiteltu 9 tai 11 luvun lista toisena tekijänä. Talletetaan kaikki nämä miljoonat pikkulistat isoon listaan ja lajitellaan se suurusjärjestykseen. Identtisiä pikkulistoja on useissa kohtaa peräkkäin kymmenittäin. Poimitaan niistä aina vain se ensimmäinen uuteen isoon listaan ja laitetaan mukaan muista vain lukumäärä. Alkuperäisen ison listan voi tuhota muistin vapauttamiseksi.

Suoritetaan laskenta loppuun asti kaikile uuden ison listan pikkulistoille.

Tuon ison lajitellut listan muodostamisen menee minuutti tai pari. Säästö kymmeniä tunteja. Jos tai kun muisti ei riitä, niin isoon listaan voi tallentaa vain ne pikkulistat, joiden viimeinen (10. tai 12.) luku on 1. Sitten 2 jne... Nopeuttaa lajitteluakin.

Varmasti löytyy jotain muutakin optimoimista. Aluksi lasketun alkuosan pituutta voi kasvattaa tarvittaessa 14 tai 16 luvun mittaiseksi. Oltava parillinen määrä!

Kokeilkaa aluksi paljon pienemmillä lukumäärillä. Kaikki selviää hetkessä ihan vaan katselemalla ja ihmettelemällä.

Anonyymi kirjoitti:

Laskennan saa helposti paljon alle kymmenysosaan tarkastelemalla hiukan muodostettujen lukujonojen alkuosaa. Suurin osa on tehtävän kannalta matemaattisesti täysin samoja. Siis sama luku viimeisenä ja kaikki muut luvut keskenään samoja, mutta eri järjestyksessä. Riittää laskea loppuun asti aina vain yksi noista ja kertoa tulos samanlaisten määrällä.

Jos n on paljon yli 20, tehtävä kannattaa jakaa kahteen eri vaiheeseen. Ensin muodostetaan kaikki lailliset 10 tai 12 luvun pituiset alkuosat. Muodosteaan alkukuosasta lista, jossa viimeinen luku on erillään ensimmäisenä ja sen jälkeen suurusjärjestykseen lajiteltu 9 tai 11 luvun lista toisena tekijänä. Talletetaan kaikki nämä miljoonat pikkulistat isoon listaan ja lajitellaan se suurusjärjestykseen. Identtisiä pikkulistoja on useissa kohtaa peräkkäin kymmenittäin. Poimitaan niistä aina vain se ensimmäinen uuteen isoon listaan ja laitetaan mukaan muista vain lukumäärä. Alkuperäisen ison listan voi tuhota muistin vapauttamiseksi.

Suoritetaan laskenta loppuun asti kaikile uuden ison listan pikkulistoille.

Tuon ison lajitellut listan muodostamisen menee minuutti tai pari. Säästö kymmeniä tunteja. Jos tai kun muisti ei riitä, niin isoon listaan voi tallentaa vain ne pikkulistat, joiden viimeinen (10. tai 12.) luku on 1. Sitten 2 jne... Nopeuttaa lajitteluakin.

Varmasti löytyy jotain muutakin optimoimista. Aluksi lasketun alkuosan pituutta voi kasvattaa tarvittaessa 14 tai 16 luvun mittaiseksi. Oltava parillinen määrä!

Kokeilkaa aluksi paljon pienemmillä lukumäärillä. Kaikki selviää hetkessä ihan vaan katselemalla ja ihmettelemällä.

Lue lisää

Ei tuossa tarvitse muodostaa mitään jättikokoisia listaa ja lajitella sitä. Pääsee paljon vähemmällä kuin muodostaa ne "pikkulistat" yksitellen. Yhteiseksi valittu luku kannattaa laittaa ensimmäiseksi, sillä eihän sillä ole mitään merkitystä, miten päin listaa katsoo. Tällätavalla sen pituus voi ola myös pariton. Kannattanee olla puolet n:n arvosta.

Oletetaan n:n olevan 23. Luvuista 1...23 voidaan valita 11 eri lukua m:llä eri tavalla. Jokainen noista käsitellään erikseen. Jokainen mukana oleva luku laitetaan vuoron perään ensimäiseksi ja lasketaan kuinka monta erilaista järjetystä kussakin eri tapauksessa saadaan.

Sitten lasketaan jäljelle jääneistä 12:sta luvusta vastaavalla tavalla eri järjestykset ja niiden lukumäärät ja yritetään yhdistää "listat" toisiinsa alkupisteistään. Onnistuu jos alussa olevien lukujen summa on alkuluku. Yhdistetyn pitkän (23) "listan" järjestysten lukumäärät saadaan kertomalla lyhyiden listojen eri järjestysten määrät keskenään.

Käydään läpi kaikki miljoonat vaihtoehdot ja summataan tulokset. Jos kaikki on tehty oikein, saadaan oikea vastaus.

Nopea testata ensin esim. n:n arvolla 12.

Tämä on juuri sitä matematikkaa, jota kouluissa pyritään opettamaan. Jokainen saa itse valita, käyttääkö pelkästään kynää, suttupaperia ja taskulaskinta vai pieniä kertakäyttöisiä ohjelmapätkiä.

Anonyymi kirjoitti:

Ei tuossa tarvitse muodostaa mitään jättikokoisia listaa ja lajitella sitä. Pääsee paljon vähemmällä kuin muodostaa ne "pikkulistat" yksitellen. Yhteiseksi valittu luku kannattaa laittaa ensimmäiseksi, sillä eihän sillä ole mitään merkitystä, miten päin listaa katsoo. Tällätavalla sen pituus voi ola myös pariton. Kannattanee olla puolet n:n arvosta.

Oletetaan n:n olevan 23. Luvuista 1...23 voidaan valita 11 eri lukua m:llä eri tavalla. Jokainen noista käsitellään erikseen. Jokainen mukana oleva luku laitetaan vuoron perään ensimäiseksi ja lasketaan kuinka monta erilaista järjetystä kussakin eri tapauksessa saadaan.

Sitten lasketaan jäljelle jääneistä 12:sta luvusta vastaavalla tavalla eri järjestykset ja niiden lukumäärät ja yritetään yhdistää "listat" toisiinsa alkupisteistään. Onnistuu jos alussa olevien lukujen summa on alkuluku. Yhdistetyn pitkän (23) "listan" järjestysten lukumäärät saadaan kertomalla lyhyiden listojen eri järjestysten määrät keskenään.

Käydään läpi kaikki miljoonat vaihtoehdot ja summataan tulokset. Jos kaikki on tehty oikein, saadaan oikea vastaus.

Nopea testata ensin esim. n:n arvolla 12.

Tämä on juuri sitä matematikkaa, jota kouluissa pyritään opettamaan. Jokainen saa itse valita, käyttääkö pelkästään kynää, suttupaperia ja taskulaskinta vai pieniä kertakäyttöisiä ohjelmapätkiä.

Lue lisää

Kokeilin Pythonin Pypyllä tuota tapaa. Kesti kolme ja puoli minuuttia laskea n=23 ja 1h45min laskea n=25. Kaikki pienemmät arvo ihan hetkessä. Miljardeja sekalaisia laskutoimituksia ja pienten listojen ja taulukoiden kanssa pelaamista ja kaikki tulokset laakista oikein.

Jos n on pariton, ja n:stä luvusta valitaan 11 kpl, niin niistä on 6 oltava parittomia. Karsii lähes yli 2/3 pois. Ensimmäinen luku on varmasti pariton. Toisessa listassa aina parillinen. Vähentää laskentaa merkittävästi.

Anonyymi kirjoitti:

Kokeilin Pythonin Pypyllä tuota tapaa. Kesti kolme ja puoli minuuttia laskea n=23 ja 1h45min laskea n=25. Kaikki pienemmät arvo ihan hetkessä. Miljardeja sekalaisia laskutoimituksia ja pienten listojen ja taulukoiden kanssa pelaamista ja kaikki tulokset laakista oikein.

Jos n on pariton, ja n:stä luvusta valitaan 11 kpl, niin niistä on 6 oltava parittomia. Karsii lähes yli 2/3 pois. Ensimmäinen luku on varmasti pariton. Toisessa listassa aina parillinen. Vähentää laskentaa merkittävästi.

Lue lisää

Tuossa yllä laskin n=25 tapauksen valitsemalla pikkilistan pituudeksi 11. Jos pituudeksi laittoi 12, niin aika supistui n. kolmannekseen eli 38 minuutiksi.

Peilikuvat saa karsittua helposti pois, jos laittaa yhden pikkulistaan valituista numeroista kiinteästi 1:ksi (pariton), jos n on parillinen tai 3, 7, 11, 15, 19, 23, 27. Noissa parittomissa listoissa on aina keskellä parillinen numero. Jos n on 5, 9, 13, 17, 21, 25, 29, niin kiinteän luvun on oltava parillinen, esim. 2. Noilla n:n arvoilla listoissa on keskellä aina pariton numero.

Peilikuvien poistolla kaikki laskenta-ajat vielä puolittuivat eli n=25 kesti vain 19 min ja n=27 kesti 3h50m.

Näillä optimoinneilla olisi jo mahdollista laskea oeis.org:sta puuttuvat n=29 ja n=30. Kannattanee kuitenkin vielä yrittää keksiä lisää yksinkertaisia optimointeja. Aika usein valitulle pikkulistalle tai sen komplementtilistalle ei löydy yhtään ratkaisua. Jotenkin nuo pitäisi heti pystyä tunnistamaan ja suodattamaan pois. Varmasti paljon muutakin turhaa laskentaa.

Anonyymi kirjoitti:

Tuossa yllä laskin n=25 tapauksen valitsemalla pikkilistan pituudeksi 11. Jos pituudeksi laittoi 12, niin aika supistui n. kolmannekseen eli 38 minuutiksi.

Peilikuvat saa karsittua helposti pois, jos laittaa yhden pikkulistaan valituista numeroista kiinteästi 1:ksi (pariton), jos n on parillinen tai 3, 7, 11, 15, 19, 23, 27. Noissa parittomissa listoissa on aina keskellä parillinen numero. Jos n on 5, 9, 13, 17, 21, 25, 29, niin kiinteän luvun on oltava parillinen, esim. 2. Noilla n:n arvoilla listoissa on keskellä aina pariton numero.

Peilikuvien poistolla kaikki laskenta-ajat vielä puolittuivat eli n=25 kesti vain 19 min ja n=27 kesti 3h50m.

Näillä optimoinneilla olisi jo mahdollista laskea oeis.org:sta puuttuvat n=29 ja n=30. Kannattanee kuitenkin vielä yrittää keksiä lisää yksinkertaisia optimointeja. Aika usein valitulle pikkulistalle tai sen komplementtilistalle ei löydy yhtään ratkaisua. Jotenkin nuo pitäisi heti pystyä tunnistamaan ja suodattamaan pois. Varmasti paljon muutakin turhaa laskentaa.

Lue lisää

Jos n on 4:llä jaollinen (esim. 28), niin molempien pikkulistojen pituus on parillinen 14. Tällöin riittää laskea vain parillisilla numeroila alkavien järjesysten lukumäärä molemmissa pikkulistoissa ja askeltaa aina myös vimeisen luvun (varmasti pariton) laskuria.

Sitten yritetään naittaa (alkuluku) ekan pikkulistan parilliset numerot tokan pikkulistan parittomien numeroiden (ja parittomat parillisten kanssa) kanssa ja kertoa vastaavien laskurien arvot keskenään. Laskenta-aika puolittuu jälleen täysin ilmaiseksi.

Anonyymi kirjoitti:

Jos n on 4:llä jaollinen (esim. 28), niin molempien pikkulistojen pituus on parillinen 14. Tällöin riittää laskea vain parillisilla numeroila alkavien järjesysten lukumäärä molemmissa pikkulistoissa ja askeltaa aina myös vimeisen luvun (varmasti pariton) laskuria.

Sitten yritetään naittaa (alkuluku) ekan pikkulistan parilliset numerot tokan pikkulistan parittomien numeroiden (ja parittomat parillisten kanssa) kanssa ja kertoa vastaavien laskurien arvot keskenään. Laskenta-aika puolittuu jälleen täysin ilmaiseksi.

Lue lisää

Tuolla tavalla sain laskettua n=28. Jaoin tehtävän kuuten eri osaan ja suoritin niitä kolmella ytimellä. Yhteenlaskettu aika n. 20 h. Muistia ei tarvittu juuri lainkaan. Eikä yhtään kirjasto-ohjelmaa.

Eikö kukaan keksi mitään järkevää "matemaattista" tapaa laskea, jos n>28? Jotenkin useita gigatavuja muistia käyttämällä voisi ehkä keksiä jotain merkittävää ajansäästöä. Jos lukujonon jakaa yli kahteen osaan, niin niiden osien muodostaminen ja yhdisteleminen muuttuu liian monimutkaiseksi ja aikaavieväksi eikä mitään ajansäästöä synny, ellei keksi jotain todella älykästä.

a. Parittomat ja parilliset ovat toisistaan riippumattomia, joten kyse on kahdesta erillisestä neljän valinnasta 16:sta.

Menee suoraan kaavalla (16!/(4!*12!))^2 = 3312400

c. Ehdoton maksimi on 8*4*3*3*2*2 = 1152. Löytynee varmasti monia.

Anonyymi kirjoitti:

a. Parittomat ja parilliset ovat toisistaan riippumattomia, joten kyse on kahdesta erillisestä neljän valinnasta 16:sta.

Menee suoraan kaavalla (16!/(4!*12!))^2 = 3312400

c. Ehdoton maksimi on 8*4*3*3*2*2 = 1152. Löytynee varmasti monia.

Lue lisää

c.
576
[1, 7, 13, 31] [6, 10, 16, 30]
[1, 7, 25, 31] [6, 12, 16, 22]
[5, 9, 15, 29] [2, 8, 14, 32]
[5, 11, 15, 21] [2, 8, 26, 32]
3312400 1505401

Peilikuvineen 2*576 = 1152

Laskin Pypyllä järjestykset n=32:

32: 2*286461841829709909 = 572923683659419818

Aikaa yhdellä ytimellä vajaa 4 vrk eli n. 90h. Muistitarve n. 4 Gb, joten hyvin toimii 8 Gtavuisessa koneessa.

Sama ohjelma laskee oikean tuloksen n=24 paljon alle kahdessa minuutissa.

Suuruusluokka näyttäsi olevan ihan ok. Google ei tunnista lukua (vielä).

Anonyymi kirjoitti:

Laskin Pypyllä järjestykset n=32:

32: 2*286461841829709909 = 572923683659419818

Aikaa yhdellä ytimellä vajaa 4 vrk eli n. 90h. Muistitarve n. 4 Gb, joten hyvin toimii 8 Gtavuisessa koneessa.

Sama ohjelma laskee oikean tuloksen n=24 paljon alle kahdessa minuutissa.

Suuruusluokka näyttäsi olevan ihan ok. Google ei tunnista lukua (vielä).

Lue lisää

OEIS:kseen voi lähettää lisätermejä: https://oeis.org/Submit.html. Vaatii kyllä kirjautumisen.

Anonyymi kirjoitti:

OEIS:kseen voi lähettää lisätermejä: https://oeis.org/Submit.html. Vaatii kyllä kirjautumisen.

Lue lisää

Tulosten pitää tietysti olla varmennettuja ja tässä tapauksessa pitäsi tietysti laskea myös n:n arvot 29, 30 ja 31. Onnistuu keneltä tahansa matemaatikolta, jos on käytössä pienikin supertietokone. Vastaavia "tyhmiä" ja täysin tarpeettomia sarjoja on maailma täynnä.

Tuo n=32 (2*16 = 2*8 2*8) on matemaattisesti ja ohjelmointiteknisesti mukava erikoistapaus kotikoneelle. Lähinnä optimointia turhan laskennan välttämiseksi ja muistitarpeen pienentämistä. Yritän saada laskenta-ajan (yhdellä ytimellä) vielä alle vuorokaudeksi.

Yritän seuraavaksi laskea n=30:n kombinoimalla 10 j 2*10. Tuota tapaa pitää tietysti ensin kokeilla n=24:n kanssa 8 2*8 palikoilla. Saattaa olla nopeampi kuin 2*6 2* 6.

Anonyymi kirjoitti:

Tulosten pitää tietysti olla varmennettuja ja tässä tapauksessa pitäsi tietysti laskea myös n:n arvot 29, 30 ja 31. Onnistuu keneltä tahansa matemaatikolta, jos on käytössä pienikin supertietokone. Vastaavia "tyhmiä" ja täysin tarpeettomia sarjoja on maailma täynnä.

Tuo n=32 (2*16 = 2*8 2*8) on matemaattisesti ja ohjelmointiteknisesti mukava erikoistapaus kotikoneelle. Lähinnä optimointia turhan laskennan välttämiseksi ja muistitarpeen pienentämistä. Yritän saada laskenta-ajan (yhdellä ytimellä) vielä alle vuorokaudeksi.

Yritän seuraavaksi laskea n=30:n kombinoimalla 10 j 2*10. Tuota tapaa pitää tietysti ensin kokeilla n=24:n kanssa 8 2*8 palikoilla. Saattaa olla nopeampi kuin 2*6 2* 6.

Lue lisää

Laskin ihan kotikoneella n=29.

n=29: 1133076110416228

Kombinoin 14 ja 15 luvun pituiset listat. Aikaa neljällä ytimellä laskien n. 14 h.

Rekursiivisen aliohjelman korvaaminen 14- ja 15-tasoisilla pitkillä silmukkaketjuilla nopeutti laskua mekittävästi. Tällä tavalla sain laskettua n=28 neljällä ytimellä tasan kahdessa tunnissa.

Myös n=30 pitäsi olla laskettavissa muutamassa päivässä neljällä ytimellä ja paljon useammalla muutamassa tunnissa.

Anonyymi kirjoitti:

Laskin ihan kotikoneella n=29.

n=29: 1133076110416228

Kombinoin 14 ja 15 luvun pituiset listat. Aikaa neljällä ytimellä laskien n. 14 h.

Rekursiivisen aliohjelman korvaaminen 14- ja 15-tasoisilla pitkillä silmukkaketjuilla nopeutti laskua mekittävästi. Tällä tavalla sain laskettua n=28 neljällä ytimellä tasan kahdessa tunnissa.

Myös n=30 pitäsi olla laskettavissa muutamassa päivässä neljällä ytimellä ja paljon useammalla muutamassa tunnissa.

Lue lisää

Tuo n=30 on lasekettavissa samalla tavalla kuin n=32. Voidaan jakaa kahtia 15 15 ja
laskea nuo 8 7 pituisina esilaskettuina palasina. Aikaa kuluu ehkä neljännes n=32 laskusta.

Mikä tahansa valinta luvuista 1...30 (tai 1...32) voidaan esittää 30 (32) bittisenä lukuna. Alin bitti vastaa 1:stä ja ylin 30:stä (32:sta). Samaan indeksoitavaan taulukkoon voidaan sijoittaa sekaisin 7 ja 8 lukuisia valintoja. Niistä muodostuu varmasti eri indeksi.

Lähes tyhjästä taulukosta kannattaa tehdä kaksiulotteinen, jolloin lähes kaikki tyhjät rivit voidaan korvata yhdellä nollalla. Säästyy muistia 99 %. Ja n=30 vaatii vain neljänneksen n=32 tarvitsemasta muistista. Helppo homma. Kokeilkaa ensin n=26:lla. Ei kestä montaa minuuttia.

Anonyymi kirjoitti:

Laskin ihan kotikoneella n=29.

n=29: 1133076110416228

Kombinoin 14 ja 15 luvun pituiset listat. Aikaa neljällä ytimellä laskien n. 14 h.

Rekursiivisen aliohjelman korvaaminen 14- ja 15-tasoisilla pitkillä silmukkaketjuilla nopeutti laskua mekittävästi. Tällä tavalla sain laskettua n=28 neljällä ytimellä tasan kahdessa tunnissa.

Myös n=30 pitäsi olla laskettavissa muutamassa päivässä neljällä ytimellä ja paljon useammalla muutamassa tunnissa.

Lue lisää

Laskin n=30 kuudella ytimellä n. 36 tunnissa.

n=30: 14932578106956476

Kokeilen joskus myöhemmin nopeampaa tapaa esilasketuilla 7 ja 8 pituisilla palikoilla.

Anonyymi kirjoitti:

Laskin n=30 kuudella ytimellä n. 36 tunnissa.

n=30: 14932578106956476

Kokeilen joskus myöhemmin nopeampaa tapaa esilasketuilla 7 ja 8 pituisilla palikoilla.

Lue lisää

Nopealla tavalla sain laskettua saman tuloksen kahdella ytimellä 8 tunnissa. Paljon yli 10 kertainen nopeus.

Samalla ohjelmalla pitäisi onnistua myös n=31. Aikaa kulunee hiukan vähemmän kuin n=32 laskuun.

Anonyymi kirjoitti:

Nopealla tavalla sain laskettua saman tuloksen kahdella ytimellä 8 tunnissa. Paljon yli 10 kertainen nopeus.

Samalla ohjelmalla pitäisi onnistua myös n=31. Aikaa kulunee hiukan vähemmän kuin n=32 laskuun.

Lue lisää

Aikaa meni n=31 laskuun kahdella ytimellä alle 16 h.

n=31: 51030504080033096

Suuruusluokka näyttäisi olevan oikea. Pitää joskus kokeilla laskemalla vaikkapa vain 100 satunnaisnäytettä 16 luvun valinnasta 31:sta. Ilman peilikuvia 41409225 kpl ((16!/(8!*8!))*(15!/(8!*7!)/2)). Aivan sama miten noiden yksittäisten alkeistapausten kombinaatiot laskee, kunhan laskee oikein ja saa saman tuloksen kuin muilla tavoilla.

20: 241559918
21: 675603568
22: 8723487720
23: 22850057800
24: 285146572432
25: 859834538938
26: 8276479696196
27: 32343039694056
28: 429691823372130
29: 1133076110416228
30: 14932578106956476
31: 51030504080033096
32: 572923683659419818