# The rice and chess problem

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.

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.

• You probably want a test case where the multiplier is 1 and another where it is 0 (assuming both are valid). Also "anything" is pretty broad, does the square root of negative one count? How about "potato"? ;) I'd recommend "any real number" or something. May 3, 2016 at 14:58
• If your language of choose can't display too large numbers, it's ok as long as your program can correctly process smaller inputs Careful, that has caused problems in the past. meta.codegolf.stackexchange.com/a/8245/31716 May 3, 2016 at 17:11
• ... it must have been a rich province, because even today, the yearly world production of rice is still less than 2^64 grains.
– vsz
May 3, 2016 at 18:36
• @vsz Actually, the guy was killed. The amount added to the king giving away the entire kingdom to the man, so naturally the easier way out was taken. May 4, 2016 at 8:13
• @cst1992 the version I read says the man gave up on his request and got a province as a gift. May 4, 2016 at 9:09

# 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


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

• Or as a function train: ⊣⊥1⍴⍨⊢×⊢ (8 bytes) As an interactive REPL command, ⎕⊥×⍳⎕*2 (7 bytes) works as well. May 4, 2016 at 6:05

# Jelly, 4 bytes

²b1ḅ


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

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


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

• Ah right, my bad. Anyway, I really like seeing all the different approaches you took :) May 3, 2016 at 20:57

# Pyth, 6 bytes

1 byte saved thanks to @FryAmTheEggman.

s^Lvz*


Try it online!

Test suite.

## Haskell, 25 bytes

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


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

# JavaScript (ES2016/ES7), 3129 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).

• Welcome to PPCG! Your answer is pretty good! May 3, 2016 at 18:55
• Welcome! The + operator was a test I forgot to edit out, so you can shave off 1 byte by omitting it :) May 3, 2016 at 19:25
• The formula doesn't work for m = 1 :3 May 3, 2016 at 21:55
• @user6245072 are you on chrome canary? Or on node? If on node, enable harmony flag May 4, 2016 at 5:15
• Would /--b save you a byte or two?
– Neil
May 4, 2016 at 19:29

# Jelly, 6 bytes

²R’*@S


Try it online!

# MATLAB, 23 bytes

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


Test it here!

# Javascript ES6, 593735 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],

## 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. • where is the code ? May 4, 2016 at 11:09 • The "code" for the actual challenge is the first summation sign (capital Sigma) you see under the heading "Challeng Solution". The other bits of "code" are given under the heading "Solution Variants". What you see in the image is exactly what gets written down on a Mathcad worksheet - Mathcad uses mathematical symbols for various operations, such as a vector sum or product, function integration or differentiation, or logical operations. Most operators can be input with a key combination (for example, ctl-4 for an implicit vector sum or ctl-& for an iterated sum), or via a menu or toolbar. May 4, 2016 at 15:26 # 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 ║ ╚══════╩══════╩══════════════════════╝  # TI-Basic, 19 bytes S is side length, and M is the multiplier. Prompt S,M:Σ(M^I,I,0,S²-1  # Python, 40 bytes lambda l,m:sum(m**i for i in range(l*l))  • lambda l,m:(m**(l*l)-1)/(m-1) May 3, 2016 at 14:50 • In regular languages using formula would be shorter. I used map because in esolangs maps would be shorter. May 3, 2016 at 14:51 • Where's the strikethrough? May 3, 2016 at 14:52 • @KennyLau I was still working on my answer, I posted this before seeing your comment. – orlp May 3, 2016 at 14:52 • Alright, (7 more to go...) May 3, 2016 at 14:54 # 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  • When did Ruby get a sum function??? This is gamechanging May 13, 2016 at 3:18 • Oh no! What I thought was a ruby core method is in fact a rails method sad face. I've updated the answer. May 13, 2016 at 3:27 • Can you just change your language to Rails? I don't know about any imports you might need for that May 13, 2016 at 4:16 # Python, 41 Bytes Totally new at this golfing thing, criticism welcome! lambda n,m:sum(m**i for i in range(n**2))  • It's actually quite good ; ) May 23, 2016 at 21:23 • Haha, thanks. I had to google how to do lambdas in python again, since I haven't touched python in a while. May 23, 2016 at 21:34 • Welcome to Programming Puzzles & Code Golf! This is a nice answer, but it's rather similar to this one. May 23, 2016 at 21:40 • Ah, I didn't see if there were any other solutions. Did he save a byte by doing l**l instead of what I did? May 23, 2016 at 21:45 • l*l actually, which is shorter than l**2. May 24, 2016 at 18:06 # Jolf, 1815 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  • Nice work! You can remove the a before the zeta, as that is implicitly outed. You can also use Mu (map) instead of for each, and I think you can replace the D with a d and remove the ending }. May 3, 2016 at 17:29 • @Cᴏɴᴏʀ O'Bʀɪᴇɴ Neat, keep forgetting about the implicit parts of Jolf, they are certainly some of the best ways to shave off a few bytes. May 3, 2016 at 17:41 # 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)]  ## 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). # 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]&  • You could write your first version as Tr[#^Range[#2^2]/#]& May 7, 2016 at 10:48 # 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))  ## C#, 56 bytes double f(int n,double q){return(Math.Pow(q,n*n)-1)/--q;}  • Testcase 256, 1? May 4, 2016 at 7:40 • Is it not 256^2? May 4, 2016 at 8:53 • (Math.Pow(1, 256 * 256) - 1) / --1 = 0/0. May 4, 2016 at 9:11 • You need either using System; or System.Math.Pow. And your code doesn't work, when q=1, as stated by @user6245072. Jun 18, 2017 at 15:47 # 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)  • Hello, and welcome to PPCG! Great answer! May 4, 2016 at 1:37 • l,m=...r=0 for i=0,l^2 do r=r+m^i end print(r) May 4, 2016 at 4:27 • This should save some bytes. May 4, 2016 at 4:27 • renaming d saves one byte because it allows to skip the space in c=1 d=1 => a,b=...c=1g=1 for i=2,a^2 do c=c*b g=g+c end print(g). if @user6245072 's suggestion works, you could save a byte on the same principle => r=0l,m=...for i=0,l^2 do r=r+m^i end print(r) May 4, 2016 at 11:56 • The whitespace between r=0 and l,m=... is anyway compulsory, so it doesn't change. Also the loop should be for i=0,l^2-1 but this is my fault lol. May 4, 2016 at 12:45 # 𝔼𝕊𝕄𝕚𝕟, 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


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