Die Mathe-Redaktion - 19.04.2018 15:26 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 659 Gäste und 23 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » Grenzzyklen einer Harshad-Iteration
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Grenzzyklen einer Harshad-Iteration
querin
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.01.2018
Mitteilungen: 68
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-04-14 21:29

\(\begingroup\)
Harshad- oder Niven-Zahlen sind natürliche Zahlen, die durch ihre Quersumme teilbar sind (siehe OEIS Folge A005349).

Ich betrachte nun folgende Harshad-Iteration:

$a_0=n$, eine positive ganze Zahl, und

$a_{k+1}=\frac{a_k}{s(a_k)}$ falls $a_k$ eine Harshad-Zahl ist, sonst $a_{k+1}=a_k+s(a_k)$

Dabei bezeichnet $s(a_k)$ die Quersumme von $a_k$, also die Summe aller Dezimalziffern von $a_k$.

Ich möchte zeigen, dass diese Folge für jeden Startwert n beschränkt ist.

Über Hinweise und Anregungen würde ich mich sehr freuen.

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2736
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-04-15 09:32


Zumindest kann man die Suche nach Gegenbeispielen deutlich einschränken:

Sei <math>a_k</math> eine höchstens <math>n</math>-stellige Zahl. Dann ist <math>s(a_k) \leq 9n</math>. Angenommen, diese Folge geht in keinen Zyklus über, dann müsste sie irgendwann einen Wert von mindestens <math>10^n</math> annehmen. Der kleinste solche ist dann nach der gerade durchgeführten Überlegung <math>10^n+9n-1</math>.

Also muss man für alle höchstens <math>n</math>-stelligen Zahlen nur die <math>9n</math> Zahlen des Intervalls <math>I:=\left[10^n; 10^n+9n-1\right]</math> untersuchen.

Das Ganze geht noch ein bisschen besser: Sei nämlich 9n eine m-stellige Zahl. Dann ist die Quersumme aller Zahlen in I und generell für alle Zahlen im Intervall <math>\left[10^n; 10^n+10^m-1\right]</math>, welches I umfasst, beschränkt durch 1+9m. Iterieren wir die Folge weiter, bis zum ersten mal der Wert <math>10^n+10^m</math> erreicht bzw. überschritten ist, dann muss das Ergebnis im Intervall <math>J:=\left[10^n+10^m; 10^n+10^m+9m\right]</math> liegen. Es sind also nur noch 9m+1 Zahlen zu testen.

Analog: Ist 9m eine l-stellige Zahl, dann ist die Quersumme alle Zahlen im Intervall <math>\left[10^n+10^m; 10^n+10^m+10^l-1\right]</math>, welches das Intervall J umfasst, beschränkt durch 2+9l. Dementsprechend muss sich das kleinste Folgenglied, was mindestens <math>10^n+10^m+10^l</math> beträgt, im Intervall <math>K:=\left[10^n+10^m+10^l; 10^n+10^m+10^l+9l+1\right]</math> liegen.

Usw. usf. Leider konvergiert diese Intervall-Länge nicht, d.h., für beliebig groß werdende Startzahlen, wächst auch diese Intervall-Länge zu überprüfender Zahlen beliebig an.

Aber z.B. genügt es aus, eine relativ kleine Anzahl von Zahlen zu überprüfen, wenn man sich eine obere Schranke setzt:

Ist die Startzahl kleiner als <math>10^{\left(10^{111110}\right)}</math>, so ist <math>n=10^{111110}</math>, <math>m=111111</math> und <math>l=6</math>. Somit müssen nur die 56 Zahlen von <math>10^n+10^m+10^l</math> bis <math>10^n+10^m+10^l+55</math> überprüft werden.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2736
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-04-15 14:55


Bringen wir den Beweis für alle Startzahlen < <math>S:=10^{\left(10^{111110}\right)}</math> mal zu Ende.

Beweis:

Nach obiger Bemerkung existiert für jede dieser Startzahlen ein Zyklus, dessen Maximum auch kleiner als S ist, oder aber ein Folgenglied, dass im Intervall <math>I=\left[10^n; 10^n+9n-1\right]</math> mit <math>n=10^{111110}</math> liegt. Jedes dieser Folgenglieder kommt nun entweder in den nächsten Iterationen zu einem "Divisions-Schritt", der entweder zu einem Zyklus der Länge 1 (für eine reine Zehnerpotenz) oder zu einem neuen Folgenglied kleiner S führt; oder zu einem Folgenglied aus dem Intervall <math>J=\left[10^n+10^m; 10^n+10^m+9m\right]</math> mit <math>n=10^{111110}</math> und <math>m=111111</math>. Analog folgt wieder ein "Divisions-Schritt", der sofort in einen Zyklus, oder zumindest in ein Folgenglied < S führt, oder ein Folgenglied im Intervall <math>K=\left[10^n+10^m+10^l; 10^n+10^m+10^l+9l+1\right]</math> mit <math>n=10^{111110}</math>, <math>m=111111</math> und <math>l=6</math>.

