Skip to content

Instantly share code, notes, and snippets.

@bbarry

bbarry/Van_der_Waerden_2_6.cs

Created November 17, 2017 22:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bbarry/404dd81a5f69dfbb53cb4c2f72e1d0c6 to your computer and use it in GitHub Desktop.
Save bbarry/404dd81a5f69dfbb53cb4c2f72e1d0c6 to your computer and use it in GitHub Desktop.
Download ZIP
WIP of a program that proves W(2,6) = 1132; currently capable (in a few thousands of years I think) of finding all sequences of 1120 length.
Raw
Van_der_Waerden_2_6.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Threading;
using System.Threading.Tasks;
namespace ConsoleApplication8 {
class Program {
static uint[][] _lchecks; // bitmasks for sets of 6 progressive checks involving more than one u32 segment
static readonly uint[] U32Strings = new uint[437502481]; // all valid 32 bit strings that don't trigger an invalid bit within the next 6 and have high order bit 0
static void Main(string[] args) {
var checks = GenerateChecks().ToArray();
Array.Sort(checks);
int i;
var sChecks = GetShortChecks(checks, out i);
var iChecks = GetIntChecks(checks, ref i);
_lchecks = GetMultipleQuadChecks(checks, i);
var local = U32Strings;
int c = 0;
foreach (var u in Valid32BitStrings(sChecks, iChecks)) {
local[c] = u;
if (c % 1000000 == 0) Console.WriteLine(c);
c++;
}
Console.WriteLine(c);
// Dive(0x60d11de1);
var opts = new ParallelOptions {MaxDegreeOfParallelism = 6};
Parallel.ForEach(local, opts, Dive);
}
private static int total = 0;
[ThreadStatic]
private static long N = 0;
private static void Dive(uint prefix) {
var max = Dive(new List<uint> {prefix}, 1, 0);
Interlocked.Increment(ref total);
Console.WriteLine("{0} : {1:x8} : {2}", total, prefix, max);
}
private static int Dive(List<uint> canvas, int count, int lcheckLower) {
N++;
// int b = 0;
int max = count;
int lcheckUpper;
uint checkIfAny0;
uint checkIfAny1;
uint[] checkIfAll0;
uint[] checkIfAll1;
if (!ProduceBitmaskChecks(canvas, count, lcheckLower, out lcheckUpper, out checkIfAny0, out checkIfAll0, out checkIfAny1, out checkIfAll1)) return max;
var u32 = U32Strings;
if (checkIfAny0 <= int.MaxValue) {
foreach (var subsequence in u32) {
if ((subsequence & checkIfAny1) != 0) continue;
var inverted = ~subsequence;
if ((inverted & checkIfAny0) != 0) continue;
foreach (var mask in checkIfAll1) {
if ((subsequence & mask) == mask) {
goto next;
}
}
foreach (var mask in checkIfAll0) {
if ((inverted & mask) == mask) {
goto next;
}
}
canvas.Add(subsequence);
// b++;
max = Math.Max(max, Dive(canvas, count + 1, lcheckUpper));
canvas.RemoveAt(count);
next:
continue;
}
}
if (checkIfAny1 <= int.MaxValue) {
foreach (var inverted in u32) {
var subsequence = ~inverted;
if ((subsequence & checkIfAny1) != 0) continue;
if ((inverted & checkIfAny0) != 0) continue;
foreach (var mask in checkIfAll1) {
if ((subsequence & mask) == mask) {
goto next;
}
}
foreach (var mask in checkIfAll0) {
if ((inverted & mask) == mask) {
goto next;
}
}
canvas.Add(subsequence);
// b++;
max = Math.Max(max, Dive(canvas, count + 1, lcheckUpper));
canvas.RemoveAt(count);
next:
continue;
}
}
// if (b == 0) {
// var value = string.Join("", canvas.Select(x => $"{x:x8}"));
// using (var x = File.OpenWrite(value + ".txt")) {
// using (var writer = new StreamWriter(x))
// {
// writer.WriteLine("any 0: {0:X8}", checkIfAny0);
// writer.WriteLine("all 0:");
// foreach (var mask in checkIfAll0)
// {
// writer.WriteLine("{0:x8}", mask);
// }
// writer.WriteLine("any 1: {0:X8}", checkIfAny1);
// writer.WriteLine("all 1:");
// foreach (var mask in checkIfAll1)
// {
// writer.WriteLine("{0:x8}", mask);
// }
// }
// }
// }
return max;
}
private static bool ProduceBitmaskChecks(List<uint> canvas, int count, int lcheckLower, out int lcheckUpper, out uint checkIfAny0, out uint[] acheckIfAll0, out uint checkIfAny1, out uint[] acheckIfAll1) {
var lchecks = _lchecks;
lcheckUpper = 0;
List<uint> checkIfAll0 = new List<uint>();
checkIfAny0 = 0;
List<uint> checkIfAll1 = new List<uint>();
checkIfAny1 = 0;
acheckIfAll0 = null;
acheckIfAll1 = null;
for (int i = lcheckLower; i < lchecks.Length; i++) {
var bitmask = lchecks[i];
if (bitmask.Length > count + 1) {
// done computing necessary checks at this depth
lcheckUpper = i;
break;
}
var check0 = true;
var check1 = true;
for (int j = 0; j < canvas.Count && (check0 || check1); j++) {
var subsequence = canvas[j];
var mask = bitmask[j];
check0 = check0 && (~subsequence & mask) == mask;
check1 = check1 && (subsequence & mask) == mask;
}
var finalmask = bitmask[count];
var singlebit = (finalmask & (finalmask - 1)) == 0;
if (check0) {
if (singlebit) {
checkIfAny0 = checkIfAny0 | finalmask;
} else {
checkIfAll0.Add(finalmask);
}
}
if (check1) {
if (singlebit) {
checkIfAny1 = checkIfAny1 | finalmask;
} else {
checkIfAll1.Add(finalmask);
}
}
}
if (lcheckUpper == 0) {
//todo: call out to another function to handle bit strings that are within 32 bits of maximum length
//last 32 bits handled special
var value = string.Join("", canvas.Select(x => $"{x:x8}"));
Console.WriteLine(value);
return false;
}
if (count > 5) {
// this is completely arbitrary
var value = string.Join("", canvas.Select(x => $"{x:x8}"));
UpdateLongest(value);
}
// if any single must not be 1 and must not be 0 at the same time, no need to do any of this
if ((checkIfAny0 & checkIfAny1) != 0) {
return false;
}
// remove covering checks, ex:
// *.1.1.1.1
// *.1.1
// you cannot match the first without also matching the second, so no need for the first check
acheckIfAll0 = ReduceChecks(checkIfAll0, checkIfAny0);
acheckIfAll1 = ReduceChecks(checkIfAll1, checkIfAny1);
foreach (var mask in checkIfAll1) {
// given mask
// *.1.1
// if all are 1, test will fail
// if any are 0 test will pass
// thus if all mask bits are in the any0 mask, that test will fail
if ((checkIfAny0 & mask) == mask) goto fls;
}
foreach (var mask in checkIfAll0) {
if ((checkIfAny1 & mask) == mask) goto fls;
}
return true;
fls:
return false;
}
private static uint[] ReduceChecks(List<uint> list, uint singles) {
var remove = new bool[list.Count];
var any = false;
for (int i = 0; i < list.Count; i++) {
var c = list[i];
if ((c & singles) != 0) {
//if a single bit covers this mask it will also cover any mask that this mask covers
remove[i] = true;
any = true;
//so no need to do the inner loop
continue;
}
for (int j = i + 1; j < list.Count; j++) {
var d = list[j];
var u = c & d;
if (u == c) {
// if all bits in c are also in d then d is unnecessary
remove[j] = true;
any = true;
} else if (u == d) {
// and the reverse
remove[i] = true;
any = true;
}
}
}
if (any) {
var temp = new List<uint>(list.Count);
for (int i = 0; i < list.Count; i++) {
if (!remove[i]) {
temp.Add(list[i]);
}
}
return temp.ToArray();
}
return list.ToArray();
}
static readonly object l = new object();
private static string longest = "";
private static void UpdateLongest(string value) {
Console.WriteLine(N);
if (value.Length > longest.Length) {
lock (l) {
if (value.Length > longest.Length) {
longest = value;
Console.WriteLine(longest.Length + " : " + longest);
}
}
}
}
private static IEnumerable<uint> Valid32BitStrings(ushort[] sChecks, uint[] iChecks) {
var u16Strings = Valid16BitStrings(sChecks);
var hu16Strings = u16Strings.Select(b => (uint) b << 16).TakeWhile(b => b <= int.MaxValue).ToArray();
uint[] testForce32 = new uint[] {
0x2082083F, // if a string masked by this ...
0x218A4A30,
0x10C52518,
0x0862928C,
0x04314946,
0x0218A4A3,
0x81031519,
0x81230C4A,
0x40918625,
0x8512450C,
0x42892286,
0x21449143
};
uint[] checkForce32 = new uint[] {
0x0000001F, // ... equals this, the next bit in the progression identified here
0x01084210, // cannot be either 0 or 1
0x00842108,
0x00421084,
0x00210842,
0x00108421,
0x81020408,
0x81020408,
0x40810204,
0x81020408,
0x40810204,
0x20408102
};
foreach (var high in hu16Strings) {
foreach (var low in u16Strings) {
var b = high + low;
var nb = ~b;
bool g = true;
foreach (var check in iChecks) {
if ((b & check) == check) {
g = false;
break;
}
if ((nb & check) == check) {
g = false;
break;
}
}
if (g) {
for (int i = 0; i < testForce32.Length; i++) {
if ((b & testForce32[i]) == checkForce32[i])
{
g = false;
break;
}
if ((nb & testForce32[i]) == checkForce32[i])
{
g = false;
break;
}
}
}
if (g) {
// these sequences prevent one of the next 6 bits from being either 0 or 1
yield return b;
}
}
}
}
private static ushort[] Valid16BitStrings(ushort[] sChecks) {
List<ushort> good = new List<ushort>();
for (ushort b = 0; b < ushort.MaxValue; b++) {
bool g = true;
var nb = ~b;
foreach (var check1 in sChecks) {
if ((b & check1) == check1) {
g = false;
break;
}
if ((nb & check1) == check1) {
g = false;
break;
}
}
if (g) {
good.Add(b);
if (good.Count % 10 == 0) Console.WriteLine("{0}, {1:x}", good.Count, b);
}
}
Console.WriteLine(good.Count);
return good.ToArray();
}
private static uint[][] GetMultipleQuadChecks(BigInteger[] checks, int i) {
// checks larger than uint.MaxValue are initially stored in BigInteger values and we need them in uint[] arrays
// BigInteger provides a method that returns the underlying bytes but they are in the wrong order if we
// simply reinterpreted the array... given a big endian BigInteger stored like this:
// hgfedcba87654321
// we need this (little endian):
// 12345678abcdefgh
// ToByteArray returns this:
// 87654321hgfedcba
// (each byte is big endian, byte array is little endian)
List<uint[]> lchecks = new List<uint[]>();
for (; i < checks.Length; i++) {
var bytes = checks[i].ToByteArray();
if (bytes.Length < 5) {
throw new Exception("program failure; int check discovered where longer check expected");
}
var s = new List<uint>();
for (int j = 0; j < bytes.Length; j += 4) {
uint u1 = j + 3 < bytes.Length ? ReverseBits(bytes[j + 3]) : 0;
uint u2 = j + 2 < bytes.Length ? ReverseBits(bytes[j + 2]) << 8 : 0;
uint u3 = j + 1 < bytes.Length ? ReverseBits(bytes[j + 1]) << 16 : 0;
uint u4 = ReverseBits(bytes[j]) << 24;
s.Add(u1 + u2 + u3 + u4);
}
if (s[s.Count - 1] == 0) {
// remove the extra sign byte that occurs if bytes[bytes.Length-1]>128 && bytes.Length % 4 = 1
s.RemoveAt(s.Count - 1);
}
// any bitmask that fits inside a single uint is unnecessary because such a result wouldn't be returned from Valid32BitStrings
if (s.Where(s1 => s1 != 0).Take(2).Count() == 1) continue;
lchecks.Add(s.ToArray());
}
var multipleQuadChecks = lchecks.ToArray();
return multipleQuadChecks;
}
static uint ReverseBits(byte a) {
return (uint) (((a & 0x1) << 7) | ((a & 0x2) << 5) |
((a & 0x4) << 3) | ((a & 0x8) << 1) |
((a & 0x10) >> 1) | ((a & 0x20) >> 3) |
((a & 0x40) >> 5) | ((a & 0x80) >> 7));
}
private static uint[] GetIntChecks(BigInteger[] checks, ref int i) {
List<uint> iChecks = new List<uint>();
while (checks[i] < uint.MaxValue) {
var item = (uint) checks[i];
if ((item & ushort.MaxValue) != 0) {
//we only care about the ones with low bits set (if no low bits are set, the high bits were checked already)
iChecks.Add(item);
}
i++;
}
return iChecks.ToArray();
}
private static ushort[] GetShortChecks(BigInteger[] checks, out int i) {
i = 0;
List<ushort> sChecks = new List<ushort>();
while (checks[i] < ushort.MaxValue) {
sChecks.Add((ushort) checks[i]);
i++;
}
return sChecks.ToArray();
}
static IEnumerable<BigInteger> GenerateChecks() {
BigInteger max = BigInteger.Pow(2, 1134);
//n ^ 5 + n ^ 4 + n ^ 3 + n ^ 2 + n + 1
BigInteger n = 2;
do {
var n2 = n * n;
var n3 = n2 * n;
var n4 = n3 * n;
var n5 = n4 * n;
if (n5 > max) yield break;
var check = n5 + n4 + n3 + n2 + n + 1;
while (check < max) {
yield return check;
check <<= 1;
}
n <<= 1;
} while (true);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment