Linear Spike Method: Exploring the Relationship Between phi(x,y) and pi(N)

[Playdo]

I call this method the linear spike because it utilizes a linear envelope. The example is in base six but the method is more general. For every natural number we can write

(1) [tex]N=6z+\{1,5\} = (6x+\{1,5\})(6y+\{1,5\})[/tex]

This leads to three possible reduced equations

(2) [tex]z = 6xy+x+y[/tex]
(3) [tex]z = 6xy+5x+y[/tex]
(4) [tex]z=6xy+5x+5y+4[/tex]

Using 2 as an example, consider the ratio of the terms 6xy and x+y

(5) [tex]\phi(x,y)=\frac{1}{6x}+\frac{1}{6y}[/tex]

Since we know that x and y are integers greater than zero the maximum of (5) is found at x=y=1 and is 1/3.

Let U = 6xy and V = x+y, (5) helps us put bounds on the ratio of those two terms to each other and the maximum relationship is

(6) U+V=U + 1/3U = 4/3U = z

so we can rewrite (2) in general as

(7) z = 3/4z+T+U

(8) 1/4z = T + U

Example

Let x =7 and y = 8 Then z = 351

(9) 351 = 6*7*8 + 7 + 8 = 336 + 15 = U + V

(10) U ~ floor(3/4*z)+T

(11) 351-floor(3/4*351) = 351-264 = 87 = T + V

This is a linear diophantine equation that can be solved for positive values rather easily.

But more importantly the bound is not as tight as it might be since we can use the case 6x^2+2x = z to estimate the maximum value for (5) relative to N.

Namely

(13) [tex]\phi(x*,x*) = \frac{1}{3x*}[/tex]

In this case the ratio is

(14) 1/3*44 ~ 7/1000

this is the lower bound. An upper bound can be lowered by simply checking N for some of the other smaller primes, if we check it up to say 13 we get an upper bound of 1/6~.16 that is

(15) U + .16U = z -> U ~ z/1.16

(16) z - floor(z/1.16) = T + U

In the example that is

(17) 49 = T + U

An decrease in search space over 87

If we checked all primes up to 25 we would have had (5) at ~1/12

(18) z-floor(z/1.083) = T + U

(19) 27 = T + U

now notice that Mod(z,6) = Mod(U,6) so that

(20) [27-Mod(z,6)]/6 ~T/6 + Div(U,6)

(21) 24/6 = 4 = T/6 + Div(U,6)

(22) 1<Div(U,6) < 4

So returning to just after (19) we have

(23) 24 = T + Div(U,6) where 1 < Div(U,6) < 4

Yielding

(24) 24 = T + 2 or 24 = T + 3

The first yields T = 22 the second T = 21 if follows that

x + y = 6*2+ 3 = 15 or x+y=6*3+3 = 21

The first gives 351 - 15 = 6xy = floor(z/1.083) + T

More importantly we have the system

x+y = 15
6xy = 336 -> xy = 56

x+ 56/x -15 = 0

x^2 -15x + 56 = 0

Quadratic Formula gives

x = [15+/-SQRT(225-224)]/2 = 7 or 8

Even before looking at the relationship between phi(x,y) and pi(N) or trying to extend it to other bases than 6, it is clear that the rate at which phi(x,y) declines and it's level curves compared to the level curve z = 6xy+x+y is important. Furthermore for each small prime that we check N by we gain power in the algorithm by reducing the eventual search area. And since the density of primes becomes more sparse the further out we go in the natural numbers it seems reasonable to assume that the search area might be being reduced in size faster than new primes are being included under the root of N. This should be investigated further and I will in subsquent posts try to put it forward in as simple a manner as possible.

 

[CRGreathouse]

For every natural number we can write

(1) [tex]N=6z+\{1,5\} = (6x+\{1,5\})(6y+\{1,5\})[/tex]

I really must not understand you. The first equality here says that all natural numbers are [itex]\pm1[/itex] mod 6, which isn't true. The second equality holds trivially given the first, with (6z+a)(6*0+1) where a is the {1, 5} from the left hand side.

What am I missing? What are you trying to say?

 

[Playdo]

I really must not understand you. The first equality here says that all natural numbers are [itex]\pm1[/itex] mod 6, which isn't true. The second equality holds trivially given the first, with (6z+a)(6*0+1) where a is the {1, 5} from the left hand side.

