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 13:59, 9 March 2024

167 bytes added ,  3 months ago
m
→‎resursive alternative: with max prime divisor for first 100. more compact.
m (→‎resursive alternative: correct max prime factor to test 2,642,246)
m (→‎resursive alternative: with max prime divisor for first 100. more compact.)
Line 568:
const
//Apéry's Constant
Z3 : extended = = 1.20205690315959428539973816151144999;
RezZ3 = 0.831907372580707468683126278821530734417;
{
limits :array[0..9] of UInt64 =
(1199,12019,120203,1202057,12020570,120205685,1202056919,
12020569022,120205690298,1202056903137);
}
 
type
Line 581 ⟶ 576:
tDl3 = UInt64;
tPrmCubed = array[tPrimeIdx] of tDl3;
 
var
{$ALIGN 8}▼
SmallPrimes: tPrimes;
▲ {$ALIGN 832}
PrmCubed : tPrmCubed;
 
Line 684 ⟶ 680:
end;
 
procedure OutNum(lmt,n,CntDivs:Uint64);
var
MaxPrimeFac : Uint64;
Line 691 ⟶ 687:
if MaxPrimeFac > sqr(SmallPrimes[high(tPrimeIdx)]) then
MaxPrimeFac := 0;
writeln(Numb2Usa(lmt):26,'|',Numb2Usa(n):26,'|',Numb2Usa(MaxPrimeFac):15,'|',Numb2Usa(CntDivs):7);
end;
//##########################################################################
 
var
cnt : Uint64Int64;
CntDivs : Uint32;
 
procedure check(lmt:Uint64;i:integer;flip :Boolean);
Line 707 ⟶ 702:
if lmt < p then
BREAK;
inc(CntDivs);▼
p := lmt DIV p;
if flip then
Line 718 ⟶ 712:
end;
 
function GetLmtfromCnt(inCnt:Uint64):Uint64;
procedure Checklmt(lmtIdx:Uint32);
var
limit : extended;
lmt,dezLmt: Int64;
lastCntDivs : Uint64;
begin
limitresult := trunc(Z3*inCnt);
dezLmt := 1;▼
while LmtIdx>0 do
Begin▼
limit *= 10;▼
dezLmt *=10;
dec(LmtIdx);
end;▼
lmt := trunc(limit);
 
repeat
cnt := lmtresult;
CntDivs := check(result,0,true);
check(lmt,0,true);▼
//new approximation
inc(lmtresult,trunc(Z3*(dezlmtinCnt-cntCnt)));
until cnt = dezLmtinCnt;
// OutNum(lmt,cnt,CntDivs);
 
//maybe lmt is not cubefree, like 1200 for cnt 1000
//faster than checking for cubefree of lmt for big lmt▼
//1200 was the only one ....
▲ //faster than checking for cubefree of lmt
repeat
▲ incdec(CntDivsresult);
lastCntDivs := CntDivs;
dec(lmt)cnt := result;
▲ check(lmtresult,0,true);
cnt := lmt;
until cnt CntDivs< := 0inCnt;
checkinc(lmt,0,trueresult);
until cnt < dezLmt;
 
inc(lmt);
cnt := dezLmt;
CntDivs := lastCntDivs;
 
OutNum(lmt,cnt,CntDivs);
end;
//##########################################################################
 
var
T0,lmt:Int64;
i : integer;
Begin
InitSmallPrimes;
InitPrmCubed(PrmCubed);
 
Writeln('Tested with Apéry´s Constant approximation of ',Z3:19:15);▼
For i := 1 to 100 do
▲ Begin
lmt := GetLmtfromCnt(i);
write(highestDiv(lmt):4);
if i mod 10 = 0 then
Writeln;
▲ end;
Writeln;
 
▲ Writeln('Tested with Apéry´s Constant approximation of ',Z3:1917:15);
write(' ');
writeln('Limit | cube free numbers |max prim factor| divs');
T0 := GetTickCount64;
▲ dezLmtlmt := 1;
For i := 0 to 18 do
Begin
Checklmt(i);
OutNum(GetLmtfromCnt(lmt),lmt);
▲ limitlmt *= 10;
end.;▼
T0 := GetTickCount64-T0;
writeln(' runtime ',T0/1000:0:3,' s');
 
▲end.
end.</syntaxhighlight>
{{out|@home}}
<pre>
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
 
Tested with Apéry´s Constant approximation of 1.202056903159594
Limit | cube free numbers |max prim factor| divs
1| 1| 1| 0
11| 10| 11| 1
118| 100| 59| 2
1,199| 1,000| 109| 6<
12,019| 10,000| 101| 14
120,203| 100,000| 1,693| 30
1,202,057| 1,000,000| 1,202,057| 65<
12,020,570| 10,000,000| 1,202,057| 141
120,205,685| 100,000,000| 20,743| 301
1,202,056,919| 1,000,000,000| 215,461| 645<
12,020,569,022| 10,000,000,000| 1,322,977| 1,392
120,205,690,298| 100,000,000,000| 145,823| 3,003
1,202,056,903,137| 1,000,000,000,000|400,685,634,379| 6,465<
12,020,569,031,641| 10,000,000,000,000| 1,498,751| 13,924
120,205,690,315,927| 100,000,000,000,000| 57,349| 30,006
1,202,056,903,159,489| 1,000,000,000,000,000| 74,509,198,733| 64,643<
12,020,569,031,596,003| 10,000,000,000,000,000| 0|139,261
120,205,690,315,959,316| 100,000,000,000,000,000| 0|300,023
1,202,056,903,159,593,905| 1,000,000,000,000,000,000| 89,387|646,394<
runtime 0.013008 s real//best 0m0,019value.
real 0m0,013s
// as an experiment with factor of 1 for changing approximation.
Tested with Apéry´s Constant approximation of 1.000000000000000
runtime 0.065 s real 0m0,071s
real 0m0,071s</pre>
 
=={{header|Phix}}==
Horst
132

edits

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