unit U_RemainderOf1;
{Copyright 2002, Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org

 This program may be used or modified for any non-commercial purpose
 so long as this original notice remains in place.
 All other rights are reserved
 }

 { What is the smallest multiple of 13 which leaves a remainder of 1 when
   divided by each of the numbers 2 through 12?

   We'll try 2 methods to find a solution:
      1. Brute force- testing successive multiples of 13  until we find one
         that leaves a remainder of 1 when divided by 2 througgh 12.
      2, Find lowest common multiple (LCM) of 2 through 12 and
         test successive (multiples of LCM) + 1 until we find one
         divisible by 13
  }


interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ComCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    SearchBtn1: TButton;
    SearchBtn2: TButton;
    Memo2: TMemo;
    Memo3: TMemo;
    StatusBar1: TStatusBar;
    StatusBar2: TStatusBar;
    procedure SearchBtn1Click(Sender: TObject);
    procedure SearchBtn2Click(Sender: TObject);
  end;

var  Form1: TForm1;

implementation
{$R *.DFM}

var searchlimit:integer=100000;

{************** TForm1.SearchBtn1Clcik *********}
procedure TForm1.SearchBtn1Click(Sender: TObject);
var  i:int64;
     j:integer;
     solved:boolean;
     start,stop,freq:int64;
begin
  i:=13;
  queryperformancecounter(start);
  repeat
    inc(i,26); {it has to remain odd}
    solved:=true;
    for j:=2 to 12 do
    if i mod j <>1 then
    begin
      solved:=false;
      break;
    end;
  until solved or (i>Searchlimit);
  queryperformancecounter(stop);
  queryperformancefrequency(freq);
  if solved then showmessage(format('Solution is %8.0n,'
  +#13+'Calculation time:  %8d microseconds',
                   [i+0.0, 1000000*(stop-start) div freq]))
  else showmessage(format('No solutions less than %8.0n',[searchlimit+0.0]));
end;

{**************** GCD2 *************}
Function gcd2(a,b:integer):integer;
{return greated common denominator of a and b}
{Euclids method -  any number that divides a and b must divide a-b}

var g,z:integer;
begin
  g:=b;
  If b<>0 then
  while g<>0 do
  begin
    z:=a mod g;
    a:=g;
    g:=z;
  end;
  result:=a;
end;

(*
{*************** GCD **************}
{Not used here but included for completeness}
Function GCD(A:array of integer):integer;
{Greatest Common Denominator of an array of integers}
var i,g:integer;
begin
  g:=a[0];
  if length(a)>=2 then
  begin
    g:=gcd2(g,a[1]);
    if length(a)>2 then
    for i:= 2 to length(a)-1 do g:=gcd2(g,a[i]);
  end;
  result:=g;
end;
*)

{*************** LCM ************}
Function LCM(A:array of integer):integer;
{Find the Lowest Common Multiple of an array of integers}
var i,x:integer;
begin
  x:=a[0];
  for i:=1 to length(a)-1 do x:=(x*a[i]) div gcd2(x,a[i]);
  result:=x;
End;

{************** Tform1.SearchBtn2Click *********}
procedure TForm1.SearchBtn2Click(Sender: TObject);
var i,n:integer;
    start,stop,freq:int64;
begin
  queryperformancecounter(start);
  n:=lcm([2,3,4,5,6,7,8,9,10,11,12]);
  i:=0;
  repeat
    inc(i);
  until ((i*n +1) mod 13 =0) or (i>10);
  queryperformancecounter(stop);
  queryperformancefrequency(freq);
  if (i*n+1) mod 13 =0

  then showmessage(format('LCM of [2..12] is %8.0n,'
                          +#13
                          +'Solution is %8.0n (%2.0n X %8.0n + 1),'
                          +#13+'Calculation time:  %8d microseconds'
                           ,[n+0.0,i*n+1.0,i+0.0,n+0.0,
                              1000000*(stop-start) div freq]))
  else showmessage(format('No solutions less than %8.0n',[i*n+1+0.0]));
end;

end.