Divisibility Streak [duplicate]

Question

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:

More test cases can be found here.

Notes

Based on Project Euler Problem 601
This sequence can be found on OEIS, shifted down by 1.

Rules

You can assume the input is greater than 1.

Scoring

code-golf: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. — TehPers, 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. — TehPers, Aug 14, 2017 at 15:33
Isn't this the same as finding the smallest k which doesn't divide n-1? — Paŭlo Ebermann, Aug 14, 2017 at 22:28
@PaŭloEbermann Take n=7 where k=3: n-1 is divisible by k. — Oliver, Aug 15, 2017 at 0:19

Community · Accepted Answer · 2020-06-17 09:04:33Z

19

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 14, 2017 at 15:01

Kevin Cruijssen

126k11 gold badges140 silver badges377 bronze badges

1

\$\begingroup\$ 42 bytes \$\endgroup\$
– Leaky Nun
Aug 14, 2017 at 15:02
1

\$\begingroup\$ 41 bytes Just shaved a byte from LeakyNun's suggestion. \$\endgroup\$
– TheLethalCoder
Aug 14, 2017 at 15:08
2

\$\begingroup\$ 39 bytes \$\endgroup\$
– Nevay
Aug 14, 2017 at 15:23

Add a comment |

H.PWiz · Accepted Answer · 2017-08-14 15:10:52Z

9

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

edited Aug 14, 2017 at 15:10

answered Aug 14, 2017 at 15:04

H.PWiz

11.6k2 gold badges20 silver badges56 bronze badges

Add a comment |

Leaky Nun · Accepted Answer · 2017-08-14 14:55:24Z

8

Pyth, 6 5 bytes

f%tQh

Try it online!

edited Aug 14, 2017 at 14:55

answered Aug 14, 2017 at 14:44

Leaky Nun

49.7k6 gold badges108 silver badges282 bronze badges

Add a comment |

H.PWiz · Accepted Answer · 2017-08-14 14:51:56Z

6

Husk, 7 bytes

ḟ§%→+⁰N

Try it online!

answered Aug 14, 2017 at 14:51

H.PWiz

11.6k2 gold badges20 silver badges56 bronze badges

Add a comment |

Emigna · Accepted Answer · 2017-08-14 15:39:31Z

6

05AB1E, 7 6 bytes

Ý+āÖ0k

Try it online!

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

edited Aug 14, 2017 at 15:39

answered Aug 14, 2017 at 14:52

Emigna

53k5 gold badges42 silver badges162 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

\$\begingroup\$ -1: ⊃∘⍸⍳(×+∘×|+)⊢ Try it online! \$\endgroup\$
– Adám
May 21, 2020 at 5:56 — Adám, May 21, 2020 at 5:56

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

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>

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 14, 2017 at 14:47

Shaggy

41.9k4 gold badges34 silver badges93 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 14, 2017 at 16:09

JungHwan Min

13.8k3 gold badges22 silver badges69 bronze badges

Add a comment |

Xcali · Accepted Answer · 2018-01-10 23:04:05Z

5

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

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

Try it online!

edited Jan 10, 2018 at 23:04

answered Aug 14, 2017 at 15:03

Xcali

14.9k2 gold badges14 silver badges38 bronze badges

Add a comment |

ovs · Accepted Answer · 2017-08-14 17:20:35Z

4

Python 2, 35 bytes

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

Try it online!

answered Aug 14, 2017 at 17:20

ovs

59.3k3 gold badges47 silver badges158 bronze badges

Add a comment |

mkst · Accepted Answer · 2020-05-22 08:31:31Z

4

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!

edited May 22, 2020 at 8:31

answered May 8, 2020 at 16:39

mkst

5,17511 silver badges19 bronze badges

3

\$\begingroup\$ 15 bytes with #1_(~!/)(1+)\1, \$\endgroup\$
– Traws
May 21, 2020 at 15:34

Add a comment |

MickyT · Accepted Answer · 2017-08-14 19:56:21Z

3

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

answered Aug 14, 2017 at 19:56

MickyT

12.2k2 gold badges25 silver badges48 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-08-22 19:02:36Z

3

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!

edited Aug 22, 2017 at 19:02

answered Aug 14, 2017 at 14:51

Mr. Xcoder

42.4k9 gold badges79 silver badges214 bronze badges

\$\begingroup\$ 41 bytes \$\endgroup\$
– Leaky Nun
Aug 14, 2017 at 15:06

Add a comment |

totallyhuman · Accepted Answer · 2017-08-14 15:01:59Z

2

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!

edited Aug 14, 2017 at 15:01

answered Aug 14, 2017 at 14:58

totallyhuman

17.2k3 gold badges31 silver badges88 bronze badges

1

