OKlibrary  0.2.1.6
Numbers.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 12.4.2009 (Swansea) */
00002 /* Copyright 2009, 2010 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007
00022 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/RamseyTheory/Lisp/VanderWaerden/Numbers.mac")\$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")\$
00025 oklib_include("OKlib/ComputerAlgebra/RamseyTheory/Lisp/Sequences.mac")\$
00026
00027
00028 kill(f)\$
00029
00030
00031 /* ***************************
00032    * Van der Waerden numbers *
00033    ***************************
00034 */
00035
00036 okltest_vanderwaerden(f) := (
00037   assert(f([]) = 1),
00038   for k : 1 thru 5 do
00039     assert(f([k]) = k),
00040   for k : 1 thru 5 do
00041     assert(f([1,k]) = k),
00042   assert(f([2,2]) = 3),
00043   assert(f([3,3]) = 9),
00044   assert(f([4,4]) = 35),
00045   assert(f([5,5]) = 178),
00046   assert(f([6,6]) = 1132),
00047   for k : 1 thru 6 do
00048     assert(f(sort([2,k])) = if oddp(k) then 2*k else 2*k-1),
00049   assert(f([2,2,3]) = 7),
00050   assert(f([3,7]) = 46),
00051   assert(f([4,7]) = 109),
00052   assert(f([4,8]) = 146),
00053   assert(f([5,6]) = 206),
00054   assert(f([2,3,3]) = 14),
00055   assert(f([2,2,3,3]) = 17),
00056   assert(f([2,2,2,3,3]) = 20),
00057   assert(f([2,2,2,2,3,3]) = 21),
00058   assert(f([2,2,2,2,2,3,3]) = 24),
00059   assert(f([2,2,2,2,2,2,3,3]) = 25),
00060   assert(f([2,2,2,2,2,2,2,3,3]) = 28),
00061   assert(f([2,3,4]) = 21),
00062   assert(f([2,2,3,4]) = 25),
00063   assert(f([2,2,2,3,4]) = 29),
00064   assert(f([2,2,2,2,3,4]) = 33),
00065   assert(f([2,2,2,2,2,3,4]) = 36),
00066   assert(f([2,3,5]) = 32),
00067   assert(f([2,2,3,5]) = 43),
00068   assert(f([2,2,2,3,5]) = 44),
00069   assert(f([2,2,2,2,3,5]) = 50),
00070   assert(f([2,3,6]) = 40),
00071   assert(f([2,2,3,6]) = 48),
00072   assert(f([2,2,2,3,6]) = 56),
00073   assert(f([2,2,2,2,3,6]) = 60),
00074   assert(f([2,3,7]) = 55),
00075   assert(f([2,2,3,7]) = 65),
00076   assert(f([2,2,2,3,7]) = 72),
00077   assert(f([2,3,8]) = 72),
00078   assert(f([2,2,3,8]) = 83),
00079   assert(f([2,2,2,3,8]) = 88),
00080   assert(f([2,3,9]) = 90),
00081   assert(f([2,2,3,9]) = 99),
00082   assert(f([2,3,10]) = 108),
00083   assert(f([2,2,3,10]) = 119),
00084   assert(f([2,3,11]) = 129),
00085   assert(f([2,3,12]) = 150),
00086   assert(f([2,3,13]) = 171),
00087   assert(f([2,4,4]) = 40),
00088   assert(f([2,2,4,4]) = 53),
00089   assert(f([2,2,2,4,4]) = 54),
00090   assert(f([2,2,2,2,4,4]) = 56),
00091   assert(f([2,4,5]) = 71),
00092   assert(f([2,2,4,5]) = 75),
00093   assert(f([2,2,2,4,5]) = 79),
00094   assert(f([2,4,6]) = 83),
00095   assert(f([2,2,4,6]) = 93),
00096   assert(f([2,4,7]) = 119),
00097   assert(f([2,5,5]) = 180),
00098   assert(f([2,3,3,3]) = 40),
00099   assert(f([2,2,3,3,3]) = 41),
00100   assert(f([2,2,2,3,3,3]) = 42),
00101   assert(f([2,3,3,4]) = 60),
00102   assert(f([2,2,3,3,4]) = 63),
00103   assert(f([2,3,3,5]) = 86),
00104   assert(f([3,3,4]) = 51),
00105   assert(f([3,3,5]) = 80),
00106   assert(f([3,4,4]) = 89),
00107   assert(f([7,7,7]) = [48812,inf-1]),
00108   assert(f([7,7,7,7]) = [420218,inf-1]),
00109   true)\$
00110
00111 okltest_vanderwaerden_p(f) := (
00112   assert(f([]) = true),
00113   assert(f(1) = false),
00114   assert(f({1}) = false),
00115   assert(f([0]) = false),
00116   assert(f([1/2]) = false),
00117   assert(f([1,1]) = true),
00118   assert(f([2,1]) = false),
00119   true)\$
00120
00121
00122 /* ************************
00123    * The transversal case *
00124    ************************
00125 */
00126
00127 okltest_vanderwaerdent_a(f) := (
00128   assert(f([]) = []),
00129   assert(f([1]) = [0,1]),
00130   assert(f([1,2]) = [1,1]),
00131   assert(f([1,2,2]) = [2,1]),
00132   assert(f([1,2,3]) = []),
00133   assert(f([1,2,2,4]) = []),
00134   assert(f([2]) = [0,2]),
00135   assert(f([2,2]) = [1,2]),
00136   assert(f([2,2,2]) = [2,2]),
00137   assert(f([3]) = [0,3]),
00138   assert(f([3,3]) = []),
00139   assert(f([2,3]) = [1,3]),
00140   assert(f([2,3,4]) = []),
00141   assert(f([2,2,3]) = [2,3]),
00142   assert(f([2,2,2,4]) = [3,4]),
00143   true)\$
00144
00145
00146 /* *******************************************************
00147    * The formula from [Landman, Robertson, Culver, 2005] *
00148    *******************************************************
00149 */
00150
00151 okltest_lrc_j(f) := (
00152   for k : 1 thru 5 do
00153     assert(f(1,k) = 0),
00154   for r : 1 thru 5 do
00155     assert(f(r,1) = 0),
00156   true)\$
00157
00158 okltest_lrc_l0p(f) := (
00159   for k : 1 thru 5 do
00160     assert(f(1,k) = true),
00161   for r : 1 thru 5 do
00162     assert(f(r,1) = if r = 1 then true else false)
00163   )\$
00164
00165 okltest_lrc_l1p(f) := (
00166   for k : 1 thru 5 do
00167     assert(f(1,k) = true),
00168   for r : 1 thru 5 do
00169     assert(f(r,1) = if r <= 2 then true else false)
00170   )\$
00171
00172
00173 /* ********************************
00174    * Generalised transversal case *
00175    ********************************
00176 */
00177
00178 okltest_vanderwaerdents_a(f) := block([a,b],
00179   assert(f([]) = []),
00180   assert(f([1]) = []),
00181   assert(f([2]) = []),
00182   assert(f([2,3]) = []),
00183   assert(f([a]) = []),
00184   assert(f([a,b]) = []),
00185   assert(f([2,2,2]) = []),
00186   assert(f([a,b,2]) = []),
00187   assert(f([2,2,3]) = []),
00188   assert(f([2,2,a]) = []),
00189   assert(f([3,3,3]) = []),
00190   assert(f([2,2,3]) = []),
00191   assert(f([2,3,3]) = [1,[3],3]),
00192   assert(f([2,2,3,3,3]) = [2,[3,3],3]),
00193   assert(f([2,2,2,3,4,5]) = [3,[3,4],5]),
00194   assert(f([2,2,3,4,4]) = [2,[3,4],4]),
00195   true)\$
00196
00197
00198 /* ******************************************************************
00199    * Transversal numbers of hypergraphs of arithmetic progresssions *
00200    ******************************************************************
00201 */
00202
00203 okltest_alpha_steplist_arithprog_seq(f) := (
00204   assert(prefix_p(rest(transform_threshold_l(f[3])), alphal_arithprog(3)) = true),
00205   true)\$
00206
00207
00208 /* *********************************
00209    * Analysing transversal numbers *
00210    *********************************
00211 */
00212
00213 okltest_alpha_arithprog(f) := (
00214   for n : 1 thru 6 do
00215     assert(f(1,n) = 0),
00216   for n : 1 thru 6 do
00217     assert(f(2,n) = 1),
00218   assert(f(3,1) = 1),
00219   assert(f(3,2) = 2),
00220   assert(f(3,3) = 2),
00221   assert(f(3,4) = 3),
00222   assert(f(3,5) = 4),
00223   assert(f(3,6) = 4),
00224   true)\$
00225
00226 okltest_alphal_arithprog(f) := (
00227   assert(take_l(6,f(3)) = [1,2,2,3,4,4]),
00228   assert(take_l(51,f(4)) = [
00229    1,2,3,3,4,5,5,6,7,8,
00230    8,8,9,9,10,10,11,11,12,12,
00231    13,13,14,14,15,15,16,17,17,18,
00232    18,18,19,20,20,20,21,21,21,22,
00233    22,22,23,23,24,24,24,25,25,26,
00234    26]), /* A003003 */
00235   assert(take_l(50,f(5)) = [
00236    1,2,3,4,4,5,6,7,8,8,
00237    9,10,11,12,12,13,14,15,16,16,
00238    16,16,16,17,18,18,19,20,21,21,
00239    22,22,23,24,24,25,26,27,28,28,
00240    29,30,31,32,32,32,32,32,33,33]), /* A003004 */
00241   true)\$
00242
00243 okltest_bestgamma_vdWt(f) := block([R],
00244   if oklib_test_level = 0 then return(true),
00245   R : f(),
00246   assert(first(R) = [3,15/7]),
00247   /* XXX */
00248   true)\$
00249
00250 okltest_condition_kl_vdWt(f) := block([R],
00251   if oklib_test_level = 0 then return(true),
00252   R : f(),
00253   assert(take_elements(2,R) = [[3,false],[4,true]]),
00254   /* XXX */
00255   true)\$
00256
00257
00258 /* ****************************************
00259    * Checking the consistency of the data *
00260    ****************************************
00261 */
00262
00263 /* Checking whether from the initial sequence of vdW-transversal-numbers
00264    one obtains back the initial sequence of transversal numbers of
00265    vdW-hypergraphs.
00266 */
00267 okltest_consistency_check_1() := (
00268   for k : 3 thru exactk_tau_arithprog do block(
00269    [T : tau_arithprog_seq[k], l],
00270     /* First cutting off final values where no increase occurs anymore: */
00271     l : last(T),
00272     T : take_l(find_first_l(lambda([x],is(x=l)),T),T),
00273     /* Adding the initial value for n=0: */
00274     T : cons(0,T),
00275     assert(transform_threshold_l(initial_sequence_vdWt(k)) = T)
00276   ),
00277   true)\$
00278
```