- #1
Playdo
- 88
- 0
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.
(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.
Last edited: