This site is supported by donations to The OEIS Foundation.
User:Susanne Wienand
Contents
About me
I am a chemical engineer, though with few and long ago working experience (graduation in 1988, TU Dortmund).
One of my hobbies are mathematical online games where regularly problems are published to be solved by the users.
If I do not find a fast solution for a problem, I mostly calculate results for small parameters and look for a pattern. The OEIS is helpful to find such patterns. It is a very nice encyclopedia.
I registered at the OEIS in order to submit a pattern which I had used to solve a problem of project euler.
Sequences which I submitted
I submitted A194595, A197653, A197654, A197655, A197657, A198256, A198257 and A198258. These are number triangles and their row sums. They are about a certain kind of binary curves for which Peter Luschny introduced the name 'meander'. You can find much information about this kind of meanders on his user page in his BLOG on OEIS (Meanders and walks on the circle and Fibonacci Meanders).
Definition of meanders concerned by these sequences
A binary curve C is a triple (m, S, dir) such that
- S is a list with values in {L,R} which starts with an L,
- dir is a list of m different values, each value of S being allocated a value of dir,
- consecutive Ls increment the index of dir,
- consecutive Rs decrement the index of dir,
- the integer m>0 divides the length of S and
- C is a meander if each value of dir occurs length(S)/m times.
An example of a meander
Below a meander is shown. The list S consists of 24 elements with values of either 'L' or 'R' and starts with an 'L'. The values of dir are 0, 1 or 2. Each of them occurs eight times in the course of the curve.
The meander is illustrated as a curve of arcs with 120° (plotted by the help of the vector graphics language Asymptote and Windows Paint).
In the illustration there are arcs which coincide, so a point moving along the curve shows the meander more clearly.
The animation is plotted by the help of sage (version 4.8).
Counting amounts of meanders
The following brute force code counts the amounts of meanders for a certain value of m, a certain length of S and different compositions of S. S is initialized as an array which consists of a one ensued by length-1 zeroes. The one stands for an L and the zeroes stand for Rs. S is incremented until it consists just of ones. For each state of S, it is tested if all values of dir are allocated length(S)/m times to a value of S. If this is the case, the curve is counted as a meander.
c#-code:
using System;
namespace count_meanders
{
class Program
{
static int length = 1;
static int[] S = new int[length];
static int m = 1;
static int[] count_dir = new int[m];
static int dir = 0;
static int max = length / m;
static int[] amount_L = new int[length + 1];
static long amount_total = 0;
static void Main(string[] args)
{
if (length % m != 0)
Console.WriteLine("m does not divide the length of S.");
else
{
S[0] = 1;
test();
while (count_up() == true)
test();
int sum = 0;
for (int i = m; i <= length; i += m) //print a row of the number triangle
{
sum += amount_L[i];
Console.Write("counted meanders with " + i + " Ls: " + amount_L[i]);
if (i < length)
Console.WriteLine();
}
Console.WriteLine(" sum: " + sum); //row sum
Console.WriteLine();
Console.WriteLine("totally counted meanders: " + amount_total); //row sum
Console.ReadLine();
}
}
static void test()
{
int Ls = 1;
for (int i = 0; i < m; i++)
count_dir[i] = 0;
dir = 0;
count_dir[dir]++;
for (int i = 1; i < length; i++)
{
if (S[i] == 1 && S[i - 1] == 1)
dir = (dir + 1) % m;
if (S[i] == 0 && S[i - 1] == 0)
dir = (dir - 1 + m) % m;
if (++count_dir[dir] > max)
return;
if (S[i] == 1)
Ls++;
}
amount_L[Ls]++;
amount_total++;
}
static bool count_up()
{
int index = length-1;
while (S[index] == 1)
{
S[index] = 0;
index--;
if (index <= 0)
return false;
}
S[index] = 1;
return true;
}
}
}
Some results of this counting for small values of length(S) are summarized in the tables below.
The tables match with the number triangles
- A007318 (Pascal's triangle) (m=1)
- A103371 (m=2)
- A194595 (m=3)
- A197653 (m=4)
- A197654 (m=5)
- A197655 (m=6)
For m=1, the amounts of meanders with a certain length and a certain number of Ls are found in A007318. For m=1, there is only one value of dir, so that in this case all binary strings of Ls and Rs which begin with an L are meanders. If the list S has a length of and contains Ls, there are positions for Ls (the first element in S is always an L). The number of ways to build up such strings is , the values in Pascal's triangle. However, if m exceeds 1, it is not yet proved for all lengths of S that the triangles match with the amounts of meanders.
How to determine amounts of meanders faster
So far, you saw a brute force method to determine and count the meanders. Peter Luschny describes an improved approach in his blog, under generating meanders. Using brute force, you know all meanders which are counted exactly.
However, in order to know how many meanders with a certain amount of Ls and Rs exist, dynamic programming can do the work.
Start with one curve that consists of an L. Say it has got direction 0. It can be extended by either an R or an L and thus is the predecessor of two possible curves of length two. Add Rs and Ls until the whished-for length of curve is reached and keep track of the data needed to sum up the relevant binary curves: The total amount of Ls, the total amount of Rs, the last character, the direction resulting from that character and also how often each direction occurred. Concatenated to a string, these data can be the key of a hash. It's value can contain the amount of meanders belonging to that key. At last all curves with the required amounts of Ls and Rs for which all directions occurred equally often, are summed up, yet the exact course of these curves is unknown.
Comparison of brute force and dynamic programming
Below, in two tables an example of brute force and an example of dynamic programming for counting meanders of length 6 which contain three Ls and have a central angle of 120° are shown. The frequencies of the directions are denoted by , , and . The meanders are marked by an x.
brute force
| no. | characters | directions | marks | ||||
|---|---|---|---|---|---|---|---|
| 1 | LRRRLL | 002112 | 2 | 2 | 2 | x | |
| 2 | LRRLRL | 002222 | 2 | 0 | 4 | ||
| 3 | LRRLLR | 002200 | 4 | 0 | 2 | ||
| 4 | LRLRRL | 000022 | 4 | 0 | 2 | ||
| 5 | LRLRLR | 000000 | 6 | 0 | 0 | ||
| 6 | LRLLRR | 000110 | 4 | 2 | 0 | ||
| 7 | LLRRRL | 011022 | 2 | 2 | 2 | x | |
| 8 | LLRRLR | 011000 | 4 | 2 | 0 | ||
| 9 | LLRLRR | 011110 | 2 | 4 | 0 | ||
| 10 | LLLRRR | 012210 | 2 | 2 | 2 | x |
dynamic programming
| length | no. of predecessor | amount of Ls | amount of Rs | last character | last direction | no. | remarks | |||
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | - | 1 | 0 | L | 0 | 1 | 0 | 0 | 1.1 | |
| 2 | 1.1 | 2 | 0 | L | 1 | 1 | 1 | 0 | 2.1 | |
| 1.1 | 1 | 1 | R | 0 | 2 | 0 | 0 | 2.2 | ||
| 3 | 2.1 | 3 | 0 | L | 2 | 1 | 1 | 1 | 3.1 | |
| 2.1 | 2 | 1 | R | 1 | 1 | 2 | 0 | 3.2 | ||
| 2.2 | 2 | 1 | L | 0 | 3 | discarded, too big | ||||
| 2.2 | 1 | 2 | R | 2 | 2 | 0 | 1 | 3.3 | ||
| 4 | 3.1 | 4 | discarded, too many Ls | |||||||
| 3.1 | 3 | 1 | R | 2 | 1 | 1 | 2 | 4.1 | ||
| 3.2 | 3 | 1 | L | 1 | 1 | 3 | discarded, too big | |||
| 3.2 | 2 | 2 | R | 0 | 2 | 2 | 0 | 4.2 | ||
| 3.3 | 2 | 2 | L | 2 | 2 | 0 | 2 | 4.3 | ||
| 3.3 | 1 | 3 | R | 1 | 2 | 1 | 1 | 4.4 | ||
| 5 | 4.1 | 4 | discarded, too many Ls | |||||||
| 4.1 | 3 | 2 | R | 1 | 1 | 2 | 2 | 5.1 | ||
| 4.2 | 3 | 2 | L | 0 | 3 | discarded, too big | ||||
| 4.2 | 2 | 3 | R | 2 | 2 | 2 | 1 | 5.2 | ||
| 4.3 | 3 | 2 | L | 0 | 3 | discarded, too big | ||||
| 4.3 | 2 | 3 | R | 2 | 2 | 0 | 3 | discarded, too big | ||
| 4.4 | 2 | 3 | L | 1 | 2 | 2 | 1 | 5.3 | ||
| 4.4 | 1 | 4 | discarded, too many Rs | |||||||
| 6 | 5.1 | 4 | discarded, too many Ls | |||||||
| 5.1 | 3 | 3 | R | 0 | 2 | 2 | 2 | 6.1 | x | |
| 5.2 | 3 | 3 | L | 2 | 2 | 2 | 2 | 6.2 | x | |
| 5.2 | 2 | 4 | discarded, too many Rs | |||||||
| 5.3 | 3 | 3 | L | 2 | 2 | 2 | 2 | 6.2 | x | |
| 5.3 | 2 | 4 | discarded, too many Rs |
As with the brute force method, dynamic programming counts three meanders, one of them ending with character R and direction 0, two of them ending with character L and direction 2. These two, numbered by 6.2, can be pooled under the same key.
A dynamic programming code to count meanders
//© 2015 (see The_OEIS_End-User_License_Agreement) //visual c#, Microsoft Visual Studio Express 2013
//parameters //m: 360° divided by the central angle of the curves //count: numbering //myW: c# objekt to write data in a file //length: length of the particular curves //limitDir: the frequency of the particular directions if a curve is a meander //stepsL: intended number of Ls //stepsR: intended number of Rs //paths0, paths1: hashes. Their keys contain data of the curves and their values store how often the particular keys occur. //paths0 is initialized by a curve of length 1. Hence the data for curves of length 2 are determined and //stored in pahts1. Then the data in paths0 are replaced by the data in paths1 and the data in paths1 are deleted. //This is continued until the desired length of curves is reached. //s: string to contain the keys of paths0 //s1: array of strings which stores the data contained in s //s1[0]: number of Ls //s1[1]: number of Rs //s1[2]: last character of the particular curves //s1[3]: last direction of the particular curves //s1[4]...s1[3+m]: frequencies of the directions //v, v1: auxiliary variables //ok : boolean variable, which determines if a certain key is created //t: the data for the keys of paths1 are written in this string //sum: the number of meanders with a certain length and amount of Ls are added up in sum //f: after reaching the desired length of curves, it is looked up in the keys, if all directions occur equally often. //If thís is true, f = true //addition(string1, string2): function to add very big numbers
using System; using System.Collections; using System.IO;
namespace meanderDp5 { class Program { static void Main(string[] args) { int m = 3; int count = -1; StreamWriter myW = new StreamWriter("C:\\myPath\\myFile.txt"); for (int length = m; length <= 63 * m; length += m) { int limitDir = length / m; for (int stepsL = m; stepsL <= length; stepsL += m) { count++; Console.WriteLine(count); int stepsR = length - stepsL; Hashtable paths0 = new Hashtable(); Hashtable paths1 = new Hashtable(); //initialization of paths0 string s = "1 0 L 0 1 "; for (int i = 1; i < m; i++) s += "0 "; paths0[s] = 1; for (int step = 2; step <= length; step++) { foreach (DictionaryEntry e in paths0) { s = e.Key.ToString(); string[] s1 = s.Split(' '); int v = Int32.Parse(s1[0]); //add an L to curves if (v < stepsL) { bool ok = true; string t = (v + 1) + " " + s1[1] + " L "; v = Int32.Parse(s1[3]); //two consecutive Ls increment the direction if (s1[2] == "L") v = (v + 1) % m; t += v + " "; for (int i = 0; i < m; i++) { if (i == v) { int v1 = Int32.Parse(s1[i + 4]) + 1; if (v1 > limitDir) { ok = false; break; } t += v1 + " "; } else t += s1[i + 4] + " "; } if (ok == true) { if (paths1[t] == null) paths1[t] = e.Value; else paths1[t] = addition(paths1[t].ToString(), e.Value.ToString()); } } v = Int32.Parse(s1[1]); //add an R to curves if (v < stepsR) { bool ok = true; string t = s1[0] + " " + (v + 1) + " R "; v = Int32.Parse(s1[3]); //two consecutive Rs decrement the direction if (s1[2] == "R") { v--; if (v < 0) v += m; } t += v + " "; for (int i = 0; i < m; i++) { if (i == v) { int v1 = Int32.Parse(s1[i + 4]) + 1; if (v1 > limitDir) { ok = false; break; } t += v1 + " "; } else t += s1[i + 4] + " "; } if (ok == true) { if (paths1[t] == null) paths1[t] = e.Value; else paths1[t] = addition(paths1[t].ToString(), e.Value.ToString()); } } } paths0.Clear(); foreach (DictionaryEntry e in paths1) paths0[e.Key] = e.Value; paths1.Clear(); } string sum = "0"; foreach (DictionaryEntry e in paths0) { bool f = true; string t = e.Key.ToString(); string[] t1 = t.Split(' '); if (Int32.Parse(t1[0]) == stepsL && Int32.Parse(t1[1]) == stepsR) { for (int i = 1; i < m; i++) { if (t1[i + 4] != t1[4]) { f = false; break; } } } if (f == true) sum = addition(sum, e.Value.ToString()); } myW.WriteLine(count + " " + sum); } } myW.Close(); Console.WriteLine("ready"); Console.ReadLine(); }
static string addition(string str1, string str2) { int exponent = 4; int mod = (int)Math.Pow(10, exponent); int[] arr = new int[1000]; int indexA = -1; int index1 = str1.Length; int index2 = str2.Length; int carry = 0; checked { try { while (index1 > 0 || index2 > 0) { indexA++; if (index1 > 0) { int k = exponent; while (index1 - k < 0) k--; arr[indexA] += Int32.Parse(str1.Substring(index1 - k, k)); index1 -= k; } if (index2 > 0) { int k = exponent; while (index2 - k < 0) k--; arr[indexA] += Int32.Parse(str2.Substring(index2 - k, k)); index2 -= k; } arr[indexA] += carry; carry = arr[indexA] / mod; arr[indexA] %= mod; } while (carry > 0) { indexA++; arr[indexA] = carry % mod; carry /= mod; } } catch (OverflowException) { Console.WriteLine("overflow"); Console.ReadLine(); } } string str3 = arr[indexA].ToString(); for (int i = indexA - 1; i >= 0; i--) { string v = arr[i].ToString(); ; while (v.Length < exponent) v = 0 + v; str3 += v; } return str3; } } }
Example of a meander counted by A197654
The curve is plotted by Asymptote Vector Graphics Language and the text is inserted by Microsoft Paint.
Asymptote-code for this plot:
import settings; size(8cm,0); outformat="pdf";
int m = 5;
string[] S = {"L","R","R","R","R","R","L","L","R","L","R","R","L","R","R","R","R","L","R","L","L","L","R","R","L"};
real angle = 360/m;
real x_m = 0;
real y_m = 0;
real a_0 = 0;
real a_1 = angle;
draw(arc((x_m,y_m),1,a_0,a_1),orange,ArcArrow);
for (int i = 1; i <S.length; ++i)
{
if (S[i] == "L" && S[i-1] == "L")
{
a_0 = a_1;
a_1 += angle;
draw(arc((x_m,y_m),1,a_0,a_1),orange,ArcArrow);
}
if (S[i] == "R" && S[i-1] == "R")
{
a_0 = a_1;
a_1 -= angle;
draw(arc((x_m,y_m),1,a_0,a_1),heavygreen,ArcArrow);
}
if (S[i] == "L" && S[i-1] == "R")
{
x_m += 2*cos(a_1*pi/180);
y_m += 2*sin(a_1*pi/180);
a_0 = a_1 - 180;
a_1 = a_1 - 180 + angle;
draw(arc((x_m,y_m),1,a_0,a_1),orange,ArcArrow);
}
if (S[i] == "R" && S[i-1] == "L")
{
x_m += 2*cos(a_1*pi/180);
y_m += 2*sin(a_1*pi/180);
a_0 = a_1 + 180;
a_1 = a_1 + 180 - angle;
draw(arc((x_m,y_m),1,a_0,a_1),heavygreen,ArcArrow);
}
}
dot((1,0),black);
shipout("example of a meander", bbox(0.3cm));