\$\begingroup\$ 40 bytes \$\endgroup\$
– Leaky Nun
Aug 14, 2017 at 15:00

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 14, 2017 at 15:52

Mr. Xcoder

42.4k9 gold badges79 silver badges214 bronze badges

Add a comment |

TheLethalCoder · Accepted Answer · 2017-08-14 16:20:01Z

2

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!

edited Aug 14, 2017 at 16:20

answered Aug 14, 2017 at 15:07

TheLethalCoder

7,20927 silver badges43 bronze badges

Add a comment |

brhfl · Accepted Answer · 2017-08-14 18:15:35Z

2

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.

answered Aug 14, 2017 at 18:15

brhfl

1,47111 silver badges14 bronze badges

Add a comment |

Business Cat · Accepted Answer · 2017-08-14 18:29:13Z

2

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.

answered Aug 14, 2017 at 18:29

Business Cat

9,1671 gold badge16 silver badges37 bronze badges

Add a comment |

cole · Accepted Answer · 2017-08-14 18:47:10Z

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.

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 — Jonah, May 24, 2020 at 15:59
@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. — cole, May 24, 2020 at 19:09

ETHproductions · Accepted Answer · 2017-08-15 00:57:59Z

2

Japt, 7 bytes

õ b!%UÉ

Test it online!

answered Aug 15, 2017 at 0:57

ETHproductions

50k6 gold badges93 silver badges239 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 14, 2017 at 18:07

Yytsi

3,7621 gold badge18 silver badges34 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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!

Xanderhall · Accepted Answer · 2017-08-16 13:45:24Z

2

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.

answered Aug 16, 2017 at 13:45

Xanderhall

1,3066 silver badges14 bronze badges

Add a comment |

MercyBeaucou · Accepted Answer · 2017-09-07 17:34:38Z

2

Befunge, 19 bytes

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

Try it online!

answered Sep 7, 2017 at 17:34

MercyBeaucou

3,06112 silver badges30 bronze badges

Add a comment |

user45941user45941 · Accepted Answer · 2017-09-08 10:40:45Z

2

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

answered Sep 8, 2017 at 10:40

user45941

Add a comment |

lyxal · Accepted Answer · 2020-05-07 01:30:06Z

2

Keg, 17 bytes

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

Try it online!

answered May 7, 2020 at 1:30

lyxal

33.3k2 gold badges60 silver badges139 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Shaggy · Accepted Answer · 2021-09-15 14:43:23Z

2

Japt `-æ`, 9 8 7 5 bytes

N°u°U

Try it

Original (w/o flag), 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.

edited Sep 15, 2021 at 14:43

answered Aug 14, 2017 at 14:51

Shaggy

41.9k4 gold badges34 silver badges93 bronze badges

\$\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, 2018 at 14:44

Add a comment |

Julian · Accepted Answer · 2021-09-17 02:10:49Z

2

PowerShell Core, 30 bytes

for(;!($args[0]++%++$i)){}$i-1

Try it online!

answered Sep 17, 2021 at 2:10

Julian

3,0386 silver badges16 bronze badges

Add a comment |

tybocopperkettle · Accepted Answer · 2022-12-01 08:13:14Z

2

Vyxal, 7 bytes

?+n›%)Ṅ

Try it online!

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

answered Dec 1, 2022 at 8:13

tybocopperkettle

1,7246 silver badges15 bronze badges

Add a comment |

Divisibility Streak [duplicate]

Challenge

Examples:

Test Cases:

Notes

Rules

Scoring

54 Answers 54

Java 8, 44 42 41 39 bytes

Haskell, 35 bytes

Pyth, 6 5 bytes

Husk, 7 bytes

05AB1E, 7 6 bytes

APL (Dyalog Unicode), 16 14 13 bytes

Explanation

JavaScript (ES6), 28 bytes

Test it

Mathematica, 30 27 bytes

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

Python 2, 35 bytes

K (oK), 23 15 bytes

Cubix, 17 bytes

Python 2, 43 41 bytes

Python 2, 40 bytes

Python 2, 44 40 bytes

Swift 4, 56 bytes

Swift 4, 56 bytes

C# (Mono), 41 39 bytes

dc, 28 bytes

Gaia, 8 bytes

Explanation

J, 17 bytes

Explanation (ungolfed)

Japt, 7 bytes

Ruby, 34 32 31 bytes

x86 Machine Code, 16 bytes

PHP, 34 bytes

Befunge, 19 bytes

Jelly, 7 bytes

Keg, 17 bytes

K4, 27 25 bytes

Japt -æ, 9 8 7 5 bytes

Original (w/o flag), 7 bytes

Explanation

PowerShell Core, 30 bytes

Vyxal, 7 bytes

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

Linked

Related

Hot Network Questions

Japt `-æ`, 9 8 7 5 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
number
division
or ask your own question.