matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieZahlensuche
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Zahlentheorie" - Zahlensuche
Zahlensuche < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Zahlensuche: Teilbarkeit und Quersumme
Status: (Frage) überfällig Status 
Datum: 12:12 So 14.01.2007
Autor: ThomasLehmann

Aufgabe
Gegeben sei eine Zahl 'n'.
Gesucht ist einen Zahl 'm' für die gilt:
   1) 'm' ist durch 'n' teilbar und 'm' ist die kleinste Zahl dieser Art!
   2) Quersumme('m') = 'n'

Hintergrund: Ich bin Programmierer (Arbeit=Hobby) und unter www.sproj.pl gibt es die Aufgabe 'INUMBER' die ich gerne lösen möchte. Es gibt einen einfachen Algorithmus der alle Lösungen liefert aber nicht unter 7 Sekunden (von mir in Python geschrieben)!

Da ich davon ausgehe, daß ich mehr über Zahlentheorie wissen muß, stelle ich hier die Frage.

Probleme die ich hatte:
- 'n + k*9' liefert nicht immer eine Zahl deren Quersumme 'n' ist
   (n=10 -> 19, 28, 37, 46, 55, 64, 73, 84, 91, >100<, 109, 118, ...)
- kleinste Quersumme für 40 ist 49999, aber die Zahl ist immer noch
   weit von 699880 entfernt - wie komme ich schnell näher heran?
- Erkennen von Regelmäßigkeiten.

Könnte Bitte jemand helfen?

Anhang: (Auszug aus meiner Programmausgabe)

n            m
------------------
10          190
11          209
12          48
13          247
...
55          60989995
56          7979888

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Zahlensuche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:20 So 14.01.2007
Autor: felixf

Hallo Thomas!

> Gegeben sei eine Zahl 'n'.
>  Gesucht ist einen Zahl 'm' für die gilt:
>     1) 'm' ist durch 'n' teilbar und 'm' ist die kleinste
> Zahl dieser Art!
>     2) Quersumme('m') = 'n'
>  Hintergrund: Ich bin Programmierer (Arbeit=Hobby) und
> unter www.sproj.pl gibt es die Aufgabe 'INUMBER' die ich

Du meinst sicher spoj.pl? Der genaue Link zum Problem: http://www.spoj.pl/problems/INUMBER/

> gerne lösen möchte. Es gibt einen einfachen Algorithmus der
> alle Lösungen liefert aber nicht unter 7 Sekunden (von mir
> in Python geschrieben)!
>  
> Da ich davon ausgehe, daß ich mehr über Zahlentheorie
> wissen muß, stelle ich hier die Frage.
>  
> Probleme die ich hatte:
>   - 'n + k*9' liefert nicht immer eine Zahl deren Quersumme
> 'n' ist
>     (n=10 -> 19, 28, 37, 46, 55, 64, 73, 84, 91, >100<,

> 109, 118, ...)

Genau. Aber jede Zahl, deren Quersumme $n$ ist und die durch $n$ teilbar ist, laesst sich so schreiben.

(Ich schreib das jetzt mal ein wenig mathematischer auf, wenn du mit der Schreibweise nicht klar kommst frag nach!)

Man kann sogar noch mehr sagen: Wenn $m = [mm] \sum_{i=0}^k a_i 10^i$ [/mm] ist mit [mm] $a_i \in \{ 0, \dots, 9 \}$ [/mm] (Dezimaldarstellung), dann muss ja [mm] $\sum_{i=0}^k a_i [/mm] = n$ und [mm] $\sum_{i=0}^k a_i 10^i \equiv [/mm] 0 [mm] \pmod{n}$ [/mm] gelten.

Das [mm] $\sum_{i=0}^k a_i [/mm] = n$ impliziert natuerlich auch [mm] $\sum_{i=0}^k a_i \equiv [/mm] n [mm] \pmod{9}$. [/mm] Nun ist aber [mm] $\sum_{i=0}^k a_i 10^i \equiv \sum_{i=0}^k a_i \pmod{9}$, [/mm] womit $m [mm] \equiv [/mm] n [mm] \pmod{9}$ [/mm] gilt.

Damit hast du die zwei Kongruenzgleichungen $m [mm] \equiv [/mm] n [mm] \pmod{9}$ [/mm] und $m [mm] \equiv [/mm] 0 [mm] \pmod{n}$. [/mm] Nach dem Chinesischen Restsatz kann man das in der Form $m [mm] \equiv \ell \pmod{lcm(9, n)}$ [/mm] schreiben (wobei lcm das kleinste gemeinsame Vielfach ist) fuer irgendein [mm] $\ell \in \{ 0, \dots, lcm(9, n) \}$. [/mm]