Es bleibt also noch zu zeigen, dass auf alle Zahlen im Intervall <math>K</math> irgendwann ein "Divisions-Schritt" folgt, der auf ein Folgenglied < S (oder eine stationäre Folge) führt. Hat man dies gezeigt, so gilt für alle Startzahlen  < S, dass sie entweder in eine stationäre Folge übergehen, oder aber nach endlich vielen Folgengliedern wieder im Bereich < S landen, also aufgrund der deterministischen Definition und der endlichen Anzahl an natürlichen Zahlen < S irgendwann in einen Zyklus übergehen müssen, in beiden Fällen also beschränkt sind, was man beweisen wollte.

Wir definieren die Zahlen <math>x_k</math> als <math>x_k:=10^n+10^m+10^l+k</math> für <math>k\geq 0</math>. Dann ist <math>K=\{x_0; \dots; x_{55}\}</math> die Menge der noch zu betrachtenden Zahlen. Offensichtlich ist auch <math>s(x_k)=3+s(k)</math> für <math>k<9*10^l</math>.

Nun die Fallunterscheidung der 56 verbliebenen Zahlen:

0) Es ist <math>s(x_0)=3 | x_0</math>, sodass hier sofort ein "Divisions-Schritt" durch 3 folgt, der auf ein Folgenglied < S führt.

1) Es ist <math>x_1 \rightarrow x_5 \rightarrow x_{13} \rightarrow x_{20}</math>. Ich habe nicht nachgerechnet, ob der konkrete Wert <math>x_{13}</math> durch <math>s(x_{13})=7</math> teilbar ist, aber spätestens <math>x_{20}</math> durch <math>s(x_{20})=5</math> teilbar, sodass entweder beim vorhergehenden oder diesem Folgenglied ein "Divisions-Schritt" folgt, der auf ein Folgenglied < S führt.

2) Es ist <math>x_2 \rightarrow x_7 \rightarrow x_{17} \rightarrow x_{28} \rightarrow x_{41} \rightarrow x_{49} \rightarrow x_{65} \rightarrow x_{79} \rightarrow x_{98} \rightarrow x_{118} \rightarrow x_{131} \rightarrow x_{139} \rightarrow x_{155} \rightarrow x_{169} \rightarrow x_{188} \rightarrow x_{208} \rightarrow x_{221} \rightarrow x_{229} \rightarrow x_{245} \rightarrow x_{259} \rightarrow x_{278} \rightarrow x_{298} \rightarrow x_{320}</math>.

Dabei ist <math>x_{320}=10^n+10^m+10^l+320</math> durch <math>s(x_{320})=1+1+1+3+2=8</math> teilbar.

3) Es ist <math>x_3 \rightarrow x_9 \rightarrow x_{21} \rightarrow x_{27} \rightarrow x_{39} \rightarrow x_{54} \rightarrow x_{66} \rightarrow x_{81} \rightarrow x_{93} \rightarrow x_{108}</math>. Es ist <math>x_{108}=10^n+10^m+10^l+108</math> und <math>s(x_{108})=12 | x_{108}</math>.

4) Es ist <math>x_4 \rightarrow x_{11} \rightarrow x_{16} \rightarrow x_{26} \rightarrow x_{37} \rightarrow x_{50} \rightarrow x_{58} \rightarrow x_{74} \rightarrow x_{88} \rightarrow x_{107} \rightarrow x_{118}</math>, weiter siehe Berechnung bei <math>x_2</math>.

5) Siehe <math>x_1</math>.

6) Es ist <math>x_6</math> durch <math>s(x_6)=9</math> teilbar.

7) Siehe <math>x_2</math>.

8) Es ist <math>x_8 \rightarrow x_{19} \rightarrow x_{32} \rightarrow x_{40} \rightarrow x_{47} \rightarrow x_{61} \rightarrow x_{71} \rightarrow x_{82} \rightarrow x_{95} \rightarrow x_{112} \rightarrow x_{119} \rightarrow x_{133} \rightarrow x_{143} \rightarrow x_{154} \rightarrow x_{167} \rightarrow x_{184} \rightarrow x_{200}</math>, was durch <math>s(x_{200})=5</math> teilbar ist.

9) Siehe <math>x_3</math>.

10) Es ist <math>x_{10} \rightarrow x_{14} \rightarrow x_{22} \rightarrow x_{29} \rightarrow x_{43} \rightarrow x_{53} \rightarrow x_{64} \rightarrow x_{77} \rightarrow x_{94} \rightarrow x_{110}</math>, was durch <math>s(x_{110})=5</math> teilbar ist.

11) Siehe <math>x_4</math>.

12) Es ist <math>x_{12}</math> durch <math>s(x_{12})=6</math> teilbar.

13) Siehe <math>x_1</math>.

14) Siehe <math>x_{10}</math>.

15) Es ist <math>x_{15}</math> durch <math>s(x_{15})=9</math> teilbar.

16) Siehe <math>x_4</math>.

17) Siehe <math>x_2</math>.

18) Es ist <math>x_{18} \rightarrow x_{30}</math>, was durch <math>s(x_{30})=6</math> teilbar ist.

19) Siehe <math>x_8</math>.

20) Siehe <math>x_1</math>.

