Talk:Ducci sequence

The common claim that Ducci iterations converge to a zero sequence iff the length of the sequence is a power of 2 is incorrect. The correct formulation is "Ducci iterations converge for any starting sequence iff the length of the sequence is a power of 2. For example, for N = 6, one gets to 0s starting with 101010, 123210, or 121210.

I recommend an external link

• Integer Iterations on a Circle (from cut-the-knot)

Alexb@cut-the-knot.com (talk) 04:38, 31 March 2008 (UTC)

Thanks for the feedback. I didn't quite understand the difference between the common claim and the correct formulation. Are you saying that there are sequences that converge but not to zeros? As your link states, it's possible to converge to e.g 333333 but this gives 000000 in the next step. EverGreg (talk) 10:40, 31 March 2008 (UTC)

No, what I am saying is that, even for N which is not a power of 2, there are sequences that converge to 0. The article says "It has been proven that for n not a power of two, the Ducci sequence will settle on a loop with 'binary' sequences. That is, with elements composed of only two different digits." This is incorrect. Again, for some starting sequences the iterations will converge to 0 even for, say, N = 6, as the three examples 101010, 123210, or 121210 show.

Alexb@cut-the-knot.com (talk) 22:39, 12 April 2008 (UTC)

Aha! yes 101010 do indeed converge to zeros. I've changed the text accordingly.EverGreg (talk) 14:22, 13 April 2008 (UTC)

Very good. Now please give credit where credit is due. An external link to the page suggested above will do the job. Besides a Java simulation, the page contains additional references including to a recent paper by Greg Brockman that brought him the 6th place at the Intel Science Talent Search Competition.

Alexb@cut-the-knot.com (talk) 03:10, 14 April 2008 (UTC)

Format

It looks harder to read the sequences with the new format. If I was unfamiliar with the topic, I wouldn't know at first if I should read them line by line or column by column. Do others have the same impression or are they better in a multi-column format? EverGreg (talk) 11:55, 29 January 2009 (UTC)

I changed the original "one tuple per line" format because it took up way too much space on the screen and looked unbalanced. But I agree there is now an ambiguity in the order of reading. Maybe an explanatory note would help. Alternatively, arrows could show the sequence of iterations like this:

$(0,653,1854,4063)\rightarrow (653,1201,2209,4063)\rightarrow (548,1008,1854,3410)\rightarrow$

$(460,846,1556,2862)\rightarrow (386,710,1306,2402)\rightarrow (324,596,1096,2016)\cdots$

Gandalf61 (talk) 13:37, 29 January 2009 (UTC)

Yes those arrows could help, though it looks a bit cluttered. But it might work better on the simpler sequences. If the big 4-tuple follows as the last example, it would be enough to write the starting numbers and simply state that it ends after 24 iterations.EverGreg (talk) 17:16, 29 January 2009 (UTC)

I've added arrows to the examples, and shortened the first one by only showing first and last few iterations. Gandalf61 (talk) 13:41, 1 February 2009 (UTC)

Yes that gave a good readability! :-) —Preceding unsigned comment added by EverGreg (talk • contribs) 17:06, 1 February 2009 (UTC)

if and only if..

Florian Breuer clearly states: 'Every Ducci sequence of n-tuples of integers vanishes if and only if n is a power of two.' Other sources are also clear on the if and only if part, but we've got an example of a 6-tuple that vanishes. Where's the misunderstanding? EverGreg (talk) 14:02, 30 January 2009 (UTC)

I don't think there is any contradiction here. If n is a power of 2 then every Ducci sequence of n-tuples will eventually "vanish" (i.e. reach the zero tuple). If n is not a power of 2 then some Ducci sequences of n-tuples do not vanish, but enter a loop of binary n-tuples instead. Of course, some Ducci sequences will vanish for any n - a tuple whose members are all equal will immediately vanish, for example, - but only if n is a power of 2 can we say that every Ducci sequence will eventually vanish. Gandalf61 (talk) 14:19, 30 January 2009 (UTC)

Ah, I read "every" but thought "a" :-) EverGreg (talk) 16:40, 30 January 2009 (UTC)