Kuriose Rekursion

[Rainer adS]

Sei a eine natürliche Zahl >= 1.

tau(n) sei - wie üblich - die Anzahl der positiven Teiler von n.

Wir definieren rekursiv

a_1 = a.
a_{n+1} = (tau(a_n))^2

Beweise, daß die Folge irgendwann konstant wird.

Das ist nicht schwer zu zeigen aber erscheint erst mal unplausibel.

Gruß,

Rainer

[Alfred Flaßhaar]

Am 16.01.2023 um 14:35 schrieb Rainer adS:
> Sei a eine natürliche Zahl >= 1.
>
> tau(n) sei - wie üblich - die Anzahl der positiven Teiler von n.
>
> Wir definieren rekursiv
>
>     a_1 = a.
>     a_{n+1} = (tau(a_n))^2
>
> Beweise, daß die Folge irgendwann konstant wird.
>

Der Fixpunkt ist nicht 42 sondern 9.

Gruß, Alfred

[Rainer adS]

Beweis?

Rainer

PS: In der Vorlesung vor 50 Jahren hieß das "Beweis durch hingucken" :)

[Diedrich Ehlerding]

Alfred Flaßhaar meinte:

Hm ... sobald ein tau(a_n)=p eine Primzahl ist, hat p^2=a_{n+1} nur
die Teiler 1,p und p^2, und dann ist a_{n+2} wieder das Quadrat einer
Primzahl, nämlich der Primzahl 3. Wenn es also einen Fixpunkt gibt,
einen für alle Zahlen a_1 identischen Fixpunkt, dann ist es tatsächlich
die 9.

Nur sehe ich noch nicht, wieso für beliebiges a_1 für irgendein n ein
tau(a_n) Primzahl werden muss.
--
gpg-Key (DSA 1024) D36AD663E6DB91A4
fingerprint = 2983 4D54 E00B 8483 B5B8 C7D1 D36A D663 E6DB 91A4
HTML-Mail wird ungeleſen entſorgt.

[Alfred Flaßhaar]

Am 19.01.2023 um 19:07 schrieb Diedrich Ehlerding:
> Alfred Flaßhaar meinte:
>
>> Am 16.01.2023 um 14:35 schrieb Rainer adS:
>>> Sei a eine natürliche Zahl >= 1.
>>>
>>> tau(n) sei - wie üblich - die Anzahl der positiven Teiler von n.
>>>
>>> Wir definieren rekursiv
>>>
>>> a_1 = a.
>>> a_{n+1} = (tau(a_n))^2
>>>
>>> Beweise, daß die Folge irgendwann konstant wird.
>>>
>> Der Fixpunkt ist nicht 42 sondern 9.
>
> Hm ... sobald ein tau(a_n)=p eine Primzahl ist, hat p^2=a_{n+1} nur
> die Teiler 1,p und p^2, und dann ist a_{n+2} wieder das Quadrat einer
> Primzahl, nämlich der Primzahl 3. Wenn es also einen Fixpunkt gibt,
> einen für alle Zahlen a_1 identischen Fixpunkt, dann ist es tatsächlich
> die 9.
>
> Nur sehe ich noch nicht, wieso für beliebiges a_1 für irgendein n ein
> tau(a_n) Primzahl werden muss.

Die Rekursion erzeugt eine Folge natürlicher Zahlen. Wenn diese Folge ab
einem Index nur noch konstante Glieder liefert, dann wird ab diesem
Index die Fixpunktgleichung x = (tau(x))^2 erfüllt. Sei also x eine
solche Lösung der Fixpunktgleichung. Unabhängig davon besitzt x die
eindeutige klassische Primzahldarstellung aus n Faktoren

x = (p_1)^(alfa_1) * ... * (p_n)^(alfa_n).

Nimmt man die Eins zur Teileranzahl hinzu, dann ergibt sich die
Teileranzahl von x durch Kombinationsberechnung aus den Exponenten e_i

zu tau(x) = (alfa_1 + 1)* ... *(alfa_n + 1) .

