Have some code (written in C), need the equivalent notation for mathematics. Is it possible using if-statements and sigma notation for this, and if so, how?

int res = 0;
for (int i=0; i < (N/2)+1; i=i+1)
  if (N % pow(2, i) == 0) res = i;

I have gotten as far as:

$$ \sum _{i=0}^{{N\over2}+1}\:(N \mod 2^i )$$ (missing the == 0 and res = i)

Ideas or a solution are welcome.

  • $\begingroup$ You need to look at what the code does. I suppose you're trying to write down an expression for the value of the variable res when the code terminates. You're claiming that it's a sum of modulus expressions, but that's very unlikely to be correct because the code doesn't add a bunch of things to res. The most natural expression for the final value of res isn't going to be a sum of terms. $\endgroup$ Jun 14 '18 at 15:31
  • $\begingroup$ Im not claiming anything, I know what the code does. res is not a sum of terms, you are right about that, but it is a value that is updated inside the for-loop (in the code). Wether or not a simple solution for math exists I don't know. I ask because maybe someone knows. $\endgroup$ Jun 14 '18 at 15:51
  • $\begingroup$ Let's not quibble about language. Your question states that the answer has something to do with the sum you quote; I explained why it doesn't. I'm trying to encourage you to work out the answer yourself by reasoning about what the code does, rather than by applying "rules" such as "it's a for loop so it must be some kind of summation. $\endgroup$ Jun 14 '18 at 15:54

Let me define $$f(x) = \begin{cases} 0 & x \ne 0 \\ 1 & x = 0\end{cases}$$ Now it is $$ \sum _{i=0}^{{N\over2}+1}\:f(N \text { mod } 2^i)$$ The code calculates how many times number is divisible by two (which by the way could be simplified to checking number of trailing zeros in binary representation, say hacky method x & -x).

You can define {N, 2} for the highest power of a prime 2 that divides N, and it is the valid notation. There are other approaches and notations of greatest power of two dividing N at MathOverflow.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.