Giuga numbers: Difference between revisions

Content added Content deleted
m (→‎alternative version: limit count of search factors to 7 and other small optimizations)
m (→‎alternative version: extreme cheating: limit the used factors in the specific column 3041 is highest factor at column 5)
Line 497: Line 497:
</pre>
</pre>
====alternative version====
====alternative version====
Generating recurursive squarefree numbers of ascending primes and check those numbers.<BR>
Generating recursive squarefree numbers of ascending primes and check those numbers.<BR>
2*3 are set fixed. 2*3*5 followed 2*3*7 than 2*3*11. Therefor the results are unsorted.
2*3 are set fixed. 2*3*5 followed 2*3*7 than 2*3*11. Therefor the results are unsorted.
<lang pascal>program Giuga;
<lang pascal>program Giuga;
Line 523: Line 523:
;
;
const
const
LMT = 24423128562;//24423128562;//2214408306;//432749205173838
LMT =14737133470010574;// 432749205173838;//24423128562;//2214408306;
type
type
tFac = packed record
tFac = packed record
fMul :Uint64;
fMul :Uint64;
fPrime,
fPrime,
fPrimIdx :Uint32;
fPrimIdx,
fprimMaxIdx,dummy :Uint32;
dummy2: Uint64;
end;
end;
tFacs = array[0..64] of tFac;
tFacs = array[0..15] of tFac;
tPrimes = array[0..62157] of Uint32;//775807
tPrimes = array[0..62157] of Uint32;//775807 see factor of 432749205173838
// tPrimes = array[0..14379] of Uint32;//sqrt 24423128562
// tPrimes = array[0..4875{14379}] of Uint32;//sqrt 24423128562
// tPrimes = array[0..1807414] of Uint32;//29133437
// tPrimes = array[0..1807414] of Uint32;//29133437
// tPrimes = array[0..50847533] of Uint32;// 1e9
// tPrimes = array[0..5761454] of Uint32;//1e8
var
var
SmallPrimes: tPrimes;
SmallPrimes: tPrimes;
Line 540: Line 544:


procedure InitSmallPrimes;
procedure InitSmallPrimes;
//get primes. Sieving only odd numbers
//get primes. #0..65535.Sieving only odd numbers
const
const
//MAXLIMIT = (trunc(sqrt(LMT)+1)-1) shr 1+4;
//MAXLIMIT = (trunc(sqrt(LMT)+1)-1) shr 1+4;
Line 624: Line 628:
begin
begin
Mul := fMul;
Mul := fMul;
i := fPrimIdx+1;
i := fPrimIdx;
end;
end;

if i<High(SmallPrimes) then
while i<High(SmallPrimes) do
repeat
begin
inc(i);
with F[idx] do
with F[idx] do
begin
begin
if i >fprimMaxIdx then
⚫
BREAK;
p := SmallPrimes[i];
p := SmallPrimes[i];
⚫
fPrime := p;
⚫
fPrimIdx := i;
if p*Mul>LMT then
if p*Mul>LMT then
BREAK;
BREAK;
fMul := Mul*p;
fMul := p*Mul;
fPrime := p;
⚫
fPrimIdx := i;
IF (Mul-1) MOD p = 0 then
IF (Mul-1) MOD p = 0 then
IF ChkGiuga(F,idx) then
IF ChkGiuga(F,idx) then
OutFac(F,idx);
OutFac(F,idx);
end;
end;
// max 7 factors [0..6]
// max 6 factors //for lmt 24e9 need 7 factors
if idx <6 then
if idx <5 then
InsertNextPrimeFac(F,idx+1);
InsertNextPrimeFac(F,idx+1);
inc(i);
end;
until i>High(SmallPrimes);
end;
end;


