[Question]
  [
**This question already has answers here**:
 
 
[Find the smallest number that doesn't divide N](/questions/105412/find-the-smallest-number-that-doesnt-divide-n)
 (100 answers)
 
Closed 6 months ago.
We can define the Divisibility Streak `k` of a number `n` by finding the smallest non-negative integer `k` such that `n+k` is not divisible by `k+1`.
### Challenge
In your language of choice, write a program or function that outputs or returns the Divisibility Streak of your input.
### Examples:
```
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
```
The Divisibilty Streak of `13` is `4`
```
n=120:
120 is divisible by 1 
121 is not divisible by 2 
```
The Divisibilty Streak of `120` is `1`
### Test Cases:
```
n      DS
2      1
3      2
4      1
5      2
6      1
7      3
8      1
9      2
10     1
2521   10
```
More test cases can be found [here](https://tio.run/##ZY8xa8MwEIXn6lc8DAUJO0FpRzVTQqYECh66dBGuGgSxBNLFKBj/dldyITT0DbrH3fdOUhdXnQ9mvkbrzmhvkUyv5u6iY8R78OegezYyZEXSZDsM3n7hpK3jYmmP7GnnXfQXs/4IlszROsMrlyf79tNVQrEFK/r2AXzQAYQtXlQub3iVUmZX1@KOjXdXVPiUeake2ssuBU6okQSewVN2G4FtQZHywsfA/0e2FPKf1wcfek28GuVULt9MVUNNEn/iE/s9p3n@AQ).
### Notes
* Based on [Project Euler Problem 601](https://projecteuler.net/problem=601)
* This sequence can be found on [OEIS](http://oeis.org/A055874), shifted down by 1.
### Rules
* You can assume the input is greater than 1.
### Scoring
[code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"):The submission with the lowest score wins.
  
[Answer]
# Java 8, ~~44~~ ~~42~~ ~~41~~ 39 bytes
[*Crossed out 44 is still regular 44 ;(*](https://codegolf.stackexchange.com/a/136384/52210)
```
n->{int r=0;for(;~-n%--r<1;);return~r;}
```
-2 bytes thanks to *@LeakyNun*.  
-1 byte thanks to *@TheLethalCoder*.  
-2 bytes thanks to *@Nevay*.
**Explanation:**
[Try it here.](https://tio.run/##dU9LCoMwEN33FLMpGCSiQlcxvUHduCxdpDGWtDpKjEIRvbpN1G1hPsznvXnzFqOgbafwXX5WWYu@h5vQOJ0ANFplKiEV5L7cGiADH5Ew15mdO@utsFpCDggcVqTXya8YHrOqNQFbKJ4pNVnCCDPKDgYXw@aV7eBueNYOfHCMrS6hcfeDwhqNr/sDBNmPey7Pq3nKQGc8iV0Kw2MKUHx7q5qoHWzUOaitMcDIqSWb1F3s3630kibk@Glefw)
```
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
```
[Answer]
# [Haskell](https://www.haskell.org/), 35 bytes
```
f n=[k|k<-[1..],rem(n+k)(k+1)>0]!!0
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P00hzzY6uybbRjfaUE8vVqcoNVcjTztbUyNb21DTziBWUdHgf25iZp6CrUJBUWZeiYJGmoKhgSaXAhDY2SGJGWOKGZkaGWr@BwA "Haskell – Try It Online")
Using `until` is also 35 bytes
```
f n=until(\k->rem(n+k)(k+1)>0)(+1)1
```
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), ~~6~~ 5 bytes
```
f%tQh
```
[Try it online!](http://pyth.herokuapp.com/?code=f%25tQh&input=13&debug=0)
[Answer]
# [Husk](https://github.com/barbuz/Husk), 7 bytes
```
ḟ§%→+⁰N
```
[Try it online!](https://tio.run/##yygtzv7//@GO@YeWqz5qm6T9qHGD3////41MjQwB "Husk – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~7~~ 6 bytes
```
Ý+āÖ0k
```
[Try it online!](https://tio.run/##MzBNTDJM/V9TVln5//Bc7SONh6cZZP@vVDq830rh8H4lnf9GXMZcJlymXGZc5lwWXJZchgZcRqZGhgA "05AB1E – Try It Online")
**Alternate 7 byte solutions:**  
`<DLÖγнg`  
`Ls<ÑKн<`
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~16~~ ~~14~~ 13 [bytes](https://codegolf.meta.stackexchange.com/questions/9428/when-can-apl-characters-be-counted-as-1-byte-each/9429#9429)
```
⊃∘⍸⍳(×+∘×|+)⊢
```
-1b thanks to Adám
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/x91NT/qmPGod8ej3s0ah6drAzmHp9doaz7qWvQ/DajiUW8fRHFX86H1xo/aJgJ5wUHOQDLEwzP4/6PeuQp5CmDgEsyVpmAEZoJEgcAQKGCMLGAEFDBBV2GKrsIMXYU5soAxUMACXYUluhmGBmgqjEyNDBECBgA "APL (Dyalog Unicode) – Try It Online")
Previous solution made tacit (i.e. using trains)
---
```
{⊃⍸×(1+⍳⍵)|⍵+⍳⍵}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/6sfdTU/6t1xeLqGofaj3s2Perdq1gAJKLv2fxpQ1aPePoiGruZD640ftU0E8oKDnIFkiIdn8P9HvXMV8hTAwCWYK03BCMwEiQKBIVDAGFnACChggq7CFF2FGboKc2QBY6CABboKS3QzDA3QVBiZGhkiBAwA "APL (Dyalog Unicode) – Try It Online")
Only my second APL answer so I'm sure it can be golfed further!
Justification for only searching up to 2n is due to [Bertrand's Postulate](https://en.m.wikipedia.org/wiki/Bertrand%27s_postulate) which states that for any n>3, there exists a prime number between n and 2^n-2. Since by definition a prime only has factors of itself and 1, it will always terminate the divisibility streak.
## Explanation
```
{⊃⍸×(1+⍳⍵)|⍵+⍳⍵}  ⍝
{              }  ⍝ dfn, in this case taking a single argument (e.g. 13) mapped to ⍵
             ⍳⍵   ⍝ computes array of digits 0,1,2,3,4...,12
           ⍵+     ⍝ adds the original argument to each element of this array - 13,14,15,16...25
    (1+⍳⍵)        ⍝ computes a new array from 1...13
          |       ⍝ applies modulo to elements at the same index across the two arrays, e.g. 13%1,14%2,15%3,16%4,17%5...26%14 = 0 0 0 0 2...12
   ×              ⍝ converts any number >1 to 1, e.g. 0 0 0 0 1...1
  ⍸               ⍝ find the index of all 'true's. e.g. 4 6 7 8 9 10 12 13
 ⊃                ⍝ take the first, e.g. 4
```
[Answer]
# JavaScript (ES6), 28 bytes
```
n=>g=(x=2)=>++n%x?--x:g(++x)
```
---
## Test it
```
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>
```
[Answer]
# Mathematica, ~~30~~ 27 bytes
```
0//.i_/;(i+1)∣(#+i):>i+1&
```
An unnamed function that takes an integer argument.
[Try it on Wolfram Sandbox](http://sandbox.open.wolframcloud.com)
Usage:
```
0//.i_/;(i+1)∣(#+i):>i+1&[2521]
```
> 
> `10`
> 
> 
> 
[Answer]
# [Perl 5](https://www.perl.org/), ~~23~~ 21 + 1 (-p) = 22 bytes
```
1until$_++%++$\}{$\--
```
[Try it online!](https://tio.run/##K0gtyjH9/9@wNK8kM0clXltbVVtbJaa2WiVGVxcobPwvv6AkMz@v@L@ur6megaHBf90CAA "Perl 5 – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), 35 bytes
```
f=lambda n,x=1:n%x<1and-~f(n+1,x+1)
```
[Try it online!](https://tio.run/##HcuxCsIwFAXQPV9xF6GlV@iLVm0xXyIOkRoM6GtpM8TFX4/i2c/8To9JbSnBPf3rNnoos5NBN/ksXsftJ1TaCHMjdUn3Na1wuFhiR@yJjjgQR@JE9IS0hO2sXI0J04KIqPinweBnXqImhCrW5Qs "Python 2 – Try It Online")
[Answer]
# [K (oK)](https://github.com/JohnEarnest/ok), ~~23~~ 15 bytes
```
#1_(~!/)(1+)\1,
```
[Try it online!](https://tio.run/##y9bNz/7/X9kwXqNOUV9Tw1BbM8ZQx9D4/38A "K (oK) – Try It Online")
**Explanation:**
```
(~!/)(1+)\1, / the solution
          1, / prepend 1 to input
     (1+)\   / iterate, increasing by 1
(~!/)        / until the modulo (!) is not (~) zero
```
* -8 bytes thanks to @Traws!
[Answer]
# [Cubix](https://github.com/ETHproductions/cubix), 17 bytes
```
)uUqI1%?;)qUO(;/@
```
[Try it online!](https://tio.run/##Sy5Nyqz4/1@zNLTQ01DV3lqzMNRfw1rf4f9/I1MjQwA "Cubix – Try It Online")
Cubified
```
    ) u
    U q
I 1 % ? ; ) q U
O ( ; / @ . . .
    . .
    . .
```
* `I1` setup the stack with input and divisor
* `%?` do mod and test
	+ `;)qU)uqU` if 0 remove result and increment input and divisor. Bit of a round about path to get back to `%`
	+ `/;(O@` if not 0, drop result, decrement divisor, output and exit
[Watch it run](https://ethproductions.github.io/cubix/?code=ICAgICkgdQogICAgVSBxCkkgMSAlID8gOyApIHEgVQpPICggOyAvIEAgLiAuIC4KICAgIC4gLgogICAgLiAuCg==&input=MjUyMQo=&speed=20)
[Answer]
# [Python 2](https://docs.python.org/2/), ~~43~~ 41 bytes
*Saved 2 bytes thanks to [Leaky Nun](https://codegolf.stackexchange.com/users/48934/leaky-nun)!*
```
i=input();k=1
while~-i%-~k<1:k+=1
print k
```
[Try it online!](https://tio.run/##K6gsycjPM/r/P9M2M6@gtERD0zrb1pCrPCMzJ7VON1NVty7bxtAqWxsoVlCUmVeikP3/v6ExAA "Python 2 – Try It Online")
# [Python 2](https://docs.python.org/2/), 40 bytes
```
f=lambda i,k=1:~-i%-~k<1and f(i,k+1)or k
```
[Try it online!](https://tio.run/##K6gsycjPM/r/P802JzE3KSVRIVMn29bQqk43U1W3LtvGMDEvRSFNAyiobaiZX6SQ/b@gKDOvRCNNw9BYU/M/AA "Python 2 – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), ~~44~~ 40 bytes
*-4 bytes thanks to Leaky Nun.*
```
f=lambda n,x=1:~-n%-~x and x or f(n,x+1)
```
[Try it online!](https://tio.run/##HYxNCsIwGAX3OcXbFCy@gon2x0JOIi4iNRjQr6XNIm569Ric7TCzfONrFpOzt2/3eUwOwmT1uDdSNXuCkwkJ8wp/KOKo6xyfW9xgcTPEmbgQLdERPTEQV0KfCNMafVfKlzAgCP7RqFBY1iCx7EKdfw "Python 2 – Try It Online")
[Answer]
# [Swift 4](https://www.swift.org), 56 bytes
This is a full function `f`, with an integer parameter `i` that prints the output.
```
func f(i:Int){var k=0;while(i-1)%(k+1)<1{k+=1};print(k)}
```
**[Try it here.](http://swift.sandbox.bluemix.net/#/repl/5991c724cb3d25200b15340f)**
# [Swift 4](https://www.swift.org), 56 bytes
This is an anonymous function, that returns the result.
```
{var k=0;while($0-1)%(k+1)<1{k+=1};return k}as(Int)->Int
```
**[Try it here.](http://swift.sandbox.bluemix.net/#/repl/5991c72ecb3d25200b153410)**
**[Check out the Test Suite!](http://swift.sandbox.bluemix.net/#/repl/5991c652cb3d25200b15340e)**
[Answer]
# [C# (Mono)](http://www.mono-project.com/), ~~41~~ 39 bytes
```
n=>{int r=0;while(~-n%--r<1);return~r;}
```
Essentially a port of [@Kevin Cruijssen's Java 8 answer](https://codegolf.stackexchange.com/a/139000/38550) with further golfing.
[Try it online!](https://tio.run/##bYwxC8IwFIT3/Iq3CAkaaQtOaboITgqCg3OJqT5oXyBJFSntX4/p7nLH3XecCXJw5NIYkJ5w@4ZoB8WY6dsQ4MomFmIb0cDb4QMuLRIXuTyNZGqkuIMsDXSgE@lmygG8LtTnhb3li6SNlL4uhfI2jp4Wr@aUzzvnga9bBA2VylZrKAsF2y2u70dHwfV2f/cY7RnJ8o6jEIrNf1F1qMqVZjynHw)
[Answer]
# [dc](https://www.gnu.org/software/bc/manual/dc-1.05/html_mono/dc.html), 28 bytes
```
1si[1+dli1+dsi%0=M]dsMxli1-p
```
[Try it online!](https://tio.run/##S0n@b2RqZPjfsDgz2lA7JScTSBRnqhrY@samFPtWAPm6Bf//AwA "dc – Try It Online")
This feels *really* suboptimal, with the incrementing and the final decrement, but I can't really see a way to improve on it. Basically we just increment a counter `i` and our starting value as long as value mod `i` continues to be zero, and once that's not true we subtract one from `i` and print. 
[Answer]
# [Gaia](https://github.com/splcurran/Gaia), 8 bytes
```
@1Ė₌)†↺(
```
[Try it online!](https://tio.run/##S0/MTPz/38HwyLRHTT2ajxoWPGrbpfH/v6ExAA "Gaia – Try It Online")
### Explanation
```
@         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.
```
[Answer]
# J, 17 bytes
```
[:{.@I.>:@i.|i.+]
```
[Try it online!](https://tio.run/##y/r/P81WL9qqWs/BU8/OyiFTryZTTzuWiys1OSNfIU3ByNTI8P9/AA)
I think there's still room for golfing here.
### Explanation (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
```
The cap (`[:`) is there to make sure that J doesn't treat the last verb (`{.@I.`) as part of a hook.
The only sort of weird thing about this answer is that `I.` actually duplicates the index of each non-zero number as many times as that number's value. e.g.
```
   I. 0 1 0 2 3
1 3 3 4 4 4
```
But it doesn't matter since we want the first index anyways (and since `i.` gives an ascending range, we know the first index will be the smallest value).
Finally, here's a very short proof that it is valid to check division only up to `n`.
We start checking divisibility with `1 | n`, so assuming the streak goes that far, once we get to checking divisibility by `n` we have `n | 2n - 1` which will never be true (`2n - 1 ≡ n - 1 (mod n)`). Therefore, the streak will end there.
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 7 bytes
```
õ b!%UÉ
```
[Test it online!](http://ethproductions.github.io/japt/?v=1.4.5&code=9SBiISVVyQ==&input=MTM=)
[Answer]
# Ruby, ~~34~~ ~~32~~ 31 bytes
```
f=->n,d=1{n%d<1?1+f[n+1,d+1]:0}
```
A recursive lambda. Still new to Ruby, so suggestions are welcome!
[Try it online!](https://tio.run/##KypNqvz/P1vBViE9taRYryQ/PpOLK81W1y5PJ8XWsDpPNcXG0N5QOy06T9tQJ0XbMNbKoJaLq6C0pFghLTo79v9/Q2MA)
[Answer]
# x86 Machine Code, 16 bytes
```
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)
```
The above function takes a single parameter, `n`, in the `ECX` register. It computes its divisibility streak, `k`, and returns that via the `EAX` register. It conforms to the 32-bit [fastcall calling convention](https://en.wikipedia.org/wiki/X86_calling_conventions#Microsoft_fastcall), so it is easily callable from C code using either Microsoft or Gnu compilers.
The logic is pretty simple: it just does an iterative test starting from 1. It's functionally identical to most of the other answers here, but hand-optimized for size. Lots of nice 1-byte instructions there, including `INC`, `DEC`, `CDQ`, and `XCHG`. The hard-coded operands for division hurt us a bit, but not terribly so.
[Try it online!](https://tio.run/##dY5NboMwEEbX@BQjqkp2EqoC@SEizYaKS9QVcg0mloipjKksVbl66ZA0yy5Gb8bf03hk1Eo5TbI3gwN5EhZ8ti36unl7hxcIuU9j7suS@/Uea8d9hiwy7vfIcnfLsg33rwn3uzXOW/TwbY9ZkYY5GZxwWsJoBt2apoaqEs5Z/TG6pqooVWJwUnQdY0AXitG7x/D7v1Py6UEb2Y11A4fB1bp/Oh2JNg7OQhs6N8K2cnU7f7HA4YuRbxKo3sI11rgryREHiOMclkvNSIBC8GkxVjR8rLmLjtwhTbgCvQJFNWM5CS7kPynZJPHszbyqJLCNG62B55xcph@pOtEOU3ROk18 "C (gcc) – Try It Online")
[Answer]
# [PHP](https://php.net/), 34 bytes
```
for(;$argv[1]++%++$r<1;);echo$r-1;
```
[Try it online!](https://tio.run/##K8go@G9jXwAk0/KLNKxVEovSy6INY7W1VbW1VYpsDK01rVOTM/JVinQNrf/b2/3/b2gMAA "PHP – Try It Online")
Simple enough. Checks the remainder of division (mod) each loop while incrementing each value, outputs when the number isn't divisible anymore.
[Answer]
# [Befunge](https://github.com/catseye/Befunge-93), 19 bytes
```
#v_1+::&+1-\%
1<@.-
```
[Try it online!](https://tio.run/##S0pNK81LT/3/X7ks3lDbykpN21A3RpXL0MZBT/f/fyNTI0MA "Befunge – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 7 bytes
```
Ḷ+%RTḢ’
```
[Try it online!](https://tio.run/##y0rNyan8///hjm3aqkEhD3csetQw8////0amRoYA "Jelly – Try It Online")
Explanation:
```
Ḷ+%RTḢ’  main link, argument: n
Ḷ+       [n, 2n-1]
   R     [1, n]
  %      modulo
    TḢ   index of first truthy value (first value where k+1 does not divide n+k), 1-indexed
      ’  decrement
```
[Answer]
# [Keg](https://github.com/JonoCode9374/Keg), 17 bytes
```
®n0&{©n⑻+⑹⑻%0=|}⑺
```
[Try it online!](https://tio.run/##y05N////0Lo8A7XqQyvzHk3crf1o4k4gpWpgW1P7aOKu//8Njf/rFgUBAA "Keg – Try It Online")
[Answer]
# [K4](https://kx.com/download/), ~~27~~ 25 bytes
**Solution:**
```
*(1+)/[{y=x*_y%x}. 1+;]1,
```
**Explanation:**
Pretty naive. Start with list of [1, x] and increment both until no longer divisible.
```
*(1+)/[{y=x*_y%x}. 1+;]1, / the solution
                       1, / prepend input with 1
 (  )\[              ;]   / (loop)\[condition;start]
       {        }.        / lambda taking implicit x & y
                   1+     / add 1 (vectorised) [1, 13] => [2, 14]
             y%x          / divide y by x
            _             / floor
          y*              / multiply by x
        y=                / equals y?
  1+                      / add 1 (vectorised) [1, 13] => [2, 14]
*                         / take first [2, 14] => 2
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt) [`-æ`](https://codegolf.meta.stackexchange.com/a/14339/), ~~9~~ ~~8~~ ~~7~~ 5 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
N°u°U
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&flags=LeY&code=TrB1sFU&input=MjUyMQ)
## Original (w/o flag), 7 bytes
```
@°uXÄ}a
```
[Test it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QLB1WMR9YQ&input=MjUyMQ)
---
## Explanation
Implicit input of integer `U`.
```
@     }a
```
Return the first integer that returns a truthy value (a number `>0`) when passed through a function (with `X` being the current integer) ...
```
°
```
That postfix increments `U` ...
```
uXÄ
```
And modulos it (`u`) by `X+1`.
[Answer]
# [PowerShell Core](https://github.com/PowerShell/PowerShell), 30 bytes
```
for(;!($args[0]++%++$i)){}$i-1
```
[Try it online!](https://tio.run/##VY3bCoJAEIbv9yk22MLFFVztSASCD1BkdxFRNnbAsHZXCsxnN63Uba6G7//nm1vyACFPEMdWmAgoSDTLiigRxrRjkJ04yrW9Mc2uaZIzpVlOzhYvcoQ8A@FymGc4jNN6d5nT7H2NDzQ@1PiIuc0@1vhE63NbC5yBwxm3KaL4hbs4@3CiQCp/J4FhAs8bhAoOeIbJ9psKkGmsStAjUdtFn3C9CPxUquQ631/Ku433NVYTpGEIUlaiRmrBvfZNm@LqZ6yatb1Nl/X3v7sc5ah4Aw "PowerShell Core – Try It Online")
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 7 bytes
```
?+n›%)Ṅ
```
[Try it online!](https://vyxal.pythonanywhere.com/#WyJBIiwiIiwiPytu4oC6JSnhuYQiLCIiLCIyXG4zXG40XG41XG42XG43XG44XG45XG4xMFxuMjUyMSJd)
Explanation:
```
     )   # Lambda f from beginning of program
      Ṅ  # First non-negative integer n such that f(n) is truthy
?        # Push the input
 +       # Add n to it
    %    # Modulo
  n›     # N incremented
```
]