Fractions

Question

Hello SoloLearn. I have been strugling with a problem for some time and i want to ask for you help. Given a number n you must tell how many irreducible fractions there are made with numbers from 1 to n. For example: for n=4 there are 11 fractions:::: 1/1 1/2 1/3 1/4 2/1 2/3 3/1 3/2 3/4 4/1 4/3 . I don't exactly know why there are 1/1 and 4/1 because they reduce as well as 2/2 but let's just say that those 1/1 2/1 3/1 /4/1 are accepted. Another example for n=5 there are 19. 1<=n<=1.000.000. Because of that limit i can't count them all.
Thank you for your time and have a good day.

Answer 1

First of all: 4/1 is irreducible because 4/1= 4, you cannot simplify that. (2/2 is another way to write 1/1, not a reduction. Reduction would be, from 2/2 transform in 1/1)

Basically, to check if a fraction can be reduced, you need to check if a/b has relations.
This means 3/9 is reducible (1/3), both 3 and 9 can be multiplied by 3. 4/2 can be reduced (2), both are multiplied by 2. 81/27 can be reduced. Both are multiples of 9. But both are also another simplification (9/3) that are multiple of 3. 9*3 = 27, it means that 81/27 also include two multiples of 27.

You can project an algorithm based on what i told you now.