using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace A161895
{
	// This program creates a b-file for OEIS sequence A161895

	class Program
	{
		static void Main(string[] args)
		{
			new Program().DoIt();
		}

		void DoIt()
		{
			string s;
			OEISBfilePrinter p = new OEISBfilePrinter("b161895.txt", 1, 10000, 1000);

			for (int bits = 1; bits <= 14; bits++)
			{

				long first = (long)Math.Pow(2, bits - 1);
				long last = (long)Math.Pow(2, bits) - 1;

				Console.WriteLine("");
				Console.WriteLine("====\t" + bits + "\t" + first + "\t" + last);

				Dictionary<string, List<long>> all = new Dictionary<string, List<long>>();

				// Collect all numbers that have identical set of runs
				for (long i = first; i <= last; i++)
				{
					s = FindRuns(i, bits);

					List<long> tmp;
					if (!all.TryGetValue(s, out tmp))
					{
						tmp = new List<long>();
						all.Add(s, tmp);
					}
					tmp.Add(i);
				}

				SortedDictionary<long, long> n = new SortedDictionary<long, long>();

				// Create a sorted list of the numbers, and their repetition count
				// in other words n and a(n)
				foreach (KeyValuePair<string, List<long>> kv in all)
				{
					foreach (long v in kv.Value)
					{
						n.Add(v, kv.Value.Count);
					}
				}

				// Report result
				Console.WriteLine("");
				foreach (KeyValuePair<long, long> kv in n)
				{
					Console.WriteLine(kv.Key + "\t" + kv.Value);
					p.Add(kv.Value);
				}
			}

			p.Close();
		}

		// Find the runs of 'v' in binary representation
		// Return a string which uniquely describes the runs
		string FindRuns(long v, int nBits)
		{
			string s;
			s = Convert.ToString(v, 2);

			int[] runsOf1 = new int[nBits + 1];
			int[] runsOf0 = new int[nBits + 1];
			int max1 = 0;
			int max0 = 0;

			// Always starts with 1
			bool isRun1 = true;
			int n = 0;

			foreach (char c in s)
			{
				if (isRun1)
				{
					if (c == '1')
					{
						n++;
					}
					else
					{
						runsOf1[n]++;
						if (n > max1) max1 = n;
						isRun1 = false;
						n = 1;
					}
				}
				else
				{
					if (c == '1')
					{
						runsOf0[n]++;
						if (n > max0) max0 = n;
						isRun1 = true;
						n = 1;
					}
					else
					{
						n++;
					}
				}
			}

			// Collect last run
			if (isRun1)
			{
				runsOf1[n]++;
				if (n > max1) max1 = n;
			}
			else
			{
				runsOf0[n]++;
				if (n > max0) max0 = n;
			}

			DelimitedString ds1 = new DelimitedString(".");
			DelimitedString ds0 = new DelimitedString(".");

			for (int k = 1; k <= max1; k++)
			{
				ds1.Add(runsOf1[k]);
			}
			for (int k = 1; k <= max0; k++)
			{
				ds0.Add(runsOf0[k]);
			}

			return ds1.ToStringItems() + "|" + ds0.ToStringItems();
		}

		class DelimitedString
		{
			string Delimiter;
			StringBuilder sb;
			int count;
			bool isEmpty;

			public int Count
			{
				get { return count; }
			}

			public DelimitedString(string delimiter)
			{
				Delimiter = delimiter;
				sb = new StringBuilder();
				count = 0;
				isEmpty = true;
			}

			public void Add(string s)
			{
				count++;
				if (!isEmpty)
				{
					sb.Append(Delimiter);
				}
				sb.Append(s);
				isEmpty = false;
			}

			public void Add(long v)
			{
				Add(v.ToString());
			}

			public override string ToString()
			{
				return count + ": " + sb.ToString();
			}

			public string ToStringItems()
			{
				return sb.ToString();
			}
		}

		class OEISBfilePrinter
		{
			int Offset;
			int MaxEntries;
			int MaxLength;
			StreamWriter w;
			public int Ix;

			public OEISBfilePrinter(string fn, int offset, int maxEntries, int maxLength)
			{
				Offset = offset;
				MaxEntries = maxEntries;
				MaxLength = maxLength;
				w = new StreamWriter(fn);
				Ix = 0;
			}

			public void Close()
			{
				if (w != null)
				{
					w.Close();
					w = null;
				}
			}

			public void Add(long v)
			{
				if (w != null)
				{
					if (Ix + Offset <= MaxEntries)
					{
						w.WriteLine((Ix + Offset) + " " + v);
						Ix++;
					}
					else
					{
						Close();
					}
				}
			}
		}
	}
}