Keskustelu: Yleinen keskustelu: Hupipulma: Alkulukujen ketjuttaminen

Tässäpä pieni pulma, jota voi tutkia myös ohjelmallisesti. Tehtävä ei ole erityisen vaikeaksi tarkoitettu.

Määritellään ensin kahden luvun antama ketjutettu jono. Lukujen ketjuttaminen (10-kantaisessa esityksessä) tarkoittakoon yksinkertaisesti sitä, että niiden numerot laitetaan peräkkäin ja näin muodostetaan uusi luku. Kahden luvun a₁ ja a₂ muodostama ketjutettu jono on lukujono, jonka jokainen a₂:n jälkeinen termi a_n on jonon termien a_n-2 ja a_n-1 ketjutus tässä järjestyksessä.

Siten luvut 1 ja 2 tuottavat jonon, joka alkaa

1, 2, 12, 212, 12212, 21212212, 1221221212212, ...

Esimerkin neljäs termi 212 on siis syntynyt edeltävistä termeistä 2 ja 12, jotka asetetaan peräkkäin. Ketjutuksessa tulee ensin aina aiemmin jonossa esiintynyt luku, ja siten kolmas termi on nimenomaan 12, eikä 21.

Nyt itse kysymys.

Jos aloitamme ketjun kahdesta alkuluvusta, mikä on pisin mahdollinen peräkkäinen ketju alkulukuja, joka näin voi muodostua?

Muistamme, että 1 ei ole alkuluku, vaan yksikkö. Siispä summaltaan pienin alkulukupari on 2 ja 2, mutta se antaa seuraavana terminä luvun 22, joka ei ole alkuluku. Luvut 2 ja 3 lähtevät paremmin alkuun. Myös 23 on alkuluku, mutta seuraava termi, 3:n ja 23:n ketjutus 323 onkin 17*19. Nyt alkulukuja oli kolme kappaletta.

Siis pari (2,2) tuottaa kaksi alkulukua (2 ja 2 itse) ja pari (2,3) antaa kolmen luvun pituisen alkulukujonon. Taitaapa joku pystyä parempaan...

Väittäisin että mitään valtaisan pitkiä tuosta ei ole mahdollista saada koska 3 jaolliset vaanii aina nurkan takana.

Eli käytännössähän meillä on neljä mahdollista alkulukuparia (n on kokonaisluku)

1. 3n+1 ja 3n+1
2. 3n+2 ja 3n+1
3. 3n+1 ja 3n+2 sekä
4. 3n+2 ja 3n+2

2. tai 3. vaihtoehdossa ketjutuksen tulos on suoraan 3 jaollinen.

1. tai 4. vaihtoehossa taas ensimmäinen ketjutuksen tulos ei ole 3 jaollinen, mutta toinen jo on.

Tervehdys

Olipa vekkuli pohtimisehdotus. Tehtävänasettelusta en kuitenkaan
ymmärtänyt, pitääkö kahden esimmäisen alkuluvun olla alle 10.
Siis jotkin luvuista 2, 3, 5, tai 7
Vai voiko ensimmäinen lukupari olla yli 10.
Siis 11, 13, 17, 19, 23 jne.
Jolloin lähtötilanne olisi esim:
13, 19, 1319, 191319 jne
Olen joskun tehnyt ohjelman, mikä tuottaa alkulukuja, mutta tuota
äskeistä lukujonoa en ole tsekannut.

Terveisin
Antti

Niin, tosiaan edelliseen postaukseeni lisäyksenä on tietenkin tämä mahdollisuus, jossa jompi kumpi sarjan "siemenluvuista" on 3.

5. 3 ja n+1 => n+1, n+2, n+3
6. 3 ja n+2 => n+2, n+1, n+3
7. n+1 ja 3 => n+1, n+1, n+2, n+3
8. n+2 ja 3 => n+2, n+2, n+1, n+3

Teoriassa on siis mahdollista saada korkeintaan kolme alkulukuyhdistelmää jos jälkimmäinen siemenluku on 3.

5, 3, 53, 353 ja 53353 on siis yksi pisimmistä mahdollisista sarjoista.

Takerruin tähän edelleen minäkin. Tuo 1319 on
alkuluku, mutta 191319 on jaollinen kolmella.

Aloittavien lukujen ei tarvitse olla alle 10. Vaaditaan kuitenkin, että ne ovat alkulukuja. Siis vaikkapa 11 ja 13 käyvät.

11
13
1113 = 3*7*53

Eipä päässyt pitkälle!

Järjestystä ei myöskään ole rajoitettu suuruusjärjestykseen. Siispä 13 ja 11 antavat:

13
11
1311 = 3*19*23

