# Divisibility Streak [duplicate]

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.

### Rules

• You can assume the input is greater than 1.

### Scoring

:The submission with the lowest score wins.

• I suggest changing "smallest positive integer" to "smallest nonnegative integer". It doesn't change the challenge at all, but with the current description, it implies we don't need to check for divisibility by 1 (which we technically shouldn't need to). Either that, or you could remove the divisibility by 1 checks from the description. Commented Aug 14, 2017 at 15:11
• The smallest positive integer is 1, and k + 1 is 2, where k is the smallest positive integer. Sorry for the nitpick. Commented Aug 14, 2017 at 15:33
• Isn't this the same as finding the smallest k which doesn't divide n-1? Commented Aug 14, 2017 at 22:28
• @PaŭloEbermann Take n=7 where k=3: n-1 is divisible by k. Commented Aug 15, 2017 at 0:19
• Ah, I missed the +1. Commented Aug 15, 2017 at 16:57

# ><>, 20 bytes

0\1-n;
?\1+:@$:1+}$%


Try it online!

# Pyt, 14 bytes

ĐřĐ0↔⁻⇹|¬*ž↓⁻+


Try it online!

Determines the first positive integer that does not divide $$\n-1\$$.

Đ                   implicit input; Đuplicate
ř                  řangify
Đ                 Đuplicate
0                push 0 (so the next action will work properly)
↔               flip the stack
⁻              decrement
⇹             swap top two items
|¬           divisibility test; negate
*ž↓        multiply element-wise, remove žeros, get minimum
⁻       decrement
+      add to get rid of pesky 0; implicit print