Dies in die Gleichung x = (tau(x))^2 eingesetzt zeigt, daß links und
rechts in der Gleichung gleichviel Faktoren (n Stück) stehen. Zum
Existenznachweis genügt daher das einzelne Gleichsetzen der linken mit
den rechten Faktoren. Da rechts Quadrate stehen, sind auf der linken
Seite die alfa_i = 2, auf der rechten Seite dann die alfa_i +1 = 3 und
durch Vergleich mit linker Seite sind die p_i dann = 3. Damit stehen
nach Einsetzen der Zahlen links und rechts Produkte aus n Faktoren 3^2.

Insgesamt:

Ist n die Anzahl der Primfaktorpotenzen von x, dann existiert zu jedem n
eine Lösung der Form x = 3^2* ...*3^2 aus n Dreierquadraten.

Morgengruß, Alfred

[neu...@tuhh.de]

Besser: Die Fixpunkte sind 1 und 9 - oder?

VG SiggiN.

[Rainer Rosenthal]

Die Aussage von Alfred lässt sich verschärfen:
Der Fixpunkt ist auch nicht 43.

Liebe Grüße,
Rainer

[neu...@tuhh.de]

Betrachte ich die Folge 18, 36, 81, 25, 9, 9, ..., 9, ...
so habe ich Zweifel am Beweis, ggf. aber auch nur weil ich ihn noch nicht verstanden habe!?

Gruß SiggiN.

[Alfred Flaßhaar]

Am 22.01.2023 um 14:15 schrieb neu...@tuhh.de:
> Alfred Flaßhaar schrieb am Freitag, 20. Januar 2023 um 07:00:10 UTC+1:
>> Am 19.01.2023 um 19:07 schrieb Diedrich Ehlerding:
>>> Alfred Flaßhaar meinte:
>>>
>>>> Am 16.01.2023 um 14:35 schrieb Rainer adS:
>>>>> Sei a eine natürliche Zahl >= 1.
>>>>>
>>>>> tau(n) sei - wie üblich - die Anzahl der positiven Teiler von n.
>>>>>
>>>>> Wir definieren rekursiv
>>>>>
>>>>> a_1 = a.
>>>>> a_{n+1} = (tau(a_n))^2
>>>>>
>>>>> Beweise, daß die Folge irgendwann konstant wird.
>>>>>

(...)

>
> Betrachte ich die Folge 18, 36, 81, 25, 9, 9, ..., 9, ...
> so habe ich Zweifel am Beweis, ggf. aber auch nur weil ich ihn noch nicht verstanden habe!?
>

Die Aufgabe verlangt nur den Nachweis, daß die rekursiv erzeugte Folge
natürlicher Zahlen nach endlich vielen Schritten konstant bleibt, die
Folgenglieder sich also selbst reproduzieren. Den offensichtlichen
Trivialfall a=1 können wir bei weiteren Betrachtungen weglassen als
Lösung der Fixpunktgleichung.

Ist mit a eine Startzahl vorgegeben, dann ist mit n als Anzahl ihrer
Primfaktoren auch eine Zahl festgemacht. Gleiches gilt für die
Primzahlexponenten (die alfas). Meine Bemerkung zu Diedrichs
Feststellung ist kein Beweis der Behauptung von Rainer adS, sondern nur
die Feststellung: Wenn die Fixpunktgleichung eine Lösung besitzt, dann
ist es eine Potenz der Neun. Daß man beim konkreten Berechnen von
Beispielen immer wieder auf Neun stößt, hat andere Ursachen.

Nur kurz skizziert, da Zeitnot im Wartebereich einer Praxis:

Ab a_2 entsteht eine monoton fallende Folge ungerader Quadratzahlen, da
Quadratzahlen immer eine ungerade Teileranzahl besitzen und es nur Sinn
macht, Teiler bis sqrt(a_i) zu untersuchen. Der unendliche Abstieg
liefert den Rest.

Gruß, Alfred

[neu...@tuhh.de]

Moin Alfred, danke, hatte es nicht verstanden,
aber Dein letzter Absatz führte zur Erleuchtung:

Ich hatte 9² als 3²*3² "geführt" und kam so nicht auf die absteigende Folge 9², 5², 3² (unendlichen Abstieg!)
in 2*3², 2²*3³, 3²*3², 5², 3², ...
Ich war aber "auf der Fährte!" ;-) Aber einfach fand ich's nicht.

Gruß SiggiN.