The rice and chess problem

Question

An Indian legend tells the story of the alleged inventor of the chess game, who impressed the emperor of India with his game so much that he would get rewarded with anything asked.

The man said he wanted to be paid in rice. He wanted a grain of rice for the first square of the chessboard, two for the second, four for the third, eight for the fourth, and so on, until the 64th square.

The emperor was amazed that the man asked for such a small reward, but as his mathematicians started counting, he ended up losing one of his provinces.

Task

Given the length of the side of a hypothetical chessboard (which is 8 on a default chessboard) and the multiplier between squares (which is 2 in the legend), calculate the number of grains of rice the emperor must pay to the man.

Notes

• The side length will always be a positive integer. The multiplier could instead be any kind of rational number.

• If your language of choice can't display very large numbers, it's okay as long as your program can correctly process smaller inputs.

• Also if your language of choice rounds larger values (with exponential notations), it's okay if those values are approximately correct.

Testcases

Input (side length, multiplier) => Output
8, 2                            => 18446744073709551615
3, 6                            => 2015539
7, 1.5                          => 850161998.2854
5, -3                           => 211822152361
256, 1                          => 65536
2, 2                            => 15
2, -2                           => -5

Please note that the explicit formula

result = (multiplier ^ (side ^ 2) - 1) / (multiplier - 1)

Performs wrong on multiplier = 1, as

1 ^ (side ^ 2) - 1 = 0
1 - 1 = 0
0 / 0 != side ^ 2 (as it should be)

Scoring

This is code-golf. Shortest answer in bytes wins.

Answer 1

MATL, 6 bytes

2^:q^s

Try it online!

2^   % Take implicit input, say N, and square it: N^2
:q   % Generate array [0 1 ... N^2-1]
^    % Take implicit input, M, and compute [M^0 M^1 ... M^(N^2-1)]
s    % Sum of the array. Implicit display

Answer 2

APL, 10 bytes

⎕⊥1+0×⍳⎕*2

⎕ is used to read user input twice. If we store the side length in s and the multiplier in m, we get the following code.

m⊥1+0×⍳s*2

And here's how APL parses this code:

Answer 3

Jelly, 4 bytes

²b1ḅ

This uses the approach from @APLDude's clever APL answer.

Try it online! or verify all test cases.

How it works

²b1ḅ  Main link. Arguments: x (side length), y (multiplier)

²     Square; yield x².
 b1   Convert to base 1 (unary), yielding a list of x² ones.
   ḅ  Convert from base y to real number.
      This yields y^(x²-1) + ... + y + 1.

Answer 4

Python, 40 bytes

lambda n,m:eval('1+m*('*n*n+'0'+')'*n*n)

Generates and evaluates a string like

1+m*(1+m*(1+m*(1+m*(0))))

that encodes the sum as a Hornerized polynomial with n*n terms.

A lot of different methods gave very similar byte counts:

#String evaluation
lambda n,m:eval('1+m*('*n*n+'0'+')'*n*n)   #40

#Direct summation
lambda n,m:sum(m**i for i in range(n*n))   #40
lambda n,m:sum(map(m.__pow__,range(n*n)))  #41

#Direct formula
lambda n,m:n*n*(1==m)or(m**n**2-1)/(m-1)   #40

#Iterative sequence
f=lambda n,m,j=0:j<n*n and 1+m*f(n,m,j+1)  #41
def f(n,m):s=0;exec"s=s*m+1;"*n*n;print s  #41

#Recursive expression
#Fails due to float imprecision of square root
f=lambda n,m:n and 1+m*f((n*n-1)**.5,m)    #39*

Answer 5

Pyth, 6 bytes

1 byte saved thanks to @FryAmTheEggman.

s^Lvz*

Try it online!

Test suite.

Answer 6

Haskell, 25 bytes

n%m=sum$(m^)<$>[0..n*n-1]

Sums the list [m^0, m^1, ..., m^(n*n-1)].

Answer 7

JavaScript (ES2016/ES7), 31 29 28 bytes

a=>b=>(b**(a*a)-1)/--b||a*a

Just @Bassdrop Cumberwubwubwub and @Kaizo's ES6 version, but with exponentiation operator. :) (I didn't have enough reputation to comment instead.)

Edit: /+(b-1) changed to /--b (thanks @Neil).

Edit: now uses currying (thanks @MamaFunRoll).

Answer 8

Jelly, 6 bytes

²R’*@S

Try it online!

Answer 9

MATLAB, 23 bytes

@(n,k)sum(k.^(0:n^2-1))

Test it here!

Answer 10

Javascript ES6, 59 37 35 34 bytes

