WisFaq!

Som van positieve delers

Ik moet voor $\sigma$(1)+$\sigma$(2)....$\sigma$(n) waarbij $\sigma$ staat voor de som van de positieve delers van een positief geheel getal op combinatorische weg een uitdrukking zien te vinden en ik heb geen idee hoe ik dit moet aanpakken. Als iemand me op weg wil helpen graag.

Tom
20-5-2019

Antwoord

Laat ik proberen een beginnetje voor je te maken.
Neem als voorbeeld n=7
Alle getallen van 1 tot 7 zijn deelbaar door 1. Dat levert 7 keer 1 op.
De getallen 2,4 en 6 zijn deelbaar door 2. Dat zijn er 3. Dat levert dus 3 keer 2 op.
De getallen 3 en 6 zijn deelbaar door 3. Dat levert dus 2 keer 3 op.
4 is deelbaar door 4: levert 1·4
5 is deelbaar door 5: levert 1·5
6 is deelbaar door 6: levert 1·6
7 is deelbaar door 7: levert 1·7
totaal 7+3·2+2·3+4+5+6+7=41

Voor het algemene geval heb je ook een formule nodig om uit te rekenen hoeveel getallen kleiner dan of gelijk aan n deelbaar zijn door k:
dat zijn er floor(n/k) (de floor functie geeft het resultaat afgekapt naar beneden.)

Dus voor elke k$\le$n bereken je floor(n/k) en vermenigvuldigt dat met k.
En dat tel je allemaal op.
Dit levert de formule:
$\eqalign{
a(n) = \sum\limits_{k = 1}^n {\sigma (k)} = \sum\limits_{k = 1}^n {k \cdot \left\lfloor {\frac{n}
{k}} \right\rfloor }
}$

$\eqalign{\left\lfloor {\frac{n}
{k}} \right\rfloor}$= floor(ⁿ/_k)

hk
20-5-2019