Anonymous user
Digit fifth powers: Difference between revisions
added =={{header|Pascal}}== minimal modified Own_digits_power_sum
Not a robot (talk | contribs) (Add FOCAL) |
(added =={{header|Pascal}}== minimal modified Own_digits_power_sum) |
||
Line 462:
194979
Total: 443839</pre>
=={{header|Pascal}}==
slightly modified [[Own_digits_power_sum]]
<lang pascal>program PowerOwnDigits2;
{$IFDEF FPC}
{$R+,O+}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
SysUtils,StrUtils;
const
MAXBASE = 10;
MaxDgtVal = MAXBASE - 1;
MaxDgtCount = 19;
type
tDgtCnt = 0..MaxDgtCount;
tValues = 0..MaxDgtVal;
tUsedDigits = array[tValues] of Int8;
tpUsedDigits = ^tUsedDigits;
tPower = array[tValues] of Uint64;
var
PowerDgt: tPower;
gblUD : tUsedDigits;
CombIdx : array of Int8;
Numbers : array of Uint64;
rec_cnt : NativeInt;
function InitCombIdx(ElemCount: Byte): pbyte;
begin
setlength(CombIdx, ElemCount + 1);
Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0);
Result := @CombIdx[0];
Fillchar(gblUD[0], sizeOf(tUsedDigits), #0);
gblUD[0]:= 1;
end;
function Init(ElemCount:byte;Expo:byte):pByte;
var
pP1 : pUint64;
p: Uint64;
i,j: Int32;
begin
pP1 := @PowerDgt[0];
for i in tValues do
Begin
p := 1;
for j := 1 to Expo do
p *= i;
pP1[i] := p;
end;
result := InitCombIdx(ElemCount);
gblUD[0]:= 1;
end;
function GetPowerSum(minpot:nativeInt;digits:pbyte;var UD :tUsedDigits):NativeInt;
var
res,r : Uint64;
dgt :Int32;
begin
dgt := minpot;
res := 0;
repeat
dgt -=1;
res += PowerDgt[digits[dgt]];
until dgt=0;
result := 0;
//convert res into digits
repeat
r := res DIV MAXBASE;
result+=1;
dgt := res-r*MAXBASE;
//substract from used digits
UD[dgt] -= 1;
res := r;
until r = 0;
end;
procedure calcNum(minPot:Int32;digits:pbyte);
var
UD :tUsedDigits;
res: Uint64;
i: nativeInt;
begin
UD := gblUD;
i:= GetPowerSum(minpot,digits,UD);
if i = minPot then
Begin
//don't check 0
i := 1;
repeat
If UD[i] <> 0 then
Break;
i +=1;
until i > MaxDgtVal;
if i > MaxDgtVal then
begin
res := 0;
for i := minpot-1 downto 0 do
res += PowerDgt[digits[i]];
setlength(Numbers, Length(Numbers) + 1);
Numbers[high(Numbers)] := res;
end;
end;
end;
function NextCombWithRep(pComb: pByte;pUD :tpUsedDigits;MaxVal, ElemCount: UInt32): boolean;
var
i,dgt: NativeInt;
begin
i := -1;
repeat
i += 1;
dgt := pComb[i];
if dgt < MaxVal then
break;
dec(pUD^[dgt]);
until i >= ElemCount;
Result := i >= ElemCount;
if i = 0 then
begin
dec(pUD^[dgt]);
dgt +=1;
pComb[i] := dgt;
inc(pUD^[dgt]);
end
else
begin
dec(pUD^[dgt]);
dgt +=1;
pUD^[dgt]:=i+1;
repeat
pComb[i] := dgt;
i -= 1;
until i < 0;
end;
end;
var
digits : pByte;
T0 : Int64;
tmp : Uint64;
Pot,dgtCnt,i, j : Int32;
begin
For pot := 2 to MaxDgtCount do
begin
Writeln('Exponent : ',Pot);
digits := Init(MaxDgtCount,pot);
T0 := GetTickCount64;
rec_cnt := 0;
// i > 0
For dgtCnt := 2 to pot+1 do
Begin
digits := InitCombIdx(Pot);
repeat
calcnum(dgtCnt,digits);
inc(rec_cnt);
until NextCombWithRep(digits,@gblUD,MaxDgtVal,dgtCnt);
end;
T0 := GetTickCount64-T0;
writeln(rec_cnt,' recursions');
If length(numbers) > 0 then
Begin
//sort
for i := 0 to High(Numbers) - 1 do
for j := i + 1 to High(Numbers) do
if Numbers[j] < Numbers[i] then
begin
tmp := Numbers[i];
Numbers[i] := Numbers[j];
Numbers[j] := tmp;
end;
tmp := 0;
for i := 0 to High(Numbers) do
begin
writeln(Numb2USA(IntToStr(Numbers[i])));
tmp +=Numbers[i];
end;
writeln('sum to ',Numb2USA(IntToStr(tmp)));
end;
writeln;
setlength(Numbers,0);
end;
Writeln('Max Uint64 ',Numb2USA(IntToStr(High(Uint64))));
{$IFDEF WINDOWS}
readln;
{$ENDIF}
setlength(CombIdx,0);
end.</lang>
{{Out}}
<pre style="height:190px">
Up to 19 Digits:
TIO.RUN Real time: 10.699 s CPU share: 98.66 %
Exponent : 2
275 recursions
Exponent : 3
990 recursions
153
370
371
407
sum to 1,301
Exponent : 4
2992 recursions
1,634
8,208
9,474
sum to 19,316
Exponent : 5
7997 recursions
4,150
4,151
54,748
92,727
93,084
194,979
sum to 443,839
Exponent : 6
19437 recursions
548,834
sum to 548,834
Exponent : 7
43747 recursions
1,741,725
4,210,818
9,800,817
9,926,315
14,459,929
sum to 40,139,604
Exponent : 8
92367 recursions
24,678,050
24,678,051
88,593,477
sum to 137,949,578
Exponent : 9
184745 recursions
146,511,208
472,335,975
534,494,836
912,985,153
sum to 2,066,327,172
Exponent : 10
352705 recursions
4,679,307,774
sum to 4,679,307,774
Exponent : 11
646635 recursions
32,164,049,650
32,164,049,651
40,028,394,225
42,678,290,603
44,708,635,679
49,388,550,606
82,693,916,578
94,204,591,914
sum to 418,030,478,906
Exponent : 12
1144055 recursions
Exponent : 13
1961245 recursions
564,240,140,138
sum to 564,240,140,138
Exponent : 14
3268749 recursions
28,116,440,335,967
sum to 28,116,440,335,967
Exponent : 15
5311724 recursions
Exponent : 16
8436274 recursions
4,338,281,769,391,370
4,338,281,769,391,371
sum to 8,676,563,538,782,741
Exponent : 17
13123099 recursions
233,411,150,132,317
21,897,142,587,612,075
35,641,594,208,964,132
35,875,699,062,250,035
sum to 93,647,847,008,958,559
Exponent : 18
20029999 recursions
Exponent : 19
30045004 recursions
1,517,841,543,307,505,039
3,289,582,984,443,187,032
4,498,128,791,164,624,869
4,929,273,885,928,088,826
sum to 14,234,827,204,843,405,766
Max Uint64 18,446,744,073,709,551,615</pre>
=={{header|Perl}}==
| |||