785. The kth Number Divisible by None of Them

A set of m distinct primes is given. Write out the positive integers that are divisible by NONE of them, in increasing order. Print the kth of them, counting from 1.

primes 2 3, k = 5 -> 13 survivors 1 5 7 11 13 17 19 23 25 and so on primes 2, k = 10 -> 19 the odd numbers primes 2 3 5, k = 1 -> 1 1 is divisible by no prime at all primes 97, k = 7 -> 7 only multiples of 97 are removed

The number 1 always survives, because it has no prime divisor.

## Counting the survivors up to x

Counting survivors directly is hard; counting CASUALTIES is easy one prime at a time, and inclusion-exclusion repairs the double counting. For a subset S of the primes, the integers in 1 .. x divisible by every prime in S number x / product(S), since the primes are distinct and therefore their product is their lcm. Then

count(x) = x - sum over non-empty S of (-1)^(|S| + 1) * (x / product(S))

which is the same thing as: add x, subtract the single-prime terms, add the pair terms, subtract the triple terms, and so on. With m up to 10 that is 1024 subsets, cheap enough to run inside a binary search.

Problem 784 is this formula with m = 2 and the complement taken, written out longhand. Seeing the general shape is the point of this one.

Problem 1349 computes exactly this count(x) and stops there: it is given a number m, factors it, and reports how many integers below a limit are coprime to it. That is the COUNTER on its own. Here the counter is the inner loop of a search, and the question is inverted: not "how many survive up to x" but "how far must x go before k have survived". Turning a counting routine into a ranking routine by wrapping a binary search around it is the move worth taking away, and it works on any counter that is monotone in its limit.

## Why the count is monotone

Going from x to x + 1 adds exactly one survivor when x + 1 is divisible by none of the primes, and nothing otherwise. So count is non-decreasing, however tangled the formula that computes it looks.

## Why the answer really is a survivor

Search for the smallest x with count(x) >= k. At the stop count(x) > count(x - 1), and the count rises only at a survivor, so x is divisible by none of the primes.

## Finding the upper bound by doubling

There is no tidy closed form for how far out the kth survivor sits, and guessing a constant is how this problem silently returns the bound instead of the answer. Grow it instead:

hi = 1 while count(hi) < k: hi = hi * 2

That costs about 33 extra evaluations and is always correct. It is the general escape when the search space has no obvious ceiling, and it is worth having in hand.

## The boundary that breaks a careless implementation

The subset product is the expression to bound, and bounding it honestly gives a different answer from the one people reach for.

In 64 bits it does NOT overflow. The largest product any subset can reach is the ten biggest primes below 100:

53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97 = 3749562977351496827

A signed 64-bit integer holds 9223372036854775807, so even that worst case has a factor of two still in hand.

In 32 bits it overflows at once, and not only in the extreme case. The ten SMALLEST primes already give

2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230

which is three times past the 2147483647 ceiling of a signed 32-bit integer, and past an unsigned one too. A 32-bit product wraps, often to a negative divisor, and x / (negative) silently poisons the count. Nothing rescues a 32-bit program here in any case, because hi alone reaches about 8 * 10^9: the products, the bounds and the count are all 64-bit.

Guard the multiplication as you build it regardless:

if product > x / prime: this subset contributes nothing, abandon it else: product = product * prime

Once the product exceeds x the term x / product is 0 anyway, so abandoning is not an approximation, it is the exact answer reached without the multiply. The guard holds every product at or below x instead of letting it climb towards 3.7 * 10^18, which is the difference between a comfortable margin and a narrow one.

## Overflow

Beyond the subset products, hi after doubling can reach about 8 * 10^9, so the bounds themselves are 64-bit.

## Cost

Time O(2^m * m * log(answer)). Space O(m).

Constraints - `1 ≤ m ≤ 10` - `2 ≤ each prime ≤ 100` - the primes are distinct - `1 ≤ k ≤ 10^9`