Line 650: Line 657:
{$ALIGN 32}
{$ALIGN 32}
Facs : tFacs;
Facs : tFacs;
i : integer;
Begin
Begin
InitSmallPrimes;
InitSmallPrimes;
Line 662: Line 670:
fMul := 2*3;fPrime := 3;fPrimIdx:= 1;
fMul := 2*3;fPrime := 3;fPrimIdx:= 1;
end;
end;
i := 2;
//search the indices of mx found factor
while SmallPrimes[i] < 11 do inc(i); Facs[2].fprimMaxIdx := i;
while SmallPrimes[i] < 71 do inc(i); Facs[3].fprimMaxIdx := i;
while SmallPrimes[i] < 3041 do inc(i); Facs[4].fprimMaxIdx := i;
while SmallPrimes[i] < 67213 do inc(i); Facs[5].fprimMaxIdx := i;
while SmallPrimes[i] < 775807 do inc(i); Facs[6].fprimMaxIdx := i;
{
writeln('Found ',cnt,' in ',(GetTickCount64-T0)/1000:10:3,' s');
//start with 2*3*7
with Facs[2] do
begin
fMul := 2*3*7;fPrime := 7;fPrimIdx:= 3;
end;
InsertNextPrimeFac(Facs,3);
//start with 2*3*11
writeln('Found ',cnt,' in ',(GetTickCount64-T0)/1000:10:3,' s');
with Facs[2] do
begin
fMul := 2*3*11;fPrime := 11;fPrimIdx:= 4;
end;
InsertNextPrimeFac(Facs,3);
}
InsertNextPrimeFac(Facs,2);
InsertNextPrimeFac(Facs,2);
writeln('Found ',cnt,' in ',(GetTickCount64-T0)/1000:10:3,' s');

T0 := GetTickCount64-T0;
writeln('Found ',cnt);
writeln;
writeln;
end.
end.
Line 672: Line 701:
<pre>
<pre>
1 2*3*5 = 30 0.000 s
1 2*3*5 = 30 0.000 s
2 2*3*7*41 = 1722 1.921 s
2 2*3*7*41 = 1722 0.810 s
3 2*3*7*43*3041*4447 = 24423128562 1.954 s
3 2*3*7*43*3041*4447 = 24423128562 0.871 s
4 2*3*11*13 = 858 2.527 s
4 2*3*11*13 = 858 1.057 s
5 2*3*11*17*59 = 66198 2.588 s
5 2*3*11*17*59 = 66198 1.089 s
6 2*3*11*23*31*47057 = 2214408306 2.645 s
6 2*3*11*23*31*47057 = 2214408306 1.152 s
Found 6
Found 6 in 1.526 s
Real time: 8.733 s CPU share: 99.45 %
Real time: 1.682 s CPU share: 99.42 %

@home:
Limit:432749205173838
start 2*3*7
Found 0 in 0.000 s
1 2*3*7*41 = 1722 147.206 s
2 2*3*7*43*3041*4447 = 24423128562 163.765 s
3 2*3*7*59*163*1381*775807 = 432749205173838 179.124 s
Found 3 in 197.002 s
start 2*3*11
4 2*3*11*13 = 858 197.002 s
5 2*3*11*17*59 = 66198 219.166 s
6 2*3*11*23*31*47057 = 2214408306 244.468 s

real 5m10,271s

Limit :14737133470010574
start 2*3*7
Found 0 in 0.000 s
1 2*3*7*41 = 1722 1330.819 s
2 2*3*7*43*3041*4447 = 24423128562 1567.028 s
3 2*3*7*59*163*1381*775807 = 432749205173838 1788.203 s
4 2*3*7*71*103*67213*713863 = 14737133470010574 2051.552 s
Found 4 in 2129.801 s
start 2*3*11
5 2*3*11*13 = 858 2129.801 s
6 2*3*11*17*59 = 66198 2305.752 s
7 2*3*11*23*31*47057 = 2214408306 2591.984 s
Found 7 in 3654.610 s


//@home real 0m1,604s
real 60m54,612s
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Giuga_numbers"