Percentage of Relatively Prime Integers

Suppose a , b , a, b, and c c are three positive integers between 1 and 200 exclusive that meet the following conditions:

  • a a is the smallest integer in the range such that the percentage of integers not larger than a a that are relatively prime to a a is the smallest.
  • b b is the largest integer in the range such that the percentage of integers not larger than b b that are relatively prime to b b is the smallest.
  • c c is the integer in the range such that the percentage of integers not larger than c c that are relatively prime to c c is the largest.

What is a + b + c ? a+b+c?


The answer is 409.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Sophie Ho
Apr 6, 2019

By Euler's Totient Function , the percentage of integers not larger than n that are relatively prime to n is the percentage representation of ϕ ( n ) n \frac{\phi \left ( n \right )}{n} .

It follows that a a must be the smallest integer that has the maximum number of prime factors within the range a = 2 × 3 × 5 = 30 \Rightarrow \; a=2\times 3\times 5=30
Percentage of positive integers not larger than 30 30 that are relatively prime to 30 30 is ( 1 2 ) ( 2 3 ) ( 4 5 ) 27 % \left ( \frac{1}{2} \right )\left ( \frac{2}{3} \right )\left ( \frac{4}{5} \right )\approx 27\%

b b must be the largest multiple of 30 30 within the range b = 2 2 3 2 5 = 180 \Rightarrow \; b=2^2\: 3^2\: 5=180 . Percentage of positive integers not larger than 180 180 that are relatively prime to 180 180 is also ( 1 2 ) ( 2 3 ) ( 4 5 ) 27 % \left ( \frac{1}{2} \right )\left ( \frac{2}{3} \right )\left ( \frac{4}{5} \right )\approx 27\%

Finally, c c must be the largest prime number within the range c = 199 \Rightarrow \; c=199 . Percentage of positive integers not larger than 199 199 that are relatively prime to 199 199 is 198 199 99.50 % \frac{198}{199}\approx 99.50\%

Hence a + b + c = 30 + 180 + 199 = 409 a+b+c=30+180+199=409

Nice problem! But ϕ ( 1 ) 1 = 1 \frac{\phi(1)}{1}=1 so either c = 1 c=1 or you should change "inclusive" in your wording to "exclusive".

Chris Lewis - 2 years, 2 months ago

You are absolutely correct and I heeded your advice in the wording. Thank you!

Sophie Ho - 2 years, 2 months ago

2 pending reports

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...