1
$\begingroup$

I am working on this coding problem, Counting bits.

For a given integer, $n$, I have to return a list of ones in the binary representation of all the numbers from $0$ to $n$. I understand that it is a dynamic programming question and that I can use the prior values that are not powers of $2$ to get the answers for the larger numbers (I keep adding $1$ once I reach a power of $2$ ).

This has been expressed in the form of this transition function. Although, I understand the approach and can code it, I don't get this mathematical representation. What does the $1,b$ mean? Add $1$ or $b$ to $P(x)$?

$P(x+b) = P(x) + 1,b = 2^m > x$

$\endgroup$
9
  • 6
    $\begingroup$ Is it the usual textual meaning: separating two clauses? Replace , with new line. Would that make sense? $\endgroup$ Commented 20 hours ago
  • 5
    $\begingroup$ OOr, rreplace thee comma with the word "where" or "for" $\endgroup$ Commented 20 hours ago
  • 1
    $\begingroup$ The long form of the statement is: $$\forall m\geq0\, (2^m>x\implies P(x+2^m)=P(x)+1)$$ $\endgroup$ Commented 20 hours ago
  • 2
    $\begingroup$ Recall that comments are not for posting answers. meta.stackexchange.com/questions/19756/how-do-comments-work $\endgroup$ Commented 20 hours ago
  • 3
    $\begingroup$ The misreading is due to poor typesetting practices. Compare: $P(x+b) = P(x) + 1,b = 2^m > x$ and $P(x+b) = P(x) + 1,\;\;\;\;b = 2^m > x$ $\endgroup$ Commented 18 hours ago

1 Answer 1

Reset to default
9
$\begingroup$

In plain English:

Whenever $b$ is a power of 2 and bigger than $x$, it is true that $P(x+b) = P(x) + 1$.

The comma-separated clause "$b=2^m > x$" is meant to communicate the first part of that, and should really introduce the variable $m$ somehow, but from context we can guess that the intent is that the equation holds if $b$ can be written as $2^m$ for any natural number $m$.

A general addendum. You will often see commas used to indicate conditions on a definition, such as below in the examples of absolute value and factorial: $$ |x| = \begin{cases} \phantom{-}x, & x \ge 0 \\ -x, & x < 0 \end{cases} \qquad n! = n \cdot (n-1)!,\; n\ge1 $$ You should imagine that the commas represent words such as "if", "for", or "where", and personally I think it's a sign of laziness not to make things more clear by including such a word.

There are other circumstances where commas make things ambiguous; for example, $0 \le x,y \le 1$ might mean "$0 \le x$ and $y \le 1$" or it might mean "$0 \le x \le 1$ and $0 \le y \le 1$". (I have been guilty of this one myself, but I have learned to avoid it.) A common piece of advice in mathematical writing is to make sure that two separate mathematical statements are separated by words, and never by punctuation alone; this avoids most of the confusion that commas can create.

$\endgroup$
5
  • 2
    $\begingroup$ The addendum was a good addition. $\endgroup$ Commented 19 hours ago
  • 4
    $\begingroup$ +1 for recommending words. $\endgroup$ Commented 18 hours ago
  • $\begingroup$ The statement "$P(x+b) = P(x) + 1,b = 2^m > x$" is particularly lazy as $m$ is never introduced. This could be written as "$P(x+b)=P(x)+1$ where $b=2^m$ for some $m\in \mathbb N$". I will confess I might use comas or semi-colons (without having a clear formality when one or the other as $P(x+b)=P(x+1); b=2^m, m\in \mathbb N$ but if someone got confused (as the OP would) I'd be embarrassed put in words. But come to think of it, what purpose does the variable $b$ serve. To write "$P(2^m+x)=P(x)+1$ when $2^m > x$ might be clearer". $\endgroup$ Commented 18 hours ago
  • 2
    $\begingroup$ It might be a sign of laziness, but often it is just a sign of lack of horizontal space. $\endgroup$ Commented 17 hours ago
  • $\begingroup$ @EmilJeřábek The way a first draft is formatted on the page isn’t a good reason not to make a second, clearer draft. $\endgroup$ Commented 9 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.