# 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


## Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 105412; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 48934; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
jQuery.ajax({
url: answersUrl(answer_page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
answers_hash = [];
answer_ids = [];
data.items.forEach(function(a) {
a.comments = [];
var id = +a.share_link.match(/\d+/);
answer_ids.push(id);
answers_hash[id] = a;
});
if (!data.has_more) more_answers = false;
comment_page = 1;
getComments();
}
});
}

function getComments() {
jQuery.ajax({
url: commentUrl(comment_page++, answer_ids),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
answers_hash[c.post_id].comments.push(c);
});
if (data.has_more) getComments();
else if (more_answers) getAnswers();
else process();
}
});
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
return a.owner.display_name;
}

function process() {
var valid = [];

answers.forEach(function(a) {
var body = a.body;
a.comments.forEach(function(c) {
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});

var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
link: a.share_link,
});

});

valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});

var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;

var answer = jQuery("#answer-template").html();
answer = answer.replace("{{PLACE}}", lastPlace + ".")
.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)
.replace("{{LINK}}", a.link);
answer = jQuery(answer);
jQuery("#answers").append(answer);

var lang = a.language;
if (/<a/.test(lang)) lang = jQuery(lang).text();

languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
});

var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);

langs.sort(function (a, b) {
if (a.lang > b.lang) return 1;
if (a.lang < b.lang) return -1;
return 0;
});

for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
.replace("{{LINK}}", lang.link);
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body { text-align: left !important}

#answer-list {
padding: 10px;
width: 290px;
float: left;
}

#language-list {
padding: 10px;
width: 290px;
float: left;
}

table thead {
font-weight: bold;
}

