Lower And Upper Bound Divisor Function

Upper and Lower Bounds for the Divisor Function © W. F. Esterhuyse*

May 2009

ABSTRACT We prove a method for finding lower bounds for the divisor function:

σ

0

(n). The method does not involve explicit computation using the

double sum, therefore not requiring computation of many values of cos (2π q) for q a rational number. The lower bounds found are beter than the trivial case and the formula can be extended to get progresivley tighter bounds. Getting lower bounds for the divisor function means getting upper bounds for the prime counting function. The formulas do give exact counts of composites smaller than a finite number. * email: [email protected]

CONTENTS: 1. Upper Bounds 2. Lower Bounds (direct counting) 3. Upper Bound for Prime Counting Function Bibliography

1. Upper Bounds We start with the result from ref. [3] for computing the divisor function σ 0(n) = d (n): d(n) = n

∑

µ

µ ^(-1) ∑ cos(2π *ν *n/µ ). µ =1 ν =1

(1)

The integral corresponding to this does not give a tight enough upper bound, however the proof is long and is omitted. The method we use indstead depends on finding the smallest number of form m! and larger than n in d(n). Since the set of numbers of form m! is sparse we need aditional theorems to get a tighter bound, by finding a suitable number closer to n and of the required form. The bound: d(n) <= 2√n

(2)

may be used (it may be tighter or not than our main method depeding on n). This follows from the rule that we only have to divide by numbers < √n to get 1/2 of the whole set of the divisors. The main results follow. We use "kCm" for k combinations of m. 1.1 Lemma If n is of form m! we have that: d(n) = d(m!) = 1Cm +2C(m-1) + 3C(m-1) + ... + (m-2)C(m-1) + 1 = f (m)

(3)

Proof: A number of form m! is factorised as: 1*2*3*...*m The first term counts the amount of factors. The second term counts a pairwise reordering except pairs including 1 i.e. 2C(m-1), the third term counts a triple reordering except triples including 1 because including 1 is equivalent to reordering

of piars. This reasoning continues untill (m-1)C(m-1) = 1.

 Set mn = min { m in IN : n < m! }. 1.2 Theorem We have: d(n) <= 1C(mn) + 2C(mn - 1) + ... + (mn - 2)C(mn - 1) + 1 = f (mn). Proof: By Lemma 1.1 and since n < m! and numbers of form m! have the maximum amount of divisors for numbers smaller than m!.

 Since in general we need to find a number closer to n than m! in order to get a tighter bound the following theorems is usefull. 1.3 Theorem If 1 < m <= k then d(k!/m) <= f (k - 1). Proof: Division by m is equivalent to deleting m form the string: 1*2*3*...*k which reduces the set to count combinations of by one.

 Notation: vj for all i <> j <= k then d(m! /v1*v2*...*vk) <= f (n - k) Proof: By theorem 1.3 and induction on k.



Given a number n using theorem 1.4 we can get closer to our target by finding the mn and then dividing by an appropriate combination of divisors. If n is large and close to and larger than m!/2 say then it is too far from m! and we may see if (m+1)!/2 is smaller.

2. Lower Bounds (direct counting) Set T = {n ∈ IN : n = 5 (mod 6)}, S = {n ∈ IN : n = 1 (mod 6)}. Set (the division submatrix with columns in T and rows in T ∪ S) = A. Set CN = (the amount of compisites <= N). Set

n}|

