Exponential digital sums: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (13 intermediate revisions by 5 users not shown) | |||
Line 30:
=={{header|
{{trans|Wren}}
{{libheader|GMP}}
<syntaxhighlight lang="cpp">#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 << '\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);
}</syntaxhighlight>
{{out}}
<pre>
Line 102 ⟶ 105:
68^7
First
18^3, 18^6, 18^7
54^6, 54^8, 54^9
Line 121 ⟶ 124:
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
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|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.
<syntaxhighlight lang="jq">
# 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)
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="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)
</syntaxhighlight>{{out}}
<pre>
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]
</pre>
=={{header|Phix}}==
Same approach as Wren, but using digitwise maths and calculating the digital sum at the same time.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">exponential_digital_sums</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">showfirst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">minways</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxpower</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">shown</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">shown</span><span style="color: #0000FF;"><</span><span style="color: #000000;">showfirst</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">},</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">maxpower</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ds</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">i</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span>
<span style="color: #000000;">ds</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">d</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">carry</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">d</span>
<span style="color: #000000;">ds</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">d</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">></span><span style="color: #000000;">10</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">></span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d^%d"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">}))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)>=</span><span style="color: #000000;">minways</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">shown</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First twenty-five integers that are equal to the digital sum of that integer raised to some power:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">exponential_digital_sums</span><span style="color: #0000FF;">(</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mp</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">150</span><span style="color: #0000FF;">}:{</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">500</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 14.4s on desktop, up to 2116 in 3.1s on JS</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nFirst %s that satisfy that condition in three or more ways:\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">ordinal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">exponential_digital_sums</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mp</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
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
=={{header|Python}}==
<syntaxhighlight lang="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
</syntaxhighlight>{{out}} Same as Raku.
=={{header|Raku}}==
Line 200 ⟶ 493:
=={{header|Wren}}==
{{libheader|Wren-gmp}}
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.
<syntaxhighlight lang="wren">import "./gmp" for Mpz
var digitSum = Fn.new { |bi|
Line 217 ⟶ 506:
}
var expDigitSums = Fn.new { |
var i = Mpz.one
var c = 0
var n = Mpz.new()
while (c <
i.inc
n.set(i)
var res = []
n.mul(i)
var ds = digitSum.call(n)
if (i == ds) {
Line 308 ⟶ 595:
3448^215, 3448^221, 3448^227
</pre>
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:
<syntaxhighlight lang="wren">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
}
}
}</syntaxhighlight>
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.
| |||