Digit fifth powers: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add FOCAL) |
(added =={{header|Pascal}}== minimal modified Own_digits_power_sum) |
||
Line 462: | Line 462: | ||
194979 |
194979 |
||
Total: 443839</pre> |
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}}== |
=={{header|Perl}}== |