4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Obviously, for the odd numbers $>1$, $2$ would be the answer. So, just evens then? $\endgroup$ Commented Oct 28, 2015 at 6:37
  • $\begingroup$ Oops...forgot to mention that 1 & 2 are excluded. Thanks $\endgroup$ Commented Oct 28, 2015 at 6:39
  • $\begingroup$ 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]. $\endgroup$ Commented Oct 28, 2015 at 6:43
  • $\begingroup$ You'll get a sequence with a bunch of threes, then. $\endgroup$ Commented Oct 28, 2015 at 6:45

1 Answer 1

Reset to default
7
$\begingroup$

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.

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.