$[n][1while[0=%n-+1<=<=][+1]dec]  Try it # Nibbles, 5.5 bytes ?,~~%+@$+$~  Attempt This Online! ? Find the index of the first item , in the numbers from 1 to ~ infinity ~ such that the result of the following is positive % modulo + add @ the input$     the number
$the number ~ 1  # Thunno 2, 5 bytes Ƙ+n⁺%  Try it online! #### Explanation Ƙ+n⁺% # Implicit input Ƙ # Find the first positive integer, n, such that: + # input + n % # mod n⁺ # n + 1 # is truthy (non-zero) # Implicit output  # SOGL V0.12, 8 bytes ]e.-ē⁴I\  Try it Here! Not bad for a language which is made for a completely different type of challenges. Explanation: ] 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  # Mathematica, 40 bytes Min@Complement[Range@#,Divisors[#-1]-1]&  Try it online! (Mathics) Mathematical approach, n+k is divisible by k+1 if and only if n-1 is divisible by k+1. And n-1 is not divisible by n, so Range@# is enough numbers. Originally I intend to use Min@Complement[Range@#,Divisors[#-1]]-1&, but this also work. • Why does the captcha appear when I use the submission from tio? Commented Aug 14, 2017 at 14:57 • Because you typed (copied-and-pasted) it too quickly. It isn't about TIO. Commented Aug 14, 2017 at 14:58 ## 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) Try it online! 9 bytes were cut thanks to Mr.Xcoder • Normally a "Try it online" link allows people to actually try the code by defining some combination of header, footer, and arguments which mean that pressing the play button gives output. Commented Aug 14, 2017 at 15:43 • @PeterTaylor By a pure guess, I tried running it as such, and to my surprise it worked. I recommend the OP to edit in with the testable version. Commented Aug 14, 2017 at 15:55 • 46 bytes (removing one space): n->(i=1;while isinteger(n/i) i+=1;n+=1end;i-1) Commented Aug 14, 2017 at 15:59 • Another pure guess allowed be to golf it down to 38 bytes: n->(i=1;while n%i<1 i+=1;n+=1end;i-1) Commented Aug 14, 2017 at 16:03 • @PeterTaylor Sorry forgot it! Commented Aug 14, 2017 at 17:08 # C (gcc), 34 bytes i;f(n){for(i=1;++n%++i<1;);n=i-1;}  Try it online! • Suggest i-- instead of n=i-1 Commented Dec 31, 2018 at 6:02 ## Batch, 70 bytes @set/an=%1-1,i=0 :l @set/ai+=1,r=n%%~i @if %r%==0 goto l @echo %i%  All this is doing is finding the largest i such that LCM(1..i) divides n-1. # Aceto, 28 27 bytes [;% I)@] iIk2I(D( rk[(&Xpu  I could save one byte if I don't have to exit. ### Explanation: We use three stacks: The left stack holds a counter starting at 2, the right one holds the given number (or its increments), the center stack is used for doing the modulo operations. We could, of course, do everything in one stack, but this way we can set the outer stacks to be "sticky" (values that are popped aren't really removed) and save ourselves many duplication operations. Here's the method in detail: Read an integer, increment it, make the current stack sticky, and "move" it (and ourselves) to the stack to the left: iI rk[  Go one more stack to the left, push a literal 2, make this stack sticky, too. Remember this position in the code (@), and "move" a value and ourselves to the center stack again.  @] k2 (  Now we test: Is the modulo of the top two numbers not 0? If so, jump to the end, otherwise go one stack to the right, increment, and push the value and us to the middle. Then go to the left stack, increment it, too, and jump back to the mark that we set before. [;% I) I( &  When the result of the modulo was not zero, we invert the position the IP is moving, go one stack to the left (where our counter lives), decrement it, and print the value, then exit.  D( Xpu  ## 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  Try it online! Edit: -2 characters from Oliver • Welcome to PPCG! Does your program take stdin? You can use TIO, which has an online F# interpreter. Also, can remove the whitespace in r = if? Commented Aug 16, 2017 at 17:41 • @Oliver Thank you, I changed the link to TIO, so now you can actually pass the argument to test it. :) Commented Aug 21, 2017 at 6:52 # Actually, 13 bytes ╗1⌠u;u@╜+%⌡╓u  Try it online! Explanation: ╗1⌠u;u@╜+%⌡╓u ╗ save n to register 0 1⌠u;u@╜+%⌡╓ first k (starting with k=0) where the following is truthy: u k+1 ;u@╜+ n+k+1 % (n+k+1)%(k+1) u increment  # APL (Dyalog Unicode), 11 bytes ⊥⍨∘⌽0=⍳|-∘1  Try it online! Uses the alternative representation: the highest k such that 1..k divides n-1. ### How it works ⊥⍨∘⌽0=⍳|-∘1 ⍝ Input: n -∘1 ⍝ n minus 1 0=⍳| ⍝ Is divisible by 1..n? ⊥⍨∘⌽ ⍝ Count the leading ones  "Count leading ones" idiom can be found on APLcart. # asm2bf, 74 bytes Try it online! I/O format: In most cases, it's ASCII, yet some interpreters will output numbers in decimal representation. That's why the test case has 1 return 4 => because in fact, ASCII(1) is 49. Golfed: in r1 incr2 @l movr3,r1 modr3,r2 ceqr3,0 cadr1,1 cadr2,1 cjn%l decr2 outr2  Commented version: ; Read the number from the standard input. in r1 ; We start the division with 1. inc r2 @l ; r3 = r1 mod r2 mov r3, r1 mod r3, r2 ; if r3 is zero, then the streak ; isn't over. ceq r3, 0 ; Pass around next number and divisor. cad r1, 1 cad r2, 1 ; Loop cjn %l ; Display the final result (it's always off-by-one), yet a dec fixes it. dec r2 out r2  # Brachylog, 10 bytes ∧.ℕ+↙?f-₁ⁿ  Try it online!  . The output ∧ (which isn't necessarily the input) ℕ is a non-negative integer, and f the factors of +↙? it plus the input -₁ⁿ do not contain the output plus 1.  # JavaScript (V8), 27 bytes (n,i=2)=>n%i^1?--i:f(n,++i)  Try it online! # Ruby, 39 bytes ->x{1.step{|i|break i-1if x%i!=0;x+=1}}  Try it online! # R, 43 37 bytes n=scan();which((n+1:n)%%(1:n+1)>0)[1]  Try it online! # F#, 64 bytes let d n= let mutable m,l=n,1 while m%l=0 do m<-m+1;l<-l+1 l-1  Try it online! Simple explanation: let divisibilityStreak n = // Arg: 'n' let mutable l = 1 // For increase the 'divisible' number let mutable n2 = n // Another one for storing mutable 'n' while n2 % l = 0 do // While 'n' is divisible by 'l', n2 <- n2 + 1 // Add 1 to both 'n2' (mutable 'n')... l <- l + 1 // and 'l' l - 1 // Finally, return 'l - 1'  # jq, 34 bytes . as$x|0|until((.+$x)%(1+.)>0;.+1)  Try it online! # jq, 40 bytes [range(.)as$x|(.+$x)%(1+$x)<1//-\$x]|-max


Try it online!

# TI-Basic, 19 21 bytes

Input N
Repeat remainder(N+Ans,Ans+1
Ans+1
End
Ans


Output is stored in Ans and displayed. This only works on TI-84+/SE with the 2.53 MP OS. The below version is 2 bytes bigger but works on earlier OS's.

### 21 23 bytes

Input N
Repeat fPart((N+Ans)/(Ans+1
Ans+1
End
Ans


# Fig, $$\10\log_{256}(96)\approx\$$ 8.231 bytes

Lt@!%mCG@}


Try it online!

Argh y'all's "first number satisfying f" builtins.

Lt@!%mCG@}
G@} # Generate an infinite list of numbers by incrementing the input
%      # Modulo each in that list by
mC    # [1, 2, 3, 4, ...]
t@        # Take while
!       # The number is 0
L          # Length of the resulting list


# Risky, 7.5 bytes

0+0+0+0??+?\?+1


Try it online!

Risky happens to be very good (for its own standards) at this specific problem.

0+0+0+0??+?\?+1
?        Find the
0+0+0+0         first
number such that
?       (the number
+       plus
?      the input)
\    modulo
?   (the number
+   plus
1  1)
is non-zero