Teilbarkeitsregeln


  • Mod

    314159265358979 schrieb:

    Wieder was gelernt. Kann man auch allgemeine Teilbarkeitsregeln für jede beliebige Zahl in jedem beliebigen Zahlensystem aufstellen?

    Nein.



  • 314159265358979 schrieb:

    Wieder was gelernt. Kann man auch allgemeine Teilbarkeitsregeln für jede beliebige Zahl in jedem beliebigen Zahlensystem aufstellen?

    Erstaunlicherweise ja, bin fast sicher. Wäre total sicher, wenn ich Projekt Euler bearbeitet hätte.
    Edit: Hängt davon ab, bis wohin Du etwas eine Teilbarkeitsregel nennst. Letztlich ist es immer eine Multiplikation oder Division, die gegebenenfalls verfrüht abgebrochen werden kann, oder wo man Zwischenergebnisse weglassen oder vereinfachen kann.

    Aber manche sind saublöd zu handhaben, wie die verschiedenen Teilbarkeitsregeln durch 7 im 10-er-System.

    Ich mag diese für die 8 im 10-er-System: Alles ab jetzt mod 8 rechnen: Vorvorletzte Ziffer nehmen. Verdoppeln. Vorletze Ziffer addieren. Verdoppeln. Letzte Ziffer addieren. Kommt 8 raus, war die Ausgangszahl durch 8 teilbar.


  • Mod

    volkard schrieb:

    Erstaunlicherweise ja, bin fast sicher. Wäre total sicher, wenn ich Projekt Euler bearbeitet hätte.

    Wirklich sicher? Ich bin mir nämlich fast sicher, dass du für einige Zahlen nur die allgemeine Regel finden kannst, dass die Zielzahl durch die Primfaktoren des Divisors teilbar sein muss. Aber das ist irgendwie billig und würde ich nicht als echte Teilbarkeitsregel zählen.



  • Dass MSVC da zwei Divisionen durchführt, dürfte daran liegen, dass

    int b = a / 10;
      int c = b % 10;
    

    statt

    int b = a / 10;
      int c = a % 10;
    

    geprüft wurde. Gcc erledigt das mit -O2 in einem Rutsch, und es sollte mich sehr wundern, wenn MSVC das nicht könnte.



  • Dann hat cookie sich wohl vertippt 🤡

    @volkard: Das interessiert mich aber jetzt genauer.



  • volkard schrieb:

    Wäre total sicher, wenn ich Projekt Euler bearbeitet hätte.

    Welche Problemnummer?



  • 314159265358979 schrieb:

    Dann hat cookie sich wohl vertippt 🤡

    Jau, ärgerlich. Hätte eigentlich sofort auffallen sollen, verdammt.

    int b = a / 10;
      int c = a % 10;
    008616C3  mov         ecx,dword ptr [esp+4]  
    008616C7  mov         eax,66666667h  
    008616CC  imul        ecx  
    008616CE  sar         edx,2  
    008616D1  mov         eax,edx  
    008616D3  shr         eax,1Fh  
    008616D6  add         eax,edx  
    008616D8  lea         edx,[eax+eax*4]  
    008616DB  add         edx,edx  
    008616DD  sub         ecx,edx
    


  • 314159265358979 schrieb:

    Dann hat cookie sich wohl vertippt 🤡
    @volkard: Das interessiert mich aber jetzt genauer.

    Den Wikipedia-Artiklen kannste komplett in der Pfeife rauchen. Die Vermischen andauernd Teilbarkeitsregeln und allein auf bestimmten Quersummen beruhende Teilbarkeitsregeln und kommen so auf die These, daß es für manche Zahlen keine Teilbarkeitsregeln geben würde. Ich bin mir sicher, sobald sie das beweisen können, fällt die Welt in sich zusammen.

    Ich mache mal folgenden Dumm-Test für die Teilbarkeit von 39457 durch 7, wobei ich vorne Vierfache von 7 abziehe.

    39457: 35 am Anfang weg
     4457: 42 am Anfang weg
      257: 21 am Anfang weg
       47: 47 ist nicht durch 7 teilbar.
    

    Das war jetzt einfach eine Grundschul-Division unter Wegfallenlassung des Ergebnisspeichers.

    Ich kann auch hinten abziehen.

    39457: 7 am Ende weg
    39450: 35 am Ende weg
    39100: 21 am Ende weg
    37000: 7 am Ende weg
    30000: 30000 ist nicht durch 7 teilbar
    

    Aber das gefällt mir nicht, da können schlimme Überträge auftauchen.

    Jetzt mag man einwenden, das sei keine Teilbarkeitsregel, weil sie nicht "genug" arbeit spare. Naja, sie erspratz mir aber, komplexere Teilbarkeitsregeln zu lernen. Diese klappt mit jeder Zahl.

    Und laß Dich hier von der 17-er-Regel beflügeln.
    http://matheplanet.com/default3.html?call=article.php?sid=134
    Ist die einfach genug?



  • Michael E. schrieb:

    volkard schrieb:

    Wäre total sicher, wenn ich Projekt Euler bearbeitet hätte.

    Welche Problemnummer?

    Ich dachte an das Zeugs um die repunits, um zu schauen, welche auf besonderen Quersummen basierende Verfahren möglich sind.



  • SeppJ schrieb:

    Zahlen nur die allgemeine Regel finden kannst, dass die Zielzahl durch die Primfaktoren des Divisors teilbar sein muss. Aber das ist irgendwie billig und würde ich nicht als echte Teilbarkeitsregel zählen.

    Die ist aber stark und unglaublich nützlich. Lassen wir sie leben!
    Vorhin die 30000 / 7.
    Ich sehe, daß die 30000 als Primfaktoren nur die 2, 5 und 3 haben kann und die Sache hat sich erledigt.



  • volkard schrieb:

    39457: 35 am Anfang weg
     4457: 42 am Anfang weg
      257: 21 am Anfang weg
       47: 47 ist nicht durch 7 teilbar. // ? 42 am Anfang weg
        5: 5 ist nicht durch 7 teilbar.
    

    🤡



  • volkard schrieb:

    Jetzt mag man einwenden, das sei keine Teilbarkeitsregel, weil sie nicht "genug" arbeit spare. Naja, sie erspratz mir aber, komplexere Teilbarkeitsregeln zu lernen. Diese klappt mit jeder Zahl.

    Naja. Es ist ja eigentlich nur genauso wieder eine Division.


  • Mod

    volkard schrieb:

    Jetzt mag man einwenden, das sei keine Teilbarkeitsregel, weil sie nicht "genug" arbeit spare. Naja, sie erspratz mir aber, komplexere Teilbarkeitsregeln zu lernen. Diese klappt mit jeder Zahl.

    Im Prinzip hast du explizit durch 7 geteilt, bloß ohne das Ergebnis hinzuschreiben. Ich würde das nicht gerade unter Teilbarkeitsregel zählen. Das ist wie zu sagen X modulo N == 0 wäre eine Teilbarkeitsregel für N. Das ist bloß die Definition von Teilbarkeit.

    Primfaktorzerlegung ist leider auch nicht immer so trivial, habe ich mir sagen lassen 😉 .



  • Noch ein Versuch für die 7:

    Ich brauche eine Operation normdupneg, die eine Ziffer modulo 7 verdoppelt, negiert und normiert.
    also
    0 -> 0
    1 (dup)->2 (neg)->5
    2 (dup)->4 (neg)->3
    3 (dup)->6 (neg)->1
    4 (neg)->3 (dup)->6
    5 (neg)->2 (dup)->4
    6 (neg)->1 (dup)->2

    3740345
    
    5 
    normdupneg = 4, +=4 = 1
    normdupneg = 5, +=3 = 1
    normdupneg = 5, +=0 = 5
    normdupneg = 4, +=4 = 1
    normdupneg = 5, +=7 = 5 (statt 12, darum nur eine Ziffer)
    normdupneg = 4, +=3 = 0
    => true
    

    edit: Zu computerisch gedacht.
    Immer die letze Ziffer verdoppeln und von der vorletzen abziehen. Wenn nicht kappt, wird eine möp-Exception geworfen und vor dem Abziehen 7 dazugezählt.

    3740345
    5 doppelt ist 10, 4-10(möp) 11-10=1
    1 dopplet ist 2, 3-2=1
    1 doppelt ist 2, 0-2(möp) 7-2=5
    5 doppelt ist 10 ist 3, 4-3=1
    1 doppelt ist 2, 7-2=5
    5 doppelt ist 10 ist 3, 3-3=0
    0=> true
    


  • 0 - 1 2 3 - 4 5 6 - 10 11 12 - 13 14 15 - 16 20 21

    0 - 1 2 3 - 4 10 11 - 12 13 14 - 20 21 22 - 23 24 30

    1111:11 testen

    1+
    1
    = 10

    10
    +1
    11

    11
    +1
    100

    andererseits...

    C:\Users\nachtfeuer>debug
    
    -rax
    AX 0000  :123
    -rbx
    BX 0000  :3
    -a
    1B29:0100 div bx
    1B29:0102
    -t
    DPMI entry hooked, new entry=1449:2C2F
    AX=0061 BX=0003 CX=0000 DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
    DS=1B29 ES=1B29 SS=1B29 CS=1B29 IP=0102 NV UP EI PL ZR NA PE NC
    1B29:0102 0000              ADD     [BX+SI],AL                       DS:0003=9F
    -rax
    AX 0061  :120
    -rip
    IP 0102  :100
    -r
    AX=0120 BX=0003 CX=0000 DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
    DS=1B29 ES=1B29 SS=1B29 CS=1B29 IP=0100 NV UP EI PL ZR NA PE NC
    1B29:0100 F7F3              DIV     BX
    -t
    AX=0060 BX=0003 CX=0000 DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
    DS=1B29 ES=1B29 SS=1B29 CS=1B29 IP=0102 NV UP EI PL ZR NA PE NC
    1B29:0102 0000              ADD     [BX+SI],AL                       DS:0003=9F
    -rip
    IP 0102  :100
    -rax
    AX 0060  :98
    -r
    AX=0098 BX=0003 CX=0000 DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
    DS=1B29 ES=1B29 SS=1B29 CS=1B29 IP=0100 NV UP EI PL ZR NA PE NC
    1B29:0100 F7F3              DIV     BX
    -t
    AX=0032 BX=0003 CX=0000 DX=0002 SP=FFFE BP=0000 SI=0000 DI=0000
    DS=1B29 ES=1B29 SS=1B29 CS=1B29 IP=0102 NV UP EI PL ZR NA PE NC
    1B29:0102 0000              ADD     [BX+SI],AL                       DS:0003=9F
    -
    

    🤡



  • Wie bitte?



  • SeppJ schrieb:

    Primfaktorzerlegung ist leider auch nicht immer so trivial, habe ich mir sagen lassen 😉 .

    trivial schon, wenn man Geduld hat 😃



  • !rr!rr_. schrieb:

    SeppJ schrieb:

    Primfaktorzerlegung ist leider auch nicht immer so trivial, habe ich mir sagen lassen 😉 .

    trivial schon, wenn man Geduld hat 😃

    Es geht un eine Teilbarekeitsregel, die eine unbekannte Zahl prüft, ob sie durch einen bekannten Teiler teilbar ist. Der bekannte Teiler hat seine Primfaktorzerlegung schon längst verraten.
    Was ich mit der 30000 machte, war eine Ausnahme.



  • Ich bin mir nicht ganz sicher, ob ich verstehe was ihr sucht, aber was man machen kann ist folgendes. Der Code um eine beliebige Zahl k zur Basis b zu dekodieren ist:

    z[1..n] = Ziffern zur Basis b
    k = 0
    for j in [1..n]:
      k = k*b + z[j]
    

    Ziel ist es anhand der Ziffern z schnell zu entscheiden ob k durch eine Zahl d teilbar ist. Man will also eigentlich wissen, ob k = 0 mod d. Um dies zu brechnen kann man obigen Code leicht modifizieren und einfach alle Rechnung mod d ausführen:

    d[1..n] = Ziffern zur Basis b
    k = 0
    for j in [1..n]:
      k = (k*b + d[j])%d
    

    Ich weiß nicht, ob das bereits eine Teilbarkeitsregel in eurem Sinn ist. Aber zum Beispiel die d=9 Teilbarkeitsregel zur Basis b=10 ist so aufgebaut. In dem Fall ist b%d = 1 und damit ist k die Quersumme. Bei d=11 ergibt sich die alternierende Quersumme. Bei d=2 ist b%d=0 und k damit einfach die letzte Ziffer und es passt auch mit der standard Regel zusammen.


Log in to reply