Van Der Waerden Numbers
log in

User of the day

User profile Profile x3mEn
I was in the wrong place at the wrong time For the wrong reason and the wrong rhyme On the wrong day of the wrong week I used the wrong method with...

Background

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 B 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.

Here is how the program works. 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) are all distinct and equal [2,4,8,5,10,9,7,3,6,1] which we color red, blue, red, blue. Now all we have to do is reorder this is sequence, getting us [1,2,3,4,5,6,7,8,9,10]. We can add the color 11, which should be blue. Rabung proved that under certain conditions we can concatenate 3 more copies of this 11-term sequence while avoiding 4 evenly spaced of the same color. We can add a 34th term, so we will. The existence of this sequence of 34 proves that W(4,2) is more than 34.

2 colors3 colors4 colors5 colors6 colors7 colors8 colors9 colors10 colors
Length 39
 
27
 
76
(37)
>170
 
>223
 
>83
(41)
>383
(191)
Length 435
(11)
293
 
>1,048
(349)
>2,254
(751)
>9,778
(3,259)
>5,800
(1,933)
>9,940
(3,313)
>11,128
(3,709)
>28,147
(4,691)Z
Length 5178
(11)ZZ
>2,173
 
>17,705
(2,213)Z
>98,740
 
63,473
(3967)ZZ
>121,973
(30,493)
>223,173
(55,793)
>405,149
(101,287)
>553,805
(138,451)
Length 61,132
(113)Z
>11,191
 
>91,131
(9,133)Z
>540,025
 
>816,981
 
>1,589,846
(317,969)
>2,707,086
(541,417)
>4,304,706
(860,941)
>11,269,856
(2,253,971)
Length 7>3,703
(617)
>48,811
 
>420,217
 
>1,381,687
(230,281)
>7,465,909
(622,159)Z
>16,466,695
(2,744,449)
>35,618,893
(2,968,241)Z
>60,413,155
(10,068,859)
>142,307,167
(23,717,861)
Length 8>11,495
(821)Z
>238,400
(34,057)
>2,388,317
(85,297)ZZ
>10,743,258
(1,534,751)
>57,445,718
(8,206,531)
>119,524,728
(17,074,961)
>428,424,207
(30,601,729)Z
>1,092,421,520
(156,060,217)
>2,190,170,228
(312,881,461)
Length 9>41,265
(2,579)Z
>932,745
(116,593)
>10,898,729
(1,362,341)
>79,706,009
(9,963,251)
>458,062,329
(57,257,791)
>1,271,890,265
(158,986,283)
>3,963,756,873
(495,469,609)
>7,589,163,897
(948,645,487)
Length 10>103,474
(11,497)
>4,173,724
(463,747)
>76,049,218
(8,449,913)
>542,694,970
(60,299,441)
>2,615,305,384
(290,589,487)
>8,485,020,442
(942,780,049)
Length 11>193,941
(9,697)Z
>18,603,731
(1,860,373)
>329,263,781
(16,463,189)Z
>3,046,508,211
(304,650,821)
>9,507,536,891
(950,753,689)
Length 12>638,727
(29,033)Z
>79,134,144
(7,194,013)
>1,536,435,264
(139,675,933)
>10,450,237,172
(950,021,561)
Length 13>1,642,309
(136,859)
>251,282,317
(20,940,193)
>7,211,253,517
(600,937,793)
Length 14>3,118,350
(239,873)
>669,256,082
(51,481,237)
>12,359,121,074
(950,701,621)
Length 15>8,523,047
(608,789)
>2,250,960,279
(160,782,877)
Length 16>16,370,086
(1,091,339)
>9,186,001,216
(612,400,081)
Length 17>46,397,777
(2,899,861)
>15,198,879,857
(949,929,991)
Length 18>91,079,252
(5,357,603)
Length 19>250,546,915
(13,919,273)
Length 20>526,317,462
(27,700,919)
Length 21>1,409,670,741
(70,483,537)
Length 22>2,582,037,634
(122,954,173)
Length 23>6,206,141,987
(282,097,363)
Length 24>10,980,093,212
(477,395,357)
>20,119,944,624
(874,780,201)
Length 25>22,413,799,897
(933,908,329)
This project has begun using the cyclic zipper method with code shared by Rabung and Lotts. Results with the cyclic zipper method are shown above. Z=zipped once, ZZ=zipped twice. > means the actual number is unknown but we know it is more than that number. The numbers in parentheses are the primes we used to find the sequences.



Code and content created by Daniel Monroe © 2016.