# Find the smallest number that doesn't divide N

This challenge is simple enough that it's basically all in the title: you're given a positive integer N and you should return the smallest positive integer which is not a divisor of N.

An example: the divisors of N = 24 are 1, 2, 3, 4, 6, 8, 12, 24. The smallest positive integer which is not in that list is 5, so that's the result your solution should find.

This is OEIS sequence A007978.

## Rules

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

## Test Cases

The first 100 terms are:

2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2,
3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3,
2, 3, 2, 4, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2,
3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3


In particular, make sure that your answer works for inputs 1 and 2 in which case the result is larger than the input.

And for some larger test cases:

N          f(N)
1234567    2
12252240   19
232792560  23

• I turned the sample output string into a vector of numbers, and realized that if you format it 24 columns across, it's extremely repetitive, except for the odd deviation. – Carcigenicate Jan 6 '17 at 0:05
• That makes sense, 24 is 0 mod 2, 3, and 4, so the only differences would be in columns where the numbers are >4. It's even more repetitive at width 120. – CalculatorFeline Jan 31 '18 at 4:41

# Mathematica, 19 bytes (UTF-8 encoding)

1//.x_/;x∣#:>x+1&


Unnamed function taking a nonzero integer argument and returning a positive integer. The vertical bar about halfway through is actually the three-byte character U+2223, which denotes the divisibility relation in Mathematica. Explanation:

1                   Starting with 1,
//.                apply the following rule until it stops mattering:
x_                if you see a number x
/;x∣#           such that x divides the function argument,
:>x+1      replace it with x+1.
&   Cool, that's a function.


Edited to add: ngenisis points out that //. will, by default, iterate a maximum of 65536 times. So this implementation works for all input numbers less than the least common multiple of the integers from 1 to 65538 (in particular, on all numbers with at most 28436 digits), but technically not for all numbers. One can replace x//.y with ReplaceRepeated[x,y,MaxIterations->∞] to fix this flaw, but obviously at the cost of 34 additional bytes.

• Very interesting way to loop without using For, While, etc – ngenisis Jan 3 '17 at 17:07
• I learned it from this site! I'm definitely enjoying learning more about Mathematica by being here (can I justify that on my timesheet...?). – Greg Martin Jan 3 '17 at 17:49
• That does not look like mathematica O_o – Mama Fun Roll Jan 3 '17 at 19:14
• don't let the lack of capital letters and brackets fool ya ;) – Greg Martin Jan 3 '17 at 20:22
• – user202729 Feb 22 '18 at 7:20

## Pyth, 3 bytes

f%Q


Basically, f loops the code until %QT (Q % T where T is the iteration variable) is true.

Try it online here.

• Saw the problem, made this answer, came here to post it, found yours. Well done! – isaacg Jan 4 '17 at 10:08
• I wrote this and felt awesome about myself: .V1In%Qb0bB Saw your answer, and not feeling so awesome anymore. – John Red Jan 5 '17 at 10:28
• @JohnRed Lol, I think you just need to familiarize yourself with the built-ins in Pyth. – busukxuan Jan 5 '17 at 10:34

## JavaScript (ES6), 25 23 bytes

f=(n,k)=>n%k?k:f(n,-~k)


Note: One interesting thing here is that the k parameter is initialized ex nihilo on the first iteration. This works because n % undefined is NaN (falsy as expected) and -~undefined equals 1. On the next iterations, -~k is essentially equivalent to k+1.

### Test

f=(n,k)=>n%k?k:f(n,-~k)

// first 100 terms
for(i = 1, list = []; i <= 100; i++) {
list.push(f(i));
}
console.log(list.join(' '));

// larger test cases
console.log(f(1234567));
console.log(f(12252240));
console.log(f(232792560));

• Exactly what I got. I'd be surprised if anything shorter is possible – ETHproductions Jan 3 '17 at 20:25
• @ETHproductions On second thought, there's a shorter one. :-) – Arnauld Jan 3 '17 at 20:31
• Um. That's... uh... wow. – ETHproductions Jan 3 '17 at 20:33

# Python, 4336 35 bytes

f=lambda n,d=2:d*(n%d>0)or f(n,d+1)


# Hexagony, 12 bytes

\\)?}'@{!%.}


Embiggened:

   \ \ )
? } ' @
{ ! % . }
. . . .
. . .


Try it online!

• That's a very impressive score for Hexagony, nice work! – Martin Ender Jan 3 '17 at 9:51

