Teilbarkeitsstreifen

31

Wir können die Teilbarkeit Streak definieren keine Reihe nvon der kleinsten nicht-negativen ganzen Zahl zu finden , kso dass n+kdurch nicht teilbar ist k+1.

Herausforderung

Schreiben Sie in der Sprache Ihrer Wahl ein Programm oder eine Funktion, die den Divisibility Streak Ihrer Eingabe ausgibt oder zurückgibt.

Beispiele:

n=13:
13 is divisible by 1 
14 is divisible by 2 
15 is divisible by 3 
16 is divisible by 4 
17 is not divisible by 5

Der Teilbarkeitsstreifen von 13ist4

n=120:
120 is divisible by 1 
121 is not divisible by 2 

Der Teilbarkeitsstreifen von 120ist1

Testfälle:

n      DS
2      1
3      2
4      1
5      2
6      1
7      3
8      1
9      2
10     1
2521   10

Weitere Testfälle finden Sie hier .

Anmerkungen

Regeln

  • Sie können davon ausgehen, dass die Eingabe größer als 1 ist.

Wertung

: Die Einsendung mit der niedrigsten Punktzahl gewinnt.

Oliver
quelle
Ich schlage vor, "kleinste positive ganze Zahl" in "kleinste nicht negative ganze Zahl" zu ändern. Es ändert nichts an der Herausforderung, aber mit der aktuellen Beschreibung impliziert es, dass wir nicht auf Teilbarkeit durch 1 prüfen müssen (was wir technisch eigentlich nicht brauchen sollten). Entweder das, oder Sie können die Teilbarkeit durch 1 Häkchen aus der Beschreibung entfernen.
TehPers
Die kleinste positive ganze Zahl ist 1 und k + 12, wobei kdie kleinste positive ganze Zahl ist. Entschuldigung für den Nitpick.
TehPers
Ist das nicht dasselbe wie das kleinste zu finden, kdas sich nicht teilt n-1?
Paŭlo Ebermann
@ PaŭloEbermann Nimm n=7wo k=3: n-1ist teilbar durch k.
Oliver
Ah, ich habe das verpasst +1.
Paŭlo Ebermann

Antworten:

17

Java 8, 44 42 41 39 Bytes

Durchgestrichen 44 ist immer noch regulär 44; (

n->{int r=0;for(;~-n%--r<1;);return~r;}

-2 Bytes dank @LeakyNun .
-1 Byte dank @TheLethalCoder .
-2 Bytes dank @Nevay .

Erläuterung:

Probieren Sie es hier aus.

n->{                 // Method with integer as parameter and return-type
  int r=0;           //  Result-integer (starting at 0)
  for(;~-n%--r<1;);  //  Loop as long as `n-1` is divisible by `r-1`
                     //   (after we've first decreased `r` by 1 every iteration)
  return~r;          //  Return `-r-1` as result integer
}                    // End of method
Kevin Cruijssen
quelle
1
42 Bytes
Undichte Nonne
1
41 Bytes Nur ein Byte von LeakyNuns Vorschlag rasiert.
TheLethalCoder
2
39 Bytes
Nevay
4

JavaScript (ES6), 28 Byte

n=>g=(x=2)=>++n%x?--x:g(++x)

Probier es aus

o.innerText=(f=

n=>g=(x=2)=>++n%x?--x:g(++x)

)(i.value=2521)();oninput=_=>o.innerText=f(+i.value)()
<input id=i><pre id=o>

Zottelig
quelle
4

Mathematica, 30 27 Bytes

0//.i_/;(i+1)∣(#+i):>i+1&

Eine unbenannte Funktion, die ein ganzzahliges Argument akzeptiert.

Probieren Sie es auf Wolfram Sandbox

Verwendung:

0//.i_/;(i+1)∣(#+i):>i+1&[2521]

10

JungHwan min
quelle
3

Cubix , 17 Bytes

)uUqI1%?;)qUO(;/@

Probieren Sie es online!

Cubified

    ) u
    U q
