Teilbarkeitsregeln



  • 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.


Anmelden zum Antworten