<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[a4paper,11pt]{article}
\usepackage{graphics,graphicx}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[polish]{babel}
\pagestyle{headings}
\usepackage[polish]{babel}
\usepackage{indentfirst}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[usenames]{color}
\usepackage{xcolor}
\usepackage{tikz}
\usepackage[left=1.5cm,top=1.5cm,right=1.5cm,bottom=1.5cm]{geometry}
\usepackage[normalem]{ulem}
\usetikzlibrary{arrows,shapes,fit,decorations.pathmorphing}

\newcommand{\myskip}{\vskip 0.4cm \noindent}

\newcommand{\calL}{{\mathcal L}}
\newcommand{\calM}{{\mathcal M}}
\newcommand{\calN}{{\mathcal N}}
\newcommand{\calO}{{\mathcal O}}
\newcommand{\calP}{{\mathcal P}}
\newcommand{\calQ}{{\mathcal Q}}
\newcommand{\calR}{{\mathcal R}}
\newcommand{\calS}{{\mathcal S}}
\newcommand{\calT}{{\mathcal T}}
\newcommand{\calU}{{\mathcal U}}
\newcommand{\calV}{{\mathcal V}}
\newcommand{\calW}{{\mathcal W}}
\newcommand{\calX}{{\mathcal X}}
\newcommand{\calY}{{\mathcal Y}}
\newcommand{\Z}{{\mathcal Z}}