What am I missing? What are you trying to say?

No, sorry the assumption is that N is in the class 6z+{1,5}. N is meant to be a natural number not all of the natural numbers. I could have used n or at least said a natural number N such that or some such thing. So then you are missing nothing. The method allows me to estimate rather tightly Div(x+y,a). There are other issues as I mention but right now I don't really have the time to do a more thorough study [I'm studying for an actuarial exam.]

I called the Linear Spike because it finds solutions based upon the linear envelope z-kz = T + V and you can decrease the search area by in a predictable way by simply testing N for divisibility by consecutive primes. Of course that is true in general, but here we gain a way of actually knowing the impact of dividing by another prime.

A question [I will get to someday] Given N and base a less than root N how many primes must we test N for to obtain 1 < Div(V,a) < 3?

If you understans the construction you will understand this last question. The distance between consecutive primes increases on average. So for very large N it might be that the ratio of the largest tested prime to the root of N satisfying the question is actually decreasing. Meaning we can factor larger and larger sets of ever larger numbers simply by knowing the next prime.

I've noticed we can attach files now, I will eventually write this up in a Word doc with graphics which will make it much easier to see what I am talking about.

 

[Hurkyl]

Your post as a whole seems incoherent to me. I doubt pictures will help at all; you need to work on your ability to explain.

I'm not even really sure what the point of it is; is it an algorithm to enumerate primes? You should explicitly write it out somewhere!

Some other problems include:

In (6) through (8) you define
U = 6xy
V = x + y
T = x/4 + y/4 - 9xy/2

So they are all constants. But suddenly you claim (11) is a Diophantine equation??

In (13), what is x*?

You talk about bounds several times... bounds on what??

 

[Playdo]

Your post as a whole seems incoherent to me. I doubt pictures will help at all; you need to work on your ability to explain.

I'm not even really sure what the point of it is; is it an algorithm to enumerate primes? You should explicitly write it out somewhere!

Some other problems include:

In (6) through (8) you define
U = 6xy
V = x + y
T = x/4 + y/4 - 9xy/2

So they are all constants. But suddenly you claim (11) is a Diophantine equation??

In (13), what is x*?

You talk about bounds several times... bounds on what??

The point is we do not know what x and y are that makes 6xy and variables. And since we seek an integer solution the equation z = 6xy + x + y (where z is knon BTW) is a diophantine equation. By using (5) we can replace the nonlinear part U = 6xy with floor(3/4z) + T the equation then becomes floor(1/4z) = T + x + y = T + V (V = x+y) that is now linear and much more tightly bounded for positive solutions, since T and V are positive. Then notice that Mod(z,6) = Mod(x+y,6)=Mod(V,6) so

[floor(1/4z)-Mod(V,6)]/6 = T/6 + Div(V,6)

Div(V,6) is easily discovered from this and is bounded as follows

1<Div(V,6) < [floor(1/4z)-Mod(V,6)]/6 -1

leading to

x+y = 6Div(V,6)+Mod(V,6)
6xy = 3/4z + T

A system easily solvable for x and y and therefore for the factors of N.
The beauty of (5) is that you can make the bound even tighter. This has nothing to do with enumerating primes save that (5) used to find the proportion of z that can be known becomes [itex]\phi(p_k) = \frac{1}{3Div(p_k,6)}[/itex].




This works even more generally as follows.

Suppose [itex]N = az+r_z[/itex] it is clear that any pair of divisors allows

(A) [tex] az+r_z = (ax+r_x)(ay+r_y)[/tex]

(B) [tex] z = axy+r_yx+r_xy+Div(r_xr_y,a)[/tex]

This is a diophantine equation in the unknowns x, y, r[x] and r[y]. Now let U = axy and [itex]V = r_yx+r_xy+Div(r_xr_y,a)[/itex]. Now consider the ratio of these two terms

(C) [tex]\phi(x,y) = \frac{V}{U} = \frac{r_y}{ay}+\frac{r_x}{ax} + \frac{Div(r_xr_y,a)}{axy}[/tex]

The last term is less than 1. When the function is at it's largest for a given N we have x = y so we can estimate a lower bound on the size of axy as

(D) [tex]\phi(x*,x*) = \frac{r_y+r_x}{ax*}<\frac{2}{x*}[/tex]