21) Siehe <math>x_3</math>.

22) Siehe <math>x_{10}</math>.

23) Es ist <math>x_{23} \rightarrow x_{31} \rightarrow x_{38} \rightarrow x_{52} \rightarrow x_{62} \rightarrow x_{73} \rightarrow x_{86} \rightarrow x_{103} \rightarrow x_{110}</math>, siehe <math>x_{10}</math>.

24) Es ist <math>x_{24}</math> durch <math>s(x_{24})=9</math> teilbar.

25) Es ist <math>x_{25} \rightarrow x_{35} \rightarrow x_{46} \rightarrow x_{59} \rightarrow x_{76} \rightarrow x_{92} \rightarrow x_{106} \rightarrow x_{116} \rightarrow x_{127} \rightarrow x_{140} \rightarrow x_{148} \rightarrow x_{164} \rightarrow x_{178} \rightarrow x_{197} \rightarrow x_{217} \rightarrow x_{230} \rightarrow x_{238} \rightarrow x_{254} \rightarrow x_{268} \rightarrow x_{287} \rightarrow x_{307} \rightarrow x_{320}</math>,

was durch <math>s(x_{320})=8</math> teilbar ist.

26) Siehe <math>x_4</math>.

27) Siehe <math>x_3</math>.

28) Siehe <math>x_2</math>.

29) Siehe <math>x_{10}</math>.

30) Siehe <math>x_{18}</math>.

31) Siehe <math>x_{23}</math>.

32) Siehe <math>x_8</math>.

33) Es ist <math>x_{33}</math> durch <math>s(x_{33})=9</math> teilbar.

34) Es ist <math>x_{34} \rightarrow x_{44} \rightarrow x_{55} \rightarrow x_{68} \rightarrow x_{85} \rightarrow x_{101} \rightarrow x_{107} \rightarrow x_{118}</math>, weiter wie bei <math>x_2</math>.

35) Siehe <math>x_{25}</math>.

36) Es ist <math>x_{36}</math> durch <math>s(x_{36})=12</math> teilbar.

37) Siehe <math>x_4</math>.

38) Siehe <math>x_{23}</math>.

39) Siehe <math>x_3</math>.

40) Siehe <math>x_8</math>.

41) Siehe <math>x_2</math>.

42) Es ist <math>x_{42}</math> durch <math>s(x_{42})=9</math> teilbar.

43) Siehe <math>x_{10}</math>.

44) Siehe <math>x_{34}</math>.

45) Es ist <math>x_{45} \rightarrow x_{57} \rightarrow x_{72}</math>, was durch <math>s(x_{72})=12</math> teilbar ist.

46) Siehe <math>x_{25}</math>.

47) Siehe <math>x_8</math>.

48) Es ist <math>x_{48} \rightarrow x_{63} \rightarrow x_{75}</math> durch <math>s(x_{75})=15</math> teilbar.

49) Siehe <math>x_2</math>.

50) Siehe <math>x_4</math>.

51) Es ist <math>x_{51}</math> durch <math>s(x_{51})=9</math> teilbar.

52) Siehe <math>x_{23}</math>.

53) Siehe <math>x_{10}</math>.

54) Siehe <math>x_3</math>.

55) Siehe <math>x_{34}</math>.


Damit ist der Beweis erbracht: Für jede Startzahl kleiner als <math>S=10^{(10^{111110})}</math> geht die vom Fragesteller definierte Folge in einen Zyklus über, <math>\Box</math>.

Bemerkung: Überall wurden Abbruch-Kriterien gefunden, die unabhängig von den konkreten Werten <math>n>k>l\geq 3</math> sind. Damit sollten sich analog auch noch deutlich größere Bereiche abdecken lassen.

Cyrix

edit: Aussagen-Bereich deutlich vergrößert.



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.01.2018
Mitteilungen: 68
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2018-04-15 21:45


Großartig, Cyrix, vielen Dank!

Du hast das so ausführlich und klar erklärt, dass sogar ich es verstanden habe.

2018-04-15 14:55 - cyrix in Beitrag No. 2 schreibt:
Bemerkung: Überall wurden Abbruch-Kriterien gefunden, die unabhängig von den konkreten Werten <math>n>k>l\geq 3</math> sind. Damit sollten sich analog auch noch deutlich größere Bereiche abdecken lassen.

Lässt sich daraus vielleicht sogar ein allgemeiner Beweis ableiten?



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.01.2018
Mitteilungen: 68
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-04-16 20:20

\(\begingroup\)
Beim Programmieren der Iteration ist mir Folgendes aufgefallen: Ab einem gewissen (vom Startwert abhängigen) Index $k_0$ gilt:

• Fall 1: die Folge wird konstant (wenn $a_{k_0}=10^p$ für $p\geq 0$), oder

• Fall 2: die Folge mündet in einen Zyklus der Länge 24 (und zwar immer in jenen, der sich aus dem Startwert 64 ergibt).

Es scheint nur diese beiden Fälle zu geben. Kann man diese Vermutung beweisen (bzw. widerlegen) oder zumindest ein Kriterium angeben, welche Startwerte zum 24er-Zyklus führen?

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
querin hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]