[a] = |{n ∈ T : a | n}| and with continuation: [a, b, c,...] = |{n ∈ T : a and b and c and ... | for some constants a, b , c etc. All references to composites and primes in this chapter

will refer to composites and primes in T or S. Set the amount of composites divisable by a or b or c or ... = [[a,b,c, ... ]], where we do not count any composite more than once if divisable by more than one of a,b,c, .... Set [[a,b,c, ... ]]N,T = |{n ∈ T : a or b or c or ... | n, n <= N}|, [[a,b,c, ... ]]N,S = |{n ∈ S : a or b or c or ... | n, n <= N}| and [[a,b,c, ... ]]N = |{n ∈ T or S: a or b or c or ... | n, n <= N}| with similar notation for [...]. We use first the division submatrix A, and find a way to compute formulas for the amount of composites in T. Note that we may obtain an upper bound for primes in T from a lower bound of composites in T since they are complement sets. We count all the numbers divisable by 5 or 7 and get our ( first lower bound for CN ) = B1 CN as follows: B1 CN = [5]N + [7]N - [5,7]N

(1)

or CN ≥ [5] + [7] - [5,7] and term three (t3) is because we counted twice (using [5] + [7]) if both 5 and 7 divides n.

RHS of (1) counts composites for N < 11*13 exactly and C11*13 + k >= [[5,7]] since the composite 11*13 cannot be counted by (1) (see matrix A). We set for convenience: g1 = B1 CN. We will need an evolvable binary operator: Km where m ∈ IN which we call a "formula combination operator" and is used to combine formulas, and the level of evolvement is specified by m. This operator is defined as evolving eventually to "plus". This operator behaves as will be illustrated next. We illustrate it's behaviour for this start value (g1) and state it in general in method 1.3, in order for the reader to get a feel of it first. We count exactly like in case of (1) the amount of numbers divisable by 7 or 11 as follows: g2 = [7] + [11] - [7,11].

(2)

Now our operator comes into play: we need to combine formula (1) and (2), i.e. B2 CN = g1 Km g2

(3)

such that B2 CN counts [[5,7,11]]N exactly. There exists a number m such that Km evolves to "plus" (by definition). Where the index on Km will be explained. We write out (3): B2 CN = [5]N + [7]N - [5,7]N K1 [7]N + [11]N - [7,11]N

(4)

and since Km is a formula operator we know that it operates on the entire formulas to it's left and right. We leave out the N subscript and reinsert it at the end of the computation. We know Km must eventually evolve to "plus", since we are counting. We see immediatley that we counted [7] twice in: [5] + [7] - [5,7] + [7] + [11] - [7,11] (the naive "result" of (4)). The m = 1 refers to the amount of numbers in braces in LHS that we are considering. Now (4) changes to:

B2 CN = [5] + [7] - [5,7] K1 [11] - [7,11]

(5)

The operator says we need to consider all singletons in braces in LHS (we haven't considered [5] yet). We do it now. Since we already counted [5] we counted too much by one (by term [11]) just in case 5,11 divides n. Therefore (5) evolves to: B2 CN = [5] + [7] - [5,7] K2 [11] - [5,11] - [7,11]

(6)

And the operator evolved to it's level 2 state (which means we have to consider pairs in braces next). By extension of step form (5) to (6) we need to add a term of m+1 = 2+1 = 3 numbers in braces when considering pairs. The only possible such triple is [5,7,11]. K2 executes as follows. We boldify all pairs that have a number in common with LHS pair and boldify the singleton in RHS: B2 CN = [5] + [7] - [5,7] K2 [11] - [5,11] - [7,11] and assign a nummber (-1) to LHS: B2 CN = [5] + [7] - [5,7] K2 [11] - [5,11] - [7,11] -1 then for every bold term in RHS we add the coefficient of this number to the previous one (left to right order) to get: B2 CN = [5] + [7] - [5,7] K2 [11] - [5,11] - [7,11] -1

0

-1

-2

(9)

where these numbers are not the vlaues (they are computuations based on the assigned number). Then we prove the following: 2.1 Theorem B2 CN = [5]N + [7]N - [5,7]N K2 [11]N - [5,11]N - [7,11]N = [5]N + [7]N - [5,7]N + [11]N - [5,11]N - [7,11]N + a[5,7,11]N = [[5,7,11]]N

(10)

where a = 1 from -2 + a = -1 and -2 is the rightmost and -1 is the leftmost number in (9). For N = 11' * 11'' - 6 = 13*17 - 6. Proof:

We just need all possible configurations of the matrix A involving rows 5, 7 and 11. This is drawn in figure 2.1: (figure 2.1 fits here) Figure 2.1 We call this the characteristic submatrix with respect to divisability by 5, 7, 11. Set [b]c = |{n ∈ T or S : b | n, n in characteristic matrix of A}| with the same extension as for [b]. We proceed to count the terms in (11) in this submatrix. Now [5]c counts the number of 1's in the first row, [7]c counts the amount in row two and counts the cases [5,7]c twice, -[5,7]c corrects this. [11]c counts the amount of 1's in row 11 and counts cases of [5,11]c and [7,11]c too much and the case of [5,7,11]c too much, we thus have: [5]c + [7]c - [5,7]c + [11]c - [5,11]c - [7,11]c + a[5,7,11]c 6 + 4

-2

- 2

+ a(1)

(11)

We get the -2's by analog to [5]c + [7]c - [5,7]c which would have counted as: 4 + 4 - (the amount of columns with 1's occuring in both row 5 and 7) = 4 + 4 - 2, the minus coming from the coefficient of [5,7]c. We determine a from (9) by definition of Km as: leftmost number = rightmost number + a |> -1 = -2 + a |> a = 1. We included the the (1) in (11) which was read off the characteristic matrix (one column occurence of 1's in all three rows). By definition of K2 and the above counting (11) we have: [5]c + [7]c - [5,7]c K2 [11]c - [5,11]c - [7,11]c = [5]c + [7]c - [5,7]c + [11]c - [5,11]c - [7,11]c + [5,7,11]c = 7 (12) and by counting the amount of columns with at least one 1 in it we have: [[5,7,11]]c = 7 which proves the theorem for the characteristic submatrix. This translates directly to the theorem just by dropping the "c" subscript since we may compute every term

(individually) in the full matrix A with columns <= N. The reader need not concern about the spacings or order in the characteristic matrix, any reordering of it column by column would give the same result (one would not count differently). This is easy to see but left to the reader to verify. The value for N follows because 13*17 is the first number divisable by a value larger than 11 above the square root boundary.

 We see that we could have assigned any number to LHS (9). If we assign 0 to LHS then (rightmost number) + a = 0 or a = - (rightmost number). This is the preference we would use in the following. We now define the Km operation in general: 1.3 Method 1. We take Km as non-associative: g1 K m g2 (g1 Km g2) Km g3 ((g1 Km g2) Km g3) Km g4 ... (...((g1 Km g2) Km g3)...) Km gn+1 2. Km instruct us to consider terms with m entries in braces in LHS, m ∈ IN. 3. The two formulas to combine must be such that LHS follows the sequence in item 1 upto the largest n in gn and RHS is the formula gn+1 such that it counts the amount of composites determined form row c, d (for c < d and c,d are adjacent rows in A and and c is the largest entry in LHS) i.e. [[c,d]]. 4. Kn evolves into Kn+1, for some maximum n+1.

5. The operator evolves into "plus" after all terms with upto m (some m) entries have been considered. This max m is equal to the number of entries in the longest term of LHS. 6. RHS of Km+1 takes as formula the RHS of Km for every m ∈ IN plus the terms determined by item 8 below, LHS of Km+1 stays the same as LHS of Km untill the operator evolves into "plus". 7. K1 acts specially on one term (the singleton repeated on both sides) such that it deletes this singleton on RHS and then operates again on the so modified RHS i.e. for example: [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K1 [11] + [13] - [11,13] = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K1 [13] - [11,13] The other singletons occuring in LHS are handled as the trivial case of item 8.4 i.e.: [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K1 [13] - [11,13] 0

1

1

[5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K1 [13] - [11,13] 0

1

1

and note to add: -[5,13] - [7,13] to RHS as K1 evolves to K2 ([11] is already taken care of). Or in general: [a] + [b] + [...,...] + ... + [c] K1 [d] + ... + [...,...] 0

1

... 1

and make a note to add: k = -1, k[a,d] to RHS (on evolution of K1 to K2) and redo item 7 for every singleton (not already handeled) in LHS. 8. For every m >= 2 boldify a single term (say tn) with m entries in LHS 8.1 Boldify the singleton in RHS and every term in RHS having an entry in common with tn.

8.2 Assign the number 0 to the LHS, place it in the next row below the formula to the left of Km. 8.3 Add to the 0 of item 8.2 the coefficient of the first bold term in RHS and write the number below the term (like in the second row of the diagram below). 8.4 Add the coefficient of the following bold term to the number obtained in (8.3 or previous iteration of 8.4) and add 0 if the term is not bold. Write the numbers obtained below the term. Redo 8.4 untill reaching the rightmost term. [] K2 [a] - [a,b] - [c,d] 0 0

1

0

1

0

0

1

0

0

(8.3 combine with 8.4 like in the above diagram just with the underlines deleted and the number strings superimposed). 8.5 When the computation of 8.4 terminates note the k = - (rightmost number) and term to add (as in 8.6) = k[tn, bold singleton in RHS] 8.6 Now the term to add after all terms of m entries has been considered is k[entries of tn , singleton in RHS after item 7] 8.7 List the terms so created and add them to RHS when advancing to m+1. 8.8 Redo 8 untill all terms of length m has been handled. 9. Increase m and redo item 8 untill m reaches the maximum number of entries of LHS and then change Km into "plus" on doing item 8 for the last time. 9. Km evolves fom m = 1 untill we reached a state in which all RHS terms are boldified. End Method. We may choose g1 as [[a,b]] for a and b in adjacent rows of A, not a = 5, b = 7 but then you can't say the result: [[a,b]] Km [b] + [c] - [b,c] counts all the composites in A smaller

than d*e (c, d and e are adjacent rows and c
(15)

We already proved: g1 Km g2 = [[5,7,11]] so we combine these: (g1 Km g2) Km g3 = [[5,7,11]] Km g3.

(14)

Write this out: B3 CN = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] Km [11] + [13] - [11,13]

(15)

For m = 1 we let K1 operate to get: B3 CN = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K2 [13] - [5,13] - [7,13] - [11,13]

(16)

We consider [5,7] in LHS and therefore the compensation for [5,7,13] and do the boldifying, number assigning and computation: B3 CN = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K2 [13] - [5,13] - [7,13] - [11,13] 0

1

0

-1

-1

so: a = 1and this forces addition of 1[5,7,13] on Km evolving from m = 2 to m = 3. We are not done with K2 though: B3 CN = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K2 [13] - [5,13] - [7,13] - [11,13] 0

1

0

0

-1

also giving a = 1, and 1[5,11,13]. One sees that the boldification due to [7,11] will also give

an a = 1 and +[7,11,13] thus: B3 CN = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K3 [13] - [5,13] - [7,13] - [11,13] + [5,7,13] + [5,11,13] + [7,11,13] We consider braces with 3 numbers therefore compensation for [5,7,11,13] and do the boldification, number assignment and computation: B3 CN = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] K3 [13] - [5,13] - [7,13] - [11,13] + [5,7,13] + [5,11,13] + [7,11,13] 0

1

0

-1

-2

-1

0

1

so: a = -1, and we reached our maximum on m therefore K3 evolves into "plus": B3 CN = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] + [13] - [5,13] - [7,13] - [11,13] + [5,7,13] + [5,11,13] + [7,11,13] - [5,7,11,13]

(17)

We prove: 2.2 Theorem [[5,7,11,13]]N = B3 CN. for N = 17*19 - 6. ((g1 Km g2) Km g3 = B3 CN is already shown from the definition above. Proof: We already have (g1 Km g2)N = [[5,7,11]]N. Counting [[5,7,11,13]]N (columns with at least one 1 in it) in the characteristic matrix in figure 2.2 we get: [[5,7,11,13]]c = 15 We count B3 CN like in theorem 2.1 using the characteristic matrix with respect to divisability by 5,7,11,13 (easily obtained from the characteristic matrix of theorem 2.1). This matrix has 1C4 + 2C4 + 3C4 + 1= 15 columns (see figure 2.2). The figure completes the proof: (figure 2.2 fits here). The value for N follows because 17*19 is the first number divisable by a value larger than 13 above the square root boundary.



On the following improvement (division by 17) we have an exact count for all composites < = 17' * 17'' - 6 = 19*23 - 6 = 431, if we can compute the terms exactly (' reads as: sucessor in T ∪ S). Now continuing is mechanical. For (((g1 Km g2) Km g3) Km g4 = B4 CN, we continue by constructing [[13,17]] = g4: [[5,7,11,13]] Km g4 = [[5,7,11,13]] Km [13] + [17] - [13,17] as shown in figure 2.3. The result is: B4 CN = [5] + [7] - [5,7] + [11] - [5,11] - [7,11] + [5,7,11] + [13] - [5,13] - [7,13] - [11,13] + [5,7,13] + [5,11,13] + [7,11,13] - [5,7,11,13] + [17] - [5,17] - [7,17] - [11,17] - [13,17] + [5,7,17] + [5,11,17] + [7,11,17] + [5,13,17] + [7,13,17] + [11,13,17] - 4[5, 7,11,17] - 4[5,7,13,17] - 4[5,11,13,17] - 4[7,11,13,17] + 13[5,7,11,13,17].

(18)

We may continue by studying the formulas statisticly or use the method for computing by computer. Here the restriction N is assumed on RHS. We may use this formula to compute π (x) exactly upto x = 17' * 17'' - 6 the sucessors being counted in T ∪ S. We proceed as follows:

π (x) = π T(x) + π S(x) + 2. where T refer to the columns in T division submatirx and S to the columns in S submatrix. Now up to x = 19*23 - 6 we have:

π T(x) = |{ n ∈ T : n <= x}| - [ B4 Cfloor(x) ]T and π S(x) = |{ n ∈ S : n <= x}| - [ B4 Cfloor(x) ]S

(19) (20)

for x <= 437. The first term (19) is computed by solving for k in 5 + 6(k-1) = y where y is the largest member of T <= x and similarly for first term (20) as 1 + 6(k-1) = y where y is the largest member of S <= x. The floor function is here taken as T or S valued in the two cases. We specify more terminology to compute terms in (18) in two cases as follows:

[a,b,c, ... ]N,T := |{n ∈ T : a, b, c, ... | n, n <= N}| [a,b,c, ... ]N,S := |{n ∈ S : a, b, c, ... | n, n <= N}|. The terms in (18) are easily computed, for example: [5,7]N, T := |{n ∈ T : 5, 7 | n, n <= N}| = max {n ∈ IN : 5*7 + 6*5*7(n-1) <= N} (21) where 5*7 = 35 is the first number divisable by 5 and 7 in T. The 6 multiplier is since we work modulo 6. This generalises easily to: [a]N,T = max {n ∈ IN : b + 6*a(n-1) <= N} where b = min { n ∈ T: a | n} is the smallest number in T divisable by a. [a]N,S = max {n ∈ IN : b + 6*a(n-1) <= N} where b = min { n ∈ S: a | n}. [a,b,c, ... ]N,T = max {n ∈ IN : s + 6*a*b*c*... (n-1) <= N} where s = min { n ∈ T: a,b,c, ... | n} [a,b,c, ... ]N,S = max {n ∈ IN : s + 6*a*b*c*... (n-1) <= N} where s = min { n ∈ S: a,b,c, ... | n}

(22)

We proceed to compute these more effectively. For this purpose we need the following: 2.3 Definition: For some numbers N ∈ T we define the first twin divisors (a,b) of N (if they exist) as: a < b and a and b are adjacent rows of A and a, b | N and a,b (both) does not divide any number in T smaller than N. We call the stair pattern of first twin divisors "s1". And count the step number in s1 as m, the first step being from 5,7 | N to 7,11 | N. For [7]N,T we computed values as a function of step number and fitted a linear function above the points so created. It turns out: [7]N,T <= (43/100)m = f(m)

(23)

where m is the step number in s1. We only computed (23) to show the count behaves more regularly as a function of step number. We construct rows in A as: if row ∈ T then 5 + 6(n-1) = row and m = 2n - 1

(24.1)

if row ∈ S then 7 + 6(n-1) = row and m = 2n.

(24.2)

since rows in A are alternately in T, S, T, S .... Where m is then the index of the row in T ∪ S - {1} and can be found from "row" in (24.1) or (24.2). 2.4 Theorem The first twin divisors define a stair type pattern in A and coincides with the square root boundary at floorA (sqr N) at N any member of T having first twin divisors (i.e at any column directly after a downstep of the stairs). Proof: By seting row = floorA (sqr N) and construction of rows of A. We use for odd m (23.1). We construct rows of A starting with 5 as: a*a' = (5 + 6(n - 1))(5 + 6(n - 1))' = (5 + 6(n - 1))(5 + 6(n - 1) + 2) = N, the successor being counted in T ∪ S. The equality with N is since N has first twin divisors. We must prove: floorA {sqr [(5 + 6(n - 1))(5 + 6(n-1) + 2)]} = 5 + 6(n - 1). Note a*(a+2) ≈ a*a and the floorA function discards the fraction upto max [0, 2) for floorA ( . ) in T. The sqr a*(a+2) cannot be larger than or equal to a+2 = sqr [(a+2)(a+2)] or smaller than sqr (a*a). For even m we use (23.2) and the construction of rows of A as: a*a' = (7+6(n-1))(7+6(n-1))' = (7+6(n-1))(7+6(n-1) + 4) and this time floorA discards upto max [0, 4). The reasoning is anologous to the odd m reasoning.

 Since the terms in (18) behave more regularly as a function of step number (m) in

s1 as (23) shows it is desirable to compute for any N ∈ T at what step number in s1 we are. We know the first twin divisor stairs (s1) is also on the square root boundary (theorem 2.4) at least in columns having twin first divisors. Therefore we compute first: max {M <= N : M ∈ T, M has first twin divisors} by iteration starting at N and iterative subtraction of 6. The twin divisors to test with would be at floorA (sqr (N)) and floorA (sqr (N)) - 2 or at floorA (sqr (N)) and floorA (sqr (N)) + 2 if m is odd. By theorem 2.4. If m is even the same applies except replace 2 with 4 because the even steps are at intersection of rows that are 4 apart. By theorem 2.4 the twin divisors obtained like this are guaranteed to be first twin divisors. Actually since we are seeking m we first determine if m is odd or even by iteration and testing all 8 possible twin divisors before the next subtraction. When this M is found we use: row = floorA (sqr M)

(24)

where the floor function value is in rows of A and s1 is between this number (row) and the next member of T ∪ S. Then plug the row value into (24.1) or (24.2) to get m the step number. 2.5 Computational Effectiveness Analysis In computing the terms like at (21): max {n ∈ IN : 5*7 + 6*5*7(n-1) <= x} we need only four discardable storage locations. This may be calculated by: floor ((x - 5*7 + 6*5*7)/6*5*7) and can terefore be calculated in constant time. 2.6 Defintion We call terms of e entries "at the level m of Bm" as the terms of e entries that got generated on Bm-1 CN evolving to Bm CN.

For N = a' * a'' - 6 (for any a in T ∪ S) we set Ta,m = terms aquired at level m in Bm CN, where m is the minimum such that Bm CN counts [[5, ..., a]]N exactly. Set the amount of singletons in this Bm CN equal to σ a. We use "nCk" for n combinations in k. We use "[]" for "occurrance of a number" with one instance of it not necesarily equal to another. We denote the a, m correspondence for N as above and min {m : Bm CN counts [[5, ..., a]]N exactly} as the "minN,m" or "mina,m" criterion. The terms Ta,m has a largest entry the (m+1)'th member of T ∪ S, where m and N correspond by minN,m criterion. Set ta,m as the coefficient of term Ta,m. For example T17 = the amount of terms with an entry of 17 in (18) = 15, σ

a

=5

The storage locations needed for storing the computing formua can be reduced to an array of size equal to the amount of terms (and even further upon noting the equality of coefficients as in theorem 2.9 for terms of same amount of entries at same level of m in Bm). We need placeholders with two indices i.e.: te,m for efficiency because we store the coefficient in te,m and e specifies the amount of entries in the term and m the level of Bm. Then the term is reconstructible as by computing like with Km and noting the entries are in T ∪ S. For example the coefficient t3,3 is that of terms with three entries in them generated at level 3 of B3. In this case we look at B3 CN then t3,3 = 1 and the terms reconstruct as all combinations of three of 5,7,11,13 into [ , , ] times 1 and 13 must be in each of them. Note that in this reconstructing we would ignore terms of three entries that arrived at level m < 3 of Bm. (in this example there was none). In general te,m would not be the coefficient of terms of e entries that arrived at level m - 1 of Bm-1. For every m the m'th member of c must also be computed in order to correctly reconstruct the terms. We therefore need in terms of storage space less than: four discardable (reusable)

storage locations of bitlength equal to the bits of x, plus the amount of terms in Bm CN plus the locations to compute the m'th member of T ∪ S plus two more reusable locations to form the product te,m*[ ...]N and an accumulator to store the sum in. The bulk of the storage locations are the coefficients of the formula. This number s17 = 15 for x = 17' 17'' - 6 so that s17 < x1/2. The storage efficiency may be improved if we can get an invariant way of predicting which coefficients will be equal to 1 or -1. In this case s17 = 3 < x1/5 which would be a marked improvement over the Extended Meissel-Lehmer algorithm ref. [3] if it holds for all x. sa also decreases by theorem 2.9 and 2.10 below. We get a better bound on sa in theorem 2.11, 2.12 below. 2.7 Theorem For a, m satisfying the mina,m criterion we have: Ta,m = 1 + 1C(σ

a

- 1) + 2C(σ

a

- 1) + ... + (σ

a

- 1)C(σ

a

- 1)

Proof: This works for a = 5 to 17 just by looking at the formulas for Bm CN for m = 1 to 4. This pattern continues because a occurs in every term aquired at the level of m in Bm were we combine Bm-1CN K2 [a] - [[], a] - ... - [[], a] and method 1.3 tells us to consider all p-lets in LHS for p = 1 to m = σ hypothesis. m = σ

a

a

- 1 and Bm-1CN satisfies the theorem by inductive

- 1 because every advance on m adds one singleton and we started

at m = 1 with two singletons.

 2.8 Theorem Let N = a' * a'' - 6 for any a in T ∪ S. The amount of terms in Bm CN that counts [[5, ..., a]]N,T exactly is: 3 + T7,m + T11,m + ... Ta,m, where the indices are successive members of T ∪ S and all predecessors of a occur in the ellipses of [[5,..., a]]N,T. Proof:

By theorem 2.7 and because Kp evolves to plus. The first term is T1,m + T5,m: the trivial case.

 We compute m = σ

a

- 1 from the m of Bm such that minx,m holds because of:

Bm Cx = [[5,..., 'a]] K2 [a] - [[], a] - ... - [[], a] where 'a is the predecessor of a in T ∪ S or by m = the amount of singletons in LHS + 1. 2.9 Theorem For any p >= 1 we have that for all terms arriving at Kp evolving to Kp+1 the coefficients are equal. Proof: By noting that the amount of boldified terms for each p in Kp are equal and distributed equally among p-lets because of the combinatorical order of LHS implied by theorem 2.7.

 2.10 Theorem For all p = 1, 2 we have the coefficient of singletons = +1, doublets = -1, triplets = +1 for all terms arriving on Kp evolving to Kp+1 and for any Bm. Proof: By noting theorem 2.9 for p = 1, 2 and that for any m in Bm Cx at the K1 stage we have the standard RHS and at the K2 stage we only have singletons and doublets in RHS and boldification on RHS determines the coefficient of triplets arriving at K2 evolving to K3. The combinatorial order applies again.

 2.11 Theorem For m and x satisfying the minx,m criterion, the (permanent) storage space requirement (sa) for coefficients of Bm Cx for x = a' * a'' and a = 5 to 13 (m = 1 to 3) is 4 and from

m = 4 follows the iteration: b4 = 6 bm = bm-1 + m - 2. Proof: Only storage for coefficients for the last addage of terms are required (as m advances by one) and they are as in theorem 2.9. By direct counting: s17 = 3 (max k) - 2 sets of terms of same coefficient (not terms of 1, 2, 3 entries) get added to last Bm Cx so this number gets added to the next sa if mina,m criterion is valid and then (max k) = m by (4) and the method.

 A subset of the terms of Bm CN may be zero when evaluated in T and another set in S. These patterns must also be studied so that the reconstruction of the formulas in the two cases can be efficiently done. If m < ∞ then we may call Bm CN the m'th partial sum.

3. Upper Bound for Prime Counting Function Since primes and composites in T are complement sets we have:

π T(x) = |{ n ∈ T : n <= x}| - Bk Cfloor (x) and

π S(x) = |{ n ∈ S : n <= x}| - Bk Cfloor (x) where the floor function is T or S valued. Here we have an exact count if Bk Cfloor(x) is computed exactly. Since all the primes are in T and S (not 2, 3) we have:

π (x) = π T(x) + π T(x) + 2. We can thus use our formulas to study the Riemann Hypothesis: | Li(x) - π (x) | <= c sqr(x) ln x ≡ Riemann Hypothesis

(2 )

We take π

T

(x) ≈ π

S

(x) as a first estimate (just to see if we are at the correct order of

magnitude) this assumption is not strictly necessary since we can use the same formulas (like 18) just computing the terms in the S division matrix. Where the primes are ristricted to occur in T or S respectively. (22) translates exactly to: | Li(x) - π T(x) - π

S

(x) - 2 | <= c sqr(x) ln x

(23)

For the testing of the order of magnitude we use: | Li(x) - 2π T(x) - 2 | <= c sqr(x) ln x or: | Li(x) - 2|{ n ∈ T : n <= x}| - 2Bk Cfloor(x) - 2 | <= c sqr(x) ln x

(24)

We use: | Li(x) - 2|{ n ∈ T : n <= x}| - 2Bk Cfloor(x) - 2 | = c sqr(x) ln x

(25)

to obtain a benchmark on c. We compute an exact count for x = 19*23 - 6 = 431 for which we can use B4 C431: (since it counts exactly upto 17' times 17'' - 6)

π T(19*23-6) = |{ n ∈ T : n <= 431}| - B4 C431. |{ n ∈ T : n <= 431}| computes as: 5 + 6(k-1) = 431 therefore k = 72, therefore:

π T(19*23-6) = k - B4 CN = 72 - B4 CN. We compute the benchmark c: | Li(431) - 2(72 - B4 CN) - 2 | = c sqr(431) ln 431 which gives (Li(431) = 76.843025, B4 CN = 31): 131.15697 = c*125.93677 c = 1.041451. If we can do an estimate for x large, plug it into (25) and get a c close to the above value then we are approaching the right order of magnitude. And the smaller the k we need to achieve this, the better for our formulas to be usable.

Bibliography [1] Ellis, Gulick. Calculus. 1986. HBJ. [2] Kreyszig. Advanced Engineering Mathematics. 1988. Wiley [3] Lagarias et. al. Computing pi(x): the Meissel-Lehmer Method. 1982. http://www.dtc.umn.edu/~odlyzko/doc/cnt.html [4] Wikipedia. Divisor Function. http://en.wikipedia.org