Prefácio

Na canção bem conhecida, Os Doze Dias de Natal , o narrador recebe vários presentes por dia. A música é cumulativa - em cada verso, um novo presente é adicionado, com uma quantidade um maior que o presente anterior. Uma perdiz, duas pombas, três galinhas francesas e assim por diante.

Em qualquer verso N , podemos calcular a soma acumulada de presentes até o momento na música, encontrando o N- ésimo número tetraédrico , que fornece os resultados:

Verse 1: 1
Verse 2: 4
Verse 3: 10
Verse 4: 20
Verse 5: 35
Verse 6: 56
Verse 7: 84
Verse 8: 120
Verse 9: 165
Verse 10: 220
Verse 11: 286
Verse 12: 364

Por exemplo, após o versículo 4, tivemos 4 * (1 perdiz) , 3 * (2 pombas) , 2 * (3 galinhas francesas) e 1 * (4 pássaros cantando) . Ao somar estes, obtemos 4(1) + 3(2) + 2(3) + 1(4) = 20.

O desafio

Sua tarefa é escrever um programa ou função que, dado um número inteiro positivo representando o número de presentes 364 ≥ p ≥ 1 , determine em que dia (verso) do Natal é.

Por exemplo, se p = 286 , estamos no 11º dia de Natal. No entanto, se p = 287 , a próxima carga de presentes começou, ou seja, é o 12º dia.

Matematicamente, isso é encontrar o próximo número tetraédrico e retornar sua posição em toda a sequência de números tetraédricos.

Regras:

• Isso é código-golfe , então a solução mais curta (em bytes) vence.
• Aplicam-se lacunas de golfe padrão.
• Quando se trata de dias, seu programa deve ser indexado 1.
• Seu envio deve ser um programa ou uma função completa - mas não um trecho.

Casos de teste

1   ->  1
5   ->  3
75  ->  7
100 ->  8
220 ->  10
221 ->  11
364 ->  12

Geléia , 7 6 bytes

-1 byte graças a Dennis (use mínimo vetorizado «, e primeiro índice i)

R+\⁺«i

TryItOnline

Quão?

Não é tão eficiente - calcula os números tetraédricos de 1º a enésimo nono em ordem em uma lista e retorna o índice baseado em 1 do primeiro que é igual ou maior.

R+\⁺«i - main link: n
R      - range                          [1,2,3,4,...,n]
 +\    - cumulative reduce by addition  [1,3,6,10,...,sum([1,2,3,4,...n])] i.e. triangle numbers
   ⁺   - duplicate previous link - another cumulative reduce by addition
                                        [1,4,10,20,...,nth tetrahedral]
    «  - min(that, n)                   [1,4,10,20,...,n,n,n]
     i - first index of n (e.g. if n=12:[1,4,10,12,12,12,12,12,12,12,12,12] -> 4)

Anterior 7 byters usando intervalo reduzido [0,1,2,3,...,n-1]e contagem tetrahedrals menos do que n:
Ḷ+\⁺<µS,
Ḷ+\⁺<ḅ1,
Ḷ+\⁺<ċ1, e
Ḷ+\⁺<¹S

Python , 27 bytes

lambda n:int((n*6)**.33359)

Experimente online!

Uma fórmula direta com algumas curvas, igual à original encontrada pela Level River St.

A equação deslocada i**3-i==n*6é próxima i**3==n*6de grande i. Resolve a i=(n*6)**(1/3). Tomando o chão, as voltas para baixo, conforme necessário, compensando a diferença.

Porém, existem 6 entradas nos limites em que o erro leva abaixo de um número inteiro que deveria estar acima. Tudo isso pode ser corrigido aumentando ligeiramente o expoente sem introduzir mais erros.

Python , 38 bytes

f=lambda n,i=1:i**3-i<n*6and-~f(n,i+1)

A fórmula n=i*(i+1)*(i+2)/6para os números tetraédricos podem ser mais bem escrita em i+1como n*6=(i+1)**3-(i+1). Então, encontramos o menor ipara o qual i**3-i<n*6. Cada vez que incrementamos a ipartir de 1, as chamadas recursivas são adicionadas 1à saída. Começando em i=1vez de i=0compensar a mudança.

J , 12 bytes

2>.@-~3!inv]

Pode haver uma maneira mais eficiente de fazer isso, mas essa é uma oportunidade adorável de usar a inversão de função interna de J.

Experimente online!

Como funciona

2>.@-~3!inv]  Monadic verb. Argument: n

           ]  Right argument; yield n.
      3       Yield 3.
       !inv   Apply the inverse of the ! verb to n and 3. This yields a real number.
              x!y computes Π(y)/(Π(y-x)Π(x)), where Π is the extnsion of the 
              factorial function to the real numbers. When x and y are non-negative
              integers, this equals yCx, the x-combinations of a set of order y.
 >.@-~        Combine the ceil verb (>.) atop (@) the subtraction verb (-) with
              swapped arguments (~).
2             Call it the combined verbs on the previous result and 2.

