Sorry, an error occurred while loading the content.
Browse Groups

• I believe that it is possible to use the first conjecture from CONTEST++ as a starting point for a new factoring method, and that even if it is found to be not
Dec 25 2:24 PM 1 of 1
View Source
I believe that it is possible to use the first
conjecture from CONTEST++
as a starting point for a new factoring method, and
that even if it is found to be not always true, the
method itself
may still be of interest:

(x,A,B,c,k,f : integers)
Let A = 20x^2 + 10x + 1;
Let B = 10x^2 + 4x + 1;
Let c = trunc(A/sqrt(5)) - 1;

For any x > 0, apply the issquare test to each k
in the interval c <= k < B.
If there exists a value of k that satisfies the
conditions of the test, then A is composite,
and there will be at least one value of k such
that 2*k - 1 will have a factor in A.
(issquare test: 0 < 5*(2*k -1)^2 - 4*A^2 = f^2)

If we are to have any hope of finding factors for large
A(x) = 20x^2 + 10x + 1 even in this small interval
by means of the issquare test, a faster
search algorithm than
issquare itself needs to be developed, and I think that
a small two-dimensional initiating sieve array
mapped onto a large one-dimensional array representing
the interval A(x)/sqrt(5)-1 to 10x^2 + 4x + 1 or some
portion of it
may be a plausable data structure{see the program
at bottom of page}
for accomplishing this goal. Success would greatly
depend on the technical aspects
of state-ofthe-art sieve construction and manipulation -
qualities that
my primitive first effort here do not reflect, but
I am hoping that perhaps the group can help
with some real expertise in these matters. I do know
that several variants of sieve will eliminate all
invalid k if they can be made
sufficiently large  the functional equivalent of
using issquare to
test every k across an interval - and that ways exist
that can improve
performance of algorithms by using several
sieves simultaneously.
My program has so much redundancy of computation,
however, that
it can in no way be considered the desired solution
without drastic
revision. Perhaps there is fortunately available
techniques of variable
simplification that may be able to rework it into
a much more efficient form.
The complete program at the end of this discussion,
written
in ancient Pascal , is merely meant to illustrate
the principles of the issquare
sieve in a basic comprehensible manner, and
though the code is executable as is, to
actually run the program requires that it be
somehow imported
into a compatible programming environment.

To begin the demonstration of simple sieve
construction
we start with an amalgam of two variants of sieve
that will
give us the smallest possible data structure for
twenty-four elements. Let Q = the product of
3,7,13,17,23,37,43,47,53,67,73,83,97,11,19,29,31,
41,59,61,71,79,89,101,
which is the size of the interval that
could be covered mod Q, and is equal to about
2.33 * 10^37.
Its advantage, if buildable, over the usual issquare
test is that it is repeatable
without any further modification, as many times
as necessary mod Q.
It would be a very sparse array and tests indicate
an error rate of about 1 in 5000000 for the
demo program,
values that would need to be checked by the regular
issquare test or GCD. A few changes to the
demo program
could lower the error rate to at least 1 in 10^7,
but would add a bit more computation time. Of course
our demo test number is tiny, and the program makes
no errors for a number that small.

For the demo choose x = 46 on 31 101 211...
so that A = 42781 ,
with k starting at 19132, and I = 10 * k =191320,
and S = A^2 + I = 42781^2 + 191320. If S is evenly
divisible by any of the twenty-four elements the
results will be
recorded at location #1 on the two-dimensional sieve.
At the same
location we check to see which of the elements
are a factor
of S + I + I+ 10, S(x) + I+ I + 10 + I + 20 etc.
for (101 + 1)/2 iterations..
We find 17,23,37,73,83,19,29,59,61,71,79 and 101 are
all found on location #1 of the sieve, and each of
these will
repeat at regular intervals at higher locations:
17 at 1 + 17*m, 23 at 1 + 23*m,
37 at 1 + 37*m, 73 at 1 + 73*m, 83 at 1 + 83*m ,
19 at 1 + 19*m etc.

For sieve location #2 we start with
S = A^2 + I = 42781^2 + 191330
and repeat the process, thus finding factors
3,13,23,37,43,47,67,97,11,29,41,61,79 which
will similarly
repeat at higher locations. We continue the
initialization process
until location #101, the maximum element size.
The results
of the initialization process are shown in the
first part of the program.
For all elements E = +/- 3 mod 10, the locations
L + E * m are
mapped onto the one-dimensional array and are
eliminated as
valid values for k ; this is the exclusion sieve
concept. For all
elements E = +/- 1 mod 10 the locations L + E * m
are mapped
onto the one-dimensional array at any value not
already eliminated as possibility by the exclusion
sieve and remain
possible only if the array value there is covered
by all eleven
E = +/- 1 mod 10 elements.
These are the only candidates left for satifying
the conditions of the
issquare test, and are the only values of k
such that 2k -1 may have a common factor in A.
For our test number
A = 42781 there is only one possible solution,
at k = 20196, so 2*k - 1 = 40391 = 239*169.
The GCD(40391,42781) = 239, a factor of A.

.{\$N+}{E+}
Program issquaresieve (input, output);

uses wincrt;
type
numptr = ^number;
number = record
next : array[0..60000] of shortint;
end;
frame = array[0..999] of numptr;
var
A,B, P,P1,xp, hq1,hq2,hqx : extended;
fr : frame;
x, w,w1,ta: longint;

Procedure bigdat;
{ESSENTIALLY A ONE-DIMENSIONAL ARRAY
ONTO WHICH UP TO 60000000 ENTRIES CAN BE MAPPED}
var i,j : integer;
a : longint;
begin

for i := 0 to 999 do
new(fr[i]);

for i := 0 to 999 do
for a := 0 to 60000 do
begin
fr[i]^.next[a] := 0;
end;
writeln(' nnn');
end;