table td {
padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
<h2>Leaderboard</h2>
<table class="answer-list">
<thead>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
</thead>
<tbody id="answers">

</tbody>
</table>
</div>
<div id="language-list">
<h2>Winners by Language</h2>
<table class="language-list">
<thead>
<tr><td>Language</td><td>User</td><td>Score</td></tr>
</thead>
<tbody id="languages">

</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>

• 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

## ><>, 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. ## Pyke, 5 bytes 1D.f%  Try it here! 1D.f - first number after 1 where % - i%input != 0  # Beeswax, 19 bytes  >~P~q {~b"%g<~1fT_  Try it online! Example, using 3 as value  lstack gstack print _ [0,0,0] [] create bee T [0,0,3] enter number f [3] push top lstack value on gstack 1 [0,0,1] push 1 on lstack ~ [0,1,0] swap lstack 1st and 2nd g< [0,1,3] push gstack 1st on lstack % [0,1,0] lstack 1st = 1st % 2nd " if lstack 1st > 0 skip next, else don’t skip b redirect to upper left > redirect to right ~ [0,0,1] swap lstack 1st and 2nd P [0,0,2] increment lstack 1st ~ [0,2,0] swap lstack 1st and 2nd q redirect to lower right < redirect to left g [0,2,3] push gstack 1st on lstack % [0,2,1] lstack 1st = 1st % 2nd " lstack 1st > 0 → skip next ~ [0,1,2] swap lstack 1st and 2nd { "2" print lstack 1st to STDOUT end program  # Java 8, 44 + 2 = 46 bytes int m(int x,int y){return x%++y>0?y:m(x,y);}  Recursive solution which requires an extra ,1 when calling. Call with m(x,1). • Is the +2 for the parameter required? I use a recursive method as well sometimes, but usually I haven't included the parameter input (usually 0 or 1) in the byte-count. Is there a rule for this? – Kevin Cruijssen Mar 24 '17 at 8:35 • @KevinCruijssen It's outside of a standard call, so yes, I would consider it necessary. I do not know if there is any "rule" for this, but this is the fair-play method as far as I'm concerned. – Addison Crump Mar 27 '17 at 18:08 # C, 30 bytes Recursion is your friend: f(x,i){return x%i?i:f(x,i+1);}  Call as follows: #include <stdio.h> f(x,i){return x%i?i:f(x,i+1);} int main() { for(int i = 1; i < 10; i++) { printf("f(%d, 1) = %d\n", i, f(i, 1)); } }  • I believe you have your ternary operator backwards. x%i?i:f(x,i+1) will call f(x,i+1) when x is NOT divisible by i instead of when it is. – Robert Benson Jan 5 '17 at 19:24 • @RobertBenson When x is divisible by i, x%i produces the value zero, which is interpreted as false by C, so f(x,i+1) gets called. Thus, the recursion happens as long as x is divisible by i, just as it should. But I agree, this ternary expression is mind-screwing: I wrote it the wrong way round at the first try myself... – cmaster - reinstate monica Jan 6 '17 at 9:35 • That's what I get for looking at these things while I'm trying to dig through FORTRAN code at work. Also... I might have looked at a different question just before looking at your answer... yeah... I'll use that as my excuse. :) Nice work. – Robert Benson Jan 7 '17 at 2:16 # Japt, 5 bytes @uX}a  Try it here # Ruby (C implementation), 26 bytes ->n{-(~n...0).min{|x|n%x}}  Explanation: ~n 2s-complement-bitwise-negates n, so it's equivalent for positive n to -(n+1). Let's work through with n=6. We generate a range from -7 to 0, excluding 0, and then find the minimum of that range using a custom comparison function. min expects a block that takes two arguments and returns a negative number if the first one is smaller, 0 if they're the same, and 1 if the first one is larger. Here, we're implicitly telling the block to ignore the second argument, so x is just the first element in the comparison. The block will return zero when x is the negation of a factor of n: in our n=6 example, 6%-3 is 0. When it's not, it'll be a negative number: 6%-4 is -2. So as Ruby iterates through the range, it'll do this: -7 is the first candidate for a minimum. Is -6 less than it? It passes -6 (x) and -7 (ignored) into the block, and the block returns 0 (since 6 is a factor of 6), so no. Is -5 less than it? It passes -5 in to the block and it returns a negative number, so yes. So the current candidate is -5. Is -4 less than -5? The block says yes. -3, -2, and -1 all get 0s, so -4 wins. Finally we negate the result to get 4. I'm calling this implementation-dependent since the Ruby spec would allow the sorting to be done differently, although my guess is most implementations do it this way. # TI-Basic, 17 bytes Absolutely genius to use the input as upper bound for for loop? For(I,1,Ans If not(fPart(Ans/I End I  • Ans is not an allowed I/O method. – user45941 Jan 9 '17 at 18:47 • According to who? – Timtech Jan 9 '17 at 18:50 • That didn't work when I tested with 24. – kamoroso94 Jan 30 '18 at 16:47 • @kamoroso94 Thanks for pointing that out, I had mistakenly put I/Ans instead of Ans/I but it's fixed now. – Timtech Jan 31 '18 at 4:11 # Husk, 5 bytes ←-NḊ  Try it online! The testing code prints the output for the first 100 terms. Note that the function runs in time proportional to the input value; the 1234567 case takes about 12 seconds on my machine. # MATL, 6 bytes t:\f1)  Try it online! • You need Q after t so that it works for inputs 1 and 2 – Luis Mendo Jan 4 '17 at 1:11 # Clojure, 48 Bytes (defn f[n](some #(if(>(mod n %)0)%)(range 1 n)))  # PowerShell, 26 bytes for(;!("$args"%++$i)){};$i


Try it online!

• Other solutions have switched from !() to <1, would that help here too? – Neil Jan 3 '17 at 19:51
• @Neil powershell uses bash-style operators, so it would end up being -lt1 (or -eq0), one byte longer unfortunately. – briantist Jan 3 '17 at 20:43

# Befunge, 2725 24 bytes

&:1>:00p%v
g1+^@.g00_:00


Try it online!

Explanation

&                 Read N from stdin.
:                Save a duplicate copy.
1               Push initial test divisor, D.

>              Main loop starts here.
:00p          Save a copy of the current D.
%v        Calculate N modulo D and move down.
_        If not zero (i.e. N is not divisible by D), then break to the left.
:       Otherwise continue to the right and prepare another copy of N.
g          00     Retrieve the previously saved D (wrapping to the beginning of the line).
1+               Increment D.
^              Repeat the loop again.

_        We break out of the loop going left.
g00         Retrieve the last value of D.
@.            Write it to stdout and exit.


Thanks to Mistah Figgins for saving me a byte.

• I believe you can shorten this by getting rid of the !. You would need to change the second line to g1+^@.g00_:00 (switching the direction of the 2 branches) – MercyBeaucou Jan 3 '17 at 19:01

# Retina, 28 bytes

.+
$*11 (1+?)(?!1\1*$).*
$.1  Try it online! Thanks to Martin for 6 bytes! In the first stage we generate N + 1 1s. Then we find the smallest number of ones such that we cannot fit that number evenly into N by hard-coding the offset by one that we introduced in the first step. This offsetting is used to allow 1 and 2 to work. ## Japt, 8 bytes U%°V?V:ß  This was inspired by Arnauld's solution. Thanks ETHproductions for golfing this even more! Try it Online! • I just realized that V defaults to 0, which allows you to do U%°V?V:ßUV (° is ++). Then you can take advantage of the fact that ß passes in U and V by default to do U%°V?V:ß for only 8 bytes :-) – ETHproductions Jan 3 '17 at 23:36 • @ETHproductions Wow, very nice! – Oliver Jan 4 '17 at 1:04 # REXX, 35 bytes arg a do n=1 until a//n>0 end say n  # dc, 21 bytes ?sn1[1+dlnr%0=b]dsbxp  Try it online! The program works by running through all integers starting with 2 until it finds one that isn't a divisor of the input. The input is kept in register n, and the current number being tested as a divisor/non-divisor is on the stack. Perl, 25 bytes sub{1 until$_[0]%++$i;$i}


# Ruby, 28 bytes

->n{(1..n+1).find{|x|n%x>0}}

• @GB yep, my bad. I foobed in the golfing stage. – Alexis Andersen Jan 5 '17 at 14:59

# S.I.L.O.S, 49 bytes

readIO
lbla
x+1
b=i
b%x
a=1
a-b
if a a
printInt x


Try it online!
Fairly simple. I was confused for a little while.

## Labyrinth, 13 bytes

+:#
" %#!
?:;


Try it online!

### Explanation

To avoid shifting around too many values to keep track of both the input and the current potential divisor, we're storing the latter implicitly as the stack depth by creating copies of the input. The 3x3 block on the left is the main loop. The first iteration doesn't really do anything, but it helps with the overall layout to delay reading the input until later.

+   Add top two stack elements. Does nothing on the first two iterations,
but removes a zero on subsequent iterations.
:   Duplicate. Does nothing on the first iteration, but copies the input
later on.
#   Push the stack depth. 2 on the first two iterations, increasingly larger
values later on.
%   Modulo. Gives zero on the first iteration, and acts as the trial division
later on. If this is positive, the loop is exited.
;   Discard the zero.
:   Duplicate a zero on the first iteration, the input on subsequent iterations,
increasing the stack depth.
?   Read input on first iteration, push zero later on.


Once % gives a positive value, we've found a non-divisor of the input. # pushes the stack depth once more, ! prints it. Then the IP hits a dead and turns around. Now #% will leave the top of the stack unchanged (and positive), so the IP now enters the 3x3 main loop in counter-clockwise order. #:+ pushes twice the stack depth but that's irrelevant. ?:; all together push a single zero so that the % now terminates the program due to a division by zero.

# Java 7, 54514947 46 bytes

Golfed:

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


Ungolfed:

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


Nothing fancy... I did try with a while(1>0) loop, was 2 bytes longer

• @Henry Pointed out in an attempted edit that you have extra whitespace in your if statement. It seems x % i > 0 can be replaced with x%i>0. – Wheat Wizard Jan 4 '17 at 4:27
• 47 bytes: int n(int x){int y=1;for(;x%++y==0;);return y;} – Addison Crump Jan 4 '17 at 10:13
• For future reference (it doesn't really help here, but still), you don't need the for-loop brackets when using a single if statement followed by a function (so for(;;)if(true)x(); would work), and you can use for(;;) instead of while(1>0). – Addison Crump Jan 4 '17 at 10:20
• @peech You can use my solution in the comment two above this, you know. ;) Shaves off another two bytes. – Addison Crump Jan 4 '17 at 16:17
• instead i==0 write i<1 – user902383 Jan 7 '17 at 13:12

# SmileBASIC, 46 bytes

INPUT N
FOR I=2TO N+1
IF N MOD I THEN ?I:Q
NEXT


I hope that triggering an error to end the program is allowed.

# Emojicode, 74 bytes

🐖🔢➡️🚂🍇🍮i 1🔁😛0🚮🐕i🍇🍮i➕1i🍉🍎i🍉


Try it online!

# Forth (gforth), 31 bytes

: f 1 begin 1+ 2dup mod until ;


Try it online!

### Explanation

 1        \ place a 1 on the stack (divisor)
begin    \ start an indefinite loop
1+       \ add 1 to the divisor
2dup     \ duplicate the top 2 stack items (n and divisor)
mod      \ get n%divisor and place it on top of the stack
until    \ end the loop when the top of the stack is anything other than 0


# AWK, 25 29 27 bytes

{for(i=0;!($1%++i););$0=i}1


Try it online!

Can save 3 bytes by leaving out the i=0 but then multi-line input would be incorrect.

As with all AWK scripts, the code can be placed in a file or typed in at the command line.

Command Line Usage:

awk '{for(i=0;!($1%++i););$0=i}1' <<< inputNumber


or place numbers in a FILE each on its own line and do:

awk '{for(i=0;!($1%++i););$0=i}1' FILE


Two bytes saved by converting to for loop, also added TIO link.

• In the case of an input file with numbers, only the first result is always correct. The following results give the smallest number that doesn't divide the given number and is greater than the previous result, because i is not reinitialized. – Christian Sievers Jan 5 '17 at 0:29
• Good catch. I can fix it by adding 4 bytes :( – Robert Benson Jan 5 '17 at 19:13
• I'm not sure if it needed to be fixed, or if it's enough to not claim that it works with more than one number. A function must be usable more than once, but I think one could argue that here we have a whole program, and giving more than one number is illegal input. – Christian Sievers Jan 6 '17 at 0:27
• @ChristianSievers I feel bad enough writing code I consider inefficient... to make something that can't be called sequentially in AWK would make me feel truly dirty. :p – Robert Benson Jan 7 '17 at 2:24
• I feel you. ;-) – Christian Sievers Jan 7 '17 at 3:16

# Excel VBA, 36 Bytes

Immediates window function; Takes input from cell A1 and prints to the Immediates window.

i=2:While([A1]Mod i=0):i=i+1:Wend:?i

• Save 1 byte by deleting the space between [A1] and mod – Engineer Toast Jan 30 '18 at 19:03

# Perl 6, 13 bytes

{+(1...\$_%*)}


Try it online!

# 05AB1E, 5 bytes

∞Ö0k>


Bugfix thanks to @Grimmy (for n=1) at no additional byte-cost, so it can be undeleted again.

Explanation:

∞      # Push an infinite positive list: [1,2,3,...]
Ö     # Check for each whether it evenly divides the (implicit) input-integer
0k   # Get the first (0-based) index of 0 in this list of 0s/1s
>  # Increase this index by 1 to make it 1-based
# (after which this is output implicitly as result)
`