# Smallest integer that does NOT divide a given number

Divisible[n,m] yields True if n is divisible by m, and yields False if it is not. My query is what is the fastest way to determine the smallest integer that does not divide a given integer N?

For instance, the code below gives all the numbers (up to 20) that are NOT divisible by 3:

If[Divisible[#, 3], X, #] & /@ Range[20]

(* {1, 2, X, 4, 5, X, 7, 8, X, 10, 11, X, 13, 14, X, 16, 17, X, 19, 20} *)


What I want is the smallest integer that does NOT divide 20, which is 3 in this case. How do you find this number (other than the obvious 1 and 2) for general N?

• Obviously, for the odd numbers $>1$, $2$ would be the answer. So, just evens then? – J. M. is away Oct 28 '15 at 6:37
• Oops...forgot to mention that 1 & 2 are excluded. Thanks – thils Oct 28 '15 at 6:39
• Take the minimum of Divisors and subtract 1. If this is not 1 or 2 you're done. Otherwise just use the smallest number in the complement of the Divisors and Range[3, n]. – Sjoerd C. de Vries Oct 28 '15 at 6:43
• You'll get a sequence with a bunch of threes, then. – J. M. is away Oct 28 '15 at 6:45

This works for all numbers which are not multiples of $\text{lcm}(1, \dots, 20) = 232792560$:

smallest[n_] := LengthWhile[Range[3, 20], Divisible[n, #] &] + 3


If you use $50$ instead of $20$, you get $3099044504245996706400$ as the forbidden number, which might be more acceptable to you.

You could compile this to get something which might be faster. LengthWhile isn't compiled by default, although I really don't know why - it's one of the most obviously compilable functions there is.

• Divisible[] is not compilable either, but at least one can reformulate with Mod[]. – J. M. is away Oct 28 '15 at 7:54
• @J.M. yep, I tried that first. I would have thought this would be really low-hanging fruit for WRI. – Patrick Stevens Oct 28 '15 at 8:22
• nice, +1. Just wondering how to locate those numbers (up to 10^5) which yield the answers 7 & 8. – thils Oct 28 '15 at 8:52
• @thils Any multiple of $\text{lcm}(1, \dots, 6) = 60$ but not a multiple of 7. – Patrick Stevens Oct 28 '15 at 9:17
• If I want the numbers that gives 11, I use Select[Range[10000], smallestl[#] == 11 &].......output=2520, 5040, 7560 – thils Oct 28 '15 at 9:36