Damit haettest du schonmal einen viel kleineren Suchraum, naemlich $m = [mm] \ell [/mm] + lcm(9, n) k$, als wenn du nach $m = n + 9 k$ suchst. (Um [mm] $\ell$ [/mm] zu bestimmen, mach eine Fallunterscheidung nach $3 [mm] \nmid [/mm] n$, $3 [mm] \mid [/mm] n$ aber $9 [mm] \nmid [/mm] n$, und $9 [mm] \mid [/mm] n$.)

>   - kleinste Quersumme für 40 ist 49999, aber die Zahl ist
> immer noch
>     weit von 699880 entfernt - wie komme ich schnell näher
> heran?
> - Erkennen von Regelmäßigkeiten.

Ich vermute mal es gibt da noch ein paar mehr Regelmaessigkeiten, die man ausnutzen muss. Gerade faellt mir allerdings nichts ein,

HTH! LG Felix


Bezug
                
Bezug
Zahlensuche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:29 So 14.01.2007
Autor: felixf

Hallo Thomas,
noch etwas einfacher:
aus $n [mm] \equiv [/mm] m [mm] \pmod{9}$ [/mm] und $n [mm] \mid [/mm] m$ folgt $m = n k$ mit $k [mm] \in \IN$ [/mm] und $9 [mm] \mid [/mm] (n - m) = (n - n k) = n (1 - k)$. Also kannst du $m = n k$ schreiben so, dass $9$ ein Teiler von $n (1 - k)$ ist. Fuer $k$ muss also gelten:
- Ist 9 ein Teiler von $n$, so ist $k$ beleibig.
- Ist 3 ein Teiler von $n$, 9 aber nicht, so muss $1 - k$ durch 3 teilbar sein, also $k = 1 + 3 [mm] \ell$ [/mm] sein fuer [mm] $\ell \in \IN$. [/mm]
- Ist 3 kein Teiler von $n$, so muss $1 - k$ durch 9 teilbar sein, also $k = 1 + 9 [mm] \ell$ [/mm] fuer [mm] $\ell \in \IN$. [/mm]
LG Felix


Bezug
                        
Bezug
Zahlensuche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 06:04 Mo 15.01.2007
Autor: ThomasLehmann

Also, ich habe es auch gleich ausprobiert und das funktioniert auch! Jetzt habe ich aber dazu noch folgende kleine Fragen:
1) n|m    heißt wohl 'n' ist Teiler von 'm'?
2) n [mm] \equiv [/mm] m (mod 9) heißt wohl 9 ist Teiler von (m - n)?
3)
    In meiner Bedingung prüfe ich immer:
        WENN m TEILBAR DURCH n  UND Quersumme(m) GLEICH n DANN

    Kann auf Grund der Formeln einen Überprüfung wegfallen?




Bezug
                                
Bezug
Zahlensuche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:41 Mo 15.01.2007
Autor: felixf

Hallo Thomas,

> Also, ich habe es auch gleich ausprobiert und das
> funktioniert auch! Jetzt habe ich aber dazu noch folgende
> kleine Fragen:
>  1) n|m    heißt wohl 'n' ist Teiler von 'm'?
>  2) n [mm]\equiv[/mm] m (mod 9) heißt wohl 9 ist Teiler von (m -
> n)?

genau, beides stimmt so.

>  3)
>      In meiner Bedingung prüfe ich immer:
>          WENN m TEILBAR DURCH n  UND Quersumme(m) GLEICH n
> DANN
>  
> Kann auf Grund der Formeln einen Überprüfung wegfallen?

Wenn $m = n k$ ist fuer ein $k [mm] \in \IN$, [/mm] dann gilt natuerlich, dass $m$ teilbar durch $n$ ist; das kann also wegfallen. Die zweite Bedingung, naemlich dass die Quersumme von $m$ gleich $n$ ist, brauchst du weiterhin.

LG Felix


Bezug
                                        
Bezug
Zahlensuche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:14 Mi 24.01.2007
Autor: ThomasLehmann

Schön und gut mit den Faktoren, aber es kann nicht letzter Weisheit Schluss sein ... im Gegenteil, es muß noch einen "gigantischen" Faktor geben, der bisher scheinbar keinem aufgefallen ist.

Wenn ich eine Schleife drehe von "n  = 1 bis 70", dann bewegen wir uns (mit Python) in einen Zeitraum unter einer Minute, dann aber geht es schnell in große Zeiträume - vermutlich Stunden - ich wollte solange auf keinen Fall warten. Bis n = 1000 müsste ich Ergebnisse bekommen; wenn ich die Aufgabe schon nicht unter 7 Sekunden berechnen lassen kann, dann würde ich doch gerne unterhalb von 15 Minuten mal was sehen...

Hat irgend jemand noch andere Ideen?

Wenn einer mein jetziges Python Script mal haben will soll eine EMail Addresse angeben an die ich das senden kann, oder mir sagen, ob das in dieser Aufgabe als Beitrag angehängt werden soll.


Bezug
        
Bezug
Zahlensuche: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:20 Mi 14.02.2007
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]