Anonymous user
Untouchable numbers: Difference between revisions
m
→{{header|Pascal}}: reduced to only calc sum of divisors nearly halves time on TIO.RUN.Longer list of count of untouchable numbers
m (→{{header|Pascal}}: corrected SieveOneSieve Uint64(1) shl.. not 1 shl.., the 1 is Uint32 ...#@!... Now only use TIO.RUN) |
m (→{{header|Pascal}}: reduced to only calc sum of divisors nearly halves time on TIO.RUN.Longer list of count of untouchable numbers) |
||
Line 889:
There are 13863 untouchable numbers ≤ 100000.</pre>
=={{header|Pascal}}==
modified [[Factors_of_an_integer#using_Prime_decomposition]] to calculate only sum of divisors<BR>
Nigel is still right, that this procedure is not the way to get proven results.
<lang pascal>program UntouchableNumbers;
{$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$COPERATORS ON}
Line 900 ⟶ 899:
{$ENDIF}
uses
sysutils,strutils
{$IFDEF WINDOWS},Windows{$ENDIF}
;
const
//100*1000*1000;//10*1000*1000;//5*1000*1000;//1000*1000;
LIMIT = 5*1000*1000;
//384;//
LIMIT_mul =
//######################################################################
//gets sum of divisors of consecutive integers fast
const
SizePrDeFe =
type
tdigits = array [0..31] of Uint32;
tprimeFac = packed record
pfSumOfDivs,
pfRemain
end;
tpPrimeFac = ^tprimeFac;
Line 932 ⟶ 924:
var
{$ALIGN
PrimeDecompField :tPrimeDecompField;
{$ALIGN 16}
SmallPrimes: tPrimes;
pdfIDX,pdfOfs: NativeInt;
Line 979 ⟶ 971:
flipflop := 3-flipflop;
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
end;
Line 1,054 ⟶ 998:
end;
function
var
q :NativeInt;
Line 1,068 ⟶ 1,012:
dgt[result] := q;
result +=1;
end;
procedure CalcSumOfDivs(var pdf:tPrimeDecompField;var dgt:tDigits;n,k,pr:Uint64);
var
fac,s :Uint64;
j : Int32;
Begin
//j is power of prime
j := CnvtoBASE(dgt,n+k,pr);
repeat
fac := 1;
s := 1;
repeat
fac *= pr;
dec(j);
s += fac;
until j<= 0;
with pdf[k] do
Begin
pfSumOfDivs *= s;
pfRemain := pfRemain DIV fac;
end;
j := IncByOneInBase(dgt,pr);
k += pr;
until k >= SizePrDeFe;
end;
Line 1,073 ⟶ 1,042:
var
dgt:tDigits;
i,j,k,pr
begin
n := pdfOfs;
Line 1,083 ⟶ 1,052:
with pdf[i] do
Begin
pfSumOfDivs := 1;
pfRemain := n+i;
end;
end;
Line 1,100 ⟶ 1,065:
begin
j := BsfQWord(n+i);
pfRemain := (n+i) shr j;
pfSumOfDivs := (Uint64(1) shl (j+1))-1;
end;
i += 2;
Line 1,139 ⟶ 1,099:
//no need to use higher primes
if
BREAK;
CalcSumOfDivs(pdf,dgt,n,k,pr);
until false;
Line 1,171 ⟶ 1,112:
j := pfRemain;
if j <> 1 then
pfSumOFDivs *= (j+1);
end;
end;
Line 1,251 ⟶ 1,189:
repeat
inc(prmEndIdx);
until smallprimes[prmEndIdx] > trunc(
writeln('LIMIT = ',Numb2USA(IntToStr(LIMIT)));
writeln(prmEndIdx:10,smallprimes[prmEndIdx]:10);
writeln('factor beyond LIMIT ',LIMIT_mul);
n := 0;
Line 1,271 ⟶ 1,210:
end;
until n >LIMIT;
writeln('runtime for n<= LIMIT ',(GetTickCount64-T0)/1000:0:3,' s');
writeln('Check the rest ',Numb2USA(IntToStr((LIMIT_mul-1)*Limit)));
Line 1,283 ⟶ 1,223:
if n = lim then
Begin
writeln
lim *= 10;
end;
Line 1,293 ⟶ 1,233:
if n = lim then
Begin
writeln
lim += LIMIT DIV 10;
end;
k += 1-pUntouch[n];
end;
end.</lang>
{{out}}
<pre>
TIO.RUN
LIMIT = 5,000,000
331 2237
factor beyond LIMIT 104
runtime for n<= LIMIT 0.272 s
Check the rest 515,000,000
runtime 19.052 s
10 2
100 5
5000000 777672
//url=https://math.dartmouth.edu/~carlp/uupaper3.pdf
100000 13863
200000 28572
300000 43515
400000 58459
500000 73565
600000 88828
700000 104062
800000 119302
900000 134758
1000000 150232
2000000 305290
3000000 462110
4000000 619638
5000000 777672
6000000 936244
7000000 1095710
| |||