Talk:Calkin–Wilf tree

aWhat about the FAREY Tree? This predates Calkin-wilf by decades, and includes the essential ideas. —Preceding unsigned comment added by 85.61.225.8 (talk) 23:25, 9 May 2009 (UTC)

You mean the Stern–Brocot tree? Its existence in Wikipedia predates this one by several years, and it is mentioned and linked from this article. —David Eppstein (talk) 23:49, 9 May 2009 (UTC)

Newman's formula

In Aigner and Ziegler, Newman's formula for the next rational after q in the CW sequence is given as

$q_{i+1}={\frac {1}{\lfloor q_{i}\rfloor +1-\{q_{i}\}}},$

where {q} stands for the fractional part of q. I very strongly dislike the {q} notation (that should be reserved for singleton sets), and would prefer to write this as

$q_{i+1}={\frac {1}{\lfloor q_{i}\rfloor +1-(q_{i}{\bmod {1}})}},$

However, "mod 1" is likely confusing to people who have only seen modular notation used for integers. A trivial rearrangement avoids the mess altogether:

$q_{i+1}={\frac {1}{2\lfloor q_{i}\rfloor +1-q_{i}}},$

which is how I wrote it in the article. Now, an anonymous editor insists on changing it to the exact form written in Aigner and Ziegler, and I've changed it back twice. Rather than continuing to edit war over this, I'd appreciate opinions from other math editors on the subject so we can build a consensus on the proper way to treat this equation (and maybe also on the proper way of handling "fractional part" notation in future). —David Eppstein (talk) 16:22, 18 May 2009 (UTC)

I think there are two issues at stake here. First, should we rewrite equations? Second, what forms of notation are preferred?

For the first issue, I think there is no debate: formulas should adhere to Wikipedia standards rather than those of the source. An article might draw on ten papers with five different methods of notation, but should keep only one throughout the article (aside from perhaps explaining the others).

The second is more contentious. I've never liked {x} as the fractional part of x, but I must admit it's unlikely to cause confusion in this context. I also don't like using the inline modulus (bmod), except in pseudocode where I prefer %. The floor symbol is well-established and unambiguous, so generally preferred. (Unfortunately the analogous ceiling symbol is much less widespread.) But I wish this was addressed in WP:MOSMATH so this didn't have to come down to preferences and commonality.

As a minor issue, I prefer

$q_{i+1}={\frac {1}{2\lfloor q_{i}\rfloor -q_{i}+1}},$

CRGreathouse (t | c) 17:17, 18 May 2009 (UTC)

I agree that your ordering is better (on the principle that terms of greater magnitude should be placed before others) and have changed the article to match. —David Eppstein (talk) 17:46, 18 May 2009 (UTC)

There is no requirement that we must uncritically follow unusual notation from references. I think the floor function notation is more widely known and will be more easily read by a typical person looking at this article. Wikipedia policy permits rewriting formulas in this way, when it is straightforward to see that the result is correct. — Carl (CBM · talk) 18:26, 18 May 2009 (UTC)

I agree that we need not conform to whatever notation sources use, but in this case I don't think it's necessary to change the notation just because some of us don't like it. The {q} notation for the fractional part is fairly common in sources that deal with fractional parts (e.g., Knuth uses this notation, although admittedly he's used quite a bit of good notation that hasn't caught on), and $2\lfloor q_{i}\rfloor -q_{i}+1$ requires slightly more interpretation than $\lfloor q_{i}\rfloor +1-\{q_{i}\}$ does. Shreevatsa (talk) 19:21, 18 May 2009 (UTC)

(without prejudice toward your preference) I would think the former would take slightly less, having only one function invocation in addition to the addition and subtraction rather than two (and $\lfloor \,\rfloor$ being somewhat more common than { }). Why do you think it takes more? Maybe you see something I've missed.

CRGreathouse (t | c) 20:48, 18 May 2009 (UTC)

Oh, this is vague, but I just meant that it is immediately obvious "what" $\lfloor q_{i}\rfloor +1-\{q_{i}\}$ is: it is a number with integer part $\lfloor q_{i}\rfloor$ and fractional part $1-\{q_{i}\}$. (Or, one might read it as starting with the integer $\lfloor q_{i}\rfloor +1$ and subtracting a small $\{q_{i}\}$ from it.) For the other expression, one imagines taking the floor $\lfloor q_{i}\rfloor$ and doubling it, then subtracting $q_{i}$ to get somewhere close to $q_{i}$ but it's not clear where exactly... until one sees the trick of looking at the first two terms as $\lfloor q_{i}\rfloor -(q_{i}-\lfloor q_{i}\rfloor )$... or something like that. I suspect this is a reason the original author wrote it in that form, instead of (say) $q_{i}+1-2\{q_{i}\}$ which, similar to what you said, has only one function invocation. I realise this is all subjective nonsense, anyway. :-) Shreevatsa (talk) 23:27, 18 May 2009 (UTC)

