Zahlensuche < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| 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.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
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?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
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.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Mi 14.02.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
