http://www.vdwnumbers.org/vdwnumbers/index.php
About Van Der Waerden Numbers
Van Der Waerden Numbers is a research project that uses Internet-connected computers to find better lower bounds for these numbers. You can participate by downloading and running a free program that runs on your computer when you're not using it. To participate, Download and run BOINC, and add Project 'vdwnumbers.org/vdwnumbers/'. It only works with Windows computers (without Avast) and with Linux computers. You can also Read our rules and policies. This is a project of Daniel Monroe, who is a student at Takoma Park Middle School.
Van Der Waerden Numbers
Forum rules
#1 Van Der Waerden Numbers
The best form of help from above is a sniper on the rooftop....
#2 Re: Van Der Waerden Numbers
From project
The sequence of colors BRRBBRRB (where B is blue and R is red) does not have an evenly spaced subsequence of length 3 that are the same color. However, if you add a B to the end, you get BRRBBRRBB, which has the same color blue in positions 1,5, and 9 which are evenly spaced 4 apart. If you add an R to the end, you get BRRBBRRBR, which has R at position 3, 6, and 9. In fact, with only two colors, there is no sequence of length 9 of Bs and Rs that does not have a subsequence of 3 evenly spaced of the same color. Van der Waerden's Theorem states that for any number of colors r and length k, a long enough sequence always has an evenly spaced subsequence of the same color. The smallest length guaranteed to have an evenly spaced subsequence is called the Van Der Waerden Number and is written W(k,r). For example, W(3,2)=9. This project is to find better lower bounds for Van Der Waerden Numbers by finding sequences like BRRBBRRB. See a table of the results so far below.
This is how this program runs.
Take a prime number n(shown in parentheses on the table) and a primitive root of that number. For example, let n equal 11. See that W(4,2)-length 4, 2 colors has 11 in parentheses. Let's use the primitive root 2. 2 is a primitive root of 11 because its powers up to 2^10
[2,4,8,16,32,64,128,256,512,1024] modulo 11(the remainder when dividing by 11) equal
[2,4,8,5,10,9,7,3,6,1] and that ends with a one. Now we choose a number of colors. Let's choose 2. We color this set:
[2,4,8,5,10,9,7,3,6,1] with the pattern red(bold), blue(not bold), red, blue...and get [2,4,8,5,10,9,7,3,6,1].
Now all we have to do is reorder this is sequence, getting us [1,2,3,4,5,6,7,8,9,10]. It is proven that we can add the color 11, which should be blue (not bold). It is also proven that we can concatenate 3 more copies of this 11-term sequence while avoiding 4 evenly spaced of the same color. It is also proven we can add a 34th term, so we will. We have just found that W(4,2)-subsequence length 4, 2 colors equals 35. Note it does not equal 34 because this table shows the minimum length that guarantees an evenly spaced sequence of the same color, not the maximum length that can be reached without an evenly spaced sequence of the same color.
The sequence of colors BRRBBRRB (where B is blue and R is red) does not have an evenly spaced subsequence of length 3 that are the same color. However, if you add a B to the end, you get BRRBBRRBB, which has the same color blue in positions 1,5, and 9 which are evenly spaced 4 apart. If you add an R to the end, you get BRRBBRRBR, which has R at position 3, 6, and 9. In fact, with only two colors, there is no sequence of length 9 of Bs and Rs that does not have a subsequence of 3 evenly spaced of the same color. Van der Waerden's Theorem states that for any number of colors r and length k, a long enough sequence always has an evenly spaced subsequence of the same color. The smallest length guaranteed to have an evenly spaced subsequence is called the Van Der Waerden Number and is written W(k,r). For example, W(3,2)=9. This project is to find better lower bounds for Van Der Waerden Numbers by finding sequences like BRRBBRRB. See a table of the results so far below.
This is how this program runs.
Take a prime number n(shown in parentheses on the table) and a primitive root of that number. For example, let n equal 11. See that W(4,2)-length 4, 2 colors has 11 in parentheses. Let's use the primitive root 2. 2 is a primitive root of 11 because its powers up to 2^10
[2,4,8,16,32,64,128,256,512,1024] modulo 11(the remainder when dividing by 11) equal
[2,4,8,5,10,9,7,3,6,1] and that ends with a one. Now we choose a number of colors. Let's choose 2. We color this set:
[2,4,8,5,10,9,7,3,6,1] with the pattern red(bold), blue(not bold), red, blue...and get [2,4,8,5,10,9,7,3,6,1].
Now all we have to do is reorder this is sequence, getting us [1,2,3,4,5,6,7,8,9,10]. It is proven that we can add the color 11, which should be blue (not bold). It is also proven that we can concatenate 3 more copies of this 11-term sequence while avoiding 4 evenly spaced of the same color. It is also proven we can add a 34th term, so we will. We have just found that W(4,2)-subsequence length 4, 2 colors equals 35. Note it does not equal 34 because this table shows the minimum length that guarantees an evenly spaced sequence of the same color, not the maximum length that can be reached without an evenly spaced sequence of the same color.
The best form of help from above is a sniper on the rooftop....
- Janos (retired)
- Still a Newbie
- Posts: 1919
- Joined: Thu Feb 23, 2012 8:58 am
- Location: Aberdeenshire, Scotland
#3 Re: Van Der Waerden Numbers
I've connected... will report how the project runs...
"Happiness can be defined as: a geek with non-work related code to write, no distractions and no deadline." - Janos
#4 Re: Van Der Waerden Numbers
I've got it running. Most units seem to last 5 mins or so on an i5 laptop. Bit hit or miss about errors, will be able to tell better once my number of validates outstanding drops.
The best form of help from above is a sniper on the rooftop....
#5 Re: Van Der Waerden Numbers
Time crunched is now being updated on my WUProp account and stats showing up on free DC
http://stats.free-dc.org/stats.php?page ... dw&team=26
http://stats.free-dc.org/stats.php?page ... dw&team=26
The best form of help from above is a sniper on the rooftop....
#6 Re: Van Der Waerden Numbers
From testing seems win 7 32 or 64 bit is fine, win xp 32 bit constantly fails and Linux never validates against win which is a bust for Linux systems so far as the majority on the project is win.
Error rate for me seems to be 55 % good 45% fail but I have a lot of pendings which should change that ratio significantly.
Almost tempted to move project from new to it's own forum but will give it a few days or till I get my confirmed flights for deepest, darkest.
Janos seems to be doing well on it as he has flown off into the distance credit wise.
Error rate for me seems to be 55 % good 45% fail but I have a lot of pendings which should change that ratio significantly.
Almost tempted to move project from new to it's own forum but will give it a few days or till I get my confirmed flights for deepest, darkest.
Janos seems to be doing well on it as he has flown off into the distance credit wise.
The best form of help from above is a sniper on the rooftop....
- Janos (retired)
- Still a Newbie
- Posts: 1919
- Joined: Thu Feb 23, 2012 8:58 am
- Location: Aberdeenshire, Scotland
#7 Re: Van Der Waerden Numbers
Agreed, Linux is a bust - I've got loads of errors so I've stopped work on Linux OS machines.
"Happiness can be defined as: a geek with non-work related code to write, no distractions and no deadline." - Janos
#8 Re: Van Der Waerden Numbers
New version released today. Hopefully will curb the high error rates that have been occurring since the last version.
The best form of help from above is a sniper on the rooftop....