Can anyone solve this problem?

Let f(x) denote the number of positive integers which are less than x and also co-prime to x i.e. gcd(x, i) = 1 , where 1 ≤ i ≤ x-1. For example f(2) = 1 as only i = 1 satisfies the condition, f(6) = 2 as only i = 1 and i = 5 satisfy the condition.

We also define f(1) = 1

Your task is to compute the following sum:

where N is some positive integer.

Input Format

The only line in each test case consists of N , a positive integer.

Constraints

1 ≤ N ≤ 109

Output Format

Output a single integer - value of the sum

Sample Input 0

6

Sample Output 0

12

Explanation 0

Some of the values are: f(1) = 1 , f(2) = 1, f(3) = 2, f(4) = 2, f(5) = 4, f(6) = 2 Therefore we output (1+1+2+2+4+2) = 12

question link?

okay this is very easy brute force.
Constraints are very low.
just go from 1 to x-1 and check how many coprimes are there for each value from 1 to x.

oh no
wait

N<=10^9

yeah it was showing 109 before…hmm there must be a pattern then.
I will try to optimise my brute force solution

It’s toitent function

i just figured it out so how to find the sum in that constraints?

Toitent can be computed in O(sqrt(n))

You can find an implementation

Edit : i think i haven’t read the problem properly, i think it asks for sum of toitent over range

but n*sqrt(n) will give TLE

@kal013 Can you give us some hint ?
PS : It seems like some kind of DP related to prime factors or prime numbers but I might be totally wrong. It’s not an easy problem.

1 Like

There is no pattern afaik.

yeah even i saw that i tried to OEIS and brute forced…
Maybe Matrix Exponentiation if we get to know the dp recurrence

1 Like

I think this question can be solved using Möbius inversion
see example 1 in https://codeforces.com/blog/entry/53925.

2 Likes

I think it can be done in less than linear time. The time complexity is a bit weird to compute, but the method is as such:
Let’s denote \sum_{i=1}^n f(i) as S_n.
It can be seen that S_n is equal to the number of co-prime pairs less than n.
We can deduce that the number of pairs is \frac{n(n+1)}{2}
Now we have to find the number of pairs such that they have a common factor, lets say g. An interesting observation would be that, if we denote the pair
as \{a,b\} we can write it as \{ga_0,gb_0\} where a_0 and b_0 are coprime. This reeks of recursion. Let’s try formulating this result in and see how exactly we can implement it. The number of pairs \{a_0,b_0\} such that ga_0 and gb_0 are less than n is S_{\lfloor{n/g}\rfloor}
Using this result, we can deduce that S_n=\frac{n(n+1)}{2} - \sum_{g=2}^n S_{\lfloor n/g \rfloor}
Now we need to optimise this relation.
To do that we use the property of floor functions that after \sqrt{n}, the number starts repeating. We can actually use this property to reduce the time complexity.
To take advantage of it, We need to first find out how many times each number repeats. After a few examples i found the relation to be a given number k, would repeat \lfloor \frac{n}{k} \rfloor - \lfloor \frac{n}{(k+1)} \rfloor times. Therefore we can deduce
S_n=\frac{n(n+1)}{2} -\sum_{g=2}^{\sqrt{n}} S_{\lfloor n/g \rfloor} - \sum_{k=1}^{\sqrt{n}} (\lfloor n/k \rfloor - \lfloor n/(k+1)\rfloor) S_k
I think this can solve it quickly using recursion and memoisation.
The implentation is left as an exercise to the reader.
I don’t know whether you can see it but mine is here

3 Likes

I was watching a video of Indian Programming camp 2016 on Number Theory and Mobius Inversion.
The lecturer(@kevinsogo) actually discussed how to find the sum of totient function from 1 to n^11 using this.
I haven’t reached that part but he began the video talking about this problem.
Do check that out as well :slight_smile:
(Edit: I know it’s previously been discussed and already answered but I wanted to bring light to this resource there are more videos on Combinatronics by wonderful programmers like Kevin Sogo and Errichto there so they are helpful)

1 Like