# 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


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 COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 48934; // This should be the user ID of the challenge author.

/* App */

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

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

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

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

function process() {
var valid = [];

var body = a.body;
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],
});

});

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;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

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)
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body { text-align: left !important}

width: 290px;
float: left;
}

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

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

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

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</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. Commented Jan 6, 2017 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. Commented Jan 31, 2018 at 4:41

# 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. Commented Jan 5, 2017 at 0:29
• Good catch. I can fix it by adding 4 bytes :( Commented Jan 5, 2017 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. Commented Jan 6, 2017 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 Commented Jan 7, 2017 at 2:24
• I feel you. ;-) Commented Jan 7, 2017 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 Commented Jan 30, 2018 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)  # GolfScript, 15 bytes ~:x;1{).x\%!}do  Try it online! ~:x; # Store the input in the variable x 1 # Push 1 { !}do # While it is zero ) # Go to the next number .x\% # x mod the current number  # Python 3, 39 bytes f=lambda x,i=1:i if x%i!=0else f(x,i+1)  Try it online! This function just returns the second argument if it's a valid answer, and calls itself with an incremented second argument otherwise. • Welcome to the site, and nice first answer! I've edited in a link to an online testing environment so that others can test and run your code. You can save 2 bytes by removing the !=0 (Try it online!) and be sure to check out our Tips for golfing in Python page for more ways you could golf your answer. Commented Jan 28, 2021 at 11:08 • I got it down to 36, but how is left as an exercise to the reader ;) Commented Feb 1, 2021 at 23:49 # Canvas, 8 bytes １Ｗ╵╶┌％！｝  Try it here! ##### Explanation: 1W╵╶┌%!} | Explanation | Stack Visualization (of first iteration) ---------+-------------------------+----------------------------------------- 1 | Push 1 | 1 W } | Do ... | 1 ╵ | Increment ToS | 2 ╶ | Push input | 2, <input> ┌ | Duplicate 2nd from top | 2, <input>, 2 %! | Divides? | 2, <0/1> } | ... while POP is truthy | <output> | Print ToS (implicit) |  # Alice, 20 bytes /O \M@/1!w.?h!?%n$K?


Try it online!

M1!w.?h!?%n$K?O@ # full program M # read one argument and put it on the stack 1! # save 1 on the tape w n$K    # while loop, until the modulus is not 0
.            # duplicate the input
?h!         # get the number on the tape, increase it and update the tape
?%       # pops the input and the number on the tape, push the modulus
?O@ # print the last number on the tape, the first number that does not divide the input


# Itr, 9 bytes

#ä2+º%Ì1@

online interpreter

## Explanation

#         ; get an integer N from standard input
ä2+º     ; push the range from zero to N+1
%    ; vectorized remainder
Ì   ; get indices of non-zero elements (zero-indexed)
1@ ; get 2nd element (mod 0 is always non-zero)


# Nibbles, 3 bytes (6 nibbles)

/|,~%@


Attempt This Online!

I'm always amazed that Nibbles is able to 'fold-from-right' over an infinite list...

