[viesti Survo-keskustelupalstalla (2001-2013)]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 29.8.2005 15:21 |
Jokapäiväisen aherruksen lomassa tekee silloin tällöin mieli seikkailla
(kokonais)lukujen kiintoisassa maailmassa.
Olen kertonut näistä harrastuksista tässä keskusteluryhmässä
aikaisemmin esim. otsikoilla
Pieni kesäpähkinä 2 (7/2004),
Kultaisen leikkauksen yleistäminen (4/2005),
Pisteistä Pythagoraan kolmioihin (6/2005).
Näillä jutuillani olen myös hitusen kartuttanut Neil Sloanen ylläpitämää
kokonaislukujonojen tietokantaa
http://www.research.att.com/~njas/sequences
jossa on tällä hetkellä yli 100'000 lukujonoa.
Vähän toista viikkoa sitten mieleeni juolahti - syystä jota en osaa
selittää - tarkastella yksinkertaisen tuntuista ongelmaa, joka johti
seuraavaan lukujonoon
3 5 8 14 23 38 44 53 59 62 68 74 83 122 134 ...
Enpä usko, että kukaan keksii heti, miten lukujono jatkuu, sillä
yllätyksekseni jonoa ei löytynyt Sloanen ensyklopdiasta, vaikka
sinne näyttää pesiytyneen hyvinkin kummallisia otuksia.
Yritän selittää lukujonon syntyä koskevan säännön niin, että
vähäisilläkin matematiikan taidoilla ymmärtää juonen:
Myöhemmin ilmenevästä syystä ensimmäinen luku on 3.
Lähdetään etsimään seuraavaa lukua vaatimalla, että jos luku jaetaan
kolmella, jakojäännökseksi on tultava 2 tai suurempi luku. Luku 4 ei
siis kelpaa, koska 4=1*3+1 eli jakojäännös on 1. Luku 5 jo kelpaa,
koska 5=1*3+2 eli kun 5 jaetaan kolmella, jakojäännökseksi saadaan 2.
Lukujono alkaa siis luvuilla
3 5.
Nyt etsitään seuraavaksi lukua, jonka jakojäännös sekä 3:n että 5:n
suhteen on vähintään 2.
6 ei kelpaa: jakojäännös 3:n suhteen on 0 (jako menee tasan).
7 ei kelpaa: jakojäännös 3:n suhteen on 1.
8 kelpaa: jakojäännös 3:n suhteen on 2 ja 5:n suhteen 3.
Koossa ovat siis luvut
3 5 8.
Nyt otan käyttöön (selityksen lyhentämiseksi) jakojäännösfunktion mod.
mod(a,b) tarkoittaa jakojäännöstä, kun kokonaisluku a jaetaan
kokonaisluvulla b. Tämä funktio on pitkään ollut mukana Survon editori-
aalisessa laskennassa. Esim. mod(8,3)=2, mod(8,4)=0, mod(1000,7)=6.
Seuraavaa lukua n etsittäessä vaaditaan, että kaikki jakojäännökset
aikaisempien lukujen suhteen ovat vähintään kakkosia eli siis
mod(n,3)>1, mod(n,5)>1, mod(n,8)>1.
9 ei kelpaa: mod(9,3)=0,
10 ei kelpaa: mod(10,3)=1,
11 ei kelpaa: mod(11,5)=1,
12 ei kelpaa: mod(12,3)=0,
13 ei kelpaa: mod(13,3)=1,
14 kelpaa: mod(14,3)=2, mod(14,5)=4, mod(14,8)=6.
Säännöllä "seuraava luku on pienin sellainen, jonka jakojäännös
edellisten suhteen on vähintään 2" päädytään siis lukujonoon, jonka
alku on edellä mainitsemani ja jolle annan nimen A(2)
A(2): 3 5 8 14 23 38 44 53 59 62 68 74 83 122 134 ...
Miksi aloitettiin luvusta 3?
Jos samaa temppua yritetään pienemmillä lähtöluvuilla 1 tai 2, kumpikaan
ei anna mitään, koska mod(n,1)=0 kaikilla kokonaisluvuilla n ja
vastaavasti mod(n,2) on joko 0 tai 1 eli koskaan ei saataisi edes
kakkosta jakojäännökseksi.
Tarkastelu yleistetään määrittelemällä lukujono A(k), k=0,1,2,3,...
siten, että ensimmäinen jonon luku on k+1 ja seuraavat määräytyvät
säännöllä: "Etsitään seuraava edellisiä suurempi luku niin, että sen
jakojäännös kunkin edellisen luvun suhteen on ainakin k".
Havaitaan helposti, että
A(0): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...
eli saadaan luonnolliset luvut eli kaikki kokonaisluvut 1:stä
eteenpäin.
Yhtä helposti (tai ainakin melkein) todetaan, että
A(1): 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 ...
eli nyt saadaan kaikki alkuluvut (jaottomat luvut).
Siten A(2) näyttäisi olevan tässä mielessä johdonmukainen "yleistys"
alkuluvuille, vaikka eiväthän sen jäsenet
A(2): 3 5 8 14 23 38 44 53 59 62 68 74 83 122 134 ...
ole pelkästään alkulukuja. Ne ovat vain keskenään huonosti jaollisia,
koska otettiinpa jonosta mitkä kaksi lukua m ja n tahansa niin aina
mod(m,n) on vähintään 2.
Tähän asti voisi kuvitella, että A(2)-lukuja olisi vain äärellinen
määrä N eli jono olisi
a(1)=3, a(2)=5, a(3)=8, ..., a(N)
missä sekä N että a(N) olisivatkin todella "mielenkiintoisia" lukuja.
Kuvitelma on helppo osoittaa paikkansapitämättömäksi samaan tapaan,
jolla todistetaan, että alkulukuja riittää loputtomiin.
Muodostetaan luku
b = a(1)*a(2)*...*a(N)+2
eli oletettujen kaikkien A(2)-lukujen tulo ja lisätään siihen 2.
Koska tuo tulo on tasan jaollinen kaikilla luvuilla a(1),a(2),...,a(N),
niin väistämättä luvun b jakojäännös kaikkien lukujen a(1),a(2),...,a(N)
suhteen on 2 eli luvun b ollessa lukua a(N) suurempi viimeistään se
kelpaisi jatkoksi jonoon, ellei (kuten yleensä) jokin aikaisempi
kelpaa. Siis lukuun a(N) päättynyttä jonoa saatetaankin jatkaa, mikä
osoittaa äärellisyysoletuksen vääräksi.
Vastaavasti näytetään, että kaikki muutkin A(k)-jonot ovat äärettömiä.
Havaittuani, että A(2)-jonoa ei ole Sloanen kokoelmassa, lähetin siitä
kuvauksen hänelle. Kirjoitin tätä ennen ripeästi alustavan selostuksen,
joka löytyy Survon sivuilta nimellä
http://www.survo.fi/papers/resseq.pdf
ja johon viittasin jonon kuvauksessa. Sloane vastasi alle kahden tunnin
sisällä ilmoittaen lukujonon nyt löytyvän kokoelmasta tunnuksella
A109022 ja pyysi toimittamaan lisää jonoja tarkoittaen lukujonoja
A(3),A(4),A(5) jne.
Lähetinkin pari päivää sitten jonot A(k), k=3,4,...,10 ja ne ovat
nyt kokoelmassa tunnuksin A109328-A109335.
Se, ettei mainittuja lukujonoja ennen ollut Sloanen ensyklopediassa,
ei tietenkään sulje pois mahdollisuutta, että kyseisiä lukujonoja
on käsitelty jossain yhteydessä aikaisemmin, koska ne ovat
määrittelyltään yksinkertaisia ja sekä luonnolliset luvut että
alkuluvut ovat A(k)-jonojen erikoistapauksia.
Jäädessäni odottamaan palautetta lähinnä lukuteoreetikoilta olen
hieman yrittänyt tutkiskella A(k)-lukujen käyttäytymistä.
Olkoon L(k,n) niiden A(k)-lukujen määrä, jotka eivät suurudeltaan
ylitä lukua n.
Alkuluvuista A(1) tiedetään (hieman epätäsmällisesti sanottuna),
että, mitä suurempi n on, sitä lähempänä L(1,n) on lukua n/log(n).
Puhtaasti määritelmän perusteella on syytä odottaa, että lukuja
A(k) suhteessa alkulukuihin A(1) on sitä vähemmän, mitä suurempi
k on.
Työhypoteesinani on, että asymptoottisesti (eli luvun n kasvaessa
kohti ääretöntä) L(k,n)/L(1,n) -> c(k), missä luvut c(k), k=2,3,...
ovat vakioita ja 1 > c(2) > c(3) > ...
Olen yrittänyt saada käsityksen tämän hypoteesin pätevyydestä
laskemalla A(k)-jonoja ja lukuja L(k,n) vähitellen yhä suuremmilla
n-arvoilla.
Aluksi tein Survoon C-modulin, joka muodosti A(k)-lukuja suoraan
määritelmän mukaisesti ja jota hieman parantelin kokemusten
perusteella. Keskityin tapaukseen k=2 ja sain (varakoneellani)
noin kolmen päivän laskennan jälkeen tulokset arvoon n=18'000'000
(siis 18 miljoonaa) asti. Tämän perusteella tuntui siltä, että suhde
L(2,n)/L(1,n) lähestyy vakiota c(2), joka on suuruusluokkaa 0.6.
Tiesin alunperin, ettei tämä ollut nopea tapa saada tuloksia ja
kyllästyttyäni ohjelman hitauteen laadin yksinkertaisen seulonta-
periaatteeseen perustuvan C-modulin, joka laskee muutamassa minuutissa
luvut L(2,n) miljoonan välein lukuun n=2'000'000'000 (2 miljardia)
asti ja yleisesti luvut L(k,n) vielä sitä nopeammin mitä suurempi k on.
Tarkistuksena laskin samalla ohjelmalla alkulukujen määräksi
(alle viidessä minuutissa) L(1,2'000'000'000)=98'222'287
mikä pitää yhtä verkosta löytyvien alkulukutietojen esim.
http://www.ieeta.pt/~tos/primes.html
kanssa.
Vaikka seulontaohjelmani ei varmasti ole paras mahdollinen nopeuden
suhteen, se on kuitenkin noin 100'000-kertainen alkuperäiseen, suoraan
määritelmään perustuvaan (mod-arvoja edellisiin lukuihin nähden
laskevaan) ohjelmaan. Tämä on jälleen osoitus siitä, miten
dramaattisesti laskentanopeus voi kasvaa, kun hiukan miettii
miten laskee.
Seulontatekniikat tunnetaan jo antiikin ajoilta (Eratostheneen nimellä).
Näytän esimerkkinä miten seulomalla käsipelillä saadaan alle 100
olevat A(2)-luvut 3 5 8 14 23 38 44 53 59 62 68 74 83.
Muodostetaan taulukko
\ 0 1 2 3 4 5 6 7 8 9
0 - - - + x x x x x x
1 x x x x x x x x x x
2 x x x x x x x x x x
3 x x x x x x x x x x
4 x x x x x x x x x x
5 x x x x x x x x x x
6 x x x x x x x x x x
7 x x x x x x x x x x
8 x x x x x x x x x x
9 x x x x x x x x x x
jossa esim. rivin 2 ja sarakkeen 7 solu vastaa lukua 27.
Luvut 0,1,2 on valmiiksi poistettu jonosta merkillä -.
Kolmonen on merkitty plussalla jonoon kuuluvaksi.
Seulonta aloitetaan siitä poistamalla (merkillä -) kaikki ne luvut n,
joille mod(n,3)<2, jolloin taulukko tulee muotoon
\ 0 1 2 3 4 5 6 7 8 9
0 - - - + - + - - x -
1 - x - - x - - x - -
2 x - - x - - x - - x
3 - - x - - x - - x -
4 - x - - x - - x - -
5 x - - x - - x - - x
6 - - x - - x - - x -
7 - x - - x - - x - -
8 x - - x - - x - - x
9 - - x - - x - - x -
Luvut ovat huvenneet noin kolmasosaan ja luvun 5 ollessa ensimmäinen
säilyneistä se on merkitty plussalla jonoon kuuluvaksi.
Nyt tulee poistaa kaikki ne luvut, joille mod(n,5)<2 eli numeroihin
0,1,5 ja 6 päättyvät:
\ 0 1 2 3 4 5 6 7 8 9
0 - - - + - + - - + -
1 - - - - x - - x - -
2 - - - x - - - - - x
3 - - x - - - - - x -
4 - - - - x - - x - -
5 - - - x - - - - - x
6 - - x - - - - - x -
7 - - - - x - - x - -
8 - - - x - - - - - x
9 - - x - - - - - x -
Siis luku 8 liittyy jonoon ja poistetaan luvut n joille mod(n,8)<2:
\ 0 1 2 3 4 5 6 7 8 9
0 - - - + - + - - + -
1 - - - - + - - - - -
2 - - - x - - - - - x
3 - - - - - - - - x -
4 - - - - x - - x - -
5 - - - x - - - - - x
6 - - x - - - - - x -
7 - - - - x - - x - -
8 - - - x - - - - - -
9 - - x - - - - - x -
Luku 14 on seuraava hyväksytty ja poistetaan luvut n joille mod(n,14)<2:
\ 0 1 2 3 4 5 6 7 8 9
0 - - - + - + - - + -
1 - - - - + - - - - -
2 - - - + - - - - - -
3 - - - - - - - - x -
4 - - - - x - - x - -
5 - - - x - - - - - x
6 - - x - - - - - x -
7 - - - - x - - x - -
8 - - - x - - - - - -
9 - - x - - - - - - -
Siis 23 kelpaa ja tehdään sitä vastaavat poistot:
\ 0 1 2 3 4 5 6 7 8 9
0 - - - + - + - - + -
1 - - - - + - - - - -
2 - - - + - - - - - -
3 - - - - - - - - + -
4 - - - - x - - - - -
5 - - - x - - - - - x
6 - - x - - - - - x -
7 - - - - x - - x - -
8 - - - x - - - - - -
9 - - - - - - - - - -
Nyt hypätään jo lukuun 38 ja poistetaan sen mukaisesti:
\ 0 1 2 3 4 5 6 7 8 9
0 - - - + - + - - + -
1 - - - - + - - - - -
2 - - - + - - - - - -
3 - - - - - - - - + -
4 - - - - + - - - - -
5 - - - x - - - - - x
6 - - x - - - - - x -
7 - - - - x - - - - -
8 - - - x - - - - - -
9 - - - - - - - - - -
Päästään lukuun 44, mutta sen kerrannaiset (paitsi 88) ovat jo niin
suuria, ettei enempää tarvitse tehdä.
Taulukkoon ovat jääneet luvut 3 5 8 14 23 38 44 53 59 63 68 74 83
kuten pitikin.
Seulontamenettelyn nopeus perustuu siihen, ettei tarvita lainkaan kerto-
ja jakolaskua. Riittää pelkkä yhteenlasku (peräkkäisiin kerrannaisiin)
ja taulukon ylläpito.
Jotta päästään suuriin n-arvoihin, taulukon tulee olla mahdollisimman
tiivis. Tällöin varataan kutakin kokonaislukua kohti pelkästään 1 bitti,
joita tavussa on 8 kpl.
Ohjelmoinnissa joudutaan siis harrastamaan bittikohtaista työskentelyä,
johon en aikaisemmin ole joutunut menemään, mutta C-kielellä ja Survon
avustuksella tällaisetkin hommat on kätevä toteuttaa.
Koneessani on keskusmuistia 512 megatavua, mikä tarkoittaa teoriassa,
että olisi mahdollista ulottaa n jopa lähes 4 miljardiin. Muistia on
käytettävissä sovellusohjelmille kuitenkin koneellani vain hieman yli
300 megatavua, jolloin tyydyin 2 miljardiin.
Tässä on taulukoituna saamani L(k,n)-luvut ja niiden suhteet, kun
n=2*10^9:
k L(k,n) L(k,n)/L(1,n)
1 98222287 1
2 56472931 0.5750
3 34281318 0.3490
4 28159808 0.2867
5 19810400 0.2017
6 18346769 0.1868
7 14786395 0.1505
8 13281120 0.1352
9 11429212 0.1164
10 10921870 0.1112
Suhdeluvut ovat vielä varsin karkeita alalikiarvoja luvuille c(k).
Olen pyrkinyt mallintamaan suhdelukuja r(k,n)=L(k,n)/L(1,n), kun k=2.
Lähdin muotoa
M1: r(2,n)=c(2)+d(2)/log(n)
olevasta mallista, joka on selvästi parempi kuin muut kokeilemani
mallityypit. Tätä mallia olen saattanut edelleen (pelkästään ESTIMATE-
operaatiolla tekemien numeeristen kokeilujen perusteella ja tarkastellen
erityisesti mallin kykyä ennustaa alkupään "havaintojen" perusteella
viimeisiä arvoja) yleistää muotoihin
M2: r(2,n)=a-b/log(log(n))
M3: r(2,n)=a-b*log(log(n))/log(n)
M4: r(2,n)=a-b*log(log(n))*log(log(log(n)))/log(n)
Olen estimoinut parametrit a,b ja niiden keskivirheet s(a),s(b)
arvoilla r(2,n), n=10^6(10^6)10^9 (siis tuhat havaintoa) ja
sitten mallien antamat ennusteet arvoilla n=10^9+10^6(10^6)2*10^9
(siis tuhannelle viimeiselle havainnolle).
Alla olevasta taulukosta nähdään ennustevirheen keskiarvo ja hajonta
sekä suurin että pienin ennustevirhe.
Viimeinen malli on tässä suhteessa selvästi paras, mutta mikään
malleista ei ole "oikea". Mm. ennusteet ovat kaikki alle todellisten
arvojen.
Ennustevirhe
a s(a) b s(b) k.arvo hajonta min max
M1 0.6548 0.00025 1.71026 0.0049 0.000747 0.000170 0.000415 0.001031
M2 0.8306 0.00063 0.78594 0.0014 0.000606 0.000137 0.000334 0.000838
M3 0.7017 0.00028 0.89078 0.0012 0.000520 0.000119 0.000283 0.000722
M4 0.8326 0.00013 1.60882 0.0008 0.000061 0.000014 0.000021 0.000093
Jos parametrit a ja b estimoidaan edellä ennusteen kohteena olleiden
1000 viimeisen havaintoarvon perusteella mallin M1 a-parametri kasvaa
2.7% mutta mallin M4 vain 0.4%.
Parhaan mallin M4 perusteella c(2) näyttäisi olevan siis jopa
suuruusluokkaa 0.85 mutta suhde r(2,n) kasvaisi erittäin hitaasti.
Mallin M4 perusteella esim.
r(2,10^12)=0.6012
r(2,10^15)=0.6246
r(2,10^100)=0.7708
r(2,10^200)=0.7966
r(2,10^300)=0.8070
Esittämäni arviot (lukumääräisiä laskelmia lukuunottamatta) ovat
pelkkiä arvauksia empiiriseltä pohjalta ilman minkäänlaista
käsitystä siitä, miten A(k)-lukuja voisi tutkia lukuteoreettisesti.
Näihin "tuloksiin" tulee siis suhtautua suurella epäilyllä.
Olisin iloinen, jos jostain ilmaantuisi lisävalaistusta asiaan.
-Seppo Mustonen
| Vastaukset: |
|---|
Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!