It's sure not obvious to me. (My first thought is: it's an expression involving a number and a set. What does that mean?) And it was sufficiently non-obvious to the anon trying to use that version of the expression that he or she felt the need to add a textual explanation for the notation below the expression, which is I think unnecessary with the version that only has the floor in it. But your reasoning makes it seem like I grouped it wrong in the bmod version; perhaps I should have written $\lfloor q\rfloor +(-q)\%1$? Unfortunately that raises its own problems (C/C++/Java don't do the right thing for modulo operations on negative numbers.) Even $\lfloor q\rfloor +\{-q\}$ would be a small improvement on the AZ version, so I don't think we should assume they found the optimal version. —David Eppstein (talk) 23:43, 18 May 2009 (UTC)

And $\lfloor q_{i}\rfloor$ is not obvious to general readers, including myself. I went searching for this formula elsewhere to find a more detailed explanation, and couldn't find it. Everything else uses a different, more intuitive formula, including the book that it turns out this formula is referenced from, so I changed it to be consistent with the literature. The only other source I can find that mentions your formula is [1]. But hey, have fun pressing the Undo button whenever anyone tries to add helpful content. I'm sure the reader's time isn't that valuable anyway. —Preceding unsigned comment added by 71.167.69.124 (talk) 01:37, 19 May 2009 (UTC)

As far as I'm concerned there is no "your formula" needing any more detailed explanation: it is the same formula as the one from the book, only rearranged in a trivial way. —David Eppstein (talk) 04:08, 19 May 2009 (UTC)

Yeah, this is an entirely trivial issue and it doesn't matter much either way. I guess the question is whether articles on a certain topic should use notation that is common in that area but possibly unfamiliar to mathematicians in general. I've seen the {x} notation often enough that I wouldn't read it as a set, but if we have reason to believe this notation is non-standard and would confuse most readers of the article, we should use something else instead. Shreevatsa (talk) 13:35, 19 May 2009 (UTC)

The CW tree use the same structure like the Mandelbrot Tree fractal: [2] —Preceding unsigned comment added by Bocutadriansebastian (talk • contribs) 19:57, 22 February 2010 (UTC)

That's an H tree. But the physical layout of the CW tree is not important: it's the same tree no matter where you draw its nodes. —David Eppstein (talk) 21:02, 22 February 2010 (UTC)

H-Tree instead of Binary tree?

Personally, I think the first picture should be a typical binary tree since that's the more familiar shape, and maybe have a second image of the H-tree underneath. Loadedsalt (talk) 00:38, 21 October 2012 (UTC)

Done pretty much as suggested. Olli Niemitalo (talk) 06:58, 5 May 2015 (UTC)

nth or (n+1)th

The section Stern's diatomic sequence says "The nth value in the sequence is the value fusc(n) of the fusc function". Only the first value in the sequence is 0, and only fusc(0) = 0. So shouldn't the article say "The (n + 1)th value in the sequence is the value fusc(n) of the fusc function"? Of some of the integer sequence articles that I checked, the article Catalan number seems to have the same error. The lede of Integer sequence implies that a sequence begins with the 1st term. Olli Niemitalo (talk) 09:49, 29 April 2015 (UTC)

Might suffice to add "Using zero-based numbering, " to remove the ambiguity. Olli Niemitalo (talk) 17:13, 29 April 2015 (UTC)

Better definition and a proof for existence and uniqueness

I propose to exchange the first three paragraphs in Definition and structure with the following (please notice I am not a native English speaker). The proofs are mine.

The Calkin-Wilf tree is an infinite binary tree in which each vertex is associated with a positive rational number expressed as an irreducible fraction $a \over b$; in particular, the number $1 \over 1$ is associated with the root vertex. Each vertex $a \over b$ has a left child whose value is $a \over a+b$ and a right child whose value is $a+b \over b$.

Observation 1: Each vertex has a left child whose value is less than 1, since $a<a+b$. Similarly, each vertex has a child on the right whose value is greater than 1.

Observation 2: The sum of the numerator and denominator of the first child is $2a+b$, while that of the second child is $a+2b$; in both cases the sum is greater than that of the parent $a+b$. It follows that by going down the tree, a strictly increasing sequence of sums is always obtained. On the contrary, going up the tree always results in a strictly decreasing sequence of sums.

The parent of any rational number can be determined after expressing the number as an irreducible fraction $p \over q$, i.e. such that the greatest common divisor of $p$ and $q$ is 1. If ${p \over q}<1$, the parent of $p \over q$ is $p \over {q-p}$; if ${p \over q}>1$, the parent of $p \over q$ is ${p-q} \over q$. Therefore, the parent is a fraction whose sum of numerator and denominator is either $p$ or $q$, and in both cases it is less than $p+q$, which is the sum corresponding to the child fraction $p \over q$. It follows that a repeated reduction of this type must sooner or later reach the irreducible fraction with minimum sum, that is, the number $1 \over 1$. This is an informal proof that every rational number appears at least once as the vertex of the tree.

Furthermore, the parent formula provides for each step a unique sum value which is lower than the previous one, therefore, given any rational number, the sequence of sums to go up from the associated vertex to the root is unique and strictly decreasing (as already observed above). Assume there are two distinct vertices with the same rational number. Due to the structure of tree graphs, going up the tree from each one would sooner or later arrive at the same vertex. Since the sequence of sums is strictly decreasing, the number of steps taken to reach this vertex from each of the two starting vertices must be the same, otherwise we would have two distinct sum values ​​for this vertex. In other words, the two sequences of sums, as well as being equal, are also synchronized. It follows that the two children of the common vertex (which correspond to the previous step of the sequences) have the same sum value, which is in contradiction with the definition of the tree. The conclusion is that no two vertices with the same rational number can exist, that is, a certain rational number can appear at most once in the tree. Overall, therefore, each rational number appears exactly once in the tree in the form of an irreducible fraction. Colemarc (talk) 17:02, 26 August 2022 (UTC)