37
\$\begingroup\$

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.

Notes

Rules

  • You can assume the input is greater than 1.

Scoring

:The submission with the lowest score wins.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – TehPers Aug 14 '17 at 15:11
  • \$\begingroup\$ The smallest positive integer is 1, and k + 1 is 2, where k is the smallest positive integer. Sorry for the nitpick. \$\endgroup\$ – TehPers Aug 14 '17 at 15:33
  • \$\begingroup\$ Isn't this the same as finding the smallest k which doesn't divide n-1? \$\endgroup\$ – Paŭlo Ebermann Aug 14 '17 at 22:28
  • \$\begingroup\$ @PaŭloEbermann Take n=7 where k=3: n-1 is divisible by k. \$\endgroup\$ – Oliver Aug 15 '17 at 0:19
  • \$\begingroup\$ Ah, I missed the +1. \$\endgroup\$ – Paŭlo Ebermann Aug 15 '17 at 16:57

42 Answers 42

7
\$\begingroup\$

Pyth, 6 5 bytes

f%tQh

Try it online!

| improve this answer | |
\$\endgroup\$
17
\$\begingroup\$

Java 8, 44 42 41 39 bytes

Crossed out 44 is still regular 44 ;(

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.

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 42 bytes \$\endgroup\$ – Leaky Nun Aug 14 '17 at 15:02
  • 1
    \$\begingroup\$ 41 bytes Just shaved a byte from LeakyNun's suggestion. \$\endgroup\$ – TheLethalCoder Aug 14 '17 at 15:08
  • 2
    \$\begingroup\$ 39 bytes \$\endgroup\$ – Nevay Aug 14 '17 at 15:23
8
\$\begingroup\$

Haskell, 35 bytes

f n=[k|k<-[1..],rem(n+k)(k+1)>0]!!0

Try it online!

Using until is also 35 bytes

f n=until(\k->rem(n+k)(k+1)>0)(+1)1
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Husk, 7 bytes

ḟ§%→+⁰N

Try it online!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 7 6 bytes

Ý+āÖ0k

Try it online!

Alternate 7 byte solutions:
<DLÖγнg
Ls<ÑKн<

| improve this answer | |
\$\endgroup\$
5
+100
\$\begingroup\$

APL (Dyalog Unicode), 16 14 13 bytes

⊃∘⍸⍳(×+∘×|+)⊢

-1b thanks to Adám

Try it online!

Previous solution made tacit (i.e. using trains)


{⊃⍸×(1+⍳⍵)|⍵+⍳⍵}

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 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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ -1: ⊃∘⍸⍳(×+∘×|+)⊢ Try it online! \$\endgroup\$ – Adám May 21 at 5:56
4
\$\begingroup\$

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>

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 30 27 bytes

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

An unnamed function that takes an integer argument.

Try it on Wolfram Sandbox

Usage:

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

10

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Perl 5, 23 21 + 1 (-p) = 22 bytes

1until$_++%++$\}{$\--

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python 2, 35 bytes

f=lambda n,x=1:n%x<1and-~f(n+1,x+1)

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Cubix, 17 bytes

)uUqI1%?;)qUO(;/@

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

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python 2, 43 41 bytes

Saved 2 bytes thanks to Leaky Nun!

i=input();k=1
while~-i%-~k<1:k+=1
print k

Try it online!

Python 2, 40 bytes

f=lambda i,k=1:~-i%-~k<1and f(i,k+1)or k

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

K (oK), 23 15 bytes

#1_(~!/)(1+)\1,

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!
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 15 bytes with #1_(~!/)(1+)\1, \$\endgroup\$ – Traws May 21 at 15:34
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Swift 4, 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.

Swift 4, 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.

Check out the Test Suite!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

C# (Mono), 41 39 bytes

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

Essentially a port of @Kevin Cruijssen's Java 8 answer with further golfing.

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

dc, 28 bytes

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

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Gaia, 8 bytes

@1Ė₌)†↺(

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.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

J, 17 bytes

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

Try it online!

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 0{[:I.>:@i.|i.+] to save one byte. The alternative I came up with independently before noticing your answer, also 16: 0{]I.@(>:@]|+)i.. Includes test cases \$\endgroup\$ – Jonah May 24 at 15:59
  • \$\begingroup\$ @Jonah I must admit, it’s been a while since I wrote this answer. I’d have no qualms with you posting that as its own answer, seeing as you came up with it independently. \$\endgroup\$ – cole May 24 at 19:09
2
\$\begingroup\$

Japt, 7 bytes

õ b!%UÉ

Test it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

PHP, 34 bytes

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

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Befunge, 19 bytes

#v_1+::&+1-\%
1<@.-

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Jelly, 7 bytes

Ḷ+%RTḢ’

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Keg, 17 bytes

®n0&{©n⑻+⑹⑻%0=|}⑺

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Japt, 9 8 7 bytes

@°uXÄ}a

Test it


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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I wish U got auto-added after the @ here, but it doesn't do that on + and -. Bummer. Maybe we should request it gets auto-added when followed by ++ or -- \$\endgroup\$ – Oliver Jun 14 '18 at 14:44
1
\$\begingroup\$

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`
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Why does the captcha appear when I use the submission from tio? \$\endgroup\$ – user202729 Aug 14 '17 at 14:57
  • 1
    \$\begingroup\$ Because you typed (copied-and-pasted) it too quickly. It isn't about TIO. \$\endgroup\$ – Leaky Nun Aug 14 '17 at 14:58
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Aug 14 '17 at 15:43
  • \$\begingroup\$ @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. \$\endgroup\$ – Mr. Xcoder Aug 14 '17 at 15:55
  • \$\begingroup\$ 46 bytes (removing one space): n->(i=1;while isinteger(n/i) i+=1;n+=1end;i-1) \$\endgroup\$ – Mr. Xcoder Aug 14 '17 at 15:59
  • \$\begingroup\$ 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) \$\endgroup\$ – Mr. Xcoder Aug 14 '17 at 16:03
  • \$\begingroup\$ @PeterTaylor Sorry forgot it! \$\endgroup\$ – Goysa Aug 14 '17 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.