I 1 % ? ; ) q U
O ( ; / @ . . .
    . .
    . .
  • I1 Richten Sie den Stapel mit Eingabe und Divisor ein
  • %? mach mod und teste
    • ;)qU)uqUWenn 0, Ergebnis entfernen und Eingabe und Divisor erhöhen. Etwas runder Pfad, zu dem man zurückkehren kann%
    • /;(O@ Wenn nicht 0, Ergebnis löschen, Divisor dekrementieren, ausgeben und beenden

Schau es dir an

MickyT
quelle
2

Gleichstrom , 28 Bytes

1si[1+dli1+dsi%0=M]dsMxli1-p

Probieren Sie es online!

Das fühlt sich mit dem Inkrementieren und dem endgültigen Dekrementieren wirklich suboptimal an, aber ich kann keinen Weg finden, es zu verbessern. Grundsätzlich inkrementieren wir nur einen Zähler iund unseren Startwert, solange der Wert mod iweiterhin Null ist. Wenn dies nicht zutrifft, subtrahieren wir einen Zähler iund drucken ihn aus.

brhfl
quelle
2

Gaia , 8 Bytes

@1Ė₌)†↺(

Probieren Sie es online!

Erläuterung

@         Push input (call it n).
 1        Push 1 (call it i).
      ↺   While...
  Ė₌       n is divisible by i:
    )†     Increment both n and i.
       (  Decrement the value of i that failed this test and print.
Geschäfts-Katze
quelle
2

J, 17 Bytes

[:{.@I.>:@i.|i.+]

Probieren Sie es online!

Ich glaube, hier ist noch Platz zum Golfen.

Erklärung (ungolfed)

[: {.@I. >:@i. | i. + ]
                 i. + ]  Range [n,2n)
                 i.       Range [0,n)
                    +     Added to each
                      ]   n
         >:@i. | i. + ]  Divisibility test
         >:@i.            Range [1,n+1)
               |          Modulo (in J, the arguments are reversed)
                 i. + ]   Range [n,2n)
    {.@I.                Get the index of the first non-divisible
       I.                 Indices of non-zero values
    {.                    Head

Das cap ( [:) soll sicherstellen, dass J das letzte Verb ( {.@I.) nicht als Teil eines Hakens behandelt.

Das einzig Seltsame an dieser Antwort ist, dass I.der Index jeder Zahl ungleich Null so oft wie der Wert dieser Zahl dupliziert wird. z.B

   I. 0 1 0 2 3
1 3 3 4 4 4

Aber es spielt keine Rolle, da wir sowieso den ersten Index wollen (und da i.es einen aufsteigenden Bereich gibt, wissen wir, dass der erste Index der kleinste Wert sein wird).

Zum Schluss noch ein kurzer Beweis, dass es gültig ist, die Teilung nur bis zu zu überprüfen n.

Wir fangen an, die Teilbarkeit mit zu überprüfen 1 | n, und gehen daher davon aus, dass der Streifen so weit geht, sobald wir die Teilbarkeit mit überprüft nhaben, n | 2n - 1die niemals wahr sein wird ( 2n - 1 ≡ n - 1 (mod n)). Daher wird der Streifen dort enden.

cole
quelle
2

x86-Maschinencode, 16 Byte

49                 dec    ecx        ; decrement argument
31 FF              xor    edi, edi   ; zero counter

                Loop:
47                 inc    edi        ; increment counter
89 C8              mov    eax, ecx   ; copy argument to EAX for division
99                 cdq               ; use 1-byte CDQ with unsigned to zero EDX
F7 FF              idiv   edi        ; EDX:EAX / counter
85 D2              test   edx, edx   ; test remainder
74 F6              jz     Loop       ; keep looping if remainder == 0

4F                 dec    edi        ; decrement counter
97                 xchg   eax, edi   ; move counter into EAX for return
C3                 ret               ;  (use 1-byte XCHG instead of 2-byte MOV)

Die obige Funktion nimmt einen einzelnen Parameter nin das ECXRegister auf. Es berechnet seinen Teilbarkeitsstreifen kund gibt diesen über das EAXRegister zurück. Es entspricht der 32-Bit- Fastcall-Aufrufkonvention und kann daher mit Microsoft- oder Gnu-Compilern problemlos aus C-Code aufgerufen werden .

Die Logik ist ziemlich einfach: Es wird nur ein iterativer Test ab 1 durchgeführt. Er ist funktional identisch mit den meisten anderen Antworten hier, aber handoptimiert für die Größe. Viele nette 1-Byte - Befehle gibt, einschließlich INC, DEC, CDQ, und XCHG. Die hartcodierten Operanden für die Division haben uns ein wenig verletzt, aber nicht so schlimm.

Probieren Sie es online!

Cody Gray
quelle
2

PHP , 34 Bytes

for(;$argv[1]++%++$r<1;);echo$r-1;

Probieren Sie es online!

Einfach genug. Überprüft den Rest der Division (mod) jeder Schleife, während jeder Wert erhöht wird, und gibt aus, wenn die Zahl nicht mehr teilbar ist.

Xanderhall
quelle
1

SOGL V0.12 , 8 Bytes

]e.-ē⁴I\

Probieren Sie es hier aus!

Nicht schlecht für eine Sprache, die für ganz andere Herausforderungen gemacht ist.

Erläuterung:

]         do .. while top of the stack is truthy
 e          push the variable E contents, by default user input
  .-        subtract the input from it
    ē       push the value of the variable E and then increase the variable
     ⁴      duplicate the item below one in the stack
      I     increase it
       \    test if divides
            if it does divide, then the loop restarts, if not, outputs POP which is `e-input`
dzaima
quelle
1

Mathematica, 40 Bytes

Min@Complement[Range@#,Divisors[#-1]-1]&

Probieren Sie es online! (Mathematik)

Mathematischer Ansatz: n + k ist genau dann durch k + 1 teilbar, wenn n-1 durch k + 1 teilbar ist. Und n-1 ist nicht durch n teilbar, ebenso Range@#wie genügend Zahlen.

Ursprünglich habe ich vor zu verwenden Min@Complement[Range@#,Divisors[#-1]]-1&, aber das funktioniert auch.

user202729
quelle
Warum wird das Captcha angezeigt, wenn ich die Übermittlung von tio verwende?
User202729
1
Weil Sie es zu schnell eingegeben (kopiert und eingefügt) haben. Es geht nicht um TIO.
Undichte Nonne
1

Julia 0.6.0 (47 Bytes) (38 Bytes)

n->(i=1;while isinteger(n/i) i+=1;n+=1 end;i-1)

n->(i=1;while n%i<1 i+=1;n+=1end;i-1)

Probieren Sie es online!

9 Bytes wurden dank Mr.Xcoder gekürzt

Goysa
quelle
2
Normalerweise können Benutzer den Code über den Link "Online testen" testen, indem sie eine Kombination aus Kopf-, Fuß- und Argumenten definieren, die bedeutet, dass durch Drücken der Wiedergabetaste eine Ausgabe erfolgt.
Peter Taylor
@PeterTaylor Aus reinen Gründen habe ich versucht, es als solches auszuführen , und zu meiner Überraschung hat es funktioniert. Ich empfehle dem OP mit der testbaren Version zu editieren.
Mr. Xcoder
46 Bytes (ein Leerzeichen entfernen):n->(i=1;while isinteger(n/i) i+=1;n+=1end;i-1)
Mr. Xcoder
Eine weitere reine Vermutung ist das Golfen auf 38 Bytes:n->(i=1;while n%i<1 i+=1;n+=1end;i-1)
Mr. Xcoder
@PeterTaylor Entschuldigung, habe es vergessen!
Goysa
1

Batch, 70 Bytes

@set/an=%1-1,i=0
:l
@set/ai+=1,r=n%%~i
@if %r%==0 goto l
@echo %i%

Das Einzige, was dies tut, ist, das größte zu finden i, das sich LCM(1..i)teilt n-1.

Neil
quelle
1

Aceto , 28 27 Bytes

[;`%
I)@]
iIk2I(D(
rk[(&Xpu

Ich könnte ein Byte sparen, wenn ich nicht beenden muss.

Erläuterung:

Wir verwenden drei Stapel: Der linke Stapel enthält einen Zähler, der bei 2 beginnt, der rechte die angegebene Zahl (oder ihre Inkremente), und der mittlere Stapel wird für die Modulo-Operationen verwendet. Wir könnten natürlich alles in einem Stapel erledigen, aber auf diese Weise können wir die äußeren Stapel so einstellen, dass sie "klebrig" sind (Werte, die auftauchen, werden nicht wirklich entfernt) und uns viele Duplizierungsvorgänge ersparen. Hier ist die Methode im Detail:

Lesen Sie eine Ganzzahl, erhöhen Sie sie, machen Sie den aktuellen Stapel klebrig und "verschieben" Sie ihn (und uns) auf den Stapel links:

iI
rk[

Gehe noch einen Stapel nach links, drücke eine wörtliche 2 und mache diesen Stapel auch klebrig. Merken Sie sich diese Position im Code ( @) und "verschieben" Sie einen Wert und uns selbst wieder in den mittleren Stapel.

  @]
  k2
   (

Jetzt testen wir: Ist das Modulo der beiden oberen Zahlen nicht 0? Wenn ja, springe zum Ende, ansonsten gehe einen Stapel nach rechts, erhöhe und drücke den Wert und uns in die Mitte. Dann gehe zum linken Stapel, erhöhe ihn ebenfalls und springe zurück zu der Markierung, die wir vorher gesetzt haben.

[;`%
I)
    I(
    &

Wenn das Ergebnis des Modulos nicht Null war, kehren wir die Position um, an der sich die IP bewegt, gehen einen Stapel nach links (wo unser Zähler lebt), dekrementieren ihn und drucken den Wert aus.

      D(
     Xpu
L3viathan
quelle
1

Ruby, 34 32 31 Bytes

f=->n,d=1{n%d<1?1+f[n+1,d+1]:0}

Ein rekursives Lambda. Ruby ist noch neu, daher sind Vorschläge willkommen!

Probieren Sie es online!

Yytsi
quelle
1

F #, 86 Bytes 84 Bytes

let s n = 
    let rec c n1 d r=if n1%d=0 then c(n1+1)(d+1)(r+1)else r
    c n 1 0

Probieren Sie es online!

Bearbeiten: -2 Zeichen von Oliver

Vladislav Khapin
quelle
Willkommen bei PPCG! Nimmt Ihr Programm Standard? Sie können TIO verwenden , das über einen Online-F # -Interpreter verfügt. Kann auch das Leerzeichen in entfernen r = if?
Oliver
1
@Oliver Danke, ich habe den Link zu TIO geändert. Jetzt können Sie das Argument tatsächlich übergeben, um es zu testen. :)
Vladislav Khapin