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 07:56, 8 March 2024

712 bytes added ,  3 months ago
m
→‎resursive alternative: Using Apéry's Constant
(→‎{{header|Free Pascal}}: added recursive version, but only to check.Not tryinge to the limit for cnt = 10^n)
m (→‎resursive alternative: Using Apéry's Constant)
Line 471:
</pre>
===resursive alternative===
only counting til limit.UsedUsing priorApéry's calculatedConstant, valueswhich tois checka quite good estimate.
<syntaxhighlight lang="pascal">
program CubeFree3;
Line 485:
;
const
//Apéry's Constant
Z3 = 1.20205690315959428539973816151144999;
RezZ3 = 0.831907372580707468683126278821530734417;
{
limits :array[0..9] of UInt64 =
(1199,12019,120203,1202057,12020570,120205685,1202056919,
12020569022,120205690298,1202056903137);
}
 
type
tPrimeIdx = 0..192724;// primes til 2,642,246 ^3 ~ 2^64-1= High(Uint64)
Line 579 ⟶ 585:
end;
 
procedure OutNum(lmt,n,CntDivs:Uint64);
begin
writeln(Numb2Usa(lmt):26,'|',Numb2Usa(n):26,'|',Numb2Usa(CntDivs):10);
end;
 
var
lmt,cnt : Uint64;
CntDivs : Uint32;
 
procedure check(lmt:Uint64;i:integer;flip :Boolean);
Line 593 ⟶ 600:
For i := i to high(tPrimeIdx) do
begin
p := lmt DIV DelCube[i];
if plmt =< 0p then
BREAK;
inc(CntDivs);
p := lmt DIV p;
if flip then
cnt -= p
Line 606 ⟶ 615:
 
procedure Checklmt(lmtIdx:Uint32);
var
limit : extended;
lmt: Uint64;
begin
limit := Z3;
if LmtIdx>High(Limits) then
while LmtIdx> High(Limits)0 do▼
Begin
lmtlimit :*= Limits[High(Limits)]10;
dec(LmtIdx);▼
▲ while LmtIdx> High(Limits) do
Beginend;
lmt := 10*lmttrunc(limit);
▲ dec(LmtIdx);
end;
end▼
else
lmt := Limits[lmtIdx];
cnt := lmt;
CntDivs := 0;
check(lmt,0,true);
OutNum(lmt,cnt,CntDivs);
end;
 
Line 627 ⟶ 636:
i : integer;
Begin
T0 := GetTickCount64;▼
InitSmallPrimes;
InitDelCube(DelCube);
Forwrite(' i := 0 to 15 do ');
writeln('Limit | cube free numbers |count of divisions');
▲ T0 := GetTickCount64;
For i := 0 to 18 do
Checklmt(i);
 
T0 := GetTickCount64-T0;
writeln(' runtime ',T0/1000:0:3,' s');
▲ end.
end.</syntaxhighlight>
{{out|@home}}
<pre>
Limit 1,199| cube free numbers |count of 1,000divisions
12,019 1| 10,000 1| 0
120,203 12| 100,000 11| 1
1,202,057 120| 1,000,000 101| 2
12,020 1,570202| 10 1,000,000002| 6
120,205 12,685020| 100 10,000,000001| 14
1,202,056 120,919205| 1 100,000,000,000001| 30
12,020 1,569202,022056| 10 999,000,000,000999| 65
120,205 12,690020,298569| 100 9,000999,000,000999| 141
1,202 120,056205,903,137690| 1 100,000,000,000,000004| 301
12 1,020202,569056,031,370903| 9,999,999,999,775986| 645
120 12,205020,690569,313,700031| 99 10,999000,999000,998008| 1,144392
1 120,202205,056690,903,137,000315| 999 100,999000,999000,981014| 3,290003
12 1,020202,569056,031903,370,000159| 9 1,999000,999000,999000,811020| 6,987465
120 12,205020,690569,313031,700,000595| 99 9,999,999,998999,120963| 13,456924
120,205,690,315,959| 100,000,000,000,027| 30,006
1,202,056,903,137,000,000 999,999,999,981,203,972
1,202,056,903,159,594| 1,000,000,000,000,087| 64,643
runtime 0.010 s // getting the primes takes most of the time...
12,020,569,031,595,942| 9,999,999,999,999,948| 139,261
120,205,690,315,959,428| 100,000,000,000,000,094| 300,023
1,202,056,903,159,594,285| 1,000,000,000,000,000,317| 646,394
runtime 0.002 s
</pre>
 
Horst
132

edits

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