# 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. Commented 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 Commented 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
Commented 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. Commented 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. Commented 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. Commented 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 :) Commented May 3, 2016 at 20:57

# Pyth, 6 bytes

1 byte saved thanks to @FryAmTheEggman.

s^Lvz*


Try it online!

Test suite.

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! Commented 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 :) Commented May 3, 2016 at 19:25
• The formula doesn't work for m = 1 :3 Commented May 3, 2016 at 21:55
• @user6245072 are you on chrome canary? Or on node? If on node, enable harmony flag Commented May 4, 2016 at 5:15
• Would /--b save you a byte or two?
– Neil
Commented 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],
[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) • Why haven't you just treated the b==1 case in the 32 bytes case? 40 bytes: (a,b)=>b-1?(Math.pow(b, a * a)-1)/(b-1):a*a Commented May 3, 2016 at 16:20 • @Kaizo you're right, I'm an idiot :D Commented May 3, 2016 at 17:08 • /~-b is obviously no good for fractional b, but /--b should work, no? – Neil Commented May 4, 2016 at 19:30 • By the way, I golfed the old version down to 47 bytes: (a,b)=>[...Array(a*a-1)].reduce(s=>s+=p*=b,p=1) – Neil Commented May 4, 2016 at 19:33 • @Neil you're right, ofcourse. That's what you get when you rush your answers :p Thanks! Commented May 4, 2016 at 20:17 # 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  # 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  # 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  ## 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. • Can't you just do n#m=sum$(m^)<$>[0..n*n-1]? – xnor Commented May 3, 2016 at 19:41 • @xnor: oh, that's nice. I think it's different enough for a separate answer. Please post it yourself. – nimi Commented May 3, 2016 at 20:21 # 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  • 6 bytes #.*:$* as per APL Dude. Commented Mar 26, 2018 at 13:04

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 ? Commented 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. Commented 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) Commented May 3, 2016 at 14:50 • In regular languages using formula would be shorter. I used map because in esolangs maps would be shorter. Commented May 3, 2016 at 14:51 • Where's the strikethrough? Commented May 3, 2016 at 14:52 • @KennyLau I was still working on my answer, I posted this before seeing your comment. – orlp Commented May 3, 2016 at 14:52 • Alright, (7 more to go...) Commented 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 Commented 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. Commented 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 Commented 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 ; ) Commented 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. Commented 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. Commented 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? Commented May 23, 2016 at 21:45 • l*l actually, which is shorter than l**2. Commented 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 }. Commented 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. Commented 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]/#]& Commented 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? Commented May 4, 2016 at 7:40 • Is it not 256^2? Commented May 4, 2016 at 8:53 • (Math.Pow(1, 256 * 256) - 1) / --1 = 0/0. Commented 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. Commented 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! Commented May 4, 2016 at 1:37 • l,m=...r=0 for i=0,l^2 do r=r+m^i end print(r) Commented May 4, 2016 at 4:27 • This should save some bytes. Commented 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) Commented 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. Commented 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
`