# Digit sum of powers in bases

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.

• Can I take a,b,n separated by newlines as input to my program? Commented Mar 9, 2015 at 15:32
• @FryAmTheEggman Any reasonable input format is fine. Commented Mar 9, 2015 at 22:13

# 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

• The browser version runs out of precision for the "15 17 18" test case. Commented Mar 17, 2015 at 1:17
• @JohnE Did you input in the correct order? i.e. 17 15 18 Commented Mar 17, 2015 at 4:58
• Ah, you're right- does work as expected with that input format. My apologies. Commented Mar 17, 2015 at 5:00

# 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.

# 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]

• Your last test case seems to be wrong... Commented Mar 9, 2015 at 9:46
• I don't know JS, but probably can't handle big (15^17) integers. Commented Mar 9, 2015 at 10:16
• @randomra maybe, but 15^17 is not so big Commented Mar 9, 2015 at 10:18
• right, 15^17 is so big indeed, 63 bits. With double the limit is 52 (near 15^13) Commented Mar 9, 2015 at 10:27

# 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.

# 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.

• Martin can you post some example output? I trust Mathematica more than OP Commented Mar 9, 2015 at 9:28
• Sort[Tr/@IntegerDigits[#^Range@#3/#,#2]]& Commented Mar 9, 2015 at 10:19
• @alephalpha Ah, neat :) Commented Mar 9, 2015 at 10:33
• @edc65 Added all the example outputs. Commented Mar 9, 2015 at 10:37

## 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


# APL (Dyalog Unicode), 29 24 bytes

{(⊂∘⍋⌷⊢)+⌿⍵(⊥⍣¯1)∊*∘⍳/⍺}


-5 bytes from Jo King.

Takes inputs as a n function b.

Try it online!

{(⊂∘⍋⌷⊢)+⌿(⊃⌽⍵)(⊥⍣¯1)(⊃⍵)*⍳⍺}


Takes inputs as n function a b

Thanks to Jo King for helping me fix this answer.

Try it online!

## Explanation

{(⊂∘⍋⌷⊢)+⌿(⊃⌽⍵)(⊥⍣¯1)(⊃⍵)*⍳⍺} ⍺ → n, ⍵ → [a,b]
⍳⍺  range (1..n)
(⊃⍵)*    a to the power of the range
(⊃⌽⍵)               take b from reverse of ⍵
(⊥⍣¯1)         inverse encode(decode) using b till it reaches zero
i.e: sum the columns
(⊂∘⍋⌷⊢)                      tacit fn:
⍋                         Get indices for ascending order
⌷                        Get elements at those indices
⊢                       From the right arg
⊂                           Enclose it


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.

# Jelly, 7 bytes

Ḷ*@b⁵§Ṣ


Try it online!

Takes input as 3 command line arguments, $$\n\$$, $$\a\$$ then $$\b\$$.

## How it works

Ḷ*@b⁵§Ṣ - Main link. n on the left, a on the right and b as the 3rd argument
Ḷ       - Range [0, 1, ..., n-1]
*@     - Take a to the power of each [1, a, ..., a^(n-1)]
⁵   - Yield b
b    - Convert each power to base b
§  - Take the digit sums of each
Ṣ - Sort the digit sums


# Husk, 13 bytes

OmoΣB²z^R¹⁴ŀ


Try it online!

## Explanation

OmoΣB²z^R¹⁴ŀ
ŀ range from 0..n-1
R¹⁴  a replicated n times
z^     zip both with power
moΣB²        convert each power to base n, and sum digits
O             Sort in ascending order