# R, 28 bytes

Pretty straightforward, nothing fancy. Takes input from stdin, increments value T until i modulo T is nonzero.

i=scan()
while(!i%%T)T=T+1
T


If you want something a little more fancy, there's the following for 29 bytes:

i=scan()
match(0,!i%%1:(i+1))


Explained:

i=scan() : Read i from stdin.

1:(i+1) : Generate all integers from 1 to i+1 (the +1 accounting for the cases of 1 and 2).

i%%1:(i+1) : Modulo the input by every number in our list.

!i%%1:(i+1) : Negate the resulting list; this implicitly converts it to a logical type, such that 0 is FALSE and nonzero is TRUE. After negating, TRUE values become FALSE and vice-versa. Now, all originally nonzero values are coded as FALSE.

match(0,!i%%1:(i+1)) : Return the index of the first instance of 0 in our list. 0 is FALSE, so this returns the index of the first FALSE in the list, which is the first nonzero value from the modulo operation. Since our original list began at 1, the index is equal to the value of the smallest non-divisor.

• Nice, just wanted to suggest using which.min, but then I saw the edit and it seems match does a similar job. – JAD Jan 3 '17 at 10:34
• Also, nice trick using T, saving the need to define it before the while loop. – JAD Jan 3 '17 at 10:36
• @JarkoDubbeldam Thanks! I can't find a way for the vectorized approach to be shorter than the while approach, which is fine as it's very memory-intensive for large N. The T trick is one of those treats which is great for golfing but absolutely horrible for actual programming. (And of course you can use F too when you need a 0.) – rturnbull Jan 3 '17 at 10:40
• You may save two bytes by using 0:i+1 instead of 1:(i+1) although I am not sure how it plays with the %% operator. – antoine-sac Jan 4 '17 at 17:52
• @antoine-sac Unfortunately, %% takes precedence over +, so parens are still necessary: (0:i+1), with the same number of bytes as 1:(i+1). I actually had the former originally, but changed it to the latter as it's easier to read. – rturnbull Jan 5 '17 at 0:14

## Haskell, 26 bytes

f n=until((>0).mod n)(+1)1


Everyone forgets about until!

# Brachylog, 10 bytes

