Uma lenda indiana conta a história do suposto inventor do jogo de xadrez, que impressionou tanto o imperador da Índia com seu jogo que ele seria recompensado com qualquer coisa que fosse solicitada.

O homem disse que queria ser pago em arroz. Ele queria um grão de arroz para o primeiro quadrado do tabuleiro de xadrez, dois para o segundo, quatro para o terceiro, oito para o quarto e assim por diante, até o 64º quadrado.

O imperador ficou surpreso que o homem pedisse uma recompensa tão pequena, mas quando seus matemáticos começaram a contar, ele acabou perdendo uma de suas províncias.

Tarefa

Dado o comprimento do lado de um tabuleiro de xadrez hipotético (que é 8 em um tabuleiro de xadrez padrão) e o multiplicador entre quadrados (que é 2 na legenda), calcule o número de grãos de arroz que o imperador deve pagar ao homem.

Notas

• O comprimento do lado sempre será um número inteiro positivo. O multiplicador poderia ser qualquer tipo de número racional.

• Se o seu idioma de escolha não puder exibir números muito grandes, tudo bem, desde que o seu programa possa processar corretamente entradas menores.

• Além disso, se o seu idioma de escolha arredondar valores maiores (com notações exponenciais), tudo bem se esses valores estiverem aproximadamente corretos.

Casos de teste

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

Observe que a fórmula explícita

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

Executa errado multiplier = 1, como

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

Pontuação

Isso é código-golfe. A resposta mais curta em bytes vence.

Gelatina , 4 bytes

²b1ḅ

Isso usa a abordagem da resposta inteligente do @ APLDude em APL .

Experimente online! ou verifique todos os casos de teste .

Como funciona

²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

Experimente 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

⎕é usado para ler a entrada do usuário duas vezes. Se armazenarmos o comprimento lateral em s e o multiplicador em m , obteremos o código a seguir.

m⊥1+0×⍳s*2

E aqui está como a APL analisa esse código:

Python, 40 bytes

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

Gera e avalia uma sequência como

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

que codifica a soma como um polinômio Hornerizado com n*ntermos.

Muitos métodos diferentes deram contagens de bytes muito semelhantes:

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

Pitão, 6 bytes

1 byte salvo graças a @FryAmTheEggman .

s^Lvz*

Experimente online!

Suíte de teste.

Haskell, 25 bytes

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

Soma a lista [m^0, m^1, ..., m^(n*n-1)].

JavaScript (ES2016 / ES7), 31 29 28 bytes

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

Apenas o @Bassdrop Cumberwubwubwub e a versão ES6 do @ Kaizo, mas com o operador de exponenciação. :) (Eu não tinha reputação suficiente para comentar.)

Editar: /+(b-1)alterado para /--b(obrigado @ Neil).

Edit: agora usa currying (obrigado @MamaFunRoll).

Gelatina, 6 bytes

²R’*@S

Experimente online!

MATLAB, 23 bytes

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

Teste aqui !

Javascript ES6, 59 37 35 34 bytes

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

Graças a @Kaizo por eliminar 19 bytes, @Neil por mais 2 e @gcampbell por mais 1!

Experimente aqui

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>

Versões quebradas alternativas

32 bytes

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

Causas NaNpara b==1.

30 bytes

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

Causas Infinitypara b==1.5.

28 bytes

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

Saídas 1para alguns casos de teste válidos.

Versão antiga para 59 bytes

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

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;
}

Notas

• Isso funcionará para resultados arbitrariamente grandes, conforme exigido pelo OP (Java muito ruim suporta grandes números, isso seria mais curto caso contrário).

Saídas

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))

Explicação:

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

05AB1E , 5 bytes

Código:

nL<mO

Explicação:

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

Experimente online! .

Haskell, 30 bytes

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

ou igualmente longo

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

A primeira versão começa com 1multiplica-se repetidamente com m. Em seguida, soma os primeiros n^2números dessa sequência. A segunda versão é a fórmula explícita, como visto em outras respostas.

J, 10 bytes

+/@:^i.@*:

Uso

Eu marco alguns números inteiros com o xsufixo para usar números inteiros estendidos para obter resultados exatos.

   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

Explicação

+/@:^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

Mathcad, [tbd] bytes (~ 11)

Usa o operador de soma incorporado do Mathcad. Também demonstra a simplificação simbólica do processador para gerar a fórmula exata.

O Mathcad efetivamente executa dois mecanismos de processamento em paralelo - um um ponto flutuante padrão IEEE de 64/80 bits e o outro um processo simbólico arbitrário de comprimento de número (MuPad). A avaliação numérica padrão é indicada pelo sinal de igual (=), enquanto uma seta para a direita indica avaliação simbólica.

Esquema de contagem do Mathcad ainda a ser determinado, portanto, nenhuma contagem de bytes fornecida.

ctl- $ entra no operador de soma (Sigma), incluindo espaços reservados vazios para colocar a variável de soma, valor inicial, valor final e expressão. Contagem aproximada de equivalentes em bytes = 11.

PostgreSQL, 67 66 bytes

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

SqlFiddleDemo

Entrada: VALUES(side, multiplier)

EDITAR:

Entrada movida para a tabela, todos os casos de uma vez:

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

SqlFiddleDemo

Saída:

╔══════╦══════╦══════════════════════╗
║  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é o comprimento lateral e Mé o multiplicador.

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

Python, 40 bytes

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

Ruby: 39 bytes

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

Teste:

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

Python, 41 bytes

Totalmente novo nessa coisa do golfe, críticas bem-vindas!

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

Jolf, 18 15 10 bytes

Obrigado a Cᴏɴᴏʀ O'Bᴏɴᴏʀ por salvar 3 bytes e me indicar o mapeamento

uΜzQjd^JwH

Experimente aqui!

 Μ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

CJam , 9 bytes

q~2#,f#:+

As entradas estão na ordem inversa, separadas por uma nova linha ou um espaço.

Experimente 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;}

Isso apenas usa a fórmula de soma para mostrar o valor, depois de verificar se o multiplicador é 1 (que retorna NAN na fórmula).

Mathematica, 22 bytes

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

Cria um intervalo de {1, 2, ... s^2}, subtrai 1 sobre ele para criar {0, 1, ..., s^2-1}. Em seguida, eleve cada um ao poder de mfazer {m^0, m^1, ..., m^(s^2-1)}e devolva a soma.

Como alternativa, o Mathematica pode usar a fórmula explícita tomando seu limite. Isso requer 29 bytes.

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

PARI / GP , 25 bytes

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

Mais longo, mas mais rápido (35 bytes):

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

Bonito (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;}

Lua, 54 47 bytes

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

Execute da linha de comando com o comprimento do lado do quadro como o primeiro argumento e o multiplicador como o segundo.

Agradecemos a user6245072 por salvar 6 bytes e a Katenkyo por salvar 1 adicional.

Versão original de 54 bytes:

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

11, 11 caracteres / 14 bytes

⨭⩥ î²)ⓜⁿ⁽í$

Try it here (Firefox/WebKit Nightly only).

Sim, agora funciona no WebKit Nightly! O suporte ao Chrome é o próximo.

Explicação

⨭⩥ î²)ⓜⁿ⁽í$ // 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.

Lambda anônima que deixa o resultado no Stack2. Uso:

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

Explicação

[                              ]!  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