A137613

22.5.2022

Lueskelin Wikipedia-artikkelia alku­lukuja tuotta­vista kaavoista, ja kohtasin sen loppu­puolella tämän kaavan:

a[1] = 7,
a[n+1] = a[n] + GCD(n+1, a[n])

Tämän jonon alki­oiden ero­tuksina on alku­lukuja – muttei kui­ten­kaan järjes­tyk­sessä, ja välissä on paljon ykkösiä. Jonon OEIS-numero on A132199, ja kun siitä poistaa ykköset saadaan jono A137613.

na[n]a[n+1]−a[n]
171
281
391
4105
5153
6181
7191
8201
9211
102211
11333
12361
13371
14381
15391

Tämä jono on minusta yksin­kertai­suudes­saan tosi kieh­tova, mutta alku­luku­ohjelmana se on varsin teho­ton: jos laskee 1000 ensim­mäistä ero­tusta, vain 25 niistä ei ole 1, ja näistä yksi­toista on 3. Ja jono myös hidastuu nopeasti: ensim­mäi­sessä 10000 ero­tuksessa on 34 alku­lukua (joista 15 on 3), ensim­mäi­sessä sadassa tuhan­nessa ero­tuksessa on 47 alku­lukua (joista 21 on 3), ja ensim­mäi­sessä mil­joo­nassa ero­tuk­sessa on 79 alku­lukua (joista 33 on kol­mosia).

Tekniikka toimii myös, jos ensim­mäinen luku a[1] on 4; tämän ero­tusten OEIS-numero on A134734. Jonot ovat alun jälkeen tis­mal­leen samat: 7-alkui­sessa viisi ensim­mäistä lukua ovat 7, 8, 9, 10 ja 15, kun taas 4-alkui­sessa ensim­mäiset viisi ovat 4, 6, 9, 10 ja 15; koska jono las­ke­taan vain yh­dellä edel­tävällä luvulla, ovat jonot tämän jälkeen ident­tiset, ja niin ovat niiden ero­tukset­kin. Tärkein ero näiden kahden jonon välillä on, että 4-alkuisen jonon ero­tukset gene­roivat alku­luvun 2, joka puuttuu 7-alkui­sesta jonosta.

na[n]a[n+1]−a[n]
142
263
391
4105
5153
6181
7191
8201
9211
102211
11333
12361
13371
14381
15391

Kokeiluja muilla aloitus­luvuilla: