# 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. – FryAmTheEggman May 3 '16 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 – DJMcMayhem May 3 '16 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 '16 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. – cst1992 May 4 '16 at 8:13
• @cst1992 the version I read says the man gave up on his request and got a province as a gift. – user6245072 May 4 '16 at 9:09

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


# 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. – Dennis May 4 '16 at 6:05

## 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 :) – FryAmTheEggman May 3 '16 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! – NoOneIsHere May 3 '16 at 18:55
• Welcome! The + operator was a test I forgot to edit out, so you can shave off 1 byte by omitting it :) – Bassdrop Cumberwubwubwub May 3 '16 at 19:25
• The formula doesn't work for m = 1 :3 – user6245072 May 3 '16 at 21:55
• @user6245072 are you on chrome canary? Or on node? If on node, enable harmony flag – NiCk Newman May 4 '16 at 5:15
• Would /--b save you a byte or two? – Neil May 4 '16 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},${b} => ${f(b)(b)}).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 – Kaizo May 3 '16 at 16:20 • @Kaizo you're right, I'm an idiot :D – Bassdrop Cumberwubwubwub May 3 '16 at 17:08 • /~-b is obviously no good for fractional b, but /--b should work, no? – Neil May 4 '16 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 May 4 '16 at 19:33 • @Neil you're right, ofcourse. That's what you get when you rush your answers :p Thanks! – Bassdrop Cumberwubwubwub May 4 '16 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 May 3 '16 at 19:41 • @xnor: oh, that's nice. I think it's different enough for a separate answer. Please post it yourself. – nimi May 3 '16 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. – FrownyFrog Mar 26 '18 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 ? – Abr001am May 4 '16 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. – Stuart Bruff May 4 '16 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) – Leaky Nun May 3 '16 at 14:50 • In regular languages using formula would be shorter. I used map because in esolangs maps would be shorter. – Leaky Nun May 3 '16 at 14:51 • Where's the strikethrough? – Leaky Nun May 3 '16 at 14:52 • @KennyLau I was still working on my answer, I posted this before seeing your comment. – orlp May 3 '16 at 14:52 • Alright, (7 more to go...) – Leaky Nun May 3 '16 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 – Value Ink May 13 '16 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. – br3nt May 13 '16 at 3:27 • Can you just change your language to Rails? I don't know about any imports you might need for that – Value Ink May 13 '16 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 ; ) – user6245072 May 23 '16 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. – Lang Tran May 23 '16 at 21:34 • Welcome to Programming Puzzles & Code Golf! This is a nice answer, but it's rather similar to this one. – Dennis May 23 '16 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? – Lang Tran May 23 '16 at 21:45 • l*l actually, which is shorter than l**2. – Dennis May 24 '16 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 }. – Conor O'Brien May 3 '16 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. – swells May 3 '16 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]/#]& – Simon Woods May 7 '16 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? – user6245072 May 4 '16 at 7:40 • Is it not 256^2? – downrep_nation May 4 '16 at 8:53 • (Math.Pow(1, 256 * 256) - 1) / --1 = 0/0. – user6245072 May 4 '16 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. – Horváth Dávid Jun 18 '17 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! – NoOneIsHere May 4 '16 at 1:37 • l,m=...r=0 for i=0,l^2 do r=r+m^i end print(r) – user6245072 May 4 '16 at 4:27 • This should save some bytes. – user6245072 May 4 '16 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) – Katenkyo May 4 '16 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. – user6245072 May 4 '16 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
`