/|,~%@      # full program
/|,~%@$$# with implicit variables added | # filter . # 1.. ~ # infinity # by truthy result of @ # input % # modulo  # it; / # then, fold from right  # returning left element each time # (so: return left-most element)  # Vyxalr, 29 bitsv1, 3.625 bytes ?%)ṅ  Try it Online! # ARBLE, 27 20 bytes (range(2,n+9)&n%x)/z  Try it online! # Thunno 2, 2 bytes Ƙ%  Try it online! #### Explanation Ƙ% # Implicit input Ƙ # First integer (starting from 1) where the following is truthy: % # The (implicit) input mod the number # (this is nonzero/truthy iff the input isn't divisible by the number) # Implicit output  ## C 70 bytes  s(int *n){ int f=1;for(f=1;f<(*n);f++){if((*n)%f!=0)return f;}return f;}  ## Racket 52 bytes (let p((n 2))(cond[(= 0(modulo m n))(p(+ 1 n))][n]))  Ungolfed: (define (f m) (let loop ((n 2)) (cond [(= 0 (modulo m n)) (loop (+ 1 n))] [else n])))  Testing: (f 24) (f 1234567) (f 12252240) (f 232792560)  Output: 5 2 19 23  # bash, 37 bytes ((1%{2-1}))&&echo 2||0 1 [2+1]  Save the program in a file. Run it from the command line with the input number N as an argument: scriptname N • ((1%(2)))&&bc<<<2||0 1 2+1 to be run as scriptname N 2 Commented Jan 7, 2017 at 7:35 • @izabera I like the idea of using bc, but I can't get it to be any shorter than the original 37 bytes without the contrivance of passing the extra argument 2. Commented Jan 7, 2017 at 18:04 ## Batch, 53 bytes @set/ad=%2+1,r=%1%%d @if %r%==0 %0 %1 %d% @echo %d%  Well I beat Java anyway... Explanation: • set /a d = %2 + 1 This takes the second argument and adds 1. Of course, normally there is no second argument, but that's no problem, you just get +1, which is still a legal expression. • set /a r = %1 %% d Since % is the argument/variable modifier, we need to double it to flag it as the remainder operator. • %0 %1 %d% This is a form of tail recursion. %0 refers to the batch file itself, %1 is the original parameter and %d% is our loop variable, becoming %2 in the next iteration. # FALSE, 32 bytes This FALSE solution is similar to the DUP solution because DUP is a dialect of FALSE with some extra abilities. 1[[$@@@@\/*-0=][1+]#.]a:\a;!  In contrast to DUP, FALSE lacks the convenient MOD,DIV operator that computes both the MOD and DIV of two numbers at one time. FALSE only offers an integer division operator /. FALSE also does not offer the convenient OVER operator, and using the PICK 1ø operator combo instead costs 3 bytes each. So, the solution above is actually the cheapest way to implement the OVER and MOD operators in FALSE. Insert the value to be tested between the : and the \, like this: 1[[$@@@@\/*-0=][1+]#.]a:1234567\a;!  Explanation: 1[[$@@@@\/*-0=][1+]#.]a:n\a;! (n marks the number) 1 [1] PUSH 1 (counter c) [ ]a: define function a n [1,n] PUSH n \ [n,1] SWAP a;! fetch address of a, execute a [ ][ ]# while loop while 1st block true, execute 2nd block \ ~1~ [1,n] SWAP DUP @ ROT @@@ [n,1,n,1,n,1] DUP,ROT,DUP,ROT,DUP,ROT,SWAP (create 2 duplicates of the pair) / [n,1,n,1,n/1=n] DIV * [n,1,n,1*n] MUL - [n,1,n-n=0] SUB 0 [n,1,0,0] PUSH 0 = [n,1,-1] if 0==0 PUSH true(-1), else push false (0) if true, execute next block, if false, continue at ~2~ ] [1+]# [n,2] PUSH 1, ADD, (increment c), loop back to ~1~ . ~2~ [n,c] print integer c (top stack value) to STDOUT  Try it out here. • You can remove the function definition/call entirely: 1[$@@@@\/*-0=][1+]#. to get 24 bytes. (insert the value to test at the beginning) Commented Jan 30, 2018 at 15:39 # DUP, 23 bytes (21 chars) DUP is a derivative of FALSE, with a similar solution. 1[[^^/%0=][1+]#.]⇒a\a  Insert the value to be tested between the first a and the \, like this: 1[[^^/%0=][1+]#.]⇒a1234567\a  Explanation:  data stack 1 [1] PUSH 1 on data stack [ ]⇒a define operator a n [1,n] PUSH integer n on data stack \ [n,1] SWAP a execute operator a 1[[^^/%0=][1+]#.]⇒a1234567\a [ ][ ]# while loop: while first block true, execute second block [ ~1~ ^ [n,1,n] OVER ^ [n,1,n,1] OVER / [n,1,n%1,n/1] MODDIV: computes mod and division % [n,1,n%1] POP 0 [n,1,n%1,0] PUSH 0 = [n,1,true/false] n%1 == 0 ? ] if false (0), continue at ~2~ if true (-1), execute next block [ 1 [n,1,1] PUSH 1 + [n,2] ADD ]# return to ~1~ . ~2~ [n] print number to STDOUT exit operator a, end program  Try it out here. Or clone my DUP GitHub repository for a DUP interpreter written in Julia, with full documentation. # Matlab, 45 Bytes function x=n(a) x=2;while(~mod(a,x))x=x+1;end  # Vitsy, 17 bytes V2v[VvDD1+v{M(x&]  The output is the exit code of this program. Assuming that less that LCM(Range(1,128)) is acceptable range. Try it online! ### Explanation: Let [...] at the end of the line signify the state of the stack at that line. V2v[VvDD1+v{M(x&] V Capture the input as a final global variable (FGV). 2v Save 2 as a temporary variable. [ ] Repeat the item in brackets forever. V Push the FGV to the stack. v Dump the temporary variable (TV) to the stack. (call it "x") DD Duplicate twice. The stack looks like [FGV, x, x, x]. 1+ Add one to the top value. [FGV, x, x, x+1] v Capture the top value as the new temp var. (TV = x+1) [FGV, x, x] { Rotate the top to the bottom of the stack. [x, FGV, x] M Pop the top two values, push second-to-top mod top. [x, FGV%x] ( Pop the top value. If it is zero, then... [x] x Pop the top value and exit with that exit code. [] & Enter a new stack. (Reset the stack).  # Java 8, 37 bytes n->{int i=1;while(n%++i<1);return i;}  # Scala, 33 bytes (n:Int)=>(1 to n+1)find(n%_>0)get  Straightforwardly constructs a Range that covers the possible answers, finds the first one that is an answer, and gets it from the Option, knowing that it must exist. # C++ 55 Bytes start: while(n%i>0) {;goto end;} i++; goto start; end:;  The while loop checks whether the number(input given by the user) is divisible by i(here the divisor which is continuously increasing). The entire code is #include<iostream> using namespace std; int main(){ int n,i=1; cout<<"Enter A Number"; cin>>n; start: while(n%i>0) { cout<<"The lowest integer that does not divide "<<n<<" is "<<i; goto end; } i++; goto start; end: return 0; }  • You don't need all that whitespace, and you can easily save bytes by using shorter identifiers than end and start. On the other hand, you do need to submit either a full program or a function (not a snippet, like you have there), and you current demonstration code is way too long to really serve that role. (I also think you're using rather more verbose control constructs than you need to; in the C family, for is normally best for loops in code-golf because it's fairly flexible and it has the shortest name.) – user62131 Commented Jan 5, 2017 at 8:12 Q/KDB+ 36 Bytes f:{[0=(y%x)mod 1;f[x+1;y];x]} f[1;n]  Description: Function f f:{[0=(y%x)mod 1;f[x+1;y];x]}  which consists of a conditional [0=(y%x)mod 1;f[x+1;y];x]  The conditional has 3 statements, each separated by a semi colon. 0=(y%x)mod 1 //y divided by x, mod 1 to determine if it is a decimal or not. f[x+1;y] //If it is not a decimal, call the function again and increment x. x //If it is a decimal, return x (as it doesn't divide n evenly.  To call the function: f[1;n]  Start at 1 and pass in the value of n. # GameMaker Language, 58 bytes a=argument0 for(i=1;i<=a;i++){if a mod i return i}return i  ## Clojure, 90 bytes Horribly long, but I like how it reads ungolfed. #(apply min(remove(into #{}(filter(fn[m](=(rem % m)0))(range 1(+ % 1))))(range 2(+ % 2))))  I probably have a lot of room to golf this given this was a totally naïve attempt at an algorithm. Ungolfed: (defn smallest [n] (let [mults (into #{} (filter (fn [m] (= (rem n m) 0)) (range 1 (+ n 1))))] ; Find multiples, and place in a set for membership lookup (apply min ; Find minimum non-multiple (remove mults ; Remove multiples from the range 2 to (n+2) (range 2 (+ n 2))))))  # FALSE, 2219 18 bytes 1[$$3ø\/*2ø=][1+]#


