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-ofthe-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

some advanced

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]);

readln;

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,' ');

readln;

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 ');

readln;

end;

BEGIN {TOP}

writeln('ENTER AN INTEGER FOR X');

READLN(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