Procedure gcd1;
{GREATEST COMMON DIVISOR}
var
i,j : longint;
aa,bb: longint;
k,n1,n2 : integer;
c,hqf1, hqf2,r,s,t : extended;
begin
r := 2;
hqf1 := P1*2 -1;{hqx;{}
writeln('2*K-1 = ',trunc(HQF1));
hqf2 := P;
If hqf1 <> hqf2 then
begin
While r > 1 do {}
begin
c := hqf1/hqf2;
s := trunc(c/1e9)*1e9;
t := c - s;
s := s + trunc(t);
r := hqf1 - s*hqf2;
hqf1 := hqf2; hqf2 := r;
end;
end;
if r = 0 then writeln('FACTOR ',trunc(hqf1));

{else writeln(' gcd 1 ');
{writeln('end gcd '); }
end;

Procedure Issqseries;
{SETS UP THE INITIAL BOUNDRIES FOR THE SIEVE}
var ab : array[1..15] of extended;
x,y,z,z1,z2 : extended;
ct : longint;
i,j : integer;

procedure sieve;
{COMBINATION OF BOTH EXCLUSION
AND INCLUSION ISSQUARE SIEVE TYPES
MINIMIZE THE MODULUS SIZE}
var ft,i,j,k,count: integer;
Q : array[1..26] of 0..251;
R : array[1..26,1..251] of 0..251;
g,g1,g2 : longint;
y,y1,z,h : extended;

begin
{THE VALUES HERE ARE FOR THE EXCLUSION PORTION OF THE SIEVE}

q[1] := 3; q[2] := 7; q[3] := 13; q[4] := 17; q[5] := 23; q
[6] := 37; q[7] := 43; q[8] := 47;
q[9] := 53; q[10] := 67; q[11] := 73; q[12] := 83; q[13] := 97;
{}

{THE VALUES HERE ARE FOR THE INCLUSION PORTION OF THE SIEVE}

q[14] := 11; q[15] := 19; q[16] := 29; q[17] := 31; q[18] :=
41; q[19] := 59;
q[20] := 61; q[21] := 71; q[22] := 79; q[23] := 89; q[24] :=
101;

{THIS CODE CHECKS THE TEST NUMBER FOR SMALL FACTORS}
{ for i := 1 to 24 do
if x/q[i] = int(x/q[i]) then
begin
writeln(' Small Factor ',q[i]);
end;{}

Z := ab[1] ;
for i := 1 to 24 do
for j := 1 to 251 do
r[i,j] := 0 ;

k := 1;
repeat
count := 1;
y1 := 10*Z;
y := x + y1;
while count < 251 do
begin
for i := 1 to 24 do
if y/q[i] = int(y/q[i]) then
begin
r[i,k] := q[i];
end;
count := count + 1;
y1 := y1 + 10;
y := y + y1;
end;
z := z + 1;
k := k +1;
until k = 251 + 1;

writeln('initial locations and values ');
writeln(' of the elements of the sieve ');

for i := 1 to 24 do
begin
for j := 1 to q[i] do
write(' ',j:4,r[i,j]:4,' ');
writeln;
end; {}

bigdat;{ }
writeln;

{EXCLUSION SIEVE ELIMINATES MOST
INVALID ISSQUARE VALUES}
for i := 1 to 13 do
begin
for j := 1 to q[i] do
if r[i,j] > 0 then
begin
g := j;
fr[0]^.next[g] := -1;

while g < w+1 -w1 do
begin
g := g + Q[i];
g1 := g mod 60000;
g2 := g div 60000;
fr[g2]^.next[g1] := -1;
end;
end;
end;{}

{INCLUSION SIEVE PICKS
POSSIBLE VALID ISSQUARE VALUES
FROM THOSE THAT REMAIN}

for i := 14 to 24 do
begin
for j := 1 to q[i] do
if r[i,j] > 0 then
begin
g := j;
if fr[0]^.next[g] > -1 then
fr[0]^.next[g] := fr[0]^.next[g] + 1;
while g < w+1 -w1 do
begin
g := g + Q[i];
g1 := g mod 60000;
g2 := g div 60000;
if fr[g2]^.next[g1] > -1 then
fr[g2]^.next[g1] := fr[g2]^.next[g1] + 1;

end;
end;
end;

{OUTPUT OF PROGRAM}
ct := 0;
For g := 1 to w+1 - w1 do
begin
g1 := g mod 60000;
g2 := g div 60000;
begin
if fr[g2]^.next[g1] = 11 then
begin
ct := ct + 1;
end;
end ;
if fr[g2]^.next[g1] = 11 then
begin
write('K = ',TRUNC(g1 + g2*60000 + w1 -1),' ');
P1 := (g1 + g2*60000 + w1 -1);
GCD1;
end;

end;
WRITELN;
writeln(' NUMBER OF POSSIBLE VALID ISSQUARES ',ct);
writeln(' xxx ');
for i := 0 to 999 do
dispose(fr[i]);

end;

begin{top}

ab[10] := sqr(P);{}
X := AB[10];{}
ab[1] := trunc(P/sqrt(5)) ;{}
w1 := trunc(ab[1]);
write('test interval ',w1,' ');
w :=trunc(B-1);{****}
writeln(w);

Sieve;
writeln(' end sieve ');
end;

BEGIN {TOP}
writeln('ENTER AN INTEGER FOR X');

A := 20*sqr(x)+ 10*x +1;
B := 10*sqr(x) +4*x + 1;
WRITELN(' A = ',A);
WRITELN(' B = ',B);

p := A;

{p := p *p;{}
{p := sqrt(p);{}

Issqseries;{}

END.

Merry Christmas,
Aldrich Stevens
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.