Digit sum of powers in bases

Question

You should write a program or function which outputs or returns the sum of the digits in base b representation of the first n natural power of a in ascending order.

Example for a = 2, b = 3 and n = 4

The base10 numbers are 2^0, 2^1, 2^2 and 2^3.
Their base3 representations are 1, 2, 11, 22.
The digit sums are 1, 2, 2, 4.
The sorted digit sums are 1, 2, 2, 4 which is the result.

Input

• 3 integers a > 1, b > 1 andn > 0

Output

• A list of integers

Examples

Input => Output

2 5 10 => 1 2 4 4 4 4 4 4 8 8
3 2 20 => 1 2 2 3 4 5 6 6 6 8 9 10 11 11 13 14 14 14 15 17
5 6 1 => 1
6 6 11 => 1 1 1 1 1 1 1 1 1 1 1
6 8 20 => 1 6 6 8 8 8 13 13 15 20 22 22 22 27 29 34 34 34 36 41
8 2 10 => 1 1 1 1 1 1 1 1 1 1
15 17 18 => 1 15 17 31 31 33 49 49 63 65 81 95 95 95 95 113 127 129

This is code-golf so shortest code wins.

Answer 1

Pyth, 11

Smsj^vzdQvw

Note that this requires the inputs separated by newlines in the order a,b,n.

Try it online here

Pyth has built-ins that do each step for us. We map over each value from 0 to n-1, raising a to that power. Then we use j to convert each of these numbers to base b. We sum the resulting lists, and the final list of numbers is Sorted.

The input is read in the order z, Q then w. z and w have to be evaled in order to be used as numbers.

Answer 2

CJam, 13 bytes

q~,f#\fb::+$p

I think this can be improved, but lets get this started.

The input is in the following order : b a n

Example input:

3 2 4

Output:

[1 2 2 4]

Code expansion:

q~             "Read the input and parse it. Now we have on stack, b a and n"
  ,            "Get an array from 0 to n-1";
   f#          "Get all the powers of a present in the array, i.e. 0 to n-1";
     \         "Swap the array of a^i and bring the base on top";
      fb       "For each number in the array, convert it into its base representation array";
        ::+    "Calculate the sum of each of the sub arrays in the bigger array";
           $p  "Sort and print the sum of digits of base representation of n powers of a";

Try it online here

Answer 3

JavaScript (ES6) 170 175 196 98 100

