Exponential digital sums

From Rosetta Code
Exponential digital sums is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.


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
                    break
                end
            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>
<!--

-->

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

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

Library: 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. 

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.

Retrieved from "https://rosettacode.org/wiki/Exponential_digital_sums?oldid=347876"