Rosetta Code

Greatest prime dividing the n-th cubefree number: Difference between revisions

Page Discussion

Greatest prime dividing the n-th cubefree number (view source)

Revision as of 09:17, 6 March 2024

8,990 bytes added ,  3 months ago
→‎{{header|Phix}}: prepand pascal, a little bit lengthy
m (→‎{{header|Phix}}: logic eludes me comment)
(→‎{{header|Phix}}: prepand pascal, a little bit lengthy)
Line 181:
The 10000000th term of a[n] is 1202057</pre>
 
=={{header|Pascal}}==
==={{header|Free Pascal}}===
Uses factors of integer
<syntaxhighlight lang="pascal">
program CubeFree;
// gets factors of consecutive integers fast
// limited to 1.2e11
{$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$COPERATORS ON}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils
{$IFDEF WINDOWS},Windows{$ENDIF}
;
//######################################################################
//prime decomposition
const
//HCN(86) > 1.2E11 = 128,501,493,120 count of divs = 4096 7 3 1 1 1 1 1 1 1
HCN_DivCnt = 4096;
type
tItem = Uint64;
tDivisors = array [0..HCN_DivCnt] of tItem;
tpDivisor = pUint64;
const
//used odd size for test only
SizePrDeFe = 32768;//*72 <= 64kb level I or 2 Mb ~ level 2 cache
type
tdigits = array [0..31] of Uint32;
//the first number with 11 different prime factors =
//2*3*5*7*11*13*17*19*23*29*31 = 2E11
//56 byte
tprimeFac = packed record
pfSumOfDivs,
pfRemain : Uint64;
pfDivCnt : Uint32;
pfMaxIdx : Uint32;
pfpotPrimIdx : array[0..9] of word;
pfpotMax : array[0..11] of byte;
end;
tpPrimeFac = ^tprimeFac;
 
tPrimeDecompField = array[0..SizePrDeFe-1] of tprimeFac;
tPrimes = array[0..65535] of Uint32;
 
var
{$ALIGN 8}
SmallPrimes: tPrimes;
{$ALIGN 32}
PrimeDecompField :tPrimeDecompField;
pdfIDX,pdfOfs: NativeInt;
 
function Numb2USA(n:Uint64):Ansistring;
const
//extend s by the count of comma to be inserted
deltaLength : array[0..24] of byte =
(0,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7);
var
pI :pChar;
i,j : NativeInt;
Begin
str(n,result);
i := length(result);
//extend s by the count of comma to be inserted
// j := i+ (i-1) div 3;
j := i+deltaLength[i];
if i<> j then
Begin
setlength(result,j);
pI := @result[1];
dec(pI);
while i > 3 do
Begin
//copy 3 digits
pI[j] := pI[i];
pI[j-1] := pI[i-1];
pI[j-2] := pI[i-2];
// insert comma
pI[j-3] := ',';
dec(i,3);
dec(j,4);
end;
end;
end;
 