~{=#>:A'*}


Try it online!

This came out very similar to (but shorter than) Fatalize's original solution. Fatalize has since switched to a different algorithm that ties with this one via a different method, so I'm going to have to explain it myself:

~{=#>:A'*}
~{       }    inverse of the following function:
=           try possible values for the input, if it's unbound
#>         the input is a positive integer
:A'*     there is no A for which the input times A is the output


When we invert the function, by swapping "input" and "output", we get a fairly reasonable algorithm (just expressed in an awkward way): "try possible positive integers, in their natural order (i.e. 1 upwards), until you find one that can't be multiplied by anything to produce the input". Brachylog doesn't do floating-point calculations unless all inputs are known, so it'll only consider integer A.

• Never thought about doing that, that's neat! – Fatalize Jan 3 '17 at 10:38

# Brachylog, 11 10 bytes

,.=:?r'%0'


Try it online!

### Explanation

,.=           Assign an integer to the output
. :?r'%0     Input mod Output ≠ 0
0'    Output ≠ 0


# COW, 174 bytes

oomMOOMMMmoOmoOmoOMMMmOomOoMoOMMMmoOmoOmoOMMMmOoMOOmoO
MOomoOMoOmOoMOOmoOmoomoOMOOmOoMoOmoOMOomoomOomOoMOOmOo
moomoOMOomoomoOmoOMOOmOomOomOomOoOOMOOOMOomOOmoomOomOo
mOomOomOomoo


Try it online!

This code is only partially my own -- it implements a modulus algorithm that I ported from brainfuck. The rest of the code is my own. However, since I did not write the modulus algorithm, I haven't truly investigated how it works and cannot document that part of the code. Instead, I'll give my usual breakdown, followed by a more in-depth explanation of why the code works.

## Code breakdown

oom                          ;Read input into [0].
MOO                          ;Loop while [0].  We never change [0], so the program only terminates forcibly after a print.
MMMmoOmoOmoOMMMmOomOo      ; Copy [0] to [3] and navigate to [1].
MoOMMMmoOmoOmoOMMM         ; Increment [1], and copy it to [4]
mOo                        ; Navigate back to [3].
MOO                        ; Modulus algorithm.  Direct port of brainfuck algorithm.
moOMOomoOMoOmOo
MOO
moO
moo
moO
MOO
mOoMoOmoOMOo
moo
mOomOo
MOO
mOo
moo
moOMOo
moo                        ; End modulus algorithm.
moOmoO                     ; Navigate to [5].  This contains our modulus.
MOO                        ; Only perform these operations if [5] is non-zero -- i.e. [0] % [1] != 0
mOomOomOomOoOOMOOOMOomOO ;  Navigate to [1], print its contents, then error out.
moo                        ; End condition
mOomOomOomOomOo            ; Since we're still running, [0] % [1] == 0, so navigate back to [0] and try again.
moo                          ;End main loop.


## Explanation

The code first reads the integer into [0]. Each iteration of the main loop (lines 2 through 26) increments [1], then copies everything necessary over to the modulus algorithm, which spits out its result into [5]. If [5] contains any value, then [1] is the number we need to print. We print it, and then force-quit the program.

Since COW is a brainfuck derivative, it functions relatively similar to the way brainfuck operates -- infinite strip of tape, you can move left or right, increase or decrease, and "loop" while the current tape value is non-zero. In addition to brainfuck, COW comes with a couple of useful features.

(0) moo -- Equivalent to ]
(1) mOo -- Equivalent to <
(2) moO -- Equivalent to >
(3) mOO -- No equivalent.  Evaluate current tape value as instruction from this list.
(4) Moo -- If tape is 0, equivalent to ,; if tape is non-zero, equivalent to .
(5) MOo -- Equivalent to -
(6) MoO -- Equivalent to +
(7) MOO -- Equivalent to [
(8) OOO -- No equivalent.  Set tape (positive or negative) to 0
(9) MMM -- No equivalent.  If register is empty, copy tape to register.  If register is non-empty, paste register to tape and clear register.
(10) OOM -- No equivalent.  Print an integer from tape to STDOUT
(11) oom -- No equivalent.  Read an integer from STDIN and store it on tape


The real point of interest here is instruction 3, mOO. The interpreter reads the current tape value, and executes an instruction based on that tape value. If the value is less than 0, greater than 11, or equal to 3, the interpreter terminates the program. We can use this as a quick-and-dirty force quit of the main loop (and the program entirely) once we've found our non-divisor. All we have to do is print our number, clear [1] (with OOO), decrement it to -1 with MOo, and then execute instruction -1 via mOO which ends the program.

The tape itself for this program functions as follows:

[0]  -- Read-in integer from STDIN.
[1]  -- Current divisor to test
[2]  -- Placeholder for modulus algorithm
[3]  -- Temporary copy of [0] for use for modulus algorithm
[4]  -- Temporary copy of [1] for use for modulus algorithm
[5]  -- Placeholder for modulus algorithm.  Location of remainder at end of loop.
[6]  -- Placeholder for modulus algorithm
[7]  -- Placeholder for modulus algorithm


The modulus algorithm naturally clears [2], [3], [6], and [7] at the end of the operation. [4]'s contents get overwritten with the register paste on line 4, and [5] is zero when [0] is divisible by [1], so we don't have to clear it. If [5] is non-zero, we force-quit on line 23 so we don't have to worry about it.

# 05AB1E, 7 bytes

Xµ¹NÖ_½


Try it online!

Explanation

Xµ       # run until counter is 1
¹      # push input
N     # push iteration counter
Ö_   # push input % iteration counter != 0
½  # if true, increase counter
# output last iteration

• Nice, I was wondering how you'd do this iteratively in 05AB1E. – Magic Octopus Urn Jan 3 '17 at 15:36

# Jelly, 5 bytes

1%@#Ḣ


Try it online!

Explanation:

1%@#Ḣ
1  #      Find the first … numbers, counting up from 1, such that
%@       dividing those numbers into … gives a truthy remainder
Ḣ     then return the first


This is a horrendous abuse of #; there are plenty of operators in this program, but a ton of missing operands. # really wants the 1 to be given explicitly for some reason (otherwise it tries to default to the input); however, everything else that isn't specified in the program defaults to the program's input. (So for example, if you give 24 as input, this program finds the first 24 numbers that don't divide 24, then returns the first; kind-of wasteful, but it works.)

• Damn you Jelly! Pyth beats you today! :D – John Red Jan 5 '17 at 10:38
• ASCII-only: 2%@1# – Erik the Outgolfer Jan 30 '18 at 20:08

# C, 32 35 bytes

i;f(x){for(i=1;x%++i<1;);return i;}


Edit: added i=1 in the loop

### Usage

main(c,v)char**v;{printf("%d",f(atoi(*++v)));}


### Full Program version, 64 Bytes:

main(c,v)char**v;{*++v;for(c=1;atoi(*v)%++c<1;);printf("%d",c);}


# C#, 39 37 bytes

n=>{int i=0;while(n%++i<1);return i;}


Saved two bytes thanks to Martin!

• I like while(!(n%++i)); better but of course, this is code golf and 1 byte is 1 byte. – John Hamilton Jan 3 '17 at 12:57
• Does that work? I didn't know that the 0 evaluated to false automatically – Alfie Goodacre Jan 3 '17 at 15:40
• Ah, I tried it in C++, yeah it doesn't work with C#. – John Hamilton Jan 4 '17 at 7:31

## Perl, 19 bytes

18 bytes of code + -p flag.

$_=$_%++$.?$.:redo


To run it:

perl -pE '$_=$_%++$.?$.:redo' <<< 12252240


Not very detailed explanations:
- $. is a special variable whose default value is the current line number of the last filehandle accessed (stdin here), so after reading the first line of input, it's set to 1. - $_ holds the input and is implicitly printed at the end (thanks to -p flag).
- redo (in that context) considers that the program is in a loop and redo the current iteration (only $. will be different since it got incremented). - So if we found the smallest number (stored in $.) that doesn't divide $_, then we set $_ to it, otherwise, we try the next number (thanks to redo).

# Octave/MATLAB, 26 24 bytes

@(n)find(mod(n,1:n+1),1)


find(...,1) returns the index (1-based) of the first nonzero element of the vector in the first argument. The first argument is [n mod 1, n mod 2, n mod 3, n mod 4,...,n mod (n+1)] That means we have to add +1 to the index, since we start testing at 1. Thanks @Giuseppe for -2 bytes.

Try it online!

• @(n)find(mod(n,1:n+1),1) is shorter, isn't it? – Giuseppe Jan 30 '18 at 22:05
• it is indeed, thanks! – flawr Jan 30 '18 at 22:57

# Jelly, 6 bytes

%R;‘TḢ


Try it online!

Explanation:

                                               Assume 24 is our N
R      Generate all numbers from 1 to N         [1, 2, 3, 4 .., 24]
;‘    Attach N+1 to that list (for cases 1,2)  [1, 2, 3, 4 .., 25]
%       And modulo-divide our input by it
Yields a list with the remainder         [0, 0, 0, 0, 4 ...]
T   Return all thruthy indexes               [5, 7, ...]
Ḣ  Takes the first element of that list -->  5

• I don't know Jelly, but could you save a byte by increasing N before you generate the range? – Emigna Jan 3 '17 at 9:21
• @Emigna I don't know Jelly either ;) I don't see how: incrementing it earlier also makes the modulo test against N+1, or increaes the remainders [1, 1, 1, 1, 5, ...]. – steenbergh Jan 3 '17 at 9:25
• Ah, I see. I thought it might be possible to do N%range(1,N+1), but if it increases the N in both instances that's no good. – Emigna Jan 3 '17 at 9:28

# Perl 6, 17 bytes

{first $_%*,1..*}  Try it ## Expanded: { # bare block lambda with implicit parameter ｢$_｣

# return the first value
first

# where the block's argument ｢$_｣ modulus the current value ｢*｣ # doesn't return 0 ( WhateverCode lambda )$_ % *,
# ( ｢$_ !%% *｣ would be the right way to write it ) # from 1 to Whatever 1 .. * }  # 05AB1E, 6 bytes ÌL¹ÑK¬  Try it online! Also, it spells "LINK!"... Kinda... ÌL # Push [1..n+2] ¹Ñ # Push divisors of n. K¬ # Push a without characters of b, and take first item.  • @Zgarb missed that part, initial increment by 2 fixes the problem. – Magic Octopus Urn Jan 3 '17 at 16:08 • Nice! I always forget that 05ab1e has a divisor function :) – Emigna Jan 3 '17 at 18:30 # Jelly, 5 bytes ‘ḍ€i0  Try it online! ### How it works ‘ḍ€i0 Main link. Argument: n ‘ Increment; yield n+1. ḍ€ Divisible each; test 1, ..., n+1 for divisibility by n. i0 Find the first index of 0.  ## Python 2.7.9, 32 bytes f=lambda n,d=1:n%d>0or-~f(n,d+1)  Test on Ideone Recursively counts up potential non-divisors d. It's shorter to recursively the increment the result than to output d. An offset of 1 is achieved by the Boolean of True, which equals 1, but since d==1 is always a divisor, the output is always converted to a number. Python 2.7.9 is used to allow allow 0or. Versions starting 2.7.10 will attempt to parse 0or as the start of an octal number and given a syntax error. See this on Ideone. # Actually, 7 bytes ;÷@uR-m  Try it online! (note: this is a very slow solution, and will take a long time for large test cases) Explanation: ;÷@uR-m ;÷ duplicate N, divisors @uR range(1, N+2) - set difference (values in [1, N+1] that are not divisors of N) m minimum  # Haskell, 29 bytes f n=[k|k<-[2..],mod n k>0]!!0  The expression [k|k<-[2..]] just creates an infinite list [2,3,4,5,...]. With the condition mod n k>0 we only allow those k in the list that do not divide n. Appending !!0 just returns the first entry (the entry at index 0) form that list. Try it online! # Dyalog APL, 8 bytes 1⍳⍨0≠⍳|⊢  1⍳⍨ position of first True in 0≠ the non-zero values of ⍳| the division remainders of 1...N when divided by ⊢ N TryAPL online! Note: this works for 1 and 2 because 1⍳⍨ returns 1 + the length of its argument if none is found. # julia, 28 bytes N->findfirst(x->N%x>0,1:N+2)  Note: since 1:N+2 doesn't allocate memory there is no memory problems for large N s - @flawr N+2 save for me some bytes - @Martin 's suggestion saved 1 bytes ## QBIC, 14 bytes :[a+1|~a%b|_Xb  Explanation: : Read the first cmd line param as a number, called 'a' [a+1| FOR (b=1 ; b <= a+1; b++) <-- a+1 for cases a = 1 or 2 ~a%b IF A modulo B ( == 0, implicit) |_Xb THEN exit the program, printing b [IF and FOR implicitly closed by QBIC]  # PHP, 30 bytes for(;$argv[1]%++$i<1;);echo$i;


if run from console with -r option (thx to @ais523)

php -r 'for(;$argv[1]%++$i<1;);echo$i;' 232792560  # 32 bytes <?for(;$argv[1]%++$i<1;);echo$i;


thanks to @manatwork for removing 1 byte

# 33 bytes (original)

<?for(;$argv[1]%++$i==0;);echo$i;  • IIRC, the <? doesn't have to be part of your byte count (because PHP has a command-line mode that doesn't require it). – user62131 Jan 3 '17 at 10:55 • The old trick: compare against <1 instead of ==0. – manatwork Jan 3 '17 at 11:19 • Dang. I reached to for(;!($argv[1]%$i);$i++);echo$i;. Yours is the natural evolution of mine. This has my upvote! – Ismael Miguel Jan 5 '17 at 19:00 # Cubix, 14 12 bytes I2/L/);?%<@O  Saved 2 bytes thanks to MickyT. Try it ### Explanation In cube form, the code is:  I 2 / L / ) ; ? % < @ O . . . . . . . . . . . .  Basically, this just takes the input and starts a counter. It then checks each successive value of the counter until it finds one that isn't a factor of the input. • I2/L/);?%<@O for a couple of bytes less. Same general process, just different path – MickyT Jan 30 '18 at 20:28 ## ><>, 15 +3 = 18 bytes 1\n; ?\1+:{:}$%


Input is expected to be on the stack at program start, so +3 bytes for the -v flag. Try it online!

## Jellyfish, 12 10 bytes

p\~~|1
>i


Takes input from STDIN and outputs to STDOUT. Try it online!

Martin Ender saved 2 bytes, thanks!

## Explanation

 \~~|
>i


This part is one function that uses the input value in its definition.

   ~|


This ~-cell is given a function, so it flips its arguments: its produces the binary function "left argument modulo (|) right argument". The built-in modulo function in Jellyfish takes its arguments in the reverse order.

  ~~|
i


This ~-cell is given a value and a function, so it does partial application: it produces the binary function "input (i) modulo right argument". Let's call that function f.

 \~~|
>i


The \-cell is given two functions, so it does iteration: it produces the unary function "increment (>) until the function f applied to previous and current values gives a truthy (nonzero) result, then return current value". This means that the argument is incremented until it doesn't divide the input.

p\~~|1
>i


Finally, we apply this function to the initial value 1 and print the result with p.