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.

n	a[n]	a[n+1]−a[n]
1	7	1
2	8	1
3	9	1
4	10	5
5	15	3
6	18	1
7	19	1
8	20	1
9	21	1
10	22	11
11	33	3
12	36	1
13	37	1
14	38	1
15	39	1

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.

n	a[n]	a[n+1]−a[n]
1	4	2
2	6	3
3	9	1
4	10	5
5	15	3
6	18	1
7	19	1
8	20	1
9	21	1
10	22	11
11	33	3
12	36	1
13	37	1
14	38	1
15	39	1

Kokeiluja muilla aloitus­luvuilla:

• a_[1] = 1: erotukset ovat pelkkiä ykkösiä.
• a_[1] = 2: ensimmäinen erotus on 2, tämän jälkeen vain ykkösiä.
• a_[1] = 3: pelkkiä ykkösiä.
• a_[1] = 4: tuotokset: 2, 3, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, ..., 23, 3, 1, ..., 47, 3, 1, 5, 3, 1, ..., 101, 3, 1, 1, 7, 1, .... 233, 3, 1, ...,
  Ykköset poistettuna: 2, 3, 5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 941, 3, 7, ...
• a_[1] = 5: tuotokset: 1, 3, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, ...
• a_[1] = 6: tuotokset: 2, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, ...
• a_[1] = 7: tuotokset: 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, ...
• a_[1] = 8: ensimmäinen huomattavasti erilainen: 2, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 13, 1, 5, 1, ..., 29, 3, 1, ..., 59, 3, 1, 1, 7, 1, 5, 3, ..., 131, 3, 1, ..., 263, 3, 1, ..., 17, 3, 1, 5, 3, 1, ..., 19, 1, ..., 569, 3, 1, ..., 17, 3, 1, ..., 13, 1, 1, 7, 1, 5, 3, ...
  Pelkät alkuluvut, ykköset poistettuna: 2, 7, 13, 5, 29, 3, 59, 3, 7, 5, 3, 131, 3, 263, 3, 17, 3, 5, 3, 19, 569, 3, 17, 3, 13, 7, 5, 3, ...
• a_[1] = 9: tuotokset: 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 13, 1, 5, 1, ...
• a_[1] = 10: kuin 4, mutta "5, 3" puuttuu alusta: 2, 3, 1, 1, 1, 1, 1, 1, 1, 11, 3, 1, ..., 23, 3, 1, ..., 47, 3, 1, 5, 3, 1, ...
• a_[1] = 11: kuin 4 tai 7 tai 10, mutta alusta puuttuu 2 ja 5: 1, 3, 1, 1, 1, 1, 1, 1, 1, 11, 3, 1, ...
• a_[1] = 12: kuin 11, mutta alkaa 2, 1, 1, ... ja seuraava alkuluku on 11.
• a_[1] = 13: kuin 12, mutta alkaa 1, 1, 1, ... ja ensimmäinen alkuluku on 11.
• a_[1] = 14: kuin 8, mutta kuudes luku 7 puuttuu, ja kakkosen jälkeen ensimmäinen alkuluku on 13: 2, 1, 1, ..., 13, 1, 5, 1, ...
• a_[1] = 15: kuin 8, mutta ensimmäinen alkuluku on 13, pelkkiä ykkösiä siihen asti.
• a_[1] = 16: taas uudenlainen jono. Ykköset poistettuna: 2, 3, 17, 3, 5, 3, 41, 3, 83, 3, 167, 3, 5, 3, 11, 3, 353, 3, 7, 23, 3, 11, 3, 7, 5, 3, 761, 3, 1523, 3, 11, 3, 7, 5, 3, 37, 13, 3119, 3, 17, 3, ...
• a_[1] = 17: kuin 16, ilman ekaa kakkosta.
• a_[1] = 18: kuin 17, mutta alkaa kakkosella eikä kolmosella, sitten 17.
• a_[1] = 19: kuin 17, mutta alkaa 17:llä.
• a_[1] = 20: uusi jono, ykköset poisettuna: 2, 19, 37, 73, 5, 149, 3, 13, 311, 3, 7, 17, 3, 647, 3, 5, 3, 1301, 3, 19, ...
• a_[1] = 21: kuin 20, mutta ilman ensimmäistä kakkosta.
• a_[1] = 22: kuin 4, mutta 2:n ja 3:n jälkeen ensimmäinen alkuluku on 23.
• a_[1] = 23: kuin 22, mutta ilman ekaa kakkosta.
• a_[1] = 24: kuin 22, mutta ilman ekaa kolmosta.
• a_[1] = 25: kuin 22, mutta ilman ekaa kakkosta ja kolmosta.
• a_[1] = 26: kuin 8, mutta alkaa 2, 5, 29, 3, 59, 3, 7, 5, 3, 131, ...
• a_[1] = 27: kuin 26, ilman ekaa kakkosta.
• a_[1] = 28: kuin 26, mutta ekan vitosen sijalla on kolmonen.
• a_[1] = 29: kuin 28, ilman ekaa kakkosta: 3, 29, 3, 59, 3, 7, 5, 3, 131, ...
• a_[1] = 30: kuin 29, mutta ekan kolmosen sijasta kakkonen.
• a_[1] = 31: kuin 29, ilman ekaa kakkosta: 29, 3, 59, 3, 7, 5, 3, 131, ...
• a_[1] = 32: uusi jono, ykköset poistettuna: 2, 31, 61, 11, 131, 3, 263, 3, 17, 3, 5, 3, 19, 569, 3, 17, 3, 13, 7, 5, 3, 1181, 3, 17, 3, ...
• a_[1] = 33: kuin 32, ilman ekaa kakkosta.
• a_[1] = 34: kuin 16, mutta alkaa kunnolla 41:n kohdalla: 2, 3, 5, 3, 41, 3, 83, 3, 167, ...
• a_[1] = 35: kuin 34, ilman ekaa kakkosta.
• a_[1] = 36: kuin 34, mutta alkaa 2, 5, 3, 41, ...
• a_[1] = 37: kuin 16 ja 34, mutta alkaa 5, 3, 41, ...
• a_[1] = 38: kuin 20: 2, 37, 73, 5, 149, 3, 13, 311, ...
• a_[1] = 39: kuin 20 ja 38, mutta alkaa 37:stä.
• a_[1] = 40: kuin 16, alkaa 2, 3, 41, 3, 83, ...
• a_[1] = 41: kuin 40, ilman ekaa kakkosta.
• a_[1] = 42: kuin 41, ekan kolmosen sijaan kakkonen.
• a_[1] = 43: kuin 16 ja 40, alkaen 41:stä.
• a_[1] = 44: uusi jono, ykköset poistettuna: 2, 43, 5, 89, 3, 179, 3, 359, 3, 719, 3, 1439, 3, 2879, 3, 13, 29, 3, 5801, 3, 41, 3, 5, 3, 61, 7, ...
• a_[1] = 45: kuin 44, ilman ekaa kakkosta.
• a_[1] = 46: kuin 4, mutta alkaa 2, 3, 47, 3, 5, 3, 101, ...
• a_[1] = 47: kuin 46, ilman ekaa kakkosta.
• a_[1] = 48: kuin 46, ilman ekaa kolmosta: 2, 47, 3, 5, ...
• a_[1] = 49: kuin 46, alkaen suoraan 47:stä.
• a_[1] = 50: kuin 8, mutta alkaa 2, 7, 5, 59, 3, 7, 5, 3, 131, ...