procedure InitSmallPrimes;
//get primes. #0..65535.Sieving only odd numbers
const
MAXLIMIT = (821641-1) shr 1;
var
pr : array[0..MAXLIMIT] of byte;
p,j,d,flipflop :NativeUInt;
Begin
SmallPrimes[0] := 2;
fillchar(pr[0],SizeOf(pr),#0);
p := 0;
repeat
repeat
p +=1
until pr[p]= 0;
j := (p+1)*p*2;
if j>MAXLIMIT then
BREAK;
d := 2*p+1;
repeat
pr[j] := 1;
j += d;
until j>MAXLIMIT;
until false;
 
SmallPrimes[1] := 3;
SmallPrimes[2] := 5;
j := 3;
d := 7;
flipflop := (2+1)-1;//7+2*2,11+2*1,13,17,19,23
p := 3;
repeat
if pr[p] = 0 then
begin
SmallPrimes[j] := d;
inc(j);
end;
d += 2*flipflop;
p+=flipflop;
flipflop := 3-flipflop;
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
end;
 
function CnvtoBASE(var dgt:tDigits;n:Uint64;base:NativeUint):NativeInt;
//n must be multiple of base aka n mod base must be 0
var
q,r: Uint64;
i : NativeInt;
Begin
fillchar(dgt,SizeOf(dgt),#0);
i := 0;
n := n div base;
result := 0;
repeat
r := n;
q := n div base;
r -= q*base;
n := q;
dgt[i] := r;
inc(i);
until (q = 0);
//searching lowest pot in base
result := 0;
while (result<i) AND (dgt[result] = 0) do
inc(result);
inc(result);
end;
 
function IncByBaseInBase(var dgt:tDigits;base:NativeInt):NativeInt;
var
q :NativeInt;
Begin
result := 0;
q := dgt[result]+1;
if q = base then
repeat
dgt[result] := 0;
inc(result);
q := dgt[result]+1;
until q <> base;
dgt[result] := q;
result +=1;
end;
 
function SieveOneSieve(var pdf:tPrimeDecompField):boolean;
var
dgt:tDigits;
i,j,k,pr,fac,n,MaxP : Uint64;
begin
n := pdfOfs;
if n+SizePrDeFe >= sqr(SmallPrimes[High(SmallPrimes)]) then
EXIT(FALSE);
//init
for i := 0 to SizePrDeFe-1 do
begin
with pdf[i] do
Begin
pfDivCnt := 1;
pfSumOfDivs := 1;
pfRemain := n+i;
pfMaxIdx := 0;
pfpotPrimIdx[0] := 0;
pfpotMax[0] := 0;
end;
end;
//first factor 2. Make n+i even
i := (pdfIdx+n) AND 1;
IF (n = 0) AND (pdfIdx<2) then
i := 2;
 
repeat
with pdf[i] do
begin
j := BsfQWord(n+i);
pfMaxIdx := 1;
pfpotPrimIdx[0] := 0;
pfpotMax[0] := j;
pfRemain := (n+i) shr j;
pfSumOfDivs := (Uint64(1) shl (j+1))-1;
pfDivCnt := j+1;
end;
i += 2;
until i >=SizePrDeFe;
//i now index in SmallPrimes
i := 0;
maxP := trunc(sqrt(n+SizePrDeFe))+1;
repeat
//search next prime that is in bounds of sieve
if n = 0 then
begin
repeat
inc(i);
pr := SmallPrimes[i];
k := pr-n MOD pr;
if k < SizePrDeFe then
break;
until pr > MaxP;
end
else
begin
repeat
inc(i);
pr := SmallPrimes[i];
k := pr-n MOD pr;
if (k = pr) AND (n>0) then
k:= 0;
if k < SizePrDeFe then
break;
until pr > MaxP;
end;
 
//no need to use higher primes
if pr*pr > n+SizePrDeFe then
BREAK;
 
//j is power of prime
j := CnvtoBASE(dgt,n+k,pr);
repeat
with pdf[k] do
Begin
pfpotPrimIdx[pfMaxIdx] := i;
pfpotMax[pfMaxIdx] := j;
pfDivCnt *= j+1;
fac := pr;
repeat
pfRemain := pfRemain DIV pr;
dec(j);
fac *= pr;
until j<= 0;
pfSumOfDivs *= (fac-1)DIV(pr-1);
inc(pfMaxIdx);
k += pr;
j := IncByBaseInBase(dgt,pr);
end;
until k >= SizePrDeFe;
until false;
 
//correct sum of & count of divisors
for i := 0 to High(pdf) do
Begin
with pdf[i] do
begin
j := pfRemain;
if j <> 1 then
begin
pfSumOFDivs *= (j+1);
pfDivCnt *=2;
end;
end;
end;
result := true;
end;
 
function NextSieve:boolean;
begin
dec(pdfIDX,SizePrDeFe);
inc(pdfOfs,SizePrDeFe);
result := SieveOneSieve(PrimeDecompField);
end;
 
function GetNextPrimeDecomp:tpPrimeFac;
begin
if pdfIDX >= SizePrDeFe then
if Not(NextSieve) then
EXIT(NIL);
result := @PrimeDecompField[pdfIDX];
inc(pdfIDX);
end;
 
function Init_Sieve(n:NativeUint):boolean;
//Init Sieve pdfIdx,pdfOfs are Global
begin
pdfIdx := n MOD SizePrDeFe;
pdfOfs := n-pdfIdx;
result := SieveOneSieve(PrimeDecompField);
end;
 
function CheckCubeFree(pPrimeDecomp :tpPrimeFac):boolean;
var
i : NativeInt;
begin
with pPrimeDecomp^ do
begin
For i := 0 to pfMaxIdx-1 do
if pfpotMax[i]>2 then
EXIT(false);
EXIT(True)
end;
end;
 
var
pPrimeDecomp :tpPrimeFac;
T0:Int64;
n,cnt,lmt : Uint64;
Begin
InitSmallPrimes;
T0 := GetTickCount64;
cnt := 0;
n := 1;
Init_Sieve(n);
writeln('First 100 terms of a[n]:');
repeat
pPrimeDecomp:= GetNextPrimeDecomp;
if CheckCubeFree(pPrimeDecomp) then
begin
with pPrimeDecomp^ do
begin
if pfMaxIdx=0 then
write(pfRemain:4)
else
write(SmallPrimes[pfpotPrimIdx[pfMaxIdx-1]]:4);
end;
inc(cnt);
if cnt mod 10 = 0 then
writeln;
end;
inc(n);
until cnt >= 100;
writeln;
writeln(' Limit Number highest divisor');
lmt := 1000;
repeat
pPrimeDecomp:= GetNextPrimeDecomp;
if CheckCubeFree(pPrimeDecomp)then
begin
inc(cnt);
if cnt = lmt then
begin
with pPrimeDecomp^ do
begin
write(Numb2USA(lmt):17,Numb2USA(n):16);
if pfRemain <>1 then
write(Numb2USA(pFRemain):16)
else
write(Numb2USA(SmallPrimes[pfpotPrimIdx[pfMaxIdx-1]]):16);
writeln;
end;
lmt :=lmt*10;
end;
end;
inc(n);
until cnt >= 10*1000*1000;
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
end.
</syntaxhighlight>
{{out|@home}}
<pre>
First 100 terms of a[n]:
1 2 3 2 5 3 7 3 5 11
3 13 7 5 17 3 19 5 7 11
23 5 13 7 29 5 31 11 17 7
3 37 19 13 41 7 43 11 5 23
47 7 5 17 13 53 11 19 29 59
5 61 31 7 13 11 67 17 23 7
71 73 37 5 19 11 13 79 41 83
7 17 43 29 89 5 13 23 31 47
19 97 7 11 5 101 17 103 7 53
107 109 11 37 113 19 23 29 13 59
 
Limit Number highest divisor
1,000 1,199 109
10,000 12,019 101
100,000 120,203 1,693
1,000,000 1,202,057 1,202,057
10,000,000 12,020,570 1,202,057
runtime 0.273 s
100,000,000 120,205,685 20,743
1,000,000,000 1,202,056,919 215,461
10,000,000,000 12,020,569,022 1,322,977
100,000,000,000 120,205,690,298 145,823
runtime 3637.753 s
 
real 60m37,756s
</pre>
=={{header|Phix}}==
Quite possibly flawed, but it does finish in the blink of an eye.
Horst
132

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/361291"