OKlibrary  0.2.1.6
PdNumbers.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 12.2.2011 (Swansea) */
00002 /* Copyright 2011 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/RamseyTheory/Lisp/VanderWaerden/Numbers.mac");
00023 
00024 /* ***************************************
00025    * Palindromic van der Waerden numbers *
00026    ***************************************
00027 */
00028 
00029 /* The main function, which handles all parameter-values (gathering all
00030    knowledge from all our sources). */
00031 /* Prerequisites: L ascendingly sorted list of natural numbers >= 1 */
00032 pdvanderwaerden(L) := if emptyp(L) then 1
00033  elseif first(L) = 1 then pdvanderwaerden(rest(L))
00034  elseif length(L) >= 2 and first(L)=2 and second(L)=2 then pdvanderwaerden(rest(L))
00035  elseif pdvanderwaerdend_a(L)#[] then apply(pdvanderwaerdend,pdvanderwaerdend_a(L))
00036  elseif pdvanderwaerden2k_a(L)#[] then apply(pdvanderwaerden2k,pdvanderwaerden2k_a(L))
00037  elseif pdvanderwaerden3k_a(L)#[] then apply(pdvanderwaerden3k,pdvanderwaerden3k_a(L))
00038  elseif pdvanderwaerden4k_a(L)#[] then apply(pdvanderwaerden4k,pdvanderwaerden4k_a(L))
00039  elseif pdvanderwaerden5k_a(L)#[] then apply(pdvanderwaerden5k,pdvanderwaerden5k_a(L))
00040  elseif pdvanderwaerden6k_a(L)#[] then apply(pdvanderwaerden6k,pdvanderwaerden6k_a(L))
00041  elseif pdvanderwaerden7k_a(L)#[] then apply(pdvanderwaerden7k,pdvanderwaerden7k_a(L))
00042  else unknown$
00043 
00044 /* Checking whether L is a valid input: */
00045 pdvanderwaerden_p(L) := vanderwaerden_p(L)$
00046 
00047 
00048 /* ****************
00049    * Binary cases *
00050    ****************
00051 */
00052 
00053 pdvanderwaerden2k(k) := if oddp(k) then [k,2*k] else [k-1,2*(k-1)]$
00054 pdvanderwaerden2k_a(L) := if length(L)#2 then [] else
00055  block([S : setify(L)],
00056   if elementp(2,S) then
00057     if length(S)=1 then [2] else [first(listify(disjoin(2,S)))]
00058   else [])$
00059 
00060 pdvanderwaerden3k(k) := 
00061  if k <= 39 then [
00062   [2,3],[3,6],[6,9],[15,16],[16,21],[30,31],[41,44],[52,57],[62,77],[93,94],
00063   [110,113],[126,135],[142,155],[174,183],[200,205],[232,237],[256,279],[299,312],[338,347],[380,389],
00064   [400,405],[444,463],[506,507],[568,593],[586,607],[634,643],[664,699],[[728,inf-1],[743,inf-1]],[[810,inf-1],[821,inf-1]],[[844,inf-1],[855,inf-1]],
00065   [[916,inf-1],[931,inf-1]],[[958,inf-1],[963,inf-1]],[[996,inf-1],[1005,inf-1]],[[1054,inf-1],[1081,inf-1]],[[1114,inf-1],[1155,inf-1]],[[1186,inf-1],[1213,inf-1]],[[1272,inf-1],[1295,inf-1]],[[1336,inf-1],[1369,inf-1]],[[1406,inf-1],[1411,inf-1]]
00066  ][k]
00067  else unknown$
00068 pdvanderwaerden3k_a(L) := vanderwaerden3k_a(L)$
00069 
00070 
00071 pdvanderwaerden4k(k) := 
00072  if k <= 17 then [
00073   [3,4],[3,6],[15,16],[24,25],[34,55],[62,65],[101,106],[126,129],[300,309],[320,329],
00074   [343,348],[387,394],[[519,inf-1],[538,inf-1]],[[617,inf-1],[682,inf-1]],[[724,inf-1],[727,inf-1]],[[824,inf-1],[839,inf-1]],[[855,inf-1],[1076,inf-1]]
00075  ][k]
00076  else unknown$
00077 pdvanderwaerden4k_a(L) := vanderwaerden4k_a(L)$
00078 
00079 pdvanderwaerden5k(k) := 
00080  if k <= 13 then [
00081   [4,5],[5,10],[16,21],[34,55],[150,177],[195,206],[227,236],[312,323],[[446,inf-1],[473,inf-1]],[[595,inf-1],[612,inf-1]],
00082   [[748,inf-1],[767,inf-1]],[[950,inf-1],[963,inf-1]],[[1176,inf-1],[1205,inf-1]]
00083  ][k]
00084  else unknown$
00085 pdvanderwaerden5k_a(L) := vanderwaerden5k_a(L)$
00086 
00087 pdvanderwaerden6k(k) := 
00088  if k <= 9 then [
00089   [5,6],[5,10],[30,31],[62,65],[195,206],[567,1132],[[591,inf-1],[1156,inf-1]],[[655,inf-1],[1168,inf-1]],[[943,inf-1],[1382,inf-1]]
00090  ][k]
00091  else unknown$
00092 pdvanderwaerden6k_a(L) := vanderwaerden6k_a(L)$
00093 
00094 pdvanderwaerden7k(k) := 
00095  if k <= 7 then [
00096   [6,7],[7,14],[41,44],[101,106],[227,236],[[591,inf-1],[1156,inf-1]],[[1544,inf-1],[1547,inf-1]]
00097  ][k]
00098  else unknown$
00099 pdvanderwaerden7k_a(L) := vanderwaerden7k_a(L)$
00100 
00101 
00102 /* *********************
00103    * The diagonal case *
00104    *********************
00105 */
00106 
00107 /* The "diagonal case", i.e., m parts, arithmetic progressions of length k: */
00108 pdvanderwaerdend(m,k) := if m=0 then [0,1]
00109  elseif m=1 then [k-1,k]
00110  elseif k=1 then [0,1]
00111  elseif k=2 then [1,2]
00112  elseif m=2 then pdvanderwaerdend2(k)
00113  else unknown$
00114 /* pdvanderwaerdend(m,k) = pdvanderwaerden(create_list(k,i,1,m)) */
00115 pdvanderwaerdend_a(L) := vanderwaerdend_a(L)$
00116 
00117 /* The diagonal cases with two parts: */
00118 pdvanderwaerdend2(k) :=
00119  if k <= 7 then [
00120   [0,1],[1,2],[6,9],[24,25],[150,177],[567,1132],[[1544,inf-1],[1547,inf-1]]
00121  ][k]
00122  else unknown$
00123 pdvanderwaerdend2_a(L) := vanderwaerdend2_a(L)$
00124 
00125 
00126 /* ****************************
00127    * Palindromic span and gap *
00128    ****************************
00129 */
00130 
00131 pd_span(L) := block([p : pdvanderwaerden(L)], 
00132  if p=unknown then unknown else p[2] - p[1])$
00133 pd_gap(L) := block([v : vanderwaerden(L), p : pdvanderwaerden(L)],
00134  if v=unknown and p=unknown then unknown else v - p[2])$
00135 
00136