4. Teilbarkeitsregeln

Teilbarkeitsregeln

  • C

    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
    0
  • V

    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?

    0
  • V

    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.

    0
  • V

    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.

    0
  • C

    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.

    🤡

    0
  • 3

    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.

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

    0
  • V

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

    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
-

    🤡

    0
  • 3

    Wie bitte?

    0
  • ?

    SeppJ schrieb:

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

    trivial schon, wenn man Geduld hat 😃

    0
  • V

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

    0
  • B

    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.

    0
Anmelden zum Antworten