Greatest prime dividing the n-th cubefree number: Difference between revisions
Greatest prime dividing the n-th cubefree number (view source)
Revision as of 10:20, 9 March 2024
, 3 months ago→resursive alternative: changed to search for count of cubefree numbers
(→Version 2: Added a note and changes needed to use a BitArray for the sieve.) |
(→resursive alternative: changed to search for count of cubefree numbers) |
||
Line 553:
</pre>
===resursive alternative===
<syntaxhighlight lang="pascal">
program CubeFree3;
Line 568:
const
//Apéry's Constant
Z3 = 1.20205690315959428539973816151144999;
RezZ3 = 0.831907372580707468683126278821530734417;
{
Line 580:
tPrimes = array[tPrimeIdx] of Uint32;
tDl3 = UInt64;
var
{$ALIGN 8}
SmallPrimes: tPrimes;
procedure InitSmallPrimes;
Line 629:
end;
procedure
var
i,q : Uint64;
Line 664:
dec(j,4);
end;
end;
end;
function highestDiv(n: uint64):Uint64;
//can test til 2642246^2 ~ 6,98E12
var
pr : Uint64;
i : integer;
begin
for i in tPrimeIdx do
begin
pr := Smallprimes[i];
if pr*pr>result then
BREAK;
while (result > pr) AND (result MOD pr = 0) do
result := result DIV pr;
end;
end;
procedure OutNum(lmt,n,CntDivs:Uint64);
var
MaxPrimeFac : Uint64;
begin
MaxPrimeFac := highestDiv(lmt);
writeln(Numb2Usa(lmt):26,'|',Numb2Usa(n):26,'|',Numb2Usa(CntDivs):10);▼
if MaxPrimeFac > sqr(SmallPrimes[high(tPrimeIdx)]) then
MaxPrimeFac := 0;
▲ writeln(Numb2Usa(lmt):26,'|',Numb2Usa(n):26,'|',Numb2Usa(MaxPrimeFac):15,'|',Numb2Usa(CntDivs):
end;
Line 682 ⟶ 704:
For i := i to high(tPrimeIdx) do
begin
p :=
if lmt < p then
BREAK;
Line 691 ⟶ 713:
else
cnt += p;
if p >=
check(p,i+1,not(flip));
end;
Line 699 ⟶ 721:
var
limit : extended;
lmt,dezLmt:
lastCntDivs : Uint64;
begin
limit := Z3;
while LmtIdx>0 do
Begin
limit *= 10;
dezLmt *=10;
dec(LmtIdx);
end;
lmt := trunc(limit);
▲ cnt := lmt;
repeat
▲ CntDivs := 0;
CntDivs := 0;
check(lmt,0,true);
//new apromitaion
inc(lmt,trunc(Z3*(dezlmt-cnt)));
until cnt = dezLmt;
// OutNum(lmt,cnt,CntDivs);
//maybe lmt is not cubefree, like 1200 for cnt 1000
//1200 was the only one ....
//faster than checking for cubefree of lmt
repeat
lastCntDivs := CntDivs;
dec(lmt);
cnt := lmt;
CntDivs := 0;
check(lmt,0,true);
until cnt < dezLmt;
inc(lmt);
cnt := dezLmt;
CntDivs := lastCntDivs;
OutNum(lmt,cnt,CntDivs);
end;
Line 719 ⟶ 766:
Begin
InitSmallPrimes;
InitPrmCubed(PrmCubed);
Writeln('Tested with Apéry´s Constant approximation of ',Z3:19:15);
write(' ');
writeln('Limit | cube free numbers |
T0 := GetTickCount64;
For i := 0 to 18 do
Line 731 ⟶ 779:
{{out|@home}}
<pre>
Tested with Apéry´s Constant approximation of 1.202056903159594
Limit
120,205,690,315,959,316| 100,000,000,000,000,000| 0|300,023
runtime 0.002 s▼
1,202,056,903,159,593,905| 1,000,000,000,000,000,000| 89,387|646,394
// 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
</pre>
| |||