\documentclass[a4paper,12pt]{article}
\usepackage{german}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{ulem}
\pagestyle{headings}
\begin{document}
\title{Absch\"atzung der Verh\"altnisse von aufeinander folgenden hochzusammengesetzten Zahlen}
\author{Jan Behrens}
\date{\small 25. August 2008 \linebreak Korrektur vom 18. Juli 2009}
\maketitle

Die Teileranzahl $d(n)$ einer Zahl $n$ ist die Anzahl von Zahlen, durch die sich die Zahl $n$ (restfrei) teilen l\"asst.
Eine Zahl $n$ ist dann eine hochzusammengesetzte Zahl, wenn ihre Teileranzahl $d(n)$ gr\"o{\ss}er ist, als die jeweiligen Teileranzahlen aller nat\"urlichen Zahlen kleiner als $n$. Zum Beispiel ist 12 eine hochzusammengesetzte Zahl, da sie 6 Teiler hat (n\"amlich 1,2,3,4,6 und 12), und die Zahlen 1,2,3,4,5,6,7,8,9,10 oder 11 alle jeweils weniger als 6 Teiler besitzen.

Der englische Begriff f\"ur hochzusammengesetzte Zahlen lautet "`highly composite numbers"'. Ich werde die hochzusammengesetzten Zahlen daher im folgenden als HCNs bezeichnen.

Im folgenden soll bewiesen werden, dass es nur 8 HCNs gibt, deren direkt nachfolgende HCN gr\"o{\ss}er als das jeweils $\frac{3}{2}$-fache ist. Es gibt einen \"ahnlichen Beweis, der zeigt, dass es nur 7 HCNs gibt (Ganzzahl-Folge A072938), deren jeweils nachfolgende HCN doppelt so gro{\ss} ist.

\bigskip

Habe die nat\"urliche Zahl $n$ eine Primfaktorzerlegung von
$$n = \prod_{p \in \mathbb{P}} p^{c_p}$$
dann l\"asst sich die Teileranzahl $d(n)$ sehr einfach mit Hilfe der Formel
$$d(n) = \prod_{p \in \mathbb{P}} (c_p+1)$$
bestimmen. Betrachten wir nun eine HCN der Form
$$n_\mathrm{A} = 2^{c_2} \cdot 3^{c_3} \cdot \prod_{p \in {5,7,11,...}} p^{c_p}$$
dann finden wir eine um den Faktor $\frac{3}{2}$ gr\"o{\ss}ere Zahl der Form
$$n_\mathrm{B} = 2^{c_2-1} \cdot 3^{c_3+1} \cdot \prod_{p \in {5,7,11,...}} p^{c_p}$$
mit mehr Teilern genau dann, wenn $d(n_\mathrm{B}) > d(n_\mathrm{A})$ gilt, also wenn
\begin{eqnarray*}
c_2 \cdot (c_3+2) \cdot \prod\limits_{p \in {5,7,11,...}} (c_p+1) & > & (c_2+1) \cdot (c_3+1) \cdot \prod\limits_{p \in {5,7,11,...}} (c_p+1) \\
c_2 \cdot (c_3+2) & > & (c_2+1) \cdot (c_3+1) \\
c_2 c_3 + 2 c_2 & > & c_2 c_3 + c_2 + c_3 + 1 \\
c_3 & < & c_2 - 1
\end{eqnarray*}
ist. Eine zur HCN $n_\mathrm{A}$ um den Faktor $\frac{4}{3}$ gr\"o{\ss}ere Zahl der Form
$$n_\mathrm{C} = 2^{c_2+2} \cdot 3^{c_3-1} \cdot \prod_{p \in {5,7,11,...}} p^{c_p}$$
mit mehr Teilern findet sich genau dann, wenn $d(n_\mathrm{C}) > d(n_\mathrm{A})$ gilt, also wenn
\begin{eqnarray*}
(c_2+3) \cdot c_3 \cdot \prod\limits_{p \in {5,7,11,...}} (c_p+1) & > & (c_2+1) \cdot (c_3+1) \cdot \prod\limits_{p \in {5,7,11,...}} (c_p+1) \\
(c_2+3) \cdot c_3 \cdot & > & (c_2+1) \cdot (c_3+1) \\
c_2 c_3 + 3 c_3 & > & c_2 c_3 + c_2 + c_3 + 1 \\
2 c_3 & > & c_2 + 1
\end{eqnarray*}

\bigskip

Die beiden Ungleichungen
\begin{eqnarray*}
  c_3 & < & c_2 - 1 \\
2 c_3 & > & c_2 + 1
\end{eqnarray*}
sind lediglich f\"ur $(c_2,c_3) \in S$ mit
$$S = \{(0,0), (0,1), (1,1), (2,1), (3,2)\}$$
nicht erf\"ullt, d.h. zu jeder HCN $n_\mathrm{D}$ deren Primfaktorzerlegung $(c_2,c_3) \not\in S$ ergibt, findet sich eine um den Faktor $\frac{3}{2}$ oder $\frac{4}{3}$ gr\"o{\ss}ere Zahl mit mehr Teilern. Hieraus folgt, dass die auf $n_\mathrm{D}$ direkt nachfolgende HCN maximal um den Faktor $\frac{3}{2}$ gr\"o{\ss}er sein kann. HCNs deren nachfolgende HCN um mehr als $\frac{3}{2}$ gr\"o{\ss}er ist, m\"ussen somit eine Primfaktorzerlegung mit $(c_2,c_3) \in S$ aufweisen. Im Folgenden wird die Untersuchung aller Zahlen mit einer solchen Primfaktorzerlegung zeigen, dass nur endlich viele HCNs, n\"amlich 1, 2, 6, 12, 60, 360, 2520 sowie 27720 eine direkt nachfolgende HCN besitzen, die um mehr als das $\frac{3}{2}$-fache gr\"o{\ss}er ist.

\bigskip

Mit Hilfe eines Computerprogrammes lassen sich die ersten 35 HCNs leicht berechnen:
1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440, 83160, 110880, 166320, 221760, 277200, 332640, 498960.

\bigskip

Wir betrachten zun\"achst den einfachen Fall $(c_2,c_3) = (0,0)$. Primfaktorexponenten von HCNs m\"ussen mit wachsender Primzahl monoton fallend sein, da man ansonsten durch Vertauschen der Exponenten eine kleinere Zahl mit genauso vielen Teilern erhalten w\"urde. Da $c_3 = 0$ ist, m\"ussen also auch $c_5 = c_7 = c_{11} = ... = 0$ ein. Die sich daraus ergebende Zahl $2^{c_2} \cdot 3^{c_3} = 2^0 \cdot 3^0 = 1$ ist die erste HCN deren direkt nachfolgende HCN 2 doppelt so gro{\ss} ist.

F\"ur den Fall $(c_2,c_3) = (1,0)$ sind ebenfalls $c_5 = c_7 = c_{11} = ... = 0$. Die sich daraus ergebende Zahl $2^{c_2} \cdot 3^{c_2} = 2^1 \cdot 3^0 = 2$ ist die zweite HCN, deren direkt nachfolgende HCN 4 doppelt so gro{\ss} ist.

F\"ur den Fall $(c_2,c_3) = (1,1)$ l\"asst sich keine triviale Aussage mehr \"uber die Exponenten $c_5, c_7, c_{11},$ u.s.w. treffen. Die HCN $2^1 \cdot 3^1 = 6$ ist die dritte HCN, deren direkt nachfolgende HCN 12 doppelt so gro{\ss} ist. F\"ur jede Zahl $2^1 \cdot 3^1 \cdot 5^1 \cdot \prod_{p=7,11,...} p^{c_p}$ k\"onnen wir allerdings eine Zahl $2^2 \cdot 3^2 \cdot 5^0 \cdot \prod_{p=7,11,...} p^{c_p}$ finden, die um das $\frac{6}{5}$-fache gr\"o{\ss}er ist und mehr Teiler besitzt, da $(2+1) \cdot (2+1) \cdot (0+1) > (1+1) \cdot (1+1) \cdot (1+1) \Leftrightarrow 9 > 8$. Weitere M\"oglichkeiten (mit $c_5 > 1$) entfallen aufgrund der oben erw\"ahnten Monotonie der Primfaktorexponenten $c_p$.

Beim Betrachten des Falles $(c_2,c_3) = (2,1)$ ergibt sich die HCN $2^2 \cdot 3^1 = 12$ als vierte, und die HCN $2^2 \cdot 3^1 \cdot 5^1 = 60$ als f\"unfte HCN, deren direkt nachfolgende HCNs 24 und 120 doppelt so gro{\ss} sind. Die Zahl $2^2 \cdot 3^1 \cdot 5^1 \cdot 7^1 = 420$ ist keine HCN und zu Zahlen der Form $2^2 \cdot 3^1 \cdot 5^1 \cdot 7^1 \cdot 11^1 \cdot \prod_{p=13,17...} p^{c_p}$ findet sich immer eine Zahl $2^4 \cdot 3^2 \cdot 5^1 \cdot 7^1 \cdot 11^0 \cdot \prod_{p=13,17...} p^{c_p}$, die um das $\frac{12}{11}$-fache gr\"o{\ss}er ist und mehr Teiler besitzt, da $(4+1) \cdot (2+1) \cdot (1+1) \cdot (1+1) \cdot (0+1) > (2+1) \cdot (1+1) \cdot (1+1) \cdot (1+1) \cdot (1+1) \Leftrightarrow 60 > 48$. Weitere M\"oglichkeiten (mit $c_5 > 1$, $c_7 > 1$ oder $c_{11} > 1$) entfallen aufgrund der Monotoniebedigung der Primfaktorexponenten.

Nun betrachten wir den letzten Fall $(c_2,c_3) = (3,2)$. Die Zahl $2^3 \cdot 3^2 = 72$ ist keine HCN, die Zahlen $2^3 \cdot 3^2 \cdot 5^1 = 360$ und $2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1 = 2520$ sind die sechste und siebte HCN deren direkt nachfolgende HCNs 720 und 5040 doppelt so gro{\ss} sind. Mit der Zahl $2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1 \cdot 11^1 = 27720$ haben wir eine HCN gefunden deren direkt nachfolgende HCN zwar gr\"o{\ss}er ist als $\frac{3}{2}$, jedoch nicht um das doppelte, sondern um $\frac{18}{11}$. Die Zahl $2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1 \cdot 11^1 \cdot 13^1 = 360360$ ist keine HCN, und zu jeder Zahl $2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1 \cdot 11^1 \cdot 13^1 \cdot 17^1 \cdot \prod_{p=19,23,...} p^{c_p}$ l\"asst sich immer eine Zahl $2^6 \cdot 3^3 \cdot 5^1 \cdot 7^1 \cdot 11^1 \cdot 13^1 \cdot 17^0 \cdot \prod_{p=19,23,...} p^{c_p}$ finden, die $\frac{24}{17}$-mal gr\"o{\ss}er ist und mehr Teiler besitzt, da $(6+1) \cdot (3+1) \cdot (1+1) \cdot (1+1) \cdot (1+1) \cdot (1+1) \cdot (0+1) > (3+1) \cdot (2+1) \cdot (1+1) \cdot (1+1) \cdot (1+1) \cdot (1+1) \cdot (1+1) \Leftrightarrow 448 > 384$. F\"ur alle Zahlen der Form $2^3 \cdot 3^2 \cdot 5^2 \cdot \prod_{p=7,11,...} p^{c_p}$ gibt es immer eine um den Faktor $\frac{6}{5}$ gr\"o{\ss}ere Zahl $2^4 \cdot 3^3 \cdot 5^1 \cdot \prod_{p=7,11,...} p^{c_p}$ mit mehr Teilern, da $(4+1) \cdot (3+1) \cdot (1+1) 
\cdot (0+1) > (3+1) \cdot (2+1) \cdot (2+1) \Leftrightarrow 40 > 36$. Alle weiteren M\"oglichkeiten (z.B. $c_5 > 2$) entfallen wegen der Monotoniebedingung.

\bigskip

Es konnte somit gezeigt werden, dass das Verh\"altnis zweier aufeinander folgender HCNs bis auf 8 Einzelf\"alle nie gr\"o{\ss}er als $\frac{3}{2}$ ist. In 7 dieser F\"alle handelt es sich um HCNs deren jeweils direkt nachfolgende HCN genau doppelt so gro{\ss} ist, der 8. Fall jedoch zeigt auf, dass es genau eine HCN gibt, deren direkt nachfolgende HCN mehr als $\frac{3}{2}$-mal jedoch nicht 2 mal so gro{\ss} ist. Diese HCN lautet 27720; ihr Nachfolger lautet 45360.

\bigskip

Es wurde folgendes Haskell-Programm f\"ur die Berechnungen der HCNs verwendet:

\begin{verbatim}
import Data.Ratio
import Data.Set (Set)
import qualified Data.Set as Set

printList :: (Show a) => [a] -> IO()
printList  =  putStr . concat . map (\x -> show x ++ "\n")

isPrime n
  | n >= 2     =  all isNotDivisor $ takeWhile smallEnough primes
  | otherwise  =  False
  where
    isNotDivisor d  =  n `mod` d /= 0
    smallEnough d   =  d^2 <= n

primes  =  2 : filter isPrime [ 2 * n + 1 | n <- [1..] ]

primeSynthesis  =  partialSynthesis 1 primes
  where
    partialSynthesis n _ []           =  n
    partialSynthesis n (p:ps) (c:cs)  =  partialSynthesis (n * p^c) ps cs

\end{verbatim}
\pagebreak
\begin{verbatim}

primeAnalysis n
  | n < 1   =  undefined
  | n == 1  =  []
  | n > 1   =  reverse $ buildPrimeCounts [0] n
  where
    buildPrimeCounts (c:cs) n
      | n == 1          =  (c:cs)
      | n `mod` p == 0  =  buildPrimeCounts (c+1 : cs) (n `div` p)
      | otherwise       =  buildPrimeCounts (0:c:cs) n
      where  p  =  primes !! (length cs)

divisorCount n  =  product $ map (+1) $ primeAnalysis n

primorialProducts  =  resFrom 1
  where
    resFrom n             =  resBetween n (4*n - 1) ++ resFrom (4*n)
    resBetween start end  =  Set.toAscList $ Set.fromList $ unorderedList
      where
        unorderedList  =  filter (>= start) (1 : build 0 [])
        build pos exponents
          | nextNumber <= end  =  nextNumber : build 0 nextCombination
          | newPrime           =  []
          | otherwise          =  build (pos + 1) exponents
          where
            newPrime  =  pos >= length exponents
            nextCombination
              | newPrime   =  replicate (length exponents + 1) 1
              | otherwise  =  replicate (pos + 1) ((exponents !! pos) + 1)
                              ++ drop (pos + 1) exponents
            nextNumber  =  primeSynthesis nextCombination

filterStrictlyMonotonicDivisorCount  =  filterRest 0
  where
    filterRest _ []  =  []
    filterRest lim (num:nums)
      | divisorCount num > lim  =  num : filterRest (divisorCount num) nums
      | otherwise               =  filterRest lim nums

\end{verbatim}
\pagebreak
\begin{verbatim}

highlyCompositeNumbers
  =  filterStrictlyMonotonicDivisorCount primorialProducts

findBigGaps []   =  []
findBigGaps [_]  =  []
findBigGaps (x1:x2:xs)
  | x1 * 3 < x2 * 2  =  (x1,x2) : findBigGaps (x2:xs)
  | otherwise        =  findBigGaps (x2:xs)

findGaps []   =  []
findGaps [_]  =  []
findGaps (x1:x2:xs)
  | x1 * 3 <= x2 * 2  =  (x1,x2) : findGaps (x2:xs)
  | otherwise         =  findGaps (x2:xs)
\end{verbatim}

\vfill

Es wird unentgeltlich jeder Person das Recht einger\"aumt, Kopien dieses Dokumentes und des dazugeh\"origen Haskell-Programmes zu benutzen, zu kopieren, zu modifizieren, mit anderen Werken zu kombinieren, zu ver\"offentlichen, zu verbreiten, unterzulizensieren, zu verkaufen und/oder weiteren Personen diese Rechte einzur\"aumen, solange der Autor und dieser Hinweis in allen Kopien oder wesentlichen Teilen davon erw\"ahnt werden. Fehlerfreiheit und Funktionsf\"ahigkeit werden nicht zugesichert; Verwendung erfolgt auf eigenes Risiko.

\end{document}