congproth  -  Congurences for numbers h*2^n-1
---------------------------------------------

The program CongProth computes congurences for numbers
of the form h*2^n-1 for any n and h. h is odd.

The program performs a scan for all n up to a limit,
max 99999, for h in an interval, h(low) to h(high).

For every h the program first initiates a sieve vector
with size = nmax.

For every h, the program checks all primes up to the
n-limit to find divisors. If a divisor is found, the
program proceeds to find the congurence cycle. For a
prime p the cycle is either p-1 or a divisor in p-1.
This means that if 11 is found as a divisor, the cycle
is either 10 or 5.
Once the congurece cycle is found, all values of n are
marked as taken in the sieve buffer.
When all primes below nmax are checked, the program counts
all sieve cells which do remain unchecked. The count
indicates the number of n-values which will need a more
extensive check for primality.

I have included the main code which finds the congurences.


procedure TForm1.fix_cong(K_Val : integer);
label l1;
var
  i, j, np, kc, j1, kc2 : integer;
  found : boolean;
begin
  ncong := 0;
  i := 2;
  while Zprime[i] < nmax do begin
     np := Zprime[i];
     kc := K_val mod np;
     found := false;
     for j := 0 to np-1 do begin
       if kc = 1 then begin			// found a congurence
          inc(Ncong);
          XText[NCong] := '';
          nbas[Ncong] := j;
          totmod[Ncong] := np;
          kc2 := 1;
          for j1 := 1 to (np-1) div 2 do begin  // find loop
             kc2 := (kc2*2) mod np;
             if kc2 = 1 then begin		// mark found
                nmod[Ncong] := j1;
                found := true;
                goto l1;
             end;
          end;
          nmod[ncong] := np-1;
          found := true;
          goto l1;
       end;
       kc := (kc*2) mod np;
     end;
 l1: if found and (Ncong > 1) then
        for j := 1 to nCong-1 do		// find parallell congurences
          if (nbas[j] = nbas[Ncong]) and
             ((nmod[Ncong] mod nmod[j])=0) then begin
              if xtext[j] = '' then
                 Xtext[j] := inttostr(totmod[Ncong])
              else
                 Xtext[j] := Xtext[j] + ', ' +  inttostr(totmod[Ncong]);
              dec(Ncong);
              break

     end;
     inc(i);
     if (i mod 500) = 0 then begin
       StatusBar1.Panels[2].Text := inttostr(np);
       StatusBar1.Update;
       Application.ProcessMessages;
     end
  end;

end;

function TForm1.Book_off(nmax : integer) : integer;
var
  i, j1 : integer;
begin
  for i := 1 to nmax do  // reset sieve 
    fikon[i] := 1;
  for i := 1 to nCong do begin // strike out congurences
    j1 := Nbas[i];
    while j1 <= nmax do begin
       fikon[j1] := 0;
       inc(j1,nmod[i]);
    end;
  end;
  j1 := 0;
  for i := 1 to nmax do		// count cells remaining
    inc(j1,fikon[i]);
  result := j1;
end;


The program shows the progress on the status bar.
Input fields:

Start		First h-value to be tested.

Slut		Last h-value to be tested.

max n		Highest n-value in the sieve (max 99999).

Limit remaining	Used to print h-values with few cells
		unchecked. 2 means that only h-values
		where < 2% of the cells remain will be
		output to the file lowconf.txt consisting
		of h-value, # of unmarked cells and
		nmax, separated by tab. 
		Click on "Find low remain".

Buttons:
Print list	Prints a pretty list with cells remaining
		and if the checkbox "List congurences" is
		checked, do print all details.

Text file	Generate a text file instead. (FASTER!).

Close		Halt program

Find low remain Scan a large interval of h-values and generate
		a textfile with only those h-values where
		the % of remaining cells in the sieve is
		below "linit remaining". In this case the
		output is tabseparated, so it can be used to
		make a database. As very little output is
		generated, this scan is VERY fast.
		For Riesel numbers, the cell count is 0.

Torbjrn Alm

torbjorn.alm@swipnet.se


