9
$\begingroup$

I recently saw a puzzle where you were to find the 2021st positive integer co-prime to 15 (it was phrased in terms of a game but this is the mathematical core). I wrote code to find the answer but can’t see how you would have done it by hand. What is the trick?

$\endgroup$
2
  • $\begingroup$ 15 is just 3*5. So equivalently, "find the 2021st integer co-prime to both 3 and 5". That's easy. Or the converse, "find numbers divisible by either 3 and/or 5". Then find the set of numbers that exclude them. Also known as FizzBuzz, the old interview chestnut. You should be able to set up the equation in your head in 60 seconds. $\endgroup$ – smci Jan 28 at 23:49
  • 1
    $\begingroup$ They were playing fizz-buzz for how many hours? $\endgroup$ – Jasen Jan 29 at 9:52
24
$\begingroup$

The trick is this:

Looking at the range 1 to 15, there will be 8 integers coprime to 15: {1,2,4,7,8,11,13,14}.

Now look at the range 16 to 30. Adding 15 to a number doesn't change whether it's coprime to 15 - so the integers that are coprime to 15 will be exactly the same "positions" within the range as before. So this range also has 8 integers that are coprime to 15.

And there will be 8 more in the range 31 to 45, and 8 more in the range 46 to 60...

Now, 2021/8 = 252 + 5/8. So we'll pass up 252 groups of 15, landing on 3780. Now we just have to find the fifth number coprime to 15 in the range starting at 3781 - and that would be 3788.

$\endgroup$
0
4
$\begingroup$

This is a special case of a more general problem:

How to find the $N$th positive integer coprime to $k$?

The important thing to know is that

coprimeness to $k$ depends only on a number's congruence class modulo $k$. So every interval $[pk+1,(p+1)k]$ with $p\in\mathbb{Z}^+_0$ contains the same number of integers coprime to $k$, this number being $\phi(k)$ where $\phi$ is Euler's totient function (the number of positive integers up to $k$ which are coprime with $k$, i.e. the case $p=0$).

Therefore, to find the $N$th positive integer coprime to $k$, we first

reduce $N$ modulo the number $\phi(k)$, writing $N=a\phi(k)+b$ for some $a,b\in\mathbb{Z}^+_0$ with $b<\phi(k)$. Then the integer we are looking for is $ak+b'$ where $b'<k$ is the $b$th positive integer coprime to $k$.

So basically, to solve this general problem you only need to know

which positive integers less than $k$ are coprime to $k$ (a much simpler problem),

and then the rest is just basic arithmetic.

$\endgroup$
2
$\begingroup$

15 is just 3*5

Every third nonnegative integer is divisible by 3. Every fifth nonnegative integer is divisible by 5.

(1 - 1/3) = 2/3 of numbers are coprime to 3. (1 - 1/5) = 4/5 of numbers are coprime to 5.

(1 - 1/3)(1 - 1/5) = (2/3)(4/5) = 8/15 of numbers are coprime to both 3 and 5.

So equivalently, "find the 2021st integer co-prime to both 3 and 5". Or conversely, "find numbers divisible by either 3 and/or 5", then exclude them from counting.

Then if N is the 2021st number co-prime to both 3 and 5, you want to identify the 2020 numbers < N which are co-prime to both 3 and 5.

2021-1 < 2/3 * 4/5 * N

2020 < 8N/15

N > 2020*15/8 = 3787.5

Slight wrinkle, we can't in general simply round up N > 3787.5 (as Deusovi pointed out). Strictly we need to (manually) count up, excluding multiples of 3 and 5. (or as Deusovi pointed out, you only need to compute the tabulated remainders modulo 15 once).

We get N=3788, since it's the first next number coprime to both 3 and 5.

Essentially the same problem as FizzBuzz. But this is just looking for a closed-form rather than a heuristic solution.

$\endgroup$
2
  • $\begingroup$ Just doing the division and rounding won't always work - there's no guarantee that the coprime numbers are evenly distributed within the range. If you were asked for the 2022nd coprime number, this would give you 3789.375 - and neither 3789 nor 3790 is coprime to 15! $\endgroup$ – Deusovi Jan 29 at 0:10
  • $\begingroup$ @Deusovi: so you manually count up, excluding multiples of 3 and 5. (or as you pointed out, you only need to tabulate which of the remainders modulo 15). Thanks for that. $\endgroup$ – smci Jan 29 at 0:13
1
$\begingroup$
  1. Find the prime factorization of the modulus: 3^1*5^1
  2. For each prime number in the factorization, take the prime number reduced by one power times one less than the prime number, and then multiply all of those numbers together. In this case, both prime numbers are raised to the first power, so reducing the power leaves just p^0, or 1. So we have (3-1)(5-1) = 8. This gives the totient of the modulus.
  3. Divide the count of co-prime numbers to be found by the number found above. This gives 2021/8 = 252 remainder 5.
  4. Take the whole number part of the quotient and multiply it by the modulus (252 * 15=3780). Look at the set of units of the modulus group, and take the one corresponding to the remainder of the quotient. In this case, the units are 1, 2, 4, 7, 8, 11, 13, and 14, and the remainder was five, so we take the fifth one, which is 8. Add that to product of the whole part of the quotient times the modulus. This is 242*15+8 or 3788. So the answer is 3788.
$\endgroup$

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.