Own digits power sum: Difference between revisions
m (→{{header|Python}}: simplify) |
(added pascal) |
||
Line 265: | Line 265: | ||
912985153 |
912985153 |
||
</pre> |
</pre> |
||
=={{header|Pascal}}== |
|||
recursive solution. |
|||
<lang pascal>program PowerOwnDigits; |
|||
uses |
|||
SysUtils; |
|||
const |
|||
Maxbase = 10; |
|||
MaxDgtVal = Maxbase - 1; |
|||
type |
|||
tDgtVal = 0..MaxDgtVal; |
|||
tUsedDigits = array[tDgtVal] of Int32; |
|||
var |
|||
UsedDigits: array[tDgtVal] of Int32; |
|||
PowerDgt: array[tDgtVal, tDgtVal] of Uint64; |
|||
NUmbers: array of Uint64; |
|||
procedure InitPowerDgt; |
|||
var |
|||
i, j: tDgtVal; |
|||
begin |
|||
PowerDgt[0, 0] := 0; |
|||
for i := low(tDgtVal) + 1 to High(tDgtVal) do |
|||
PowerDgt[low(tDgtVal), i] := 1; |
|||
for j := low(tDgtVal) + 1 to High(tDgtVal) do |
|||
for i := low(tDgtVal) to High(tDgtVal) do |
|||
PowerDgt[j, i] := PowerDgt[j - 1, i] * i; |
|||
end; |
|||
function calcNum(depth: Int32; UsedDigits: tUsedDigits): Uint64; |
|||
var |
|||
n, r: Uint64; |
|||
i: integer; |
|||
begin |
|||
Result := 0; |
|||
if depth < 3 then |
|||
exit; |
|||
for i := 1 to High(tDgtVal) do |
|||
begin |
|||
if usedDigits[i] > 0 then |
|||
Result += UsedDigits[i] * PowerDgt[depth, i]; |
|||
end; |
|||
if Result = 0 then |
|||
EXIT; |
|||
n := Result; |
|||
repeat |
|||
r := n div MAxBase; |
|||
Dec(UsedDigits[n - r * maxBase]); |
|||
n := r; |
|||
Dec(depth); |
|||
until r = 0; |
|||
if depth <> 0 then |
|||
EXIT(0); |
|||
i := 1; |
|||
while (i <= MaxDgtVal) and (UsedDigits[i] = 0) do |
|||
Inc(i); |
|||
if i > MaxDgtVal then |
|||
begin |
|||
setlength(NUmbers, Length(numbers) + 1); |
|||
NUmbers[high(numbers)] := Result; |
|||
end; |
|||
end; |
|||
procedure NextDigit(dgt, depth: tDgtVal); |
|||
var |
|||
i: tDgtVal; |
|||
begin |
|||
if depth < High(tDgtVal) then |
|||
begin |
|||
for i := dgt to High(tDgtVal) do |
|||
begin |
|||
Inc(UsedDigits[dgt]); |
|||
NextDigit(i, depth + 1); |
|||
Dec(UsedDigits[dgt]); |
|||
end; |
|||
end; |
|||
if dgt = 0 then |
|||
dgt := 1; |
|||
for i := dgt to High(tDgtVal) do |
|||
begin |
|||
Inc(UsedDigits[i]); |
|||
calcNum(depth, UsedDigits); |
|||
Dec(UsedDigits[i]); |
|||
end; |
|||
end; |
|||
var |
|||
T0 : Int64; |
|||
min, tmp: Uint64; |
|||
i, j, max: Int32; |
|||
begin |
|||
T0 := GetTickCount64; |
|||
InitPowerDgt; |
|||
NextDigit(0, 0); |
|||
{ |
|||
9800817 |
|||
9800817 |
|||
24678050 |
|||
24678050 |
|||
146511208 |
|||
146511208 |
|||
146511208 |
|||
... |
|||
} |
|||
// 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; |
|||
//delete doublettes |
|||
tmp := numbers[0]; |
|||
j := 0; |
|||
for i := 1 to High(numbers) do |
|||
if numbers[i] <> tmp then |
|||
begin |
|||
Inc(j); |
|||
tmp := numbers[i]; |
|||
numbers[j] := tmp; |
|||
end; |
|||
setlength(numbers, j + 1); |
|||
T0 := GetTickCount64-T0; |
|||
writeln(' runtime ',T0,' ms'); |
|||
for i := 0 to High(numbers) do |
|||
writeln(numbers[i]); |
|||
{$IFDEF WINDOWS} |
|||
readln; |
|||
{$ENDIF} |
|||
end.</lang> |
|||
{{out}} |
|||
<pre> |
|||
TIO.RUN |
|||
runtime 25 ms |
|||
153 |
|||
370 |
|||
371 |
|||
407 |
|||
1634 |
|||
8208 |
|||
9474 |
|||
54748 |
|||
92727 |
|||
93084 |
|||
548834 |
|||
1741725 |
|||
4210818 |
|||
9800817 |
|||
9926315 |
|||
24678050 |
|||
24678051 |
|||
88593477 |
|||
146511208 |
|||
472335975 |
|||
534494836 |
|||
912985153</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Use <code>Parallel::ForkManager</code> to obtain concurrency, trading some code complexity for less-than-infinite run time. |
Use <code>Parallel::ForkManager</code> to obtain concurrency, trading some code complexity for less-than-infinite run time. |
Revision as of 10:06, 26 October 2021
- Description
For the purposes of this task, an own digits power sum is a decimal integer which is N digits long and is equal to the sum of its individual digits raised to the power N.
- Example
The three digit integer 153 is an own digits power sum because 1³ + 5³ + 3³ = 1 + 125 + 27 = 153.
- Task
Find and show here all own digits power sums for N = 3 to N = 8 inclusive.
Optionally, do the same for N = 9 which may take a while for interpreted languages.
ALGOL 68
Avoids spliting the digits using division and modulo operations. Includes the Wren optimisation of if the last digit = 0 then the same number but with last digit = 1 is also a suitable number. <lang algol68># find n digit numbers N such that the sum of the nth powers of their digits = N # FOR n FROM 3 TO 9 DO
INT fdigit = 10 - n; [ 1 : 8 ]INT f; FOR i TO 8 DO f[ i ] := IF i = fdigit THEN 1 ELSE 0 FI OD; [ 1 : 8 ]INT t; FOR i TO 8 DO t[ i ] := IF i < fdigit THEN 0 ELSE 9 FI OD; [ 0 : 10 ]INT power; FOR i FROM LWB power TO UPB power DO power[ i ] := i ^ n OD; INT max n = power[ 10 ]; FOR d1 FROM f[ 1 ] TO t[ 1 ] DO INT p1 = power[ d1 ]; INT s1 = d1 * 10; FOR d2 FROM f[ 2 ] TO t[ 2 ] WHILE INT p2 = power[ d2 ] + p1; p2 < max n DO INT s2 = ( s1 + d2 ) * 10; FOR d3 FROM f[ 3 ] TO t[ 3 ] WHILE INT p3 = power[ d3 ] + p2; p3 < max n DO INT s3 = ( s2 + d3 ) * 10; FOR d4 FROM f[ 4 ] TO t[ 4 ] WHILE INT p4 = power[ d4 ] + p3; p4 < max n DO INT s4 = ( s3 + d4 ) * 10; FOR d5 FROM f[ 5 ] TO t[ 5 ] WHILE INT p5 = power[ d5 ] + p4; p5 < max n DO INT s5 = ( s4 + d5 ) * 10; FOR d6 FROM f[ 6 ] TO t[ 6 ] WHILE INT p6 = power[ d6 ] + p5; p6 < max n DO INT s6 = ( s5 + d6 ) * 10; FOR d7 FROM f[ 7 ] TO t[ 7 ] WHILE INT p7 = power[ d7 ] + p6; p7 < max n DO INT s7 = ( s6 + d7 ) * 10; FOR d8 FROM f[ 8 ] TO t[ 8 ] WHILE INT p8 = power[ d8 ] + p7; p8 < max n DO INT s8 = ( s7 + d8 ) * 10; IF s8 = p8 THEN # found a number with 0 as the final digit # # the same number with a final digit of 1 # # must also match the requirements # print( ( whole( s8, 0 ), newline ) ); print( ( whole( s8 + 1, 0 ), newline ) ) FI; FOR d9 FROM 2 TO 9 WHILE INT p9 = power[ d9 ] + p8; p9 < max n DO INT s9 = s8 + d9; IF s9 = p9 THEN print( ( whole( s9, 0 ), newline ) ) FI OD OD OD OD OD OD OD OD OD
OD</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
C
<lang c>#include <stdio.h>
- include <math.h>
- define MAX_DIGITS 9
int digits[MAX_DIGITS];
void getDigits(int i) {
int ix = 0; while (i > 0) { digits[ix++] = i % 10; i /= 10; }
}
int main() {
int n, d, i, max, lastDigit, sum, dp; int powers[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}; printf("Own digits power sums for N = 3 to 9 inclusive:\n"); for (n = 3; n < 10; ++n) { for (d = 2; d < 10; ++d) powers[d] *= d; i = (int)pow(10, n-1); max = i * 10; lastDigit = 0; while (i < max) { if (!lastDigit) { getDigits(i); sum = 0; for (d = 0; d < n; ++d) { dp = digits[d]; sum += powers[dp]; } } else if (lastDigit == 1) { sum++; } else { sum += powers[lastDigit] - powers[lastDigit-1]; } if (sum == i) { printf("%d\n", i); if (lastDigit == 0) printf("%d\n", i + 1); i += 10 - lastDigit; lastDigit = 0; } else if (sum > i) { i += 10 - lastDigit; lastDigit = 0; } else if (lastDigit < 9) { i++; lastDigit++; } else { i++; lastDigit = 0; } } } return 0;
}</lang>
- Output:
Same as Wren example.
Go
<lang go>package main
import (
"fmt" "math" "rcu"
)
func main() {
powers := [10]int{0, 1, 4, 9, 16, 25, 36, 49, 64, 81} fmt.Println("Own digits power sums for N = 3 to 9 inclusive:") for n := 3; n < 10; n++ { for d := 2; d < 10; d++ { powers[d] *= d } i := int(math.Pow(10, float64(n-1))) max := i * 10 lastDigit := 0 sum := 0 var digits []int for i < max { if lastDigit == 0 { digits = rcu.Digits(i, 10) sum = 0 for _, d := range digits { sum += powers[d] } } else if lastDigit == 1 { sum++ } else { sum += powers[lastDigit] - powers[lastDigit-1] } if sum == i { fmt.Println(i) if lastDigit == 0 { fmt.Println(i + 1) } i += 10 - lastDigit lastDigit = 0 } else if sum > i { i += 10 - lastDigit lastDigit = 0 } else if lastDigit < 9 { i++ lastDigit++ } else { i++ lastDigit = 0 } } }
}</lang>
- Output:
Same as Wren example.
Julia
<lang julia>function isowndigitspowersum(n::Integer, base=10)
dig = digits(n, base=base) exponent = length(dig) return mapreduce(x -> x^exponent, +, dig) == n
end
for i in 10^2:10^9-1
isowndigitspowersum(i) && println(i)
end
</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 472335975 534494836 912985153
Pascal
recursive solution. <lang pascal>program PowerOwnDigits;
uses
SysUtils;
const
Maxbase = 10; MaxDgtVal = Maxbase - 1;
type
tDgtVal = 0..MaxDgtVal; tUsedDigits = array[tDgtVal] of Int32;
var
UsedDigits: array[tDgtVal] of Int32; PowerDgt: array[tDgtVal, tDgtVal] of Uint64; NUmbers: array of Uint64;
procedure InitPowerDgt; var i, j: tDgtVal; begin PowerDgt[0, 0] := 0; for i := low(tDgtVal) + 1 to High(tDgtVal) do PowerDgt[low(tDgtVal), i] := 1;
for j := low(tDgtVal) + 1 to High(tDgtVal) do for i := low(tDgtVal) to High(tDgtVal) do PowerDgt[j, i] := PowerDgt[j - 1, i] * i; end;
function calcNum(depth: Int32; UsedDigits: tUsedDigits): Uint64; var n, r: Uint64; i: integer; begin Result := 0; if depth < 3 then exit; for i := 1 to High(tDgtVal) do begin if usedDigits[i] > 0 then Result += UsedDigits[i] * PowerDgt[depth, i]; end; if Result = 0 then EXIT;
n := Result; repeat r := n div MAxBase; Dec(UsedDigits[n - r * maxBase]); n := r; Dec(depth); until r = 0;
if depth <> 0 then EXIT(0); i := 1; while (i <= MaxDgtVal) and (UsedDigits[i] = 0) do Inc(i); if i > MaxDgtVal then begin setlength(NUmbers, Length(numbers) + 1); NUmbers[high(numbers)] := Result; end; end;
procedure NextDigit(dgt, depth: tDgtVal); var i: tDgtVal; begin if depth < High(tDgtVal) then begin for i := dgt to High(tDgtVal) do begin Inc(UsedDigits[dgt]); NextDigit(i, depth + 1); Dec(UsedDigits[dgt]); end; end; if dgt = 0 then dgt := 1;
for i := dgt to High(tDgtVal) do begin Inc(UsedDigits[i]); calcNum(depth, UsedDigits); Dec(UsedDigits[i]); end; end;
var
T0 : Int64; min, tmp: Uint64; i, j, max: Int32;
begin
T0 := GetTickCount64; InitPowerDgt; NextDigit(0, 0);
{ 9800817 9800817 24678050 24678050 146511208 146511208 146511208 ... }
// 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; //delete doublettes tmp := numbers[0]; j := 0; for i := 1 to High(numbers) do if numbers[i] <> tmp then begin Inc(j); tmp := numbers[i]; numbers[j] := tmp; end; setlength(numbers, j + 1); T0 := GetTickCount64-T0; writeln(' runtime ',T0,' ms'); for i := 0 to High(numbers) do writeln(numbers[i]); {$IFDEF WINDOWS} readln;
{$ENDIF} end.</lang>
- Output:
TIO.RUN runtime 25 ms 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Perl
Use Parallel::ForkManager
to obtain concurrency, trading some code complexity for less-than-infinite run time.
<lang perl>use strict;
use warnings;
use feature 'say';
use List::Util 'sum';
use Parallel::ForkManager;
my %own_dps; my($lo,$hi) = (3,9); my $cores = 8; # configure to match hardware being used
my $start = 10**($lo-1); my $stop = 10**$hi - 1; my $step = int(1 + ($stop - $start)/ ($cores+1));
my $pm = Parallel::ForkManager->new($cores);
RUN: for my $i ( 0 .. $cores ) {
$pm->run_on_finish ( sub { my ($pid, $exit_code, $ident, $exit_signal, $core_dump, $data_ref) = @_; $own_dps{$ident} = $data_ref; } );
$pm->start($i) and next RUN;
my @values; for my $n ( ($start + $i*$step) .. ($start + ($i+1)*$step) ) { push @values, $n if $n == sum map { $_**length($n) } split , $n; }
$pm->finish(0, \@values)
}
$pm->wait_all_children;
say $_ for sort { $a <=> $b } map { @$_ } values %own_dps;</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477
Python
<lang python>""" Rosetta code task: Own_digits_power_sum """
def isowndigitspowersum(integer):
""" true if sum of (digits of number raised to number of digits) == number """ digits = [int(c) for c in str(integer)] exponent = len(digits) return sum(x ** exponent for x in digits) == integer
print("Own digits power sums for N = 3 to 9 inclusive:") for i in range(100, 1000000000):
if isowndigitspowersum(i): print(i)
</lang>
- Output:
Same as Wren example. Takes over a half hour to run.
Visual Basic .NET
<lang vbnet>Option Strict On Option Explicit On
Imports System.IO
<summary> Finds n digit numbers N such that the sum of the nth powers of their digits = N </summary> Module OwnDigitsPowerSum
Public Sub Main For n As Integer = 3 To 9 Dim fdigit As Integer = 10 - n Dim f(8) As Integer For i As Integer = 1 To 8 f(i) = If(i = fdigit, 1, 0) Next i Dim t(8) As Integer For i As Integer = 1 To 8 t(i) = If(i < fdigit, 0, 9) Next i Dim power(10) As Integer For i As Integer = 0 To UBound(power) power(i) = Cint(i ^ n) Next i Dim maxN As Integer = power(10) For d1 As Integer = f(1) To t(1) Dim p1 As Integer = power(d1) Dim s1 As Integer = d1 * 10 For d2 As Integer = f(2) To t(2) Dim p2 As Integer = power(d2) + p1 If p2 >= maxN Then Exit For Dim s2 As Integer = (s1 + d2) * 10 For d3 As Integer = f(3) To t(3) Dim p3 As Integer = power(d3) + p2 If p3 >= maxN Then Exit For Dim s3 As Integer = (s2 + d3) * 10 For d4 As Integer = f(4) To t(4) Dim p4 As Integer = power(d4) + p3 If p4 >= maxN Then Exit For Dim s4 As Integer = (s3 + d4) * 10 For d5 As Integer = f(5) To t(5) Dim p5 As Integer = power(d5) + p4 If p5 >= maxN Then Exit For Dim s5 As Integer = (s4 + d5) * 10 For d6 As Integer = f(6) To t(6) Dim p6 As Integer = power(d6) + p5 If p6 >= maxN Then Exit For Dim s6 As Integer = (s5 + d6) * 10 For d7 As Integer = f(7) To t(7) Dim p7 As Integer = power(d7) + p6 If p7 >= maxN Then Exit For Dim s7 As Integer = (s6 + d7) * 10 For d8 As Integer = f(8) To t(8) Dim p8 As Integer = power(d8) + p7 If p8 >= maxN Then Exit For Dim s8 As Integer = (s7 + d8) * 10 If s8 = p8 Then ' found a number with 0 as the final digit ' the same number with a final digit of 1 ' must also match the requirements Console.Out.WriteLine(s8) Console.Out.WriteLine(s8 + 1) End If For d9 As Integer = 2 To 9 Dim p9 As Integer = power(d9) + p8 If p9 >= maxN Then Exit For Dim s9 As Integer = s8 + d9 If s9 = p9 Then Console.Out.WriteLine(s9) End If Next d9 Next d8 Next d7 Next d6 Next d5 Next d4 Next d3 Next d2 Next d1 Next n End Sub
End Module</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Real time: 7.553 s
User time: 7.044 s
Sys. time: 0.290 s on TIO.RUN using Visual Basic .NET (VBC)
Wren
Includes some simple optimizations to try and quicken up the search. However, getting up to N = 9 still took a little over 4 minutes on my machine. <lang ecmascript>import "./math" for Int
var powers = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] System.print("Own digits power sums for N = 3 to 9 inclusive:") for (n in 3..9) {
for (d in 2..9) powers[d] = powers[d] * d var i = 10.pow(n-1) var max = i * 10 var lastDigit = 0 var sum = 0 var digits = null while (i < max) { if (lastDigit == 0) { digits = Int.digits(i) sum = digits.reduce(0) { |acc, d| acc + powers[d] } } else if (lastDigit == 1) { sum = sum + 1 } else { sum = sum + powers[lastDigit] - powers[lastDigit-1] } if (sum == i) { System.print(i) if (lastDigit == 0) System.print(i + 1) i = i + 10 - lastDigit lastDigit = 0 } else if (sum > i) { i = i + 10 - lastDigit lastDigit = 0 } else if (lastDigit < 9) { i = i + 1 lastDigit = lastDigit + 1 } else { i = i + 1 lastDigit = 0 } }
}</lang>
- Output:
Own digits power sums for N = 3 to 9 inclusive: 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153