OKlibrary  0.2.1.6
PrimeNumbers.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 20.9.2008 (Swansea) */
00002 /* Copyright 2008, 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/NumberTheory/Lisp/PrimeNumbers.mac")$
00024 
00025 kill(f)$
00026 
00027 /* **********************************
00028    * Finding and enumerating primes *
00029    **********************************
00030 */
00031 
00032 okltest_primes_interval(f) := (
00033   assert(f(0,0) = []),
00034   assert(f(0,1) = []),
00035   assert(f(3,2) = []),
00036   assert(f(2,-1) = []),
00037   assert(f(-10,2) = [2]),
00038   assert(f(2,2) = [2]),
00039   assert(f(2,10) = [2,3,5,7]),
00040   block([L : f(1,1000)],
00041     assert(length(f(1,1000)) = 168),
00042     assert(L[31] = 127)
00043   ),
00044   true)$
00045 
00046 okltest_primes_first(f) := (
00047   assert(f(0) = []),
00048   assert(f(-1) = []),
00049   assert(f(1) = [2]),
00050   assert(f(2) = [2,3]),
00051   assert(f(5) = [2,3,5,7,11]),
00052   assert(length(f(66)) = 66),
00053   true)$
00054 
00055 okltest_unrank_primes(f) := (
00056   assert(f(1) = 2),
00057   assert(create_list(f(i),i,1,20) = primes_first(20)),
00058   true)$
00059 
00060 okltest_rank_primes(f) := (
00061   assert(f(2) = 1),
00062   for n : 1 thru 20 do
00063     assert(f(unrank_primes(n)) = n),
00064   true)$
00065 
00066 okltest_count_primes(f) := (
00067   assert(f(0) = 0),
00068   assert(f(inf) = inf),
00069   assert(f(1) = 0),
00070   assert(f(2) = 1),
00071   assert(f(3) = 2),
00072   assert(f(4) = 2),
00073   assert(f(5) = 3),
00074   assert(f(6) = 3),
00075   assert(f(7) = 4),
00076   assert(f(8) = 4),
00077   assert(f(9) = 4),
00078   assert(f(10) = 4),
00079   assert(f(11) = 5),
00080   true)$
00081 
00082 okltest_product_primes(f) := (
00083   assert(f(0) = 1),
00084   assert(f(1) = 1),
00085   assert(f(2) = 2),
00086   assert(f(3) = 6),
00087   assert(f(4) = 6),
00088   assert(f(5) = 30),
00089   assert(f(6) = 30),
00090   assert(f(7) = 210),
00091   assert(f(8) = 210),
00092   assert(f(9) = 210),
00093   true)$
00094 
00095 
00096 /* **********************************
00097    * The Prime Number Theorem (PNT) *
00098    **********************************
00099 */
00100 
00101 okltest_Li(f) := (
00102   assert(f(0) = 0),
00103   /* XXX */
00104   true)$
00105 
00106 okltest_count_primes_int_0(f) := (
00107   assert(f(0) = [0,0]),
00108   assert(f(1) = [0,0]),
00109   assert(f(2) = [1,1]),
00110   assert(f(3) = [2,2]),
00111   assert(f(4) = [2,2]),
00112   assert(f(5) = [5/log(5)*log(2), 2*5/log(5)]),
00113   true)$
00114 
00115 okltest_max_quotient_riemann_error(f) := block(
00116   assert(f(2,1) = [minf, undef]),
00117   assert(f(2,2) = [float((Li(2)-1)/(sqrt(2)*log(2))),2]),
00118   if oklib_test_level=0 then return(true),
00119   assert(f(2000,3000) = [float((Li(2656)-383)/(sqrt(2656)*log(2656))),2656]),
00120   true)$
00121 
00122 okltest_count_primes_int_riemann(f) := (
00123   assert(f(0) = [0,0]),
00124   assert(f(1) = [0,0]),
00125   assert(f(2) = [1,1]),
00126   assert(f(3) = [2,2]),
00127   assert(f(4) = [2,2]),
00128   assert(f(2656) = [383,383]),
00129   assert(f(2657) = block([d:1/8/%pi*sqrt(2657)*log(2657)], Li(2657) +[-d,d])),
00130   true)$
00131 
00132 
00133 /* **************************
00134    * Additive number theory *
00135    **************************
00136 */
00137 
00138 okltest_n_arithprog_primes_nc(f) := (
00139   assert(f[0,1] = 0),
00140   assert(f[0,2] = 0),
00141   assert(f[1,1] = 1),
00142   assert(f[1,2] = 1),
00143   assert(f[1,3] = 1),
00144   assert(f[2,1] = 0),
00145   assert(f[2,2] = 1),
00146   assert(f[2,3] = 2),
00147   assert(f[3,1] = 0),
00148   assert(f[3,2] = 0),
00149   assert(f[3,3] = 0),
00150   assert(f[3,4] = 1),
00151   assert(f[3,5] = 1),
00152   assert(f[3,6] = 0),
00153   assert(f[3,7] = 1),
00154   assert(f[3,20] = 4),
00155   for n : 1 thru 8 do
00156     assert(f[4,n] = 0),
00157   assert(f[4,9] = 1),
00158   /* XXX */
00159   true)$
00160 
00161 okltest_n_arithprog_primes_c(f) := (
00162   assert(f(3,1) = 0),
00163   assert(f(3,2) = 0),
00164   assert(f(3,3) = 0),
00165   assert(f(3,4) = 1),
00166   assert(f(3,5) = 2),
00167   /* XXX */
00168   true)$
00169 
00170 okltest_ln_arithprog_primes_c(f) := (
00171   for p : 0 thru 2 do
00172     for n : 0 thru 10 do
00173       assert(f(p,n) = create_list(binomial(i,p),i,1,n)),
00174   assert(f(3,20) = [0,0,0,1,2,2,3,5,7,9,11,11,13,16,17,20,23,24,26,30]),
00175   true)$
00176 
00177 okltest_first_arithprog_primes(f) := (
00178   assert(f(0) = 0),
00179   assert(f(1) = 1),
00180   assert(f(2) = 2),
00181   assert(f(3) = 4),
00182   assert(f(4) = 9),
00183   assert(f(5) = 10),
00184   true)$
00185 
00186 /* *****************
00187    * Prime factors *
00188    *****************
00189 */
00190 
00191 okltest_expfact(f) := (
00192   assert(f(1,2) = 0),
00193   assert(f(-1,-2) = 0),
00194   for e : 1 thru 4 do
00195     for p : 2 thru 6 do (
00196       assert(f(p^e,p) = e),
00197       assert(f(p^e-1,p) = 0)
00198     ),
00199   true)$
00200