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$
    – J. M.'s missing motivation ♦
    Oct 28, 2015 at 6:37
  • $\begingroup$ Oops...forgot to mention that 1 & 2 are excluded. Thanks $\endgroup$
    – thils
    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$
    – Sjoerd C. de Vries
    Oct 28, 2015 at 6:43
  • $\begingroup$ You'll get a sequence with a bunch of threes, then. $\endgroup$
    – J. M.'s missing motivation ♦
    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$
    – J. M.'s missing motivation ♦
    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$
    – Patrick Stevens
    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$
    – thils
    Oct 28, 2015 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, 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$
    – thils
    Oct 28, 2015 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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