math problem

Jul 4, 2020 at 6:33am

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.
Last edited on Jul 4, 2020 at 7:07am
Jul 4, 2020 at 6:57am
Why would d be given?
Jul 4, 2020 at 7:07am
oh yes d is not given
Jul 4, 2020 at 7:09am
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
Jul 4, 2020 at 11:30am
only n is given as input
Jul 4, 2020 at 11:45am
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
Jul 4, 2020 at 12:26pm
will here gcd(i,x) be 1?
Jul 4, 2020 at 2:41pm
"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.
Jul 4, 2020 at 8:36pm
That's intriguing. Everything I try seems to give B(N)=N
Jul 5, 2020 at 2:44am
oh
Last edited on Jul 5, 2020 at 3:36am
Jul 5, 2020 at 8:39am
lastchance wrote:
That's intriguing. Everything I try seems to give B(N)=N

I think that is what is called "math". ;)
Jul 5, 2020 at 10:14am
Jul 5, 2020 at 3:30pm
@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.
Jul 5, 2020 at 8:17pm
Now we could forget the A and write just the B:
1
2
3
4
5
6
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.
Topic archived. No new replies allowed.