Python , 22 bytes

lambda n:n**.3335//.55

Fortemente inspirado pela resposta Python do @ xnor .

Experimente online!

Geléia , 7 bytes

R‘c3<¹S

Experimente online!

Como funciona

R‘c3<¹S  Main link. Argument: n

R        Range; yield [1, ..., n].
 ‘       Increment; yield [2, ..., n+1].
  c3     Combinations; yield [C(2,3), ..., C(n+1,3)].
    <¹   Yield [C(2,3) < n, ..., C(n+1,3) < n].
      S  Sum; count the non-negative values of k for which C(k+2,3) < n.

JavaScript (ES6), 33 bytes

n=>(F=k=>k<n?F(k+3*k/i++):i)(i=1)

Com base na fórmula recursiva:

a(1) = 1
a(i) = (i + 3) * a(i - 1) / i

A segunda expressão também pode ser escrita como ...

a(i) = a(i - 1) + 3 * a(i - 1) / i

... qual é o que estamos usando aqui.

a(i - 1)é realmente armazenado na kvariável e passado para a próxima iteração aték >= n .

Casos de teste

let f =

n=>(F=k=>k<n?F(k+3*k/i++):i)(i=1)

console.log(f(1));   // ->  1
console.log(f(5));   // ->  3
console.log(f(75));  // ->  7
console.log(f(100)); // ->  8
console.log(f(220)); // ->  10
console.log(f(221)); // ->  11
console.log(f(364)); // ->  12

Ruby, 26 bytes

Editar: versão alternativa, ainda 26 bytes

->n{(n**0.3333*1.82).to_i}

Versão original

->n{((n*6)**0.33355).to_i}

Usa o fato de que T(x) = x(x+1)(x+2)/6 = ((x+1)**3-(x+1))/6está muito próximo (x+1)**3/6.

A função simplesmente multiplica por 6, localiza uma versão ligeiramente alterada da raiz do cubo (sim, são necessárias 5 casas decimais) e retorna o resultado truncado para um número inteiro.

Programa de teste e saída

f=->n{((n*6)**0.33355).to_i}
[1,4,10,20,35,56,84,120,165,220,286,364].map{|i|p [i,f[i],f[i+1]]}

[1, 1, 2]
[4, 2, 3]
[10, 3, 4]
[20, 4, 5]
[35, 5, 6]
[56, 6, 7]
[84, 7, 8]
[120, 8, 9]
[165, 9, 10]
[220, 10, 11]
[286, 11, 12]
[364, 12, 13]

JavaScript, 36 33 bytes

-3 bytes graças a Luke (fazendo a função ser curry)

n=>f=i=>n<=i/6*-~i*(i+2)?i:f(-~i)

Esta é uma função lambda sem nome que pode ser atribuída funce chamada com func(220)(), conforme descrito nesta meta post . Minha função original, sem curry, fica assim:

f=(n,i)=>n<=-~i*i/6*(i+2)?i:f(n,-~i)

Esta resposta usa o fato de que x th número tetraédrico pode ser encontrado com a seguinte função:

A submissão funciona aumentando ie encontrando recursivamente tetrahedral(i), até que seja maior ou igual a n(o número de presentes dados).

Quando chamado com um argumento conforme o esperado i = undefined, e, portanto, não é maior que n. Isso significa que f(n,-~i)é executado e -~undefinedavaliado como 1, o que desencadeia a recursão.

Snippet de teste:

func = n=>f=i=>n<=i/6*-~i*(i+2)?i:f(-~i)

var tests = [1, 5, 75, 100, 220, 221, 364];
tests.forEach(n => console.log(n + ' => ' + func(n)()));

MATL , 12 11 bytes

`G@H+IXn>}@

Experimente online!

Explicação

`       % Do...while
  G     %   Push input, n
  @     %   Push iteration index (1-based), say m
  H     %   Push 2
  +     %   Add
  I     %   Push 3
  Xn    %   Binomial coefficient with inputs m+2, 3
  >     %   Is n greater than the binomial coefficient? If so: next iteration
}       %   Finally (execute after last iteration, before exiting the loop)
  @     %   Push last iteration index. This is the desired result
        % End (implicit)
        % Display (implicit)

05AB1E , 10 bytes

XµNÌ3c¹‹_½

Experimente online!

Explicação

Xµ          # loop until counter equals 1
  NÌ3c      # binomial_coefficient(iteration_index+2,3)
      ¹     # push input
       ‹_   # not less than
         ½  # if true, increment counter
            # output last iteration index

Pyke, 11 bytes

#3RL+B6f)lt

Experimente aqui!

#3RL+B6f)   -  while rtn <= input as i:
 3RL+       -     i+j for j in range(3)
     B      -    product(^)
      6f    -   ^/6
         lt - len(^)-1

Mathematica, 26 bytes

