5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can I take a,b,n separated by newlines as input to my program? \$\endgroup\$ – FryAmTheEggman Mar 9 '15 at 15:32
  • \$\begingroup\$ @FryAmTheEggman Any reasonable input format is fine. \$\endgroup\$ – randomra Mar 9 '15 at 22:13
4
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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

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

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]

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

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.

\$\endgroup\$
2
\$\begingroup\$

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.

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

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.