Find the smallest number that doesn't divide N

Question

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 code-golf, 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>

Answer 1

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.

Answer 2

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));

Answer 3

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.

Answer 4

Hexagony, 12 bytes

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

Embiggened:

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

Try it online!

Answer 5

Python, 43 36 35 bytes

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

Answer 6

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.

Answer 7

Haskell, 26 bytes

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

Everyone forgets about until!

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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.)

Answer 13

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);}

Answer 14

C#, 39 37 bytes

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

Saved two bytes thanks to Martin!

Answer 15

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.

Answer 16

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.

Answer 17

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!

Answer 18

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

Answer 19

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.

Answer 20

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 .. *
}

Answer 21

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).

Answer 22

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

Answer 23

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!

Answer 24

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.

Answer 25

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

Answer 26

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]

Answer 27

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));
    }
}

Answer 28

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;

Answer 29

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.

Answer 30

Rust, 23 bytes

|n|(1..).find(|x|x%n>0)

Try it online!

A closure that iterates over all positive integers returning Some(n) where n is the first integer modulo input is greater than zero.