Exponential digital sums
Some integers (greater than 1), have the property that the digital sum of that integer raised to some integer power greater than 1, is equal to the original integer.
You are encouraged to solve this task according to the task description, using any language you may know.
- E.G.
92 == 81 8 + 1 == 9
Some integers have this property using more than one exponent.
183 == 5832 5 + 8 + 3 + 2 == 18 186 == 34012224 3 + 4 + 0 + 1 + 2 + 2 + 2 + 4 == 18 187 == 612220032 6 + 1 + 2 + 2 + 2 + 0 + 0 + 3 + 2 == 18
Note: every integer has an exponential digital sum equal to the original integer when using an exponent of 1. And, 0 and 1 raised to any power will have a digital sum of 0 and 1 respectively.
- Task
- Find and show the first twenty integers (with their exponents), that satisfy this condition.
- Find and show at least the first ten integers with their exponents, that satisfy this condition in three or more ways.
C++
#include <iostream>
#include <vector>
#include <gmpxx.h>
using big_int = mpz_class;
int digit_sum(const big_int& n) {
int sum = 0;
for (char c : n.get_str())
sum += c - '0';
return sum;
}
void exp_digit_sums(int count, int min_ways, int max_power) {
for (int i = 2; count > 0; ++i) {
big_int n = i;
std::vector<int> powers;
for (int p = 2; p <= max_power; ++p) {
n *= i;
if (digit_sum(n) == i)
powers.push_back(p);
}
if (powers.size() >= min_ways) {
--count;
auto it = powers.begin();
std::cout << i << "^" << *it++;
for (; it != powers.end(); ++it)
std::cout << ", " << i << "^" << *it;
std::cout << '\n';
}
}
}
int main() {
std::cout << "First twenty-five integers that are equal to the digital sum "
"of that integer raised to some power:\n";
exp_digit_sums(25, 1, 100);
std::cout << "\nFirst thirty that satisfy that condition in three or more "
"ways:\n";
exp_digit_sums(30, 3, 500);
}
- Output:
First twenty-five integers that are equal to the digital sum of that integer raised to some power: 7^4 8^3 9^2 17^3 18^3, 18^6, 18^7 20^13 22^4 25^4 26^3 27^3, 27^7 28^4, 28^5 31^7 34^7 35^5 36^4, 36^5 40^13 43^7 45^6 46^5, 46^8 53^7 54^6, 54^8, 54^9 58^7 63^8 64^6 68^7 First thirty that satisfy that condition in three or more ways: 18^3, 18^6, 18^7 54^6, 54^8, 54^9 90^19, 90^20, 90^21, 90^22, 90^28 107^11, 107^13, 107^15 181^16, 181^18, 181^19, 181^20 360^45, 360^46, 360^49, 360^51 370^48, 370^54, 370^57, 370^59 388^32, 388^35, 388^36 523^39, 523^42, 523^44, 523^45 603^44, 603^47, 603^54 667^48, 667^54, 667^58 793^57, 793^60, 793^64 1062^72, 1062^77, 1062^81 1134^78, 1134^80, 1134^82, 1134^86 1359^92, 1359^98, 1359^102 1827^121, 1827^126, 1827^131 1828^123, 1828^127, 1828^132 2116^140, 2116^143, 2116^147 2330^213, 2330^215, 2330^229 2430^217, 2430^222, 2430^223, 2430^229, 2430^230 2557^161, 2557^166, 2557^174 2610^228, 2610^244, 2610^246 2656^170, 2656^172, 2656^176 2700^406, 2700^414, 2700^420, 2700^427 2871^177, 2871^189, 2871^190 2934^191, 2934^193, 2934^195 3077^187, 3077^193, 3077^199 3222^189, 3222^202, 3222^210 3231^203, 3231^207, 3231^209 3448^215, 3448^221, 3448^227
Delphi
Program expdigitsums;
{$APPTYPE CONSOLE}
Uses
System.Sysutils,
System.Generics.Collections,
Velthuis.Bigintegers;
Function Digital_sum(J: Biginteger): Integer;
Var
Temp: String;
I: Integer;
Begin
Result := 0;
Temp := J.Tostring;
For I := 1 To Length(Temp) Do
Result := Result + Ord(Temp[I]) - Ord('0');
End;
Procedure Exp_digit_sums(Cnt, Min_ways, Max_power: Integer);
Type
Power = Record
A, B: Integer;
End;
Var
Count, X: Integer;
Pw: Biginteger;
List: Tlist<Power>;
Ppower: Power;
Begin
List := Tlist<Power>.Create;
Count := 0;
X := 1;
While Count < Cnt Do
Begin
Inc(X);
For Var I := 2 To Max_power Do
Begin
Pw := Biginteger.Pow(X, I);
If X = Digital_sum(Pw) Then
Begin
Ppower.A := X;
Ppower.B := I;
List.Add(Ppower);
End;
End;
If List.Count >= Min_ways Then
Begin
Inc(Count);
For Ppower In List Do
Write(Ppower.A, '^', Ppower.B, ' ');
Writeln;
End;
List.Clear;
End;
End;
Begin
Writeln('First twenty-five integers that are equal to the digital sum of that integer raised to some power:');
Exp_digit_sums(25, 1, 100);
Writeln;
Writeln('First thirty that satisfy that condition in three or more ways:');
Exp_digit_sums(30, 3, 500);
Readln;
End..
- Output:
First twenty-five integers that are equal to the digital sum of that integer raised to some power: 7^4 8^3 9^2 17^3 18^3, 18^6, 18^7 20^13 22^4 25^4 26^3 27^3, 27^7 28^4, 28^5 31^7 34^7 35^5 36^4, 36^5 40^13 43^7 45^6 46^5, 46^8 53^7 54^6, 54^8, 54^9 58^7 63^8 64^6 68^7 First thirty that satisfy that condition in three or more ways: 18^3, 18^6, 18^7 54^6, 54^8, 54^9 90^19, 90^20, 90^21, 90^22, 90^28 107^11, 107^13, 107^15 181^16, 181^18, 181^19, 181^20 360^45, 360^46, 360^49, 360^51 370^48, 370^54, 370^57, 370^59 388^32, 388^35, 388^36 523^39, 523^42, 523^44, 523^45 603^44, 603^47, 603^54 667^48, 667^54, 667^58 793^57, 793^60, 793^64 1062^72, 1062^77, 1062^81 1134^78, 1134^80, 1134^82, 1134^86 1359^92, 1359^98, 1359^102 1827^121, 1827^126, 1827^131 1828^123, 1828^127, 1828^132 2116^140, 2116^143, 2116^147 2330^213, 2330^215, 2330^229 2430^217, 2430^222, 2430^223, 2430^229, 2430^230 2557^161, 2557^166, 2557^174 2610^228, 2610^244, 2610^246 2656^170, 2656^172, 2656^176 2700^406, 2700^414, 2700^420, 2700^427 2871^177, 2871^189, 2871^190 2934^191, 2934^193, 2934^195 3077^187, 3077^193, 3077^199 3222^189, 3222^202, 3222^210 3231^203, 3231^207, 3231^209 3448^215, 3448^221, 3448^227
Java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public final class ExponentialDigitalSums {
public static void main(String[] args) {
System.out.println(
"The first 25 integers that are equal to the digital sum of that integer raised to some power:");
exponentialDigitalSums(25, 1, 100);
System.out.println();
System.out.println("The first 30 integers that satisfy the same condition in three or more ways:");
exponentialDigitalSums(30, 3, 500);
}
private static void exponentialDigitalSums(int resultsCount, int minWays, int maxPower) {
BigInteger number = BigInteger.ONE;
BigInteger copyNumber = BigInteger.ONE;
int count = 0;
while ( count < resultsCount ) {
number = number.add(BigInteger.ONE);
copyNumber = number;
List<String> result = new ArrayList<String>();
for ( int power = 2; power < maxPower; power++ ) {
copyNumber = copyNumber.multiply(number);
final int digitalSum = digitalSum(copyNumber);
if ( number.equals(BigInteger.valueOf(digitalSum)) ) {
result.add(number + "^" + power);
}
}
if ( result.size() >= minWays ) {
System.out.println(result.stream().collect(Collectors.joining(", ")));
count += 1;
}
}
}
private static int digitalSum(BigInteger number) {
return number.toString().chars().mapToObj( i -> (int) ( i - '0' ) )
.collect(Collectors.summingInt(Integer::intValue));
}
}
- Output:
The first 25 integers that are equal to the digital sum of that integer raised to some power: 7^4 8^3 9^2 17^3 18^3, 18^6, 18^7 20^13 22^4 25^4 26^3 27^3, 27^7 28^4, 28^5 31^7 34^7 35^5 36^4, 36^5 40^13 43^7 45^6 46^5, 46^8 53^7 54^6, 54^8, 54^9 58^7 63^8 64^6 68^7 The first 30 integers that satisfy the same condition in three or more ways: 18^3, 18^6, 18^7 54^6, 54^8, 54^9 90^19, 90^20, 90^21, 90^22, 90^28 107^11, 107^13, 107^15 181^16, 181^18, 181^19, 181^20 360^45, 360^46, 360^49, 360^51 370^48, 370^54, 370^57, 370^59 388^32, 388^35, 388^36 523^39, 523^42, 523^44, 523^45 603^44, 603^47, 603^54 667^48, 667^54, 667^58 793^57, 793^60, 793^64 1062^72, 1062^77, 1062^81 1134^78, 1134^80, 1134^82, 1134^86 1359^92, 1359^98, 1359^102 1827^121, 1827^126, 1827^131 1828^123, 1828^127, 1828^132 2116^140, 2116^143, 2116^147 2330^213, 2330^215, 2330^229 2430^217, 2430^222, 2430^223, 2430^229, 2430^230 2557^161, 2557^166, 2557^174 2610^228, 2610^244, 2610^246 2656^170, 2656^172, 2656^176 2700^406, 2700^414, 2700^420, 2700^427 2871^177, 2871^189, 2871^190 2934^191, 2934^193, 2934^195 3077^187, 3077^193, 3077^199 3222^189, 3222^202, 3222^210 3231^203, 3231^207, 3231^209 3448^215, 3448^221, 3448^227
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
gojq has infinite-precision integer arithmetic, but when working on the second task, becomes noticeably slow after producing the first ten lines or so.
# whilst/2 is like while/2 but emits the final term rather than the first one
def whilst(cond; update):
def _whilst:
if cond then update | (., _whilst) else empty end;
_whilst;
def digitSum:
def add(s): reduce s as $_ (0; . + $_);
add(tostring | explode[] | . - 48);
def expDigitSums(numNeeded; minWays; maxPower):
{i: 1, c: 0}
| whilst(.c < numNeeded;
.i += 1
| .n = .i
| reduce range(2; 1+ maxPower) as $p (.res = [];
.n *= .i
| if .i == (.n|digitSum)
then .res += ["\(.i)^\($p)"]
end)
| if .res|length >= minWays
then .c += 1
end )
| select(.res|length >= minWays)
| .res | join(", ");
"First twenty-five integers that are equal to the digital sum of that integer raised to some power:",
expDigitSums(25; 1; 100),
"\nFirst thirty that satisfy that condition in three or more ways:",
expDigitSums(30; 3; 500)
- Output:
First twenty-five integers that are equal to the digital sum of that integer raised to some power: 7^4 8^3 9^2 17^3 18^3, 18^6, 18^7 20^13 22^4 25^4 26^3 27^3, 27^7 28^4, 28^5 31^7 34^7 35^5 36^4, 36^5 40^13 43^7 45^6 46^5, 46^8 53^7 54^6, 54^8, 54^9 58^7 63^8 64^6 68^7 First thirty that satisfy that condition in three or more ways: 18^3, 18^6, 18^7 54^6, 54^8, 54^9 90^19, 90^20, 90^21, 90^22, 90^28 107^11, 107^13, 107^15 181^16, 181^18, 181^19, 181^20 360^45, 360^46, 360^49, 360^51 370^48, 370^54, 370^57, 370^59 388^32, 388^35, 388^36 523^39, 523^42, 523^44, 523^45 603^44, 603^47, 603^54 667^48, 667^54, 667^58 793^57, 793^60, 793^64 1062^72, 1062^77, 1062^81 1134^78, 1134^80, 1134^82, 1134^86 1359^92, 1359^98, 1359^102 1827^121, 1827^126, 1827^131 1828^123, 1828^127, 1828^132 2116^140, 2116^143, 2116^147 2330^213, 2330^215, 2330^229 2430^217, 2430^222, 2430^223, 2430^229, 2430^230 2557^161, 2557^166, 2557^174 2610^228, 2610^244, 2610^246 2656^170, 2656^172, 2656^176 2700^406, 2700^414, 2700^420, 2700^427 2871^177, 2871^189, 2871^190 2934^191, 2934^193, 2934^195 3077^187, 3077^193, 3077^199 3222^189, 3222^202, 3222^210 3231^203, 3231^207, 3231^209 3448^215, 3448^221, 3448^227
Julia
function equal_digitalsum_exponents(n::Integer)
equalpows = Int[]
if n > 1
npow, misses = 2, 0
while misses < n + 50
dsum = sum(digits(BigInt(n) ^ npow))
if npow > 10 && dsum > 2 * n
break # bail here for time contraints (see Wren example)
elseif dsum == n
push!(equalpows, npow)
else
misses += 1
end
npow += 1
end
end
return equalpows
end
function testdigitalequals(lim, wanted, multiswanted)
found1, found2, multis = 0, 0, Tuple{Int, Vector{Int}}[]
println("First $wanted integers that are equal to the digital sum of that integer raised to some power:")
for i in 1:lim
a = equal_digitalsum_exponents(i)
if !isempty(a)
found1 += 1
if found1 <= wanted
print(rpad(i, 6), found1 % 10 == 0 ? "\n" : "")
end
if length(a) > 2
found2 += 1
push!(multis, (i, a))
if found2 == multiswanted
println("\nFirst $multiswanted that satisfy that condition in three or more ways:")
for (n, v) in multis
println("$n: powers $v")
end
end
found1 >= wanted && found2 >= multiswanted && break
end
end
end
end
testdigitalequals(6000, 25, 30)
- Output:
First 25 integers that are equal to the digital sum of that integer raised to some power: 7 8 9 17 18 20 22 25 26 27 28 31 34 35 36 40 43 45 46 53 54 58 63 64 68 First 30 that satisfy that condition in three or more ways: 18: powers [3, 6, 7] 54: powers [6, 8, 9] 90: powers [19, 20, 21, 22, 28] 107: powers [11, 13, 15] 181: powers [16, 18, 19, 20] 360: powers [45, 46, 49, 51] 370: powers [48, 54, 57, 59] 388: powers [32, 35, 36] 523: powers [39, 42, 44, 45] 603: powers [44, 47, 54] 667: powers [48, 54, 58] 793: powers [57, 60, 64] 1062: powers [72, 77, 81] 1134: powers [78, 80, 82, 86] 1359: powers [92, 98, 102] 1827: powers [121, 126, 131] 1828: powers [123, 127, 132] 2116: powers [140, 143, 147] 2330: powers [213, 215, 229] 2430: powers [217, 222, 223, 229, 230] 2557: powers [161, 166, 174] 2610: powers [228, 244, 246] 2656: powers [170, 172, 176] 2700: powers [406, 414, 420, 427] 2871: powers [177, 189, 190] 2934: powers [191, 193, 195] 3077: powers [187, 193, 199] 3222: powers [189, 202, 210] 3231: powers [203, 207, 209] 3448: powers [215, 221, 227]
Phix
Same approach as Wren, but using digitwise maths and calculating the digital sum at the same time.
with javascript_semantics
procedure exponential_digital_sums(integer showfirst, minways, maxpower)
integer i = 1, shown = 0
while shown<showfirst do
i += 1
sequence n = {i}, res = {}
for p=2 to maxpower do
integer ds = 0, d
atom carry = 0
for j=1 to length(n) do
carry += n[j]*i
d = remainder(carry,10)
carry = floor(carry/10)
n[j] = d
ds += d
end for
while carry do
d = remainder(carry,10)
carry = floor(carry/10)
n &= d
ds += d
end while
if p>10 and ds>2*i then exit end if
if ds=i then
res = append(res,sprintf("%d^%d",{i,p}))
end if
end for
if length(res)>=minways then
printf(1,"%s\n",{join(res,", ")})
shown += 1
end if
end while
end procedure
atom t0 = time()
printf(1,"First twenty-five integers that are equal to the digital sum of that integer raised to some power:\n")
exponential_digital_sums(25, 1, 100)
integer {n,mp} = iff(platform()=JS?{18,150}:{30,500}) -- 14.4s on desktop, up to 2116 in 3.1s on JS
printf(1,"\nFirst %s that satisfy that condition in three or more ways:\n",{ordinal(n,true)})
exponential_digital_sums(n, 3, mp)
?elapsed(time()-t0)
Output same as Wren/Raku, second part stops on the 18th (2116) under JS but would match after a 26.5s blank screen if you used the same limits
Python
""" rosettacode.org/wiki/Exponential_digital_sums """
def equal_digitalsum_exponents(num):
""" return any equal exponential digital sums in an array """
equalpows = []
if num > 1:
npow, misses = 2, 0
while misses < num + 20:
dsum = sum(map(int, str(num**npow)))
if npow > 10 and dsum > 2 * num:
break # bail here for time contraints (see Wren example)
if dsum == num:
equalpows.append(npow)
else:
misses += 1
npow += 1
return equalpows
if __name__ == '__main__':
found1, found2, multis = 0, 0, []
print('First 25 integers that are equal to the digital sum of the number raised to some power:')
for i in range(1, 4000):
a = equal_digitalsum_exponents(i)
if a:
S_EXP = ', '.join(f'{i}^{j}' for j in a)
found1 += 1
if found1 <= 25:
print(S_EXP)
if len(a) > 2:
found2 += 1
multis.append(S_EXP)
if found2 == 30:
print(
'\n\nFirst 30 that satisfy that condition in three or more ways:')
for grp in multis:
print(grp)
if found1 >= 25 and found2 >= 30:
break
- Output:
Same as Raku.
Raku
Implement a lazy generator. Made some assumptions about search limits. May be poor assumptions, but haven't been able to find any counterexamples. (Edit: and some were bad.)
my @expsum = lazy (2..*).hyper.map( -> $Int {
my atomicint $miss = 0;
(2..$Int).map( -> $exp {
if (my $sum = ($Int ** $exp).comb.sum) > $Int { last if ++⚛$miss > 20 }
$sum == $Int ?? "$Int^$exp" !! Empty;
}) || Empty;
});
say "First twenty-five integers that are equal to the digital sum of that integer raised to some power:";
put .join(', ') for @expsum[^25];
say "\nFirst thirty that satisfy that condition in three or more ways:";
put .join(', ') for @expsum.grep({.elems≥3})[^30];
- Output:
First twenty-five integers that are equal to the digital sum of that integer raised to some power: 7^4 8^3 9^2 17^3 18^3, 18^6, 18^7 20^13 22^4 25^4 26^3 27^3, 27^7 28^4, 28^5 31^7 34^7 35^5 36^4, 36^5 40^13 43^7 45^6 46^5, 46^8 53^7 54^6, 54^8, 54^9 58^7 63^8 64^6 68^7 First thirty that satisfy that condition in three or more ways: 18^3, 18^6, 18^7 54^6, 54^8, 54^9 90^19, 90^20, 90^21, 90^22, 90^28 107^11, 107^13, 107^15 181^16, 181^18, 181^19, 181^20 360^45, 360^46, 360^49, 360^51 370^48, 370^54, 370^57, 370^59 388^32, 388^35, 388^36 523^39, 523^42, 523^44, 523^45 603^44, 603^47, 603^54 667^48, 667^54, 667^58 793^57, 793^60, 793^64 1062^72, 1062^77, 1062^81 1134^78, 1134^80, 1134^82, 1134^86 1359^92, 1359^98, 1359^102 1827^121, 1827^126, 1827^131 1828^123, 1828^127, 1828^132 2116^140, 2116^143, 2116^147 2330^213, 2330^215, 2330^229 2430^217, 2430^222, 2430^223, 2430^229, 2430^230 2557^161, 2557^166, 2557^174 2610^228, 2610^244, 2610^246 2656^170, 2656^172, 2656^176 2700^406, 2700^414, 2700^420, 2700^427 2871^177, 2871^189, 2871^190 2934^191, 2934^193, 2934^195 3077^187, 3077^193, 3077^199 3222^189, 3222^202, 3222^210 3231^203, 3231^207, 3231^209 3448^215, 3448^221, 3448^227
Wren
Well, as the digital sums are all over the place, it's difficult to know how many powers of each number should be tested to solve the task. We therefore have to make an educated guess.
Although it would be possible to use BigInt for this, GMP has been used instead to quicken up the search but even so still takes 110 seconds to run.
import "./gmp" for Mpz
var digitSum = Fn.new { |bi|
var sum = 0
for (d in bi.toString.bytes) {
sum = sum + d - 48
}
return sum
}
var expDigitSums = Fn.new { |numNeeded, minWays, maxPower|
var i = Mpz.one
var c = 0
var n = Mpz.new()
while (c < numNeeded) {
i.inc
n.set(i)
var res = []
for (p in 2..maxPower) {
n.mul(i)
var ds = digitSum.call(n)
if (i == ds) {
res.add("%(i)^%(p)")
}
}
if (res.count >= minWays) {
System.print(res.join(", "))
c = c + 1
}
}
}
System.print("First twenty-five integers that are equal to the digital sum of that integer raised to some power:")
expDigitSums.call(25, 1, 100)
System.print("\nFirst thirty that satisfy that condition in three or more ways:")
expDigitSums.call(30, 3, 500)
- Output:
First twenty-five integers that are equal to the digital sum of that integer raised to some power: 7^4 8^3 9^2 17^3 18^3, 18^6, 18^7 20^13 22^4 25^4 26^3 27^3, 27^7 28^4, 28^5 31^7 34^7 35^5 36^4, 36^5 40^13 43^7 45^6 46^5, 46^8 53^7 54^6, 54^8, 54^9 58^7 63^8 64^6 68^7 First thirty that satisfy that condition in three or more ways: 18^3, 18^6, 18^7 54^6, 54^8, 54^9 90^19, 90^20, 90^21, 90^22, 90^28 107^11, 107^13, 107^15 181^16, 181^18, 181^19, 181^20 360^45, 360^46, 360^49, 360^51 370^48, 370^54, 370^57, 370^59 388^32, 388^35, 388^36 523^39, 523^42, 523^44, 523^45 603^44, 603^47, 603^54 667^48, 667^54, 667^58 793^57, 793^60, 793^64 1062^72, 1062^77, 1062^81 1134^78, 1134^80, 1134^82, 1134^86 1359^92, 1359^98, 1359^102 1827^121, 1827^126, 1827^131 1828^123, 1828^127, 1828^132 2116^140, 2116^143, 2116^147 2330^213, 2330^215, 2330^229 2430^217, 2430^222, 2430^223, 2430^229, 2430^230 2557^161, 2557^166, 2557^174 2610^228, 2610^244, 2610^246 2656^170, 2656^172, 2656^176 2700^406, 2700^414, 2700^420, 2700^427 2871^177, 2871^189, 2871^190 2934^191, 2934^193, 2934^195 3077^187, 3077^193, 3077^199 3222^189, 3222^202, 3222^210 3231^203, 3231^207, 3231^209 3448^215, 3448^221, 3448^227
After studying changes in the digital sum as the power increases, one thing I've noticed is that once you get past the first 10 powers, if the point is reached when the digital sum is more than twice the number then it seems to be safe to bail out at that point.
So, if we change the expDigitSums function to the following:
var expDigitSums = Fn.new { |numNeeded, minWays, maxPower|
var i = Mpz.one
var c = 0
var n = Mpz.new()
while (c < numNeeded) {
i.inc
n.set(i)
var res = []
for (p in 2..maxPower) {
n.mul(i)
var ds = digitSum.call(n)
if (i == ds) {
res.add("%(i)^%(p)")
}
if (p > 10 && i * 2 < ds) break // added this line
}
if (res.count >= minWays) {
System.print(res.join(", "))
c = c + 1
}
}
}
the output is the same but the time taken comes down to 36 seconds.
Not very scientific but neither for that matter is guessing how many powers to test.