1 UVOD
Zapredja spadajo med najbolj raziskovane objekte v
matematiki. Prav tako imajo velik pomen v (teoretičnem)
računalništvu, še zlasti pri analizi algoritmov, teoriji
izračunljivosti in zahtevnosti.
Z zaporedjem lahko opišemo časovno ali prostorsko
zahtevnost algoritma, pri čemer n-ti člen zaporedja po-
daja zahtevnost algoritma pri vhodnih podatkih velikosti
n [1]. Zaporedje lahko opišemo z rodovno funkcijo,
področje, ki se s tem poglobljeno ukvarja, se imenuje
analitična kombinatorika [2].
V nadaljevanju se bomo ukvarjali s posplošeno obliko
enega najbolj znanih zaporedij, tj. z zaporedjem potenc
reda k prvih n naravnih števil. Če je k celo število, so
tudi vsi členi takšnega zaporedja cela števila. V članku
bomo namenili pozornost algoritmom za izračun vsote
takšnega zaporedja za poljubna k in n.
Najbolj znano in tudi enostavno je verjetno zaporedje
naravnih števil 1, 2, 3, 4, 5 . . . , katerega vsoto do poljub-
Prejet 4. april, 2013
Odobren 15. april, 2013
nega n ∈ N izračunamo po dobro znani formuli [3]:
n∑
i=1
i =
n(n+ 1)
2
. (1)
Pri zaporednih n ∈ N delne vsote
∑n
i=1 i tvorijo novo
zapredje 1, 3, 6, 10, 15, . . ., tako imenovanih trikotniških
števil. Ta pomenijo število objektov, ki jih lahko razpo-
redimo v obliko enakostraničnega trikotnika (glej Sliko
1).
Slika 1: Trikotniška števila 1, 3, 6 in 10
Formula (1) koristi pri analizi algoritmov. Na primer:
preštejmo, kolikokrat se izvede tretja vrstica v nasle-
dnjem algoritmu.
1 f o r i = 1 to n do
2 f o r j = 1 to i do
3 p r i n t ( i + j )
Obe zanki for preprosto spremenimo v vsoti in ju
seštejemo:
n∑
i=1
i∑
j=1
1 =
n∑
i=1
i =
n(n+ 1)
2
.
Dobro znano je tudi zaporedje kvadratov naravnih
števil oz. kvadratnih števil, tj. 1, 4, 9, 16, 25, . . ., ki poda-
jajo število objektov, razmeščenih v obliko kvadrata (glej
sliko 2). Vsoto prvih n kvadratnih števil izračunamo po
formuli:
n∑
i=1
i2 =
n(n+ 1)(2n+ 1)
6
. (2)
ALGORITMI ZA VSOTO POTENC NARAVNIH ŠTEVIL 35
Slika 2: Kvadratna števila 1, 4, 9 in 16
Nadalje, za zaporedne n ∈ N vsote po enačbi (2)
tvorijo novo zaporedje 1, 5, 14, 30, 55, . . . tako imeno-
vanih kvadratnih piramidnih števil, ki podajajo število
objektov, razmeščenih v obliko štiristrane piramide s
kvadratno osnovno ploskvijo (glej sliko 3). Prav tako n-
to kvadratno piramidno število npr. podaja število vseh
mogočih kvadratov v šahovnici velikosti n× n.
Slika 3: Kvadratna piramidna števila 1, 5, 14 in 30
V nadaljevanju članka se bomo ukvarjali s posplošeno
vrsto prvih n potenc reda k naravnih števil. Ta je
natančneje definirana s formulo:
Sk(n) =
n∑
i=1
ik = 1k + 2k + 3k + . . .+ nk. (3)
Vsote različnih redov so med seboj večkrat povezane
z enačbami, npr. S3(n) = (S1(n))2 (vsoti kubov zato
pravimo tudi kvadrat trikotniškega števila).
V analizi algoritmov pogosto srečamo tudi har-
monično vrsto:
H(n) = S−1(n) =
n∑
i=1
1
i
.
In ne nazadnje neskončna hiperharmonična vrsta, ki je v
matematični analizi znana kot Riemanova zeta funkcija:
ζ(s) = S−s(∞) =
∞∑
i=1
i−s.
V literaturi [4] zasledimo tudi posplošitev vrste (3), kjer
namesto zaporedja prvih n števil nastopa aritmetično
zaporedje (b+ ia).
V nadaljevanju članka bomo predstavili več algorit-
mov, ki za podana n in K izračunajo vse vsote Sk(n)
za k med 0 in K. Najprej predstavimo algoritma, ki
temeljita na definiciji Sk(n) (enačba (3)). Nato sledita
algoritma, zasnovana na rekurenčnih enačbah, ki Sk(n)
podajata kot vsoto predhodno izračunanih Si(n), kjer
je i < k. In kot zadnjega opišemo še algoritem, ki
ravno tako temelji na rekurenčni enačbi, le da za izračun
potrebuje vsak drugi člen. Na koncu opišemo še nekaj
mogočih optimizacij predstavljenih algoritmov.
2 IZRAČUN PO DEFINICIJI
Najprej si oglejmo algoritem, ki ga dobimo, če vsote
Sk(n) računamo neposredno po definiciji, podani s
formulo (3). Izračun po formuli je treba izvesti (K+1)-
krat; za vsak k od 0 do K. Implementacija samega
algoritma je preprosta. Potrebujemo dve zanki: prvo prek
parametra k in drugo za sam izračun vsote.
1 sums = [ n , 0 , 0 , . . . , 0 ]
2 f o r k = 1 to K do
3 sum = 1
4 f o r i = 2 to n do
5 sum += ik
6 sums [ k ] = sum
V vrstici 1 ustvarimo tabelo sums dolžine K + 1,
pri čemer prvi element tabele neposredno nastavimo na
S0(n) = n (seštevek n enic). Vrstica 5 vsebuje izračun
ik, ki ga po potrebi lahko implementiramo tudi z dodatno
zanko. Po izvedbi algoritma k-ti element tabele sums
vsebuje vrednost Sk(n).
Asimptotična časovna zahtevnost algoritma je
O(K2n), prostorska pa O(K). Pri tem smo upoštevali,
da operacija potenciranja zahteva O(k) množenj.
Opozorimo še, da gre pravzaprav za eksponentno
časovno zahtevnost, ker za zapis vhoda, tj. števil K in
n, potrebujemo le log(Kn) bitov.
3 OPTIMIZACIJA POTENCIRANJA
Operacijo potenciranja v algoritmu iz predhodnega raz-
delka je mogoče pohitriti. Vsote računamo postopoma
po naraščajočih k: potence reda k pa seveda ni treba
vsakič računati znova, ampak je mogoče k-to potenco
izračunati iz (k − 1)-ve. Velja namreč:
xk = x · xk−1.
Nov algoritem potrebuje dodaten prostor, tj. tabelo
velikosti n − 1 za hranjenje potenc reda k za vse
2, 3, 4, . . . , n. Implementacija je podobna algoritmu iz
predhodnega razdelka.
1 sums = [ n , 0 , 0 , . . . , 0 ]
2 pows = [ 2 , 3 , 4 , . . . , n ]
3 f o r k = 1 to K do
4 sum = 1
5 f o r i = 2 to n do
6 sum += pows [ i − 2]
7 pows [ i − 2] *= i
8 sums [ k ] = sum
V drugi vrstici se nahaja inicializacija tabele pows
(dolžine n − 1), ki hrani potence reda k. Dodana je še
vrstica 7, ki iz predhodne potence reda k − 1 izračuna
potenco reda k.
Asimptotična časovna zahtevnost algoritma je
O(Kn). S preprosto optimizacijo smo za red velikosti
zmanjšali časovno zahtevnost. Prostorska zahtevnost
algoritma je O(K + n).
4 ALTERNIRAJOČA VRSTA
V tem razdelku razvijemo algoritem za zadani problem
s pomočjo enačbe, ki med seboj povezuje vsote Si(n),
36 MIHELIČ
kjer je 0 ≤ i ≤ k. Enačba temelji na alternirajoči vrsti
členov Si(n). Najprej zapišimo enačbo, nato jo bomo
izpeljali:
k∑
i=0
(
k + 1
i
)
(−1)k−iSi(n) = nk+1. (4)
V nadaljevanju bomo večkrat potrebovali binomski
izrek, zato ga zapišimo:
(x+ y)n =
n∑
i=0
(
n
i
)
xiyn−i, (5)
pri čemer je binomski koeficient definiran kot:(
n
i
)
=
n!
(n− i)! i!
. (6)
Izpeljavo rekurenčne formule za Sk(n) začnemo iz
definicije za vsoto Sk+1(n). Najprej izrazimo zadnji, tj.
n-ti člen, nato premaknemo sumacijski indeks za ena in
upoštevamo, da je člen pri j = 1 enak 0. Nadaljujemo
z uporabo binomskega izreka, nato obrnemo vrstni red
vsot.
Sk+1(n) =
n−1∑
j=1
jk+1 + nk+1
=
n∑
j=1
(j − 1)k+1 + nk+1
=
n∑
j=1
k+1∑
i=0
(
k + 1
i
)
ji(−1)k+1−i + nk+1
=
k+1∑
i=0
(
k + 1
i
)
(−1)k+1−iSi(n) + nk+1.
V zadnjem izrazu je člen v vsoti pri i = k + 1 enak
Sk+1(n), kar se odšteje s členom na levi strani enačbe.
Preostanek je lepše zapisan v obliki enačbe (4).
Lotimo se implementacije algoritma po izpeljani
enačbi. Najprej izrazimo člen Sk(n), ki ga želimo
izračunati:
Sk(n) =
1
k + 1
(
nk+1+
k−1∑
i=0
(
k + 1
i
)
(−1)k+1−iSi(n)
)
.
(7)
Preden dokončno zapišemo psevdokodo algoritma,
naštejmo nekaj ugotovitev. Potenco nk+1 lahko
izračunavamo sproti ob samem računanju vsote. Pri
računanju vsote je treba upoštevati vse predhodno
izračunane Si(n), kjer je 0 ≤ i < k. Vrednosti Si(n)
alternirajoče enkrat prištevamo, drugič odštevamo; to
je odvisno od (−1)k+1−i. Začetni člen pri i = 0 je
lahko pozitiven ali negativen, kar je odvisno od k.
Zadnji člen pri i = k − 1 pa je (−1)2 = 1, torej vedno
pozitiven. Če vsoto začnemo računati od k − 1 proti
0, lahko vedno začnemo s prištevanjem. Poleg tega je
tako tudi laže računati binomske koeficiente, kot bomo
videli v nadaljevanju. Pri seštevanju je treba posamezne
člene Si(n), kjer 0 ≤ i < k še množiti z binomskim
koeficientom
(
k+1
i
)
.
Oglejmo si še izračun binomskih koeficientov. Izračun
po definiciji (6) se pogosto izjalovi zaradi faktoriele oz.
prevelikih števil. Poleg tega je počasen, ker izračun n!
vsebuje n−2 množenj. Spomnimo se, da je binomski ko-
eficient mogoče izračunati tudi po naslednji rekurenčni
enačbi [3]: (
k + 1
i
)
=
(
k
i
)
+
(
k
i− 1
)
.
Takšen izračun je za naš algoritem pravzaprav zelo
priročen. Rekurenčna enačba nam da dobro znani Pa-
scalov trikotnik (glej tabelo 1). Pri računanju Sk(n)
potrebujemo prvih k koeficientov vrstice (k + 1) tri-
kotnika. Vedno potrebujemo le eno vrstico, ki jo z
uporabo rekurenčne enačbe izračunamo iz predhodne.
Celotne vrstice ni treba naračunati vnaprej, ampak lahko
ustrezni koeficient izračunamo natanko takrat, ko ga
potrebujemo.
k\i 0 1 2 3 4 5 6
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
Tabela 1: Pascalov trikotnik za 0 ≤ k ≤ 6: vsaka vrstica
vsebuje števila
(
k
i
)
za 0 ≤ i ≤ k
Na voljo imamo dovolj informacij, da lahko zapišemo
implementacijo. Zopet potrebujemo dve zanki: prvo prek
parametra k in drugo za sam izračun vsote po formuli
(7).
1 binoms = [ 1 , 0 , 0 , . . . , 0 ]
2 sums = [ n , 0 , 0 , . . . , 0 ]
3 nk1 = n
4 f o r k = 1 to K do
5 sum = 0 , neg = 1
6 f o r i = k − 1 to 0 by −1 do
7 i f i > 0 then
8 binoms [ i ] += binoms [ i −1]
9 sum += neg * binoms [ i ]* sums [ i ]
10 neg = −neg
11 nk1 *= n
12 sums [ k ] = ( sum+nk1 ) / ( k +1)
13 binoms [ k ] = k + 1
Vrstice od 1 do 3 vsebujejo inicializacijo spremen-
ljivk. Tabela binoms (dolžine K + 1) pomeni aktivno
vrstico Pascalovega trikotnika. Spremenljivka nk1 vse-
buje potenco nk+1, ki jo, kot je že bilo rečeno, računamo
sproti v prvi zanki. Obe tabeli, tako binoms kot sums,
imata svoj prvi element že nastavljen na pravo vrednost.
Zunanja zanka v vrstici 4 je namenjena izračunu
Sk(n) za vse k od 1 do K. V akumulatorju sum se
ALGORITMI ZA VSOTO POTENC NARAVNIH ŠTEVIL 37
računa skupna vsota, spremenljivka neg je indikator
prištevanja oz. odštevanja. Notranja zanka z začetkom v
vrstici 6 je implementacija zgoraj zapisane rekurenčne
formule. Najprej v vrstici 8 izračunamo nov binomski
koeficient, nato ga pomnožimo (vrstica 9) z ustrezno že
predhodno izračunano vsoto, rezultat pa prištejemo oz.
odštejemo v akumulator. Po zanki dokončamo izračun
vsote in rezultat shranimo, nato sledi le še priprava na
morebitni naslednji korak zanke.
Asimptotična časovna zahtevnost algoritma je O(K2),
prostorska pa O(k). Algoritem je torej asimptotično
hitrejši od algoritma, opisanega v predhodnem razdelku.
5 NEALTERNIRAJOČA VRSTA
Algoritem po alternirajoči vrsti zahteva nekaj dodatnega
dela in pazljivosti pri seštevanju členov. Že Blaise Pascal
naj bi poznal rekurenčno enačbo, v kateri se členi v vrsti
le prištevajo:
k∑
i=0
(
k + 1
i
)
Si(n) = (n+ 1)
k+1 − 1. (8)
Veljavnost enačbe je mogoče pokazati s pomočjo
indukcije, kar pa je ne pomaga izpeljati. To lahko
storimo na več načinov: z rodovnimi funkcijami [7], z
uporabo kombinatorike [8] ali z uporabo algebraičnih
metod [9], [10]. Izpeljavo povzemamo po [10]. Začnimo
z naslednjo enačbo:
n∑
j=1
(
(j + 1)k+1 − jk+1
)
= (n+ 1)k+1 − 1
Da enačba res drži, vidimo, če zapišemo nekaj členov
vrste:
(2k+1−1k+1)+(3k+1−2k+1)+· · ·+((n+1)k+1−nk+1)
Večina členov se odšteje, ostaneta le: (−1)k+1 in (n+
1)k+1.
Lotimo se leve strani identitete. Najprej člen (j +
1)k+1 razvijemo po binomskem izreku, nato se člen
jk+1 razvoja odšteje z −jk+1. V preostanku obrnemo
vrstni red seštevanja vrst, upoštevamo definicijo za Si(n)
in enačba (8) je izpeljana:
n∑
j=1
( k+1∑
i=0
(
k + 1
i
)
ji − jk+1
)
=
=
n∑
j=1
k∑
i=0
(
k + 1
i
)
ji
=
k∑
i=0
(
k + 1
i
)
Si(n).
Lotimo se še implementacije algoritma. Najprej
enačbo (8) preoblikujmo, da bo Sk(n) na levi strani,
vse drugo pa na desni:
Sk(n) =
1
k + 1
(
(n+ 1)k+1 − 1−
k−1∑
i=0
(
k + 1
i
)
Si(n)
)
(9)
Dobljena enačba je podobna enačbi (7), le da vsota
ne vsebuje člena (−1)k+1−i, ki povzroči alternacijo
predznaka členov, kar malce poenostavi algoritem. Pri
implementaciji se zgledujemo po algoritmu iz predho-
dnega razdelka.
1 binoms = [ 1 , 0 , 0 , . . . , 0 ]
2 sums = [ n , 0 , 0 , . . . , 0 ]
3 n1k1 = n + 1
4 f o r k = 1 to K do
5 sum = 0
6 f o r i = k − 1 to 0 by −1 do
7 i f i > 0 then
8 binoms [ i ] += binoms [ i −1]
9 sum += binoms [ i ] * sums [ i ]
10 n1k1 *= n + 1
11 sums [ k ] = ( n1k1−1−sum ) / ( k +1)
12 binoms [ k ] = k + 1
Asimptotična časovna zahtevnost algoritma je enaka
kot pri algoritmu iz predhodnega razdelka, tj. O(K2).
6 PREPOLOVITEV DELA
V tem razdelku najprej izpeljemo rekurenčno enačbo,
ki za izračun Sk(n) ne potrebuje vseh vrednosti Si(n),
kjer i < k, ampak le vsako drugo. Nato zapišemo še
implementacijo algoritma po izpeljani enačbi.
Vzemimo enačbi (4) in (8) in ju seštejmo, tako
dobimo:
k∑
i=0
(
k + 1
i
)
Si(n)
(
(−1)k−i+1
)
= (n+1)k+1+nk+1−1.
V vsoto vpeljimo nov indeks j = k − i in upoštevajmo
simetričnost binomskega koeficienta
(
n
k
)
=
(
n
n−k
)
:
k∑
j=0
(
k + 1
j + 1
)
Sk−j(n)
(
(−1)j+1
)
= (n+1)k+1+nk+1−1.
Opazimo, da je vsak drugi člen vrste enak nič oz.
natančneje, da velja:
(−1)j + 1 =
{
0 j je lih
2 j je sod.
Vpeljimo nov indeks i, pri čemer j = 2i, in dobimo:
2
bk/2c∑
i=0
(
k + 1
2i+ 1
)
Sk−2i(n) = (n+ 1)
k+1 + nk+1 − 1.
Dobljeno enačbo preoblikujmo, da bo primerna za upo-
rabo v algoritmu:
Sk(n) =
1
k + 1
( (n+ 1)k+1 + nk+1 − 1
2
−
bk/2c∑
i=1
(
k + 1
2i+ 1
)
Sk−2i(n)
)
. (10)
38 MIHELIČ
Zapišimo še implementacijo. Na vsakem koraku je
treba izračunati celotno vrstico Pascalovega trikotnika,
čeprav gre vsota v enačbi (10) le do bk/2c. Zato v
algoritmu nastopata dve notranji zanki (vrstici 9 in 12).
Prva skrbi za izračun binomskih koeficientov, druga pa
dodaja še izračun vsote po enačbi (10).
1 binoms = [ 1 , 1 , 0 , 0 , . . . , 0 ]
2 sums = [ n , 0 , 0 , . . . , 0 ]
3 n1k1 = n + 1
4 nk1 = n
5 f o r k = 1 to K do
6 sum = 0
7 binoms [ k + 1] = 1
8 i = k
9 whi le i > k / 2 do
10 binoms [ i ] += binoms [ i − 1]
11 i −= 1
12 whi le i >= 1 do
13 binoms [ i ] += binoms [ i − 1]
14 sum += binoms [2* i + 1 ] *
15 sums [ k − 2* i ]
16 i −= 1
17 n1k1 *= n + 1
18 nk1 *= n
19 tmp = ( n1k1 + nk1 − 1) / 2
20 sums [ k ] = ( tmp − sum ) / ( k + 1)
Asimptotična časovna zahtevnost je enaka O(K2),
vendar je število množenj prepolovljeno. Opozorimo,
da gre pravzaprav za množenja velikih števil – časovna
zahtevnost takega množenja pa ni konstantna, ampak je
odvisna od velikosti števila.
7 OPTIMIZACIJE
Omenimo še nekaj mogočih splošnih optimizacij, ki jih
lahko uporabimo v zgoraj opisanih algoritmih. Vsote za
majhne k lahko vnajprej izračunamo po dobro znanih
formulah. S tem lahko prihranimo nekaj iteracij zunanje
zanke v vseh omenjenih algoritmih.
Vrstice v Pascalovem trikotniku so simetrične po pra-
vilu
(
n
i
)
=
(
n
n−i
)
. Z upoštevanjem simetričnosti lahko
izračunamo le polovico vrstice Pascalovega trikotnika.
Druge polovice nam niti ni treba hraniti, v algoritmu
pa moramo zaradi tega dodati preverjanje parametra i
binomskega koeficienta.
Simetričnost lahko izrabimo tudi tako, da zmanjšamo
število množenj velikih števil. Pri izračunu vsote namreč
lahko upoštevamo obe Si in Sk+1−i hkrati. Kot pri-
mer, predelajmo enačbo (9) tako, da zmanjšamo število
množenj za polovico:
Sk(n) =
1
k + 1
(
(n+ 1)k+1 − 1
− S0(n)− (k + 1)S1(n)−
−
k/2∑
i=2
(
k + 1
i
)(
Si(n) + Sk+1−i(n)
))
Zapisana enačba velja pri sodih vrednostih k, pri lihih
k ravnamo podobno, le srednji člen moramo posebej
upoštevati.
8 SKLEP
Zaporedja in njihove vsote so pomembni na številnih
znanstvenih področjih. V članku smo se ukvarjali z vsoto
zaporedja potenc reda k prvih n naravnih števil. Opisali
smo več algoritmov za izračun te vsote. Vse algoritme
smo matematično utemeljili. Poleg tega smo zapisali tudi
njihovo implementacijo, na podlagi katere smo podali
tudi asimptotično časovno zahtevnost.