Exponential digital sums: Difference between revisions
Thundergnat (talk | contribs) m (→{{header|Raku}}: typo) |
|||
Line 29: | Line 29: | ||
=={{header|Phix}}== |
|||
Same approach as Wren, but using digitwise maths and reduced limits on the second part to keep things sane. |
|||
<!--<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;">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: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nFirst eighteen that satisfy that condition in three or more ways:\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">--exponential_digital_sums(30, 3, 500) -- 48s, output matches Wren</span> |
|||
<span style="color: #000000;">exponential_digital_sums</span><span style="color: #0000FF;">(</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">150</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 2.6s on the desktop, 3.1s in a web browser</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>--> |
|||
{{out}} |
|||
<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 eighteen 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 |
|||
"2.6s" |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
Revision as of 02:17, 11 August 2023
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.
- 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.
Phix
Same approach as Wren, but using digitwise maths and reduced limits on the second part to keep things sane.
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 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) printf(1,"\nFirst eighteen that satisfy that condition in three or more ways:\n") --exponential_digital_sums(30, 3, 500) -- 48s, output matches Wren exponential_digital_sums(18, 3, 150) -- 2.6s on the desktop, 3.1s in a web browser ?elapsed(time()-t0)
- 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 eighteen 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 "2.6s"
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.
This agrees with the Raku solution for the first part but finds some other qualifying numbers for the second part.
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.
Arguably both 0 and 1 should qualify as all their powers will have digit sums of 0 and 1 respectively. However, as the Raku solution hasn't included them, neither have I.
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 { |max, minWays, limit|
var i = Mpz.one
var c = 0
var n = Mpz.new()
while (c < max) {
i.inc
n.set(i)
var p = 1
var res = []
while (p < limit) {
n.mul(i)
p = p + 1
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