Edit New version, handles bigger numbers using digits array. Score almost doubled :-(

Multiplying digit by digit is more difficult, summing the digits is simpler.

F=(a,b,n)=>
  (t=>{
    for(r=t;--n;r[n]=s)
      for(k=1,y=t,z=a;z;z=z/b|0)
        t=[...t.map(v=>(v=c+(k?w*~~y[i++]+v:w*v),s+=d=v%b,c=v/b|0,d),
           w=z%b,s=c=0,i=--k),c]       
  })([1])||r.sort((a,b)=>a-b)

Less golfed

F=(a, b, n) =>
{
  var r=[1]; // power 0 in position 0

  for(w=[]; w.push(a%b),a=a/b|0; ); // a in base b

  for(t = [1]; --n; )
  {
    // calc next power, meanwhile compute digits sum
    y=[...t]
    k=1
    w.map(w=>
      (t=[...t.map(v=>(
        v = c + (k?w*~~y[i++]+v:w*v), 
        d = v % b, // current digit
        s += d, // digits sum
        c = (v-d)/b, // carry
        d)
       ,s=c=0,i=--k),c]
      )
    ); 
    r[n] = s // store sum in result array (positions n-1..1)
  }
  return r.sort((a,b)=>a-b) // sort result in numeric order
}

My first attempt using doubles, fails for big numbers. JS doubles have 52 mantissa bits when for instance 15^14 needs 55 bits.

F=(a,b,n,r=[1])=>(x=>{for(;--n;r[n]=s)for(t=x*=a,s=0;t;t=(t-d)/b)s+=d=t%b})(1)
||r.sort((a,b)=>a-b)

Less golfed

F=(a, b, n) =>
{
  var r=[1]; // power 0 in position 0
  for(x = 1; --n; )
  {
    x *= a; // calc next power starting at 1
    for(t = x, s = 0; t; t = (t-d) / b) // loop to find digits
    {
      d = t % b;
      s += d;
    }
    r[n] = s // store sum in result array (positions n-1..1)
  }
  return r.sort((a,b)=>a-b) // sort result in numeric order
}

Test In Firefox/FireBug console

;[[2,5,10],[3,2,20],[5,6,1],[6,6,11],[6,8,20],[8,2,10],[15,17,18]]
.forEach(t=>console.log(...t,F(...t)))

2 5 10 [1, 2, 4, 4, 4, 4, 4, 4, 8, 8]
3 2 20 [1, 2, 2, 3, 4, 5, 6, 6, 6, 8, 9, 10, 11, 11, 13, 14, 14, 14, 15, 17]
5 6 1 [1]
6 6 11 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
6 8 20 [1, 6, 6, 8, 8, 8, 13, 13, 15, 20, 22, 22, 22, 27, 29, 34, 34, 34, 36, 41]
8 2 10 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
15 17 18 [1, 15, 17, 31, 31, 33, 49, 49, 63, 65, 81, 95, 95, 95, 95, 113, 127, 129]

Answer 4

A purely mathematical equation on the Cartesian Plane, written in LaTeX: Unknown size, incomplete

Demonstrated here: https://www.desmos.com/calculator/svpkyarzxh

a, b, and n are adjustable inputs.

To avoid spaghetti code, it's split into two functions, although it could be condensed.

f\left(x\right)=\floor \left(x-\left(b-1\right)\sum _{i=1}^{\log _bx}\floor \left(xb^{-i}\right)\right)
y=f\left(a^{\floor \left(x\right)}\right)\left\{0<x\le n\right\}

I'm not sure how to put the values in an adjustable list or sort the list without using an actual programming language. However, the fact that this equation allows you to put it on a programmable graphing calculator and figure out the rest from there. I know it can be done in TI-BASIC, but I'm too busy to put an example here.

Answer 5

Mathematica, 43 41 bytes

Sort[Tr/@IntegerDigits[#^Range@#3/#,#2]]&

Very straightforward and apart from the slight abuse of Tr very readable. This is an unnamed function which is called with the three parameters in order.

Example outputs:

f=Sort[Tr/@IntegerDigits[#^Range@#3/#,#2]]&
f[2, 5, 10]
(* {1, 2, 4, 4, 4, 4, 4, 4, 8, 8} *)
f[3, 2, 20]
(* {1, 2, 2, 3, 4, 5, 6, 6, 6, 8, 9, 10, 11, 11, 13, 14, 14, 14, 15, 17} *)
f[5, 6, 1]
(* {1} *)
f[6, 6, 11]
(* {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} *)
f[6, 8, 20]
(* {1, 6, 6, 8, 8, 8, 13, 13, 15, 20, 22, 22, 22, 27, 29, 34, 34, 34, 36, 41} *)
f[8, 2, 10]
(* {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} *)
f[15, 17, 18]
(* {1, 15, 17, 31, 31, 33, 49, 49, 63, 65, 81, 95, 95, 95, 95, 113, 127, 129} *)

Two bytes saved thanks to alephalpha.

Answer 6

J - 19

/:~+/"1#.inv`(^i.)/

Takes numbers in that order: b a c

Usage example (x stands for extended precision):

   /:~+/"1#.inv`(^i.)/ 5 2 10
1 2 4 4 4 4 4 4 8 8
   /:~+/"1#.inv`(^i.)/ 17 15x 18
1 15 17 31 31 33 49 49 63 65 81 95 95 95 95 113 127 129

Answer 7

Haskell, 79 bytes

import Data.Digits
import Data.List
f a b n=sort$map(sum.digits b.(a^))[0..n-1]

Usage: f 6 8 20, output: [1,6,6,8,8,8,13,13,15,20,22,22,22,27,29,34,34,34,36,41]

This is a typical Haskell function: straight forward, same as ungolfed version but the imports ruin the golf score: for every element e of the list from 0 to n-1 calculate a^e, convert to a list of base b digits and sum it. Sort the resulting list.