(0//.i_/;i+6#>i^3:>i+1)-1&

Função sem nome, usando um argumento inteiro não negativo e retornando um número inteiro não negativo (sim, funciona também para o dia 0). Queremos encontrar o menor número inteiro ipara o qual a entrada #é no máximo i(i+1)(i+2)/6, que é a fórmula para o número de presentes dados nos primeiros idias. Através de truques algébricos leves, a desigualdade # ≤ i(i+1)(i+2)/6é equivalente a (i+1) + 6# ≤ (i+1)^3. Portanto, a estrutura 0//.i_/;i+6#>i^3:>i+1começa com a 0e continua adicionando 1enquanto o teste i+6#>i^3é satisfeito; depois (...)-1&subtrai 1no final (em vez de gastar bytes com parênteses dentro da desigualdade).

Se deixarmos os 12 dias de Natal continuar, poderemos lidar com cerca de 65536 dias antes do limite de recursão //.interno para interromper o processo ... isso é cerca de 4,7 * 10 ^ 13 dias, ou cerca de dez vezes a idade do universo até agora ....

J , 9 bytes

I.~3!2+i.

Experimente online!

Isso é mais ineficiente do que usar o inverso do fatorial, mas passa a ser mais curto.

Por exemplo, se o número inteiro de entrada for n = 5, faça o intervalo [2, n+1].

2 3 4 5 6 choose 3
0 1 4 10 20

Estes são os primeiros 5 números tetraédricos. O próximo passo é determinar a que intervalo (dia) n pertence. Existem n +1 = 6 intervalos.

0 (-∞, 0]
1 (0, 1]
2 (1, 4]
3 (4, 10]
4 (10, 20]
5 (20, ∞)

Então n = 5 pertence ao intervalo 3, que é(4, 10] e o resultado é 3.

Explicação

I.~3!2+i.  Input: integer n
       i.  Range [0, n)
     2+    Add 2 to each
   3!      Combinations nCr with r = 3
I.~        Interval index of n

Python, 43 bytes

f=lambda n,i=0:n*6>-~i*i*(i+2)and-~f(n,i+1)

Economizou 5 bytes graças ao @FlipTack e outros 3 graças ao @xnor !

Japonês , 12 bytes

1n@*6§X³-X}a

Teste online!ou Verifique todos os casos de teste de uma só vez

Como funciona

1n@*6§X³-X}a  // Implicit: U = input integer
  @       }a  // Find the smallest non-negative integer X which satisfies this condition:
      X³-X    //   (X ^ 3) - X
     §        //   is greater than or equal to
   *6         //   U * 6.
1n            // Subtract 1 from the result.
              // Implicit: output result of last expression

Esta é uma simplificação da fórmula tetraédrica que várias outras respostas estão usando:

f(x) = (x)(x + 1)(x + 2)/6

Ao substituir x - 1para x, podemos simplificar esta consideravelmente:

f(x) = (x - 1)(x)(x + 1) / 6
f(x) = (x - 1)(x + 1)(x) / 6
f(x) = (x^2 - 1)(x) / 6
f(x) = (x^3 - x) / 6

Portanto, o resultado correto é um a menos que o menor número inteiro, de xmodo que(x^3 - x) / 6 maior ou igual à entrada.

Solução de 13 bytes, inspirada na resposta da @ xnor :

p.3335 /.55 f

Mais algumas soluções @ETHproductions e eu brinquei com

J+@*6§X³-X}a 
@*6§X³-X}a -1
@§X/6*°X*°X}a 
_³-V /6¨U}a -1
§(°V nV³ /6?´V:ß
§(°VV³-V /6?´V:ß

Teste aqui .

SmileBASIC, 43 bytes

INPUT X
WHILE X>P
I=I+1
R=R+I
P=P+R
WEND?I

Ié o dia, Ré o ith número triangular e Pé o inúmero th tetrahedral (número de presentes).

Acho que uma resposta semelhante em outro idioma, talvez: x=>{while(x>p)p+=r+=++i;return i}poderia ser muito boa.

Python 3, 48 46 bytes

f=lambda x,i=1:f(x,i+1)if(i+3)*i+2<x/i*6else i

Mathematica, 31 25 bytes

Floor@Root[x^3-x-6#+6,1]&

Haskell, 21 23 bytes

floor.(**(1/3)).(*6.03)

Edit: Como o xnor apontou, a solução original ( floor.(/0.82).(**0.4)) não funcionou entre os dias de natal

Lote, 69 bytes

@set/an=d=t=0
:l
@set/at+=d+=n+=1
@if %t% lss %1 goto l
@echo %n%

Calcula manualmente números tetraedronais.

Pitth 11 bytes

/^Q.3335.55

Experimente online!

praticamente traduziu a resposta de Dennis para Pyth

R, 19 caracteres

floor((n*6)^.33359)

com base na resposta do xnor em Python.

QBIC , 19 bytes

Isso rouba a fórmula de @xnor:

:?int((a*6)^.33359)

Tentei discar a resolução para 0,3336 para salvar um byte, mas isso falhou na caixa de teste final.

Bash + bc, 44 bytes

bc -l <<< "f=e(.33359*l($1*6));scale=0;f/1"