a=>b=>(Math.pow(b,a*a)-1)/--b||a*a` 

Thanks to @Kaizo for shaving off a whopping 19 bytes, @Neil for another 2 and @gcampbell for 1 more!

Try it here

f=
a=>b=>(Math.pow(b,a*a)-1)/--b||a*a

a.innerHTML='<pre>'+
  [[8,2],
   [3,6],
   [7,1.5],
   [5,-3],
   [256,1],
   [2,2],
   [2,-2]].map(b=>`${b[0]}, ${b[1]} => ${f(b[0])(b[1])}`).join('<br>')+'</pre>'

<div id=a>

Alternative broken versions

32 bytes

(a,b)=>(Math.pow(b,a*a)-1)/(b-1)

Causes NaN for b==1.

30 bytes

(a,b)=>(Math.pow(b,a*a)-1)/~-b

Causes Infinity for b==1.5.

28 bytes

(a,b)=>~-Math.pow(b,a*a)/~-b

Outputs 1 for some valid testcases.

Old version for 59 bytes

(a,b)=>Array(a*a).fill``.reduce((c,d,i)=>c+Math.pow(b,i),0)

Answer 11

Java, 132 bytes

import java.math.*;Object e(int n,BigDecimal m){BigDecimal r=BigDecimal.ONE,a=r;for(n*=n;n>1;n--)r=r.add(a=a.multiply(m));return r;}

Ungolfed

import java.math.*;

Object e(int n, BigDecimal m) {
    BigDecimal r = BigDecimal.ONE, a = r;
    for (n *= n; n > 1; n--)
        r = r.add(a = a.multiply(m));
    return r;
}

Notes

• This will work for arbitrarily big outputs as required by OP (Too bad Java supports big numbers, this would be shorter otherwise).

Outputs

Input:      8 2.0
Expected:   18446744073709551615
Actual:     18446744073709551615

Input:      3 6.0
Expected:   2015539
Actual:     2015539

Input:      7 1.5
Expected:   850161998.2854
Actual:     850161998.285399449204543742553141782991588115692138671875

Input:      5 -3.0
Expected:   211822152361
Actual:     211822152361

Input:      256 1.0
Expected:   65536
Actual:     65536

Input:      2 2.0
Expected:   15
Actual:     15

Input:      2 -2.0
Expected:   -5
Actual:     -5

Input:      263 359.9
Expected:   ?
Actual:     9709...[176798 digits]...7344.7184...[69160 digits]...6291

Answer 12

R, 18 bytes

sum(m^(1:s^2-1))

Explanation:

sum(               # Calculate sum
    m              # Multiplier
     ^             # Exponentiate
      (1:s^2-1))   # Generate sequence from 1 to s(ide)^2-1

Answer 13

05AB1E, 5 bytes

Code:

nL<mO

Explanation:

n      # Compute i ** 2
 L     # Push the list [1, ..., i ** 2]
  <    # Decrement by 1, [0, ..., i ** 2 - 1]
   m   # Power function with implicit input, [0 ** j, ..., (i ** 2 - 1) ** j]
    O  # Sum that all up

Try it online!.

Answer 14

Haskell, 30 bytes

n#m=sum$take(n^2)$iterate(*m)1

or equally long

n%1=n^2
n%m=(m**(n*n)-1)/(m-1)

The first version starts with 1 repeatedly multiplies with m. Then it sums the first n^2 numbers of this sequence. The second version is the explicit formula as seen in other answers.

Answer 15

J, 10 bytes

+/@:^i.@*:

Usage

I mark some integers with the x suffix to use extended integers to get exact results.

   f =: +/@:^i.@*:
   2x f 8
18446744073709551615
   3x f 6
75047317648499560
   6x f 3
2015539
   1.5 f 7
8.50162e8
   _3x f 5
211822152361
   1 f 256
65536
   2 f 2
15
   _2 f 2
_5

Explanation

+/@:^i.@*:
        *:  Square the value s to get s^2
     i.@    Make a range from 0 to s^2 exclusive, [0, 1, ..., s^2-1]
    ^       Using m as the base, calculate the power with the range
            [m^0, m^1, ..., m^(s^2-1)]
+/@:        Sum the entire list and return it

Answer 16

Mathcad, [tbd] bytes (~11)

Uses Mathcad's built in summation operator. Also demonstrates symbolic processor simplification to generate exact formula.

Mathcad effectively runs two processing engines in parallel - one a standard IEEE 64/80 bit floating point, and the other an arbitrary number length symbolic process (MuPad). Standard numerical evaluation is indicated by equals sign (=), whilst a right arrow indicates symbolic evaluation.

---

Mathcad counting scheme yet to be determined so no byte count given.

ctl-$ enters the summation operator (Sigma), including empty placeholders to put the summation variable, initial value, final value and expression. Approximate byte-equivalent count = 11.

Answer 17

PostgreSQL, 67 66 bytes

SELECT SUM(m^v)FROM(VALUES(3,6))t(s,m),generate_series(0,s*s-1)s(v)

SqlFiddleDemo

Input: VALUES(side, multiplier)

---

EDIT:

Input moved to table, all cases at-once:

SELECT s,m,SUM(m^v)FROM i,generate_series(0,s*s-1)s(v)GROUP BY s,m

SqlFiddleDemo

Output:

╔══════╦══════╦══════════════════════╗
║  s   ║  m   ║         sum          ║
╠══════╬══════╬══════════════════════╣
║   7  ║ 1.5  ║ 850161998.2853994    ║
║   2  ║ 2    ║ 15                   ║
║   2  ║ -2   ║ -5                   ║
║ 256  ║ 1    ║ 65536                ║
║   5  ║ -3   ║ 211822152361         ║
║   8  ║ 2    ║ 18446744073709552000 ║
║   3  ║ 6    ║ 2015539              ║
╚══════╩══════╩══════════════════════╝

Answer 18

TI-Basic, 19 bytes

S is side length, and M is the multiplier.

Prompt S,M:Σ(M^I,I,0,S²-1

Answer 19

Python, 40 bytes

lambda l,m:sum(m**i for i in range(l*l))

Answer 20

Ruby: 39 bytes

->s,m{(0...s*s).reduce(0){|a,b|a+m**b}}

Test:

f = ->s,m{(0...s*s).reduce(0){|a,b|a+m**b}}

f[8,2]   # 18446744073709551615
f[3,6]   # 2015539
f[7,1.5] # 850161998.2853994
f[5,-3]  # 211822152361
f[256,1] # 65536
f[2,2]   # 15
f[2,-2]  # -5
f[1,1]   # 1

Answer 21

Python, 41 Bytes

Totally new at this golfing thing, criticism welcome!

lambda n,m:sum(m**i for i in range(n**2))

Answer 22

Jolf, 18 15 10 bytes

Thanks to Cᴏɴᴏʀ O'Bʀɪᴇɴ for saving 3 bytes and pointing me towards mapping

uΜzQjd^JwH

Try it here!

 ΜzQj       Map over an array of 1 -> square(side length)
     d^JwH  Set the current array value to multiplier^(current value - 1)
u           Sum the array

Answer 23

CJam, 9 bytes

q~2#,f#:+

Inputs are in reverse order separated by a newline or a space.

Try it online!

q~    e# Read input. Evaluate: pushes the two numbers, M and N, onto the stack
2#    e# Square: compute N^2
,     e# Range: generates array [0 1 ... N^2-1]
f#    e# Compute M raised to each element of the array [0 1 ... N^2-1]
:+    e# Fold addition: compute sum of the array [M^0 M^1 ... M^(N^2-1)]

Answer 24

PHP, 58 54 bytes

<?function a($n,$m){$n*=$n;echo(1-$m**$n)/(1-$m)?:$n;}

This just uses the summation formula to show the value, after checking if the multiplier is 1 (which returns NAN in the formula).

Answer 25

Mathematica, 22 bytes

Tr[#^(Range[#2^2]-1)]&

Creates a range of {1, 2, ... s^2}, subtracts 1 over it to make {0, 1, ..., s^2-1}. Then raise each to the power of m making {m^0, m^1, ..., m^(s^2-1)} and return the sum of it.

Alternatively, Mathematica can use the explicit formula by taking its limit. This requires 29 bytes.

Limit[(s^#^2-1)/(s-1),s->#2]&

Answer 26

PARI/GP, 25 bytes

f(s,m)=sum(i=0,s^2-1,m^s)

Longer but faster (35 bytes):

f(s,m)=if(m==1,s^2,(m^s^2-1)/(m-1))

Cute (30 bytes):

f(s,m)=vecsum(powers(m,s^2-1))

Answer 27

C#, 56 bytes

double f(int n,double q){return(Math.Pow(q,n*n)-1)/--q;}

Answer 28

Lua, 54 47 bytes

r=0l,m=...for i=0,l^2-1 do r=r+m^i end print(r)

Run from the command line with the board side length as the first argument and the multiplier as the second.

Thanks to user6245072 for saving 6 bytes, and Katenkyo for saving an additional 1.

---

Original 54 byte version:

a,b=...c=1 d=1 for i=2,a^2 do c=c*b d=d+c end print(d)

Answer 29

𝔼𝕊𝕄𝕚𝕟, 11 chars / 14 bytes

⨭⩥ î²)ⓜⁿ⁽í$

Try it here (Firefox/WebKit Nightly only).

Yes, 𝔼𝕊𝕄𝕚𝕟 now works in WebKit Nightly! Chrome support is next.

Explanation

⨭⩥ î²)ⓜⁿ⁽í$ // implicit: î = input1, í = input2
   ⩥ î²)       // generate a range [0..î^2)
                     ⓜ      // map over range ($ is mapitem):
        ⁿ⁽í$  //   í^$
⨭            // sum resulting range
              // implicit output

Answer 30

RETURN, 32 bytes

[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!

Try it here.

Anonymous lambda that leaves result on Stack2. Usage:

8 2[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!

Explanation

[                              ]!  lambda
 a:                                store multiplier to a
   2^                              square side-length
     0\␊                           create range [0..result)
        {                          set current stack to range
         [  ][     ]#              while loop
          $¥                         check if TOS is truthy
              a;\^␌                  if so, push a^TOS to Stack2
                     ␁            set current stack to Stack2
                       [¤¥][+]#    sum Stack2