math problem

[mnnsa]

please help me how to approach this problem

A(x) and B(x) are 2 functions .
A(x)= Number of i where 1<=i<=x and gcd(i,x)=1
B(x)= sum of A(d) where d divides the number x
print B(N)

where value of N will be given.

[lastchance]

Why would d be given?

[mnnsa]

oh yes d is not given

[keskiverto]

Indeed. If d is given, then there is exactly one A(d) and B(y) is not a sum. It would be more like:

B( y, d )
  IF d divides y
  THEN return A(d)
  ELSE return 0

[mnnsa]

only n is given as input

[keskiverto]

Should the logic of B be something like:

B( y )
  sum=0
  FOR d in [1,y)
    IF d divides y
    THEN sum = sum + A(d)
  return sum

[mnnsa]

will here gcd(i,x) be 1?

[keskiverto]

"Here"?

I did show a guess of what B() could be. Does

B(x)= sum of A(d) where d divides the number x

say anything about 'gcd'? No.

[lastchance]

That's intriguing. Everything I try seems to give B(N)=N

[mnnsa]

oh

[keskiverto]

lastchance wrote:

That's intriguing. Everything I try seems to give B(N)=N

I think that is what is called "math". ;)

[marksman2op]

The answer is always N.
Read about it: https://cp-algorithms.com/algebra/phi-function.html.
OR https://proofwiki.org/wiki/Sum_of_Euler_Phi_Function_over_Divisors

[dutch]

@marksman2op,
Thanks for the links. You should edit your post and remove the period at the end of the first link. It causes the link to fail.

[keskiverto]

Now we could forget the A and write just the B:

unsigned int B( unsigned int x ) {
  // this function returns
  // Sum of Euler Phi function over divisors of x
  // see https://proofwiki.org/wiki/Sum_of_Euler_Phi_Function_over_Divisors
  return x;
}

That would be the smart thing to do; the most efficient implementation. Proven to be correct.

However, homework is probably not about getting the right return value, but about writing code that has the described logic.