On varmasti aika selvää, että kaksi yhtä suurta lukua ei johda mihinkään. Niiden ketjutus on aina jaollinen 11:llä, 101:llä, tai jollain vastaavan muotoisella luvulla, joka riippuu alkuluvun (esityksen) pituudesta.

No, Grez näyttääkin olevan varsin hyvin selvillä asioista. Minulta on vielä myöhemmin luvassa pieni yhteenveto asiasta.

No niin, viisi on todellakin pisin mahdollinen jono ja se johtuu kolmella jaollisuudesta.

Tunnetusti jokainen luku on joko jaollinen kolmella tai antaa jakojäännöksen 1 tai 2, kun se jaetaan kolmella. Ainoa alkuluku, joka on jaollinen kolmella, on kolme itse.

Koska vain ketjun kaksi ensimmäistä jäsentä voi olla < 10, katkeaa ketju ainakin tapauksessa, jossa syntyy kolmella jaollinen termi myöhemmässä vaiheessa.

Aina kun uusi termi muodostetaan, saadaan se kertomalla jokin edellinen termi kymmenen potenssilla (riippuu toisen termin pituudesta) ja summaamalla tämä tulo ja edellinen termi. Aina kun luku kerrotaan kymmenen potenssilla, sen jakojäännös kolmen suhteen ei muutu miksikään (helppo todeta miksi näin on, jos osaa lukuteroain alkeet - muuten hyvä pikku harjoitus tarkistaa).

Siispä jakojäännökset ketjussa menevät kuten Grez yllä esitti. Vain jos aloitetaan jakojäännöksillä 1 ja 0, saadaan yhteensä viiden mittainen ketju ennen kuin kolmella jaollinen termi syntyy väistämättä.

1 0 1+0=1 0+1=1 1+1=2 1+2=3 <- kuudes termi, johon katkeaa

Pisimmät mahdolliset ketjut lähtevät siis parista (p,3) ja jo näytetty (5,3) on pienin, joka tuottaa viiden pituisen jonon. Toisen termin on tietenkin pakko olla kolme, koska se on ainoa kolmella jaollinen alkuluku.

Toinen parin alkuluku voi olla paljonkin kolmea suurempi. En osaa sanoa, onko mahdollisia ratkaisuja ääretön määrä. Joku muu saa tehdä ne konjektuurit :-)

Kopeekka kirjoitti:

Vain jos aloitetaan jakojäännöksillä 1 ja 0, saadaan yhteensä viiden mittainen ketju ennen kuin kolmella jaollinen termi syntyy väistämättä.

Kyllä myös kolmen jakojäännöksillä 2 ja 0 alkava ketju saadaan viiden mittainen ketju, kuten esimerkkini 5, 3, 53, 353, 53353 mielestäni varsin selkeästi todisti.

Tuo kolmella jaollisuuspäättely menee tässä tapauksessa paljon helpommaksi, jos käyttää apuna sitä vanhaa peruskoulussa opetettua kikkaa, joka kertoo, että luku on kolmella jaollinen, jos sen numeroiden summa on kolmella jaollinen. Tällöin ei tarvitse todistusvaiheessa miettiä millä kymmenen potenssilla luku kerrotaan vaan voi suoraan laskea testilukujen jakojäännöksiä yhteen. Tuo kikka taitaa kuitenkin juurikin juontua mainitusta seikasta, että jakojäännös kolmen suhteen ei muutu kerrottaessa kymmenen potenssilla (tätä seikkaa en ollut ennen huomannutkaan, mutta noihan siinä tosiaan käy).

Esim. lukujen summien jakojäännöksillä miettiessä homma menisi näin.

13 -> 1+3           = 4  = (3*n)    + 1 => ei jaollinen kolmella
17 -> 1+7           = 8  = (3*m)    + 2 => ei jaollinen kolmella
1317 -> (1+3)+(1+7)      = (3*(n+m))+ 3 => jaollinen kolmella

Tuosta näkee suoraan, että laskenta voidaan aloittaa pelkästään tutkimalla kahden ensimmäisen luvun summien jakojäännöksi. Pisimmät jonot voidaan siis etsiä tutkimalla jakojäännösten lähtöarvoja [0,2]x[0,2] ja etsimällä pisintä jonoa, joissa ei esiinny kolmella jaollista lukua. Pisimmän jonon ratkaisujoukko näyttää olevan siis sellainen, jossa toinen lähtöarvoista on 3 ja toisen numeroiden summan jakojäännös on 2. Tuon perusteella sanoisin, että ratkaisuja on ääretön määrä olettaen (varsin perustellusti), että erilaisia alkulukuja, joilla numeroiden summan kolmen jakojäännös on 2, on ääretön määrä.

Grez, kiitos oikaisusta. FooBat myös kirjoitti asiaa. Olipa vähän huolimaton esitys. Roikutan nyt hetken päätä häpeässä, kuten one says in English.