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?

$\endgroup$
  • $\begingroup$ Obviously, for the odd numbers $>1$, $2$ would be the answer. So, just evens then? $\endgroup$ – J. M. is away Oct 28 '15 at 6:37
  • $\begingroup$ Oops...forgot to mention that 1 & 2 are excluded. Thanks $\endgroup$ – thils Oct 28 '15 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$ – Sjoerd C. de Vries Oct 28 '15 at 6:43
  • $\begingroup$ You'll get a sequence with a bunch of threes, then. $\endgroup$ – J. M. is away Oct 28 '15 at 6:45
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.

$\endgroup$
  • $\begingroup$ Divisible[] is not compilable either, but at least one can reformulate with Mod[]. $\endgroup$ – J. M. is away Oct 28 '15 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$ – Patrick Stevens Oct 28 '15 at 8:22
  • $\begingroup$ nice, +1. Just wondering how to locate those numbers (up to 10^5) which yield the answers 7 & 8. $\endgroup$ – thils Oct 28 '15 at 8:52
  • $\begingroup$ @thils Any multiple of $\text{lcm}(1, \dots, 6) = 60$ but not a multiple of 7. $\endgroup$ – Patrick Stevens Oct 28 '15 at 9:17
  • $\begingroup$ If I want the numbers that gives 11, I use Select[Range[10000], smallestl[#] == 11 &].......output=2520, 5040, 7560 $\endgroup$ – thils Oct 28 '15 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.