4

Trying to define the function $b(n)$ which counts the number of $1$s in the binary representation of $n$ arithmetically I came up with the following definition:

$$b(n)=m :\equiv (\exists k_1\dots k_m)\ k_i \neq k_j \wedge n = 2^{k_1} + \dots + 2^{k_m}$$

Eventhough looking somehow "diophantine", this is - because of the dots $\dots$ - not a sound definition.

  1. Does $b(n)$ have a name by which I can search for it?

  2. What is a sound definition of $b(n)$ in arithmetical terms (using only addition, multiplication, exponentation eventually and if necessary primitive recursion and $\mu$- recursion)?

Notice that other unsound definitions can be made into sound first-order definitions (e.g. addition recursively defined), e.g. $n + k = m :\equiv \operatorname{succ}^k(n) = m$.

Hans-Peter Stricker
  • 18,159
  • No, I didn't, but I did not want to allow $\log$, etc. but only $+$, $\cdot$ and exponentation, eventually. – Hans-Peter Stricker Aug 28 '14 at 10:49
  • I have an idea: could you use something along the lines of: there exists a set such that for indices belonging to that set, there exist k with those indices with the desired property? More formally: $\exists S$ such that $\exists k_i, \ \ i \in S$ with $k_i<k_j$ for $i<j, \ \ i,j \in S$ and ... – ShakesBeer Aug 28 '14 at 10:54
  • Sounds interesting. If this definition works, the next question would be: Is there a first order definition? – Hans-Peter Stricker Aug 28 '14 at 10:55
  • Well, you'll need to think about the fact that you need to code a variable number of $k_i$, so you're going to need a set or a ... I think. I haven't studied logic though, so that's all I can help I'm afraid. EDIT: also note, do you even need the restriction that they have to be increasing? It doesn't matter, as long as they're distinct... – ShakesBeer Aug 28 '14 at 10:56
  • You are right! I changed it. – Hans-Peter Stricker Aug 28 '14 at 11:26

2 Answers2

7

Is this something that would fit your requirements?

$b(n) = \begin{cases}0&n=0\\b(\frac n2)&n>0\land n\text{ even}\\b(\frac{n-1}2)+1&n\text{ odd}\end{cases}$

Frunobulax
  • 6,629
  • 24
  • 43
1

I think the name you're looking for is Hamming weight. The article I linked to also lists other names.

Frunobulax
  • 6,629
  • 24
  • 43