Title: Find a Ducci sequence in C#

A Ducci sequence is a sequence of tuples of integers. You start with a sequence of values such as 1-2-3-4-5. To find the next tuple, you calculate the absolute value of the difference between adjacent numbers in the sequence, wrapping around to the beginning when you reach the end of the sequence. For example, the tuple after 1-2-3-4-5 is 1-1-1-1-4.

This example calculates a Ducci sequence starting from a tuple that you enter.

Ducci sequences have a number of interesting properties. First, all sequences eventually repeat. If the length of the tuples is a power of two, then the tuples eventually become all 0s. If the length of the tuples is not a power of two, then it either eventually becomes a tuple of all 0s, or it enters a binary loop where each tuple contains only 0 and some other value. (For example, 0-0-0-2-2 or 0-0-1-1-0.)

When you enter a start tuple and click Go, the program uses the following code to find the Ducci sequence.

private void btnGo_Click(object sender, EventArgs e) { lstResults.DataSource = null; Refresh(); // Convert into a List<int>. string nums_str = txtStart.Text; List<string> ints = nums_str.Split('-').ToList(); List<int> nums = ints.ConvertAll(s => int.Parse(s)); int nums_length = nums.Count; // Build the sequence. List<string> sequence = new List<string>(); sequence.Add(NumsToString(nums)); for (; ; ) { List<int> new_nums = new List<int>(); for (int i = 0; i < nums.Count; i++) new_nums.Add(Math.Abs(nums[i] - nums[(i + 1) % nums_length])); nums = new_nums; nums_str = NumsToString(nums); if (sequence.Contains(nums_str)) { sequence.Add(nums_str); int start = sequence.IndexOf(nums_str); int length = sequence.Count - start; lblSequenceStart.Text = start.ToString(); lblSequenceLength.Text = length.ToString(); lstResults.DataSource = sequence; return; } sequence.Add(nums_str); Debug.Assert(sequence.Count < 10000); } }

This code starts by splitting the numbers that you entered at the dash characters. It calls the NumsToString method described shortly to convert the list of values into a string and adds it to the sequence list.

The program then enters an infinite loop. Inside the loop, the code finds the next tuple in the sequence. If that tuple is already in the sequence list, the code displays the Ducci sequence and some information about it and breaks out of the loop. If the new tuple is not yet in the sequence, the code adds it to the sequence list and repeats the loop.

The Debug.Assert is there to prevent the loop from running forever if there is a bug in the program.

The following code shows the NumsToString method.

// Return the numbers separated by commas. private string NumsToString(List<int> nums) { return string.Join("-", nums.ConvertAll(n => n.ToString()).ToArray()); }

This method uses the Convert.ToAll LINQ extension method to convert the values in the nums list into a list of strings. It converts the list into an array and passes it into the string class's Join method to join the values with dash characters. The method then returns the result.

Download the example to experiment with it and to see additional details.