\newcommand{\pp}{\widetilde{p}}
\newcommand{\eqn}[1]{\stackrel{#1}{=}}

\newtheorem*{fakt}{Fakt}
\newtheorem{lem}{Lemat}
\newtheorem{obs}{Obserwacja}
\newtheorem{tez}{Teza}
\newtheorem{tw}{Twierdzenie}
\newtheorem{stw}{Stwierdzenie}
\newtheorem{wnio}{Wniosek}
\tikzstyle{circ_node} = [shape = circle, fill = black, inner sep = 0pt, minimum
size = 2mm]

\date{}
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.95}

\title{\bf Liczenie podziaĹĂłw liczby: algorytm Eulera}
\author{Wojciech Rytter}

\begin{document}
\maketitle
\noindent PodziaĹy liczb sÄ bardzo skomplikowanymi obiektami kombinatorycznymi,
przedstawimy dwa algorytmy liczenia takich oblektĂłw.
Pierwszy prosty algorytm bÄdzie dziaĹaĹ w czasie $O(n^2)$ i pamiÄci $O(n^2)$, natomiast drugi,
pochodzÄcy od Eulera i
oparty na tzw. liczbach {\em pentagonalnych}, w czasie $O(n\sqrt{n})$ i pamiÄci $O(n)$.
\myskip
\noindent
PodziaĹ $\pi=(\lambda_1,\lambda_2,\ldots \lambda_r)$ to przedstawienie  liczby $n=\lambda_1+\lambda_2+\ldots \lambda_r$ w postaci
$$n=\lambda_1+\lambda_2+\ldots \lambda_r,\
\mbox{gdzie}  \ \lambda_1\ge \lambda_2\ge \ldots \lambda_r&gt;0$$
\myskip
Wszystkie podziaĹy liczby $n$, w porzÄdku antyleksykograficznym, moĹźna wygenerowaÄ iteracyjnie nastÄpujÄco:

szukamy pierwszego $\lambda_i\ge 2$ od prawej strony, zastÄpujemy $\lambda_i$ przez $\lambda_i-1$, a pozostaĹe czÄĹci
na prawo dajemy tak, aby sufiks na prawo od $\lambda_i$ byĹ jak najwiÄkszy.
Na przykĹad podziaĹy $n=5$ w porzÄdku antyleksykograficznym to:
$$5,\ \ \ \  4+1,\ \ \ \  3+2,\ \ \ \  3+1+1,\ \ \ \  2+2+1,\ \ \ \  2+1+1+1,\ \ \ \  1+1+1+1+1.$$
Oznaczmy przez $p(n)$ liczbÄ podziaĹĂłw liczby $n$, mamy:

\begin{center}
      \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
        $n:$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7&amp;8&amp;9&amp;10&amp;11&amp;12&amp;13&amp;14&amp;15&amp;16 \\ \hline
        %$w[i]$ &amp; &amp; $c$ &amp; $a$ &amp; $a$ &amp; $b$ &amp; $b$ &amp; $c$ &amp; $a$ &amp; $b$ &amp; $b$ &amp; $c$ &amp; $a$ &amp; $a$ &amp; $a$ \\\hline
        $p(n):$ &amp; 1 &amp; 1 &amp; 2 &amp; 3&amp; 5 &amp;7 &amp; 11 &amp; 15 &amp; 22&amp;30&amp;42&amp;56&amp; 77&amp;101&amp;135 &amp; 176&amp;231
      \end{tabular}
    \end{center}

    \noindent Dla $n&lt;0$ przyjmijmy, czysto formalnie, Ĺźe $p(n)=0$, natomiast $p(0)=1$.
    \myskip
 Oznaczmy przez $p(n,k)$ liczbÄ podziaĹĂłw liczby $n$ na $k$ czÄsci (niezerowych).
 Algorytm o czasie kwadratowym liczenia $p(n)$ polega na policzeniu ( kwadratowej  liczby )  wartoĹci $p(n,k)$ na podstawie rekurencji:
 $$p(n,k)=0\ \mbox{dla}\ k&lt;n \ \mbox{lub}\ k\le 0.$$
 $$p(n,k)\; =\; p(n-1,k-1)+p(n-k,k)$$
 Rekurencja wynika stÄd, Ĺźe mamy dwa przypadki:
 \begin{description}
 \item ($\lambda_k=1$) Wtedy mamy $p(n-1,k-1)$ podziaĹĂłw pomijajÄc $\lambda_k$;
 \item ($\lambda_k&gt;1$)  Wtedy moĹźemy odjÄÄ jeden od kaĹźdego $\lambda_i$ otrzymujÄc podziaĹ
 liczby $n-k$ na $k$ czÄĹci.
 \end{description}
 \myskip
 W celu szybszego policzenia $p(n)$ rozwaĹźymy podziaĹy na rĂłĹźne czÄĹci, tzn.
 $$\lambda_1&gt;\lambda_2&gt;\ldots \lambda_1.$$
 Niech $\pp(n)$ bÄdzie liczbÄ takich podziaĹĂłw.  Przez $p_{even},\pp_{even}, p_{odd},\pp_{odd}$ oznaczmy liczbÄ podziaĹĂłw
 na parzystÄ/nieparzystÄ liczbÄ czÄĹci (o rĂłĹźnych rozmiarach w przypadku $ \pp$).
 \myskip
  Na przykĹad $\pp(15)=27,\pp_{odd}(15)=14, \pp_{even}(15)=13$, patrz Rysunek~\ref{bijekcja_euler3}.

  \noindent ZauwaĹźmy, Ĺźe liczby $\pp(n)$ sÄ przewaĹźnie znacznie mniejsze od liczb $p(n)$ (chociaĹź na poczÄtku niewiele siÄ rĂłĹźniÄ).
  \myskip
 MoĹźemy rĂłnieĹź zdefiniowaÄ $\pp(n,k)$ - liczbÄ podziaĹĂłw $n$ na rĂłĹźne czÄĹci.
 Na przykĹad $\pp(50,7)=522$, co Euler policzyĹ prawie 300 lat temu
 bez komputera (ani kalkulatora) tÄ konkretnÄ wartoĹÄ odpwiadajÄc
 na pytanie matematyka  Ph. Naude.
 \myskip
 \noindent  {\bf Dygresja.} $p_{odd}(n)=\pp(n)$. 
\myskip
KluczowÄ wartoĹciÄ jest zdefiniowana poniĹźej funkcja:
$$\Delta(k)\; =\; \pp_{odd}(k)-\pp_{even}(k)$$
Funkcje $p(n),\; \pp(n)$ sÄ bardzo skomplikowane, natomiast jest zadziwiajÄce, Ĺźe $\Delta$ jest 
bardzo prosta.
PoczÄtkowe wartoĹci to:

\begin{center}
      \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
        $k:$  &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7&amp;8&amp;9&amp;10&amp;11&amp;12&amp;13&amp;14&amp;15&amp;16&amp;17&amp;18&amp;19&amp;20&amp;21&amp;22 \\ \hline
        %$w[i]$ &amp; &amp; $c$ &amp; $a$ &amp; $a$ &amp; $b$ &amp; $b$ &amp; $c$ &amp; $a$ &amp; $b$ &amp; $b$ &amp; $c$ &amp; $a$ &amp; $a$ &amp; $a$ \\\hline
        $\Delta(k):$ &amp; 1 &amp; 1 &amp; 0 &amp; 0&amp; -1 &amp;0 &amp; -1 &amp; 0 &amp; 0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp; 0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;-1
      \end{tabular}
    \end{center}

 \noindent Leonard Euler odkryĹ dwie istotne (dla liczenia $p(n)$) wĹasnoĹci funkcji $\Delta$:
 \begin{description}
 \item{\bf WĹasnoĹÄ 1:} \mbox{ \ }\\
  $p(n)$ speĹnia rekurencjÄ:
 \begin{equation}\label{equation1}
 p(n)\;=\; \sum_{k= 1}^n\; \Delta(k)\cdot p(n-k)
 \end{equation}
 \item{\bf WĹasnoĹÄ 2:}  \mbox{ \ }\\
 jak widaÄ z poczÄtkowych wartoĹci $\Delta(k)$ jest ciÄgiem bardzo {\em rzadkim} (prawie same zera).\\
 Jest on obliczalalny Ĺatwo za pomocÄ tzw. liczb pentagonalnch, wartoĹci ciÄgu to zera, +1 lub -1.

 Z tego, Ĺźe ciÄg $\Delta(n)$ jest bardzo rzadki wynika, Ĺźe dla policzenia $p(n)$ tylko
 $O(\sqrt{n})$ wartoĹci $k$ jest niezerowych.
 
 \noindent Zatem $p(n)$ liczymy w czasie $O(\sqrt{n})$ znajÄc
 $p(n-1),p(n-2),\ldots p(0)$. W sumie mamy algorytm dziaĹajÄcy w czasie $O(n\sqrt{n})$ i pamiÄci $O(n)$,
 o ile potrafimy ĹÄtwo wylistowaÄ niezerowe wartoĹci $\Delta(k)$.

 Leonard Euler najpierw odkryĹ wĹasnoĹci $\Delta$ heurystycznie, a dopiero po 10 latach znalazĹ dowĂłd
 (byÄ moĹźe wczeĹniej nie miaĹ czasu).
 \end{description}

\noindent Zdefiniujmy liczby pentagonalne (piÄciokÄtne) $$pent(i)=(3i-1)i/2$$
Nazwa pochodzi od interpretacji geometrycznej, podobnie jak dla liczb
trĂłjkÄtnych.
Mamy:
$$pent(i) = pent(i-1)+3i+1$$
Liczby pentagonalne bÄdziemy rĂłnieĹź nazywaÄ liczbami trapezowymi pierwszego typu,
a liczby $pent(i)+i$ nazywamy liczbami trapezowymi drugiego typu,
patrz lewy/prawy trapez na Rysunku \ref{trapezy}.

\begin{center}
      \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
        $i:$ &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\ \hline
        %$w[i]$ &amp; &amp; $c$ &amp; $a$ &amp; $a$ &amp; $b$ &amp; $b$ &amp; $c$ &amp; $a$ &amp; $b$ &amp; $b$ &amp; $c$ &amp; $a$ &amp; $a$ &amp; $a$ \\\hline
        $pent(i):$ &amp; 1 &amp; 5 &amp; 12 &amp; 22 &amp;35 &amp; 51 &amp; 70
      \end{tabular}
    \end{center}

\noindent Ponadto zdefinujmy  wspĂłĹczynniki
pentagonalne:

\begin{equation}\label{wzor}
    e(k) =
      \left\{
      \begin{array}{cl} %1  &amp; k=0\\
        (-1)^{i+1} &amp; \mbox{if } k=pent(i)\ \textrm{lub}\ k=pent(i)+i\\
        0 &amp; \mbox{w przeciwnym przypadku.}
      \end{array}
      \right.
  \end{equation}

  \noindent {\bf Lemat Kluczowy.}
  \begin{equation}\label{key-lemma}
  \Delta(k) \; =\; e(k).
  \end{equation}
  \myskip
  MoĹźemy teraz zapisaÄ algorytm (jednÄ iteracjÄ) liczenia $p(n)$ nastÄpujÄco:

  \begin{equation}
 p(n)\;=\; \sum_{i\ge 1}\; (-1)^{i+1}\cdot (\; p(n-pent(i))+p(n-pent(i)-i)\;)
 \end{equation}\label{equation2}
 W rĂłwnaniu tym korzystamy jedynie z wartoĹci $i$ takich, Ĺźe $pent(i)\le n$, mamy jedynie $O(\sqrt{n})$ takich wartoĹci.
 Liczby $pent(i)$ moĹźemy Ĺatwo policzyÄ.
 \myskip
{\bf Twierdzenie.}\ Liczby $p(1),p(2), ..p(n)$ moĹźemy policzyÄ w czasie $O(n\sqrt{n})$ i pamiÄci $O(n)$.

\section*{DowĂłd rĂłwnania~\ref{equation1}}
Uzasadnienie jest sprytnÄ manipulacjÄ algebraicznÄ, korzystajÄcÄ z tego Ĺźe dwa wielomiany bÄdÄce tÄ samÄ funkcjÄ
majÄ takie same wspĂłĹczynniki przy tych samych potÄgach zmiennej.
Sztuczka polega na tym, Ĺźeby te same wielomiany przedstawiÄ na dwa rĂłĹźne sposoby,
z jednego wymnoĹźenia otrzymujemy wynik, ktĂłry przyrĂłwnujemy do wymnoĹźenia w innej formie.
Zdefiniujmy:
$$\phi(x)=(1+x+x^2+\ldots x^n),\ \psi(x)=1-x.$$
$$W_1(x)\ =\ \prod_{i=1}^n\;\phi(x^i),\ W_2(x)\ =\ \prod_{i=1}^n\;\psi(x^i).$$
WprowadĹźmu notacjÄ $\eqn{n}$ dla rĂłwnoĹci wielomianĂłw z dokĹadnoĹciÄ do potÄg wyĹźszych niĹź $n$, inaczej mĂłwiÄc 
bierzemy resztÄ z dzielenia przez $x^{n+1}$.
ZauwaĹźmy, Ĺźe zachodzi dosyÄ Ĺatwe rĂłwnanie:
\begin{equation}\label{wielomany1}
W_1(x)\cdot W_2(x) \eqn{n}  1.
\end{equation}
PowyĹźsza rĂłwnoĹÄ trochÄ przypomina sytuacjÄ w rĂłwnoĹci  $(1+x)(1-x)= 1-x^2$.
Przedstawimy teraz te same wielomiany w innej formie.
\begin{equation}\label{wielomiany2}
W_1(x)\;\eqn{n}\; p(0)x^0+p(1)x^1+p(2)x^2+..p(n)x^n,\ W_2(x)\;\eqn{n}\; 1-\Delta(1)x^2-\Delta(2)x^2...-\Delta(n)x^n.
\end{equation}
Z rĂłwnania~\ref{wielomany1}   dla $n\ge 1$ wynika, Ĺźe wspĂłĹczynnik przy $x^n$ w iloczynie $W_1(x)\cdot W_2(x)$ wynosi zero,
korzystajÄc z  rĂłwnania~\ref{wielomiany2} moĹźemy ten wspĂłĹczynnik przedstawiÄ jako kombinacje iloczynĂłw
  $p(i),\Delta(j)$, gdzie $i+j=n$, w rezultacie
otrzymujemy:
$$p(n)\cdot 1 - p(n-1)\cdot \Delta(1)- p(n-2)\cdot \Delta(2)- p(n-3)\cdot \Delta(3)\ldots - \Delta(n)\cdot p(0)\ =\ 0$$
StÄd wynika bezpoĹrednio rĂłwnanie~\ref{equation1}.

\section*{DowĂłd kluczowego lematu (rĂłwnania~\ref{key-lemma})}

  \noindent W sekcji tej rozwaĹźamy tylko podziaĹy o rĂłĹźnych czÄĹciach.
  \noindent DwĂłd kluczowego lematu wymaga rozwaĹźenia interpretacji geometrycznej podziaĹĂłw.
  
PodziaĹ liczby moĹźe byÄ przedstawiony w postaci diagramu zwanego diagramem Ferrersa,
w kolejnym wierszu liczba elementĂłw odpowiada liczbie $\lambda_j$.
Diagramy Ferrersa dla przykĹadowych podziaĹĂłw liczb 22 i 26 sÄ przedstawione na rysunku \ref{trapezy}.
SÄ to bardzo szczegĂłlne podziaĹy, ktĂłre bÄdziemy nazywaÄ trapezowymi.


\noindent
PodziaĹ trapezowy rzÄdu $k$ pierwszego typu jest postaci $(k+k-1,\; k+k-2,\; k+k-3,\ldots , k)$ a drugiego typu
postaci $(k+k,\; k+k-1,\; k+k-1,\ldots , k+1)$.
\myskip {\bf Obserwacja}. PodziaĹ trapezowy majÄcy $pen(k)$ lub $pen(k)+k$ elementĂłw skĹada
siÄ z $k$ czÄĹci.
\myskip
\begin{figure}[h]
    \centering
    \includegraphics[width=.7\textwidth]{bijekcja_euler2.png}
    \caption{
      \label{trapezy}
      Trapezy rzÄdu $k$, gdzie $k=4$,  pierwszego typu ma $pen(k)$ elementĂłw, a drugiego typu ma $pen(k)+k$ elementĂłw.
      PodziaĹy odpowiadajÄce tego typu trapezom nazywamy podziaĹami trapezowymi.
      }
  \end{figure}
  
\noindent LiczbÄ $n$ nazywamy liczbÄ trapezowÄ gdy
istnieje podziaĹ $n$ bÄdÄcy trapezowym, zawsze jest co najwyĹźej jeden taki podziaĹ dla danego $n$.
\myskip
\noindent {\bf Obserwacja.}\ Liczby trapezowe sÄ postaci $pen(j)$ lub $pen(j)+j$.
\myskip
\noindent Dla trapezu $\pi$ przez $k(\pi)$ oznaczmy liczbÄ elementĂłw na prawej diagonali poczynajÄc od gĂłrnej prawej strony,
jeĹĹi odpowiadajÄcym podziaĹem jest $(a_1,a_2,\ldots a_r)$ to $k(\pi)$ jest najwiÄkszÄ liczbÄ naturalnÄ
takÄ, Ĺźe  $a_i-1=a_{i+1}$ dla $i=1,2,\ldots k(\pi)-1$. Przez $h(\pi)=a_r$ oznaczmy liczbÄ elementĂłw w najmniejszej czÄĹci.
\myskip
JeĹli podziaĹ nie jest trapezowy oraz $h(\pi)\le k(\pi)$ to $F(\pi)$ jest podziaĹem powstajÄcym z $\pi$ przez
dodanie do kaĹźdej z pierwszych $k(\pi)$ czÄĹci po jednym elemencie i usuniÄcie
najmniejszej (dolnej) czÄĹci, patrz Rysunek~\ref{funkcja_pi}.

  \begin{figure}[h]
    \centering
    \includegraphics[width=.7\textwidth]{bijekcja_euler.png}
    \caption{DziaĹanie funkcji $F$.
           }\label{funkcja_pi}
  \end{figure}

PodziaĹy o parzystej/nieparzystej liczbie czÄsci nazywamy parzystymi/nieparzystymi.
ZauwaĹźmy, Ĺźe funkcja $F$ zmienia parzystoĹÄ podziaĹu. Zachodzi nastÄpujÄcy dosyÄ oczywisty fakt.
\myskip
\noindent {\bf WĹasnoĹÄ funkcji $F$}.\ $F$ jest bijekcjÄ miÄdzy  nietrapezowymi podziaĹÄmi $n$ z $h(p)\le k(\pi)$  i
 nietrapezowymi podziaĹami $n$ z $h(p)&gt; k(\pi)$.
\begin{equation}
   \pp_{odd}(k)-\pp_{even}(k) =
      \left\{
      \begin{array}{cl} %1  &amp; k=0\\
         1 &amp; \mbox{gdy}\ n\ \textrm{jest nieparzystÄ liczbÄ trapezowÄ}\\
         -1 &amp; \mbox{gdy}\ n \ \textrm{jest parzystÄ liczbÄ trapezowÄ}\\
        0 &amp; \mbox{w przeciwnym przypadku.}
      \end{array}
      \right.
  \end{equation}

Z powyĹźszej wĹasnoĹci wynika:
$$\pp_{odd}(k)-\pp_{even}(k) \;=\; e(k)\ \mbox{dla kazdego} k.$$

\begin{figure}[h]
    \centering
    \includegraphics[width=.6\textwidth]{bijekcja_euler3.png}
    \caption{
      \label{bijekcja_euler2}
     Zgrupowanie podziaĹĂłw nietrapezowych liczby $n=15$ korzystajÄc z funkcji $F$ .
      }
  \end{figure}

\section*{Nieoczekiwana relacja miÄdzy funkcjami $p(n)$ i $\sigma(n)$}
Jako ciekawostkÄ podamy, bez uzasadnienia, pewien zwiÄzek dwĂłch pozornie
{\em odlegĹych} funkcji $p(n), \sigma(n)$, gdzie $\sigma(n)$ oznacza sumÄ dzielnikĂłw
liczby $n$ (wĹÄcznie z $n$). Mamy
\begin{center}
      \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r}
        $n:$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7&amp;8&amp;9&amp;10&amp;11&amp;12&amp;13&amp;14&amp;15&amp;16 \\ \hline
        %$w[i]$ &amp; &amp; $c$ &amp; $a$ &amp; $a$ &amp; $b$ &amp; $b$ &amp; $c$ &amp; $a$ &amp; $b$ &amp; $b$ &amp; $c$ &amp; $a$ &amp; $a$ &amp; $a$ \\\hline
        $\sigma(n):$ &amp; 0 &amp; 1 &amp; 3 &amp; 4&amp; 7 &amp;6 &amp; 12 &amp; 8 &amp; 15&amp;13&amp;18&amp;12&amp; 28&amp;14&amp;24 &amp; 24&amp;31
      \end{tabular}
    \end{center}
   Dla funkcji $\sigma$ zachodzi prawie taka sama rekurencja jak dla $p(n)$, jedyna rĂłĹźnica to
   zastÄpienie $p(0)$ przez $n$ we wzorze~\ref{equation1}.
  Funkcja  $\sigma(n)$ speĹnia rekurencjÄ:
 \begin{equation}\label{sigma}
 \sigma(n)\;=\; \sum_{k= 1}^{n-1}\; \Delta(k)\cdot \sigma(n-k)\;+\;\Delta(n)\cdot n.
 \end{equation}\label{equation}

 \noindent {\bf PrzykĹad.}\ Dla $n=15$ mamy:
 $$\sigma(15)\;=\;\sigma(15-1)+\sigma(15-2)-\sigma(15-5)-\sigma(15-7)+\sigma(15-12)+15\;=\; 24+14-18-15+4+15\;=\;24.$$
 $$p(15)\;=\;p(15-1)+p(15-2)-p(15-5)-p(15-7)+p(15-12)+p(0)\;=\; 135+101-42-22+3+1\;=\;176.$$
 %
 PoniewaĹź wartoĹci $\Delta(k)$ sÄ zwiÄzane z liczbami pentagonalnymi tak jak poprzednio, to
 wszystkie wartoĹci $\sigma(n),\sigma(n-1),\ldots \sigma(1)$ moĹźna policzyÄ
 w czasie $O(n\sqrt{n})$ i pamiÄci $O(n)$ tak jak poprzednio zrobiliĹmy to
 dla wartoĹci $p(n)$.
 \
 \noindent Zachodzi rĂłwnieĹź inny zadziwiajÄcy zwiÄzek:
 \begin{equation}
 \sigma(n)\;=\; \sum_{k= 1}^{n}\; k\cdot \Delta(k)\cdot p(n-k).
 \end{equation}\label{suprise}
 %
 Jesli $n=\prod\; p_i^{m_i}$, gdzie $p_i$ liczby pierwsze to $$\sigma(n)\;=\; \prod\; (p_i^{m_i+1}-1)\;/\; \prod\; (p_i-1)$$
 Wydaje sie ze liczenie $\sigma$ dla wszystkich liczb $1,2,\ldots n$ jednak jest szybsze korzystajac ze wzoru~\ref{sigma}
 i liczb pentagonalnych niĹź korzystajÄc z ostatnego wzoru.
\myskip
{\bf Dygresja.}
\
 Liczby $\sigma(n)$ sÄ zwiÄzane z tzw. liczbami {\em doskonaĹymi}, tzn. takimi Ĺźe $\sigma(n)=2n$.
Wiadomo, ze  $n$ parzyste  jest doskonaĹe wtw. gdy $n=2^{p-1}(2^p-1)$, gdzie $p, 2^p-1$ sÄ
pierwsze, np. dla $p=11213$, $p=30402456$ (43-cia liczba doskonaĹa).
Pierwsze 7 liczb doskonaĹych to:

\centerline{ 6, 28, 496, 8128, 33550336,  8 589 869 056, 137 438 691 328.}
Pierwsze 4 liczby doskonaĹe policzyĹ juĹź Euklides. Kilka nastÄpnych Euler. Potem juĹź byĹ potrzebny komputer.
\noindent
Nie wiadomo czy  liczb parzystych doskonaĹych jest nieskonczenie wiele ani teĹź czy istnieje
choÄby jedna nieparzysta liczba doskonaĹa.
\myskip\myskip
{\bf WiÄcej informacji} na temat liczenia podziaĹĂłw moĹźna znaleĹźÄ w:
\vskip 0.5cm
http://www.math.psu.edu/vstein/alg/antheory/preprint/andrews/chapter.pdf

http://www.rowan.edu/colleges/csm/departments/math/facultystaff/osler/

89\%20Surprising\%20Connection\%20Between\%20Partitions\%20and\%20Divisors.pdf.pdf

http://hkumath.hku.hk/~mks/EulerHeuristicReasoning.pdf
\end{document} </pre></body></html>