The sum of the residues is less than 2a so the inequality holds. if x* = Div(p_k,a) if should be clear that we are estimating the size of axy better and better as we test N for divisibility by larger primes less than root N. The question is which base a and p[k] is optimal for a given N?

Continuing on this says that I can use the estimate

(E) [tex] z = U +\frac{2U}{x*}[/tex]

(F) [tex] z\frac{x*}{x*+2}+T = U [/tex]

T is a slack variable. Substituting this into the appropriate earlier equation gives

(G) [tex] z - z\frac{x*}{x*+2} = \frac{2z}{x*+2} = T + V[/tex]

(H) [tex][\frac{2z}{x*+2}-Mod(V,a)]/a = T/a + Div(V,a)[/tex]

The smallest we can make the left-hand side is for x* to equal the integer divisor base a of the largest prime less than root N. For an approximation assume there is a prime near root N and use Div(Root(N),a) as a stand in.

(I) [tex]\frac{2z}{Div(\sqrt{N},a)+2}=\frac{2Div(N,a)}{Div(\sqrt{N},a)+2} = \sqrt{z}[/tex]

Leaving

(J) [tex][\sqrt{z}-Mod(V,a)]/a = T/a + Div(V,a)[/tex]

Clearly we want to pick the base a according to some rules. What are those rules? This generalization glosses completely over the fact that we do not know [itex]Div(r_xr_y,a)[/itex].

A posible approach to tkaing this further is to find a monotone increasing sequence of bases that leaves us able to deduce r_[x] and r_[y] rather easily. Base works well up to about N/36 < 5. What about the sequence {6, 36, 216, ...} = {6^n|n-natural number}

What if we choose

[tex] 36z+r_z = (36x+r_x)(36y+r_y)[/tex]

[tex] z = 36xy+r_yx+r_xy+Div(r_xr_y,36)[/tex]

?

The reduced residues of 36 are {1,5,7,11,13,17,19,23,25,29,31,35} these are easy to reconstruct using a parameter as {6t+{1,5}| t=0,1,2,3,4,5}

[tex]r_xr_y = (6u+\{1,5\})(6v+\{1,5\})[/tex]

[tex] 36z+r_z = 36^2xy+36y(6u+\{1,5\})+36x(6v+\{1,5\})+(6u+\{1,5\})(6v+\{1,5\})[/tex]

[tex] 36z+r_z = 36(36xy+y(6u+\{1,5\})+x(6x+\{1,5\})+uv)+(6u\{1,5\}+6v\{1,5\}+\{1,5\})[/tex]

So

[tex]Div(r_xr_y,36) = uv[/tex]

[tex]Mod(r_xr_y,36) = Mod(N,36) = r_z = (6u\{1,5\}+6v\{1,5\}+{1,5})[/tex]

The second can be simplified to obtain

[tex]Div(r_z,6)=[r_z-\{1,5\}]/6 = u\{1,5\}+v\{1,5\}[/tex]

Which is to say that one of these equations holds

[tex][r_z-1}]/6 = u+v\leq10[/tex]
[tex][r_z-1}]/30 = u+v\leq10[/tex]
[tex][r_z-5]/6 = 5u+v\leq30[/tex]
[tex][r_z-5]/6 = u+5v\leq30[/tex]

Now if we could get a tight bound on Div(r_xr_y,36) = uv say B we would have a systems

[tex]Div(r_xr_y,36) = uv < B[/tex]

The smaller B the less work we need to do you end up with only two system to check depending on Mod(r_z,6)

If Mod(r_z,6) = 1 solve

[tex]Div(r_xr_y,36) = uv < B[/tex]
[tex][r_z-1}]/6 = u+v[/tex] OR [tex][r_z-1}]/30 = u+v[/tex]

If Mod(r_z,6) = 5 solve

[tex]Div(r_xr_y,36) = uv < B[/tex]
[tex][r_z-5]/6 = 5u+v[/tex] OR [tex][r_z-5]/6 = u+5v[/tex]

There are many variations of the ladder sieve or wheel sieve. This is another. As I said I will have to investigate how well it performs. As for finding B I have not gotten that far yet, but I suspect the whole algorithm will prove to be recursive so that I can estimate B in much the same way as 6xy was estimated earlier.