This is a modified version of the other FALSE answer (which is itself a modified version of the DUP answer)

1[[$@@@@\/*-0=][1+]#.]a:\a;!  First, of course, we can remove that function definition/call, as well as outputting the number to the stack instead of printing: 1[$@$@$@$@\/*-0=][1+]#  $@@@@\ is used to create 2 copies of the top 2 values on the stack {a,b} -> {a,b,a,b,a,b}. This can be shortened to 1ø1ø1ø1ø or 2ø$2ø\ 1[$2ø$2ø\/*-0=][1+]#  For some reason, they are using a-b==0 rather than just a==b... 1[2ø$2ø\/*=][1+]#


And then I messed around some more to save 1 character:

1[3ø\/*2ø=][1+]#


# Julia 0.6, 25 bytes

f(n,x=2)=n%x>0?x:f(n,x+1)


Try it online!

L,RqVAFB]qG$_bUm  Try it online! ## How it works L, ; Create a lambda function ; Example argument: [24] R ; Range; [[1 2 3 4 ... 22 23 24]] q ; Set; [{1 2 3 4 ... 22 23 24}] V ; Save and pop; [] AFB]q ; Push the factors; [{1 2 3 4 6 8 12 24}] G ; Retrieve; [{1 2 3 4 6 8 12 24} {1 2 3 ... 22 23 24}]$_h	; Set difference;   [{5 7 9 ... 22 23 24}]