Encontre o maior número de números inteiros distintos que somam n

18

A tarefa

Dado um número inteiro positivo de entrada n(de 1 até o limite do seu idioma, inclusive), retorne ou produza o número máximo de números inteiros positivos distintos que somam n.

Casos de teste

Vamos fdefinir uma função válida de acordo com a tarefa:

A sequência para f, começando em 1:

1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, ...

Como um caso de teste maior:

>>> f(1000000000) // Might not be feasible with brute-forcers
44720

Código de teste

Para quaisquer casos de teste não fornecidos explicitamente, a saída do seu código deve corresponder ao resultado do seguinte:

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        System.out.println((int) Math.floor(Math.sqrt(2*x + 1./4) - 1./2));
    }
}

Experimente online!

Addison Crump
fonte
Pode ser indexado em 0?
totallyhuman
1
@totallyhuman "it" sendo as respostas? Porque não se trata de uma lista ...
Addison Crump
3
@totallyhuman No. Trata-se das partições distintas de números específicos.
Addison Crump
5
Este é o OEIS A003056 .
Jeppe Stig Nielsen
4
Sinto-me insignificante quase sempre que tropeço na pilha de codegolfe. As respostas e os comentários são muito mais do que humildes. As perguntas também costumam ser interessantes, mas com o comentário dele, @JeppeStigNielsen, apenas joga as plantas concluídas quando ainda estamos contemplando a área do piso.
KalleMP

Respostas:

9

05AB1E , 4 bytes

ÅTg<

Experimente online!

Ferramenta perfeita para o trabalho.

ÅTorigina o lista de Å ll t números riangular até e incluindo o N (infelizmente inclui também 0, caso contrário, seria de 3 bytes), g<recebe o len g th e diminui-la.

Mr. Xcoder
fonte
8

Gelatina , 6 5 bytes

R+\»ċ

Experimente online!

Um pouco eficiente. Essa sequência é incrementada em números triangulares, portanto, isso conta apenas quantos números triangulares são menores que n .

Explicação:

        # Main link
R       # Range, generate [1..n]
 +\     # Cumulative sum (returns the first n triangular numbers)
   »    # For each element, return the maximum of that element and 'n'
    ċ   # How many elements are 'n'? (implicit right argument is n)
DJMcMayhem
fonte
Na explicação, você certamente quer dizer "quantos números são menores ou iguais a n "
Luis Mendo
@LuisMendo Veja a nova explicação.
DJMcMayhem
6

Haskell , 26 bytes

-2 bytes graças a H.PWiz.

(!!)$do x<-[0..];x<$[0..x]

Experimente online!

Isso retorna o enésimo elemento dos números inteiros, onde cada i é replicado i + 1 vezes.

totalmente humano
fonte
3
Eu não posso deixar de perguntar o que "succ" é
Addison Crump
Sim, eu sei lol. succsignifica successor.
totallyhuman
5

Brain-Flak , 36 bytes

<>(())({()<(({}())){<>({}[()])}>{}})

Experimente online!

Isso usa a mesma estrutura que o algoritmo de divisão padrão, exceto que o "divisor" é incrementado toda vez que é lido.

Nitrodon
fonte
3

Flacidez Cerebral , 82 bytes

Espaço em branco adicionado para "Legibilidade"

(())

{
    {}

    ((({})[[]]))

    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

}{}{}{}

([]<>)

Experimente online!

DJMcMayhem
fonte
Competição como sempre
Assistente de Trigo
1
Quem pensaria que combinar duas linguagens ilegíveis, Whitespace e Brain-Flak, poderia ser considerado "legível"!
caird coinheringaahing
3

R , 28 bytes

function(n)rep(1:n,1:n+1)[n]

Experimente online!

Cria o vetor de tempos 1repetidos 2, tempos 2repetidos 3, ..., tempos nrepetidos n+1e pega o nthelemento. Isso causará erro de memória porque 1:né muito grande ou porque a lista repetida com n*(n+1)/2 - 1elementos é muito grande.

R , 29 bytes

function(n)((8*n+1)^.5-1)%/%2

Experimente online!

Calcula o valor diretamente, usando a fórmula encontrada na resposta de alefalpha . Isso deve ser executado sem problemas, além da precisão numérica possivelmente.

R , 30 bytes

function(n)sum(cumsum(1:n)<=n)

Experimente online!

Conta os números triangulares menores ou iguais a n. Isso possivelmente causará um erro de memória se 1:nfor grande o suficiente - por exemplo, 1e9ele lança Error: cannot allocate vector of size 3.7 Gb.

Giuseppe
fonte
2

TI-Basic, 12 bytes

int(√(2Ans+1/4)-.5
Timtech
fonte
2

JavaScript (Node.js) , 18 bytes

x=>(x-~x)**.5-.5|0

Experimente online!

Unihedron
fonte
Isso está sempre correto? Não tenho certeza floor((sqrt(8x+4)-1)/2)(sua fórmula) e floor((sqrt(8x+1)-1)/2)(fórmula correta) dão o mesmo resultado para todos x.
ETHproductions
@ETHproductions Eu poderia blefar e dizer "sim", mas acho que a resposta mais honesta é que você deve tentar desenvolver sua própria hipótese e descobrir se / por que ela reflete a mesma fórmula. Eu não criei essa abordagem sozinho (aprendi em um site diferente), mas brinquei um pouco com ela. É uma abordagem muito interessante e não quero dissecar o sapo tão cedo.
Unihedron
Hmm. Não tenho certeza de como provar isso diretamente, mas escrevi um forçador bruto que não encontra falhas abaixo de 100 milhões.
ETHproductions
2

Japonês , 8 bytes

Solução de fórmula fechada.

*8Ä ¬É z

Tente


Explicação

Multiplique por 8, adicione 1 ( Ä), obtenha a raiz quadrada ( ¬), subtraia 1 ( É) e o piso divida o resultado por 2 ( z).


Alternativa, 8 bytes

Porto da solução Jelly DJMcMayhem .

õ å+ è§U

Tente

Gere uma matriz de números inteiros ( õ) de 1 para entrada, reduza cumulativamente ( å) por adição ( +) e conte ( è) os elementos que são menores ou iguais a ( §) a entrada ( U).

Shaggy
fonte
2

Flacidez Cerebral , 70 56 48 bytes

{([(({}[({}())()])[()])]<>){<>({}())}{}<>{}}<>{}

Experimente online!

Explicação

A parte principal disso é o seguinte snippet que escrevi:

([(({})[()])]<>){<>({}())}{}<>{}

Isso não fará nada se o TOS for positivo e alternar as pilhas caso contrário. É super stack impuro, mas funciona. Agora, a parte principal do programa subtrai números cada vez maiores da entrada até que a entrada não seja positiva. Iniciamos o acumulador em 1 cada vez que subtraímos mais 1 do que o acumulador da entrada.

({}[({}())()])

Podemos colocar isso dentro do snippet acima

([(({}[({}())()])[()])]<>){<>({}())}{}<>{}

Isso é colocado em um loop e é executado até trocarmos de pilhas. Quando o loop termina, recuperamos o acumulador trocando pilhas e removendo o lixo.

Assistente de Trigo
fonte
2

Pitão , 7 bytes

lh{I#./

Experimente online!

Mantenha filtro as partições inteiras que são Idiferentes da desduplicação, agarre o hcabeçote e obtenha seu length.

Prova de validade

Não é muito rigoroso nem bem formulado.

Deixe A = um 1 + A 2 + ... + um n e B = b 1 + b 2 + ... + b m ser duas partições distintas do mesmo número inteiro N . Vamos assumir que A é a partição exclusiva mais longa . Depois que a desduplicar B , isto é, substituir múltiplas ocorrências da mesma inteiro com apenas um deles, sabemos que a soma de B é menos do que N . Mas também sabemos que o resultado da função está aumentando (não estritamente), para que possamos deduzir que a partição exclusiva mais longa A sempre tem pelo menos a mesma quantidade de elementos que a contagem de itens exclusivos em outras partições.

Mr. Xcoder
fonte
2

Triangularidade , 49 bytes

....)....
...2)2...
..)1/)8..
.)1/)IE/.
@^)1_+/i.

Experimente online!

Como funciona

A triangularidade exige que o código tenha uma distribuição triangular dos pontos. Ou seja, o comprimento de cada linha deve ser igual ao número de linhas multiplicado por 2 e decrementado, e cada linha deve ter (em cada lado) um número de pontos igual à sua posição no programa (a linha inferior é a linha 0, o acima é a linha 1 e assim por diante). Existem apenas alguns comandos, e qualquer caractere que não seja o listado na página 'Wiki / Comandos' é tratado como não operacional (pontos estranhos não afetam o programa de forma alguma, desde que a forma geral do programa permanece retangular).

Note-se que para os comandos de dois argumentos, eu usei um e b em todo o explicação. Tendo isso em mente, vamos ver o que o programa real faz, depois de remover todos os caracteres estranhos que compõem o preenchimento:

)2)2)1/)8)1/)IE/@^)1_+/i | Input from STDIN and output to STDOUT.

)                        | Push a 0 onto the stack. Must precede integer literals.
 2                       | Push ToS * 10 + 2 (the literal 2, basically).
  )2                     | Again, push a 2 onto the stack. This can be replaced by D
                         | (duplicate), but then the padding would discard the saving.
    )1                   | Literal 1.
      /                  | Division. Push b / a (1 / 2).
       )8)1              | The literal 8 and the literal 1 (lots of these!).
           /             | Division. Push b / a (1 / 8).
            )IE          | Get the 0th input from STDIN and evaluate it.
               /         | Divide it by 1 / 8 (multiply by 8, but there isn't any
                         | operand for multiplication, and I'm not willing to add one).
                @        | Add 1 to the result.
                 ^       | Exponentiation. Here, it serves as a square too.
                  )1_+   | Decrement (add literal -1).
                      /  | Divide (by 2).
                       i | Cast to an integer.

Uma solução alternativa e mais curta se o preenchimento não for necessário:

....)....
...2)1...
../DD)I..
.E/)4)1/.
+^s_+i...

Experimente online!

Mr. Xcoder
fonte
2

PowerShell 3.0, 45 bytes

[math]::Sqrt(2*$args[0]+.25)-.5-replace'\..*'

A chamada matemática doeu e o arredondamento dos banqueiros do PS é o diabo real (portanto, é necessário que o regex trunque para salvar um byte), mas isso parece bem.

Veskah
fonte
2

Java (JDK) , 28 bytes

n->~-(int)Math.sqrt(8*n+1)/2

Experimente online!

Como o exemplo realmente não foi muito bom: p

Créditos

Olivier Grégoire
fonte
1
28 bytes " Como o seu código não estava realmente muito bem "; p
Kevin Cruijssen
@KevinCruijssen Bem, agora é! : o
Olivier Grégoire
1

Geléia , 7 bytes

ŒPfŒṗṪL

Executa aproximadamente no tempo O (2 n ) .

Experimente online!

Como funciona

ŒPfŒṗṪL  Main link. Argument: n

ŒP       Powerset; yield all subarrays of [1, ..., n], sorted by length.
   Œṗ    Yield all integer partitions of n.
  f      Filter; keep subarrays that are partitions.
     Ṫ   Tail; extract the last result.
      L  Compute its length.
Dennis
fonte
1

JavaScript (ES7), 22 19 bytes

n=>(8*n+1)**.5-1>>1

-3 bytes graças a ETHproductions.


Tente

o.innerText=(f=
n=>(8*n+1)**.5-1>>1
)(i.value=1000000000);oninput=_=>o.innerText=f(+i.value)
<input id=i type=number><pre id=o>


Explicação

Multiplique a entrada por 8 e adicione 1, aumente para 0,5, fornecendo a raiz quadrada, subtraia 1 e mude o resultado para 1.

Shaggy
fonte
Você pode incluir uma explicação? Eu não faço Javascript há algum tempo
FantaC
Que tal n=>(8*n+1)**.5-1>>1salvar 3 bytes? (não testei)
ETHproductions
Eu superei isso em JS: codegolf.stackexchange.com/a/152558/21830
Unihedron
@ETHproductions - parece que funciona, obrigado.
Shaggy
@tfbninja, eu teria pensado bastante auto-explicativo, mas uma explicação adicionada.
Shaggy
1

Python 2/3, 32 bytes

Implementação em Python da fórmula de formulário fechado

lambda n:int((sqrt(1+8*n)-1)//2)

A divisão inteira //2arredonda para zero, portanto, não é floor( )necessário

Karl der Kaefer
fonte
1
Bem-vindo ao PPCG! Isso precisa from math import sqrtfuncionar? Nesse caso, ele deve ser incluído no bytecount. (Nesse caso, lambda n:int((math.sqrt(1+8*n)-1)//2) import math é um pouco mais curto. )
Steadybox
29 bytes
FlipTack
Sim, ele precisa da importação para funcionar, de modo que deve ser incluído na contagem de bytes.
mbomb007
1

Haskell , 28 bytes

Meio chato, mas é bem mais curto que a outra solução Haskell e tem uma ótima expressão sem pontos. Infelizmente, não consegui reduzi-lo mais sem o sistema de tipos atrapalhar:

g x=floor$sqrt(2*x+0.25)-0.5

Experimente online!

Sem ponto, 33 bytes

ceiling.(-0.5+).sqrt.(0.25+).(2*)

Como alternativa, 33 bytes

Mesmo tamanho que a versão pointfree, mas muito mais interessante.

g n=sum[1|x<-scanl1(+)[1..n],n>x]
ბიმო
fonte
Consegui amarrar a fórmula corrigindo alguns erros estúpidos!
totallyhuman
@totallyhuman: Nice, agora o seu é muito mais agradável também :)
ბიმო
1

Via Láctea , 12 bytes

'8*1+g1-2/v!

Explicação

code         explanation       value

'            push input        n          
 8*          push 8, multiply  8n
   1+        add 1             8n+1
     g       square root       sqrt(8n+1)
      1-     subtract 1        sqrt(8n+1)-1
        2/   divide by 2       (sqrt(8n+1)-1)/2
          v  floor             floor((sqrt(8n+1)-1)/2)
           ! output
ovs
fonte
1

Pyt , 7 5 bytes

Đř△>Ʃ

Explicação:

                      Implicit input
Đř△                   Gets a list of the first N triangle numbers
   >                  Is N greater than each element in the list? (returns an array of True/False)
    Ʃ                 Sums the list (autoconverts booleans to ints)



Maneira mais rápida, mas mais longa

Pyt , 11 9 bytes

Đ2*√⌈ř△>Ʃ

Explicação:

Đ2*√⌈ř△           Gets a list of triangle numbers up to the ceiling(sqrt(2*N))-th
       >          Is N greater than each element of the list? (returns an array of True/False)
        Ʃ         Sums the array



Caminho alternativo - porto da resposta de Shaggy

Pyt , 8 7 bytes

8*⁺√⁻2÷
mudkip201
fonte
1

J , 11 bytes

2&!inv<.@-*

Experimente online!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor
FrownyFrog
fonte
Eu gosto desse truque *para produzir 1
Jonah
1

Espaço em branco , 111 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_integer_from_STDIN][T T   T   _Retrieve_input][S S S T    S S S N
_Push_8][T  S S N
_Multiply][S S S T  N
_Push_1][T  S S S _Add][S S T   T   N
_Push_n=-1][N
S S N
_Create_Label_SQRT_LOOP][S S S T    N
_Push_1][T  S S S _Add][S N
S _Duplicate_n][S N
S _Duplicate_n][T   S S N
Multiply][S T   S S T   S N
_Copy_0-based_2nd_(the_input)][S S S T  N
_Push_1][T  S S S _Add][T   S S T   _Subtract][N
T   T   N
_If_negative_jump_to_Label_SQRT_LOOP][S S S T   S N
_Push_2][T  S S T   _Subtract][S S S T  S N
_Push_2][T  S T S _Integer_divide][T    N
S T _Print_integer]

Letras S(espaço), T(tabulação) e N(nova linha) adicionadas apenas como destaque.
[..._some_action]adicionado apenas como explicação.

Experimente online (apenas com espaços brutos, guias e novas linhas).

Explicação em pseudo-código:

Usa a fórmula:

fn=8n+1-12

OBSERVAÇÃO: O espaço em branco não possui uma raiz quadrada incorporada, portanto, precisamos fazer isso manualmente.

Integer i = read STDIN as integer
i = i * 8 + 1
Integer n = -1
Start SQRT_LOOP:
  n = n + 1
  If(n*n < i+1):
    Go to next iteration of SQRT_LOOP
n = (n - 2) integer-divided by 2
Print n as integer to STDOUT
Kevin Cruijssen
fonte
0

Vitsy , 16 bytes

2*14/+12/^12/-_N

Experimente online!

Também poderia adicionar minha própria contribuição à mistura. Isso é mais curto que a solução de iterações de partição no Vitsy.

Addison Crump
fonte
0

Oásis , 14 bytes

n8*1+1tm1%_b+0

Experimente online!

Quão?

n8*1+           8n + 1
     1tm        sqrt
        1%_     integer?
           b+   add f(n-1)

             0  f(0) is 0

Esta é uma solução recursiva que incrementa o resultado quando encontra um índice triangular, começando com 0 para a entrada 0.

Uriel
fonte
0

Ruby , 27 bytes

Três pelo preço de um. Estou decepcionado por não poder ir mais baixo.

->n{a=0;n-=a+=1while n>a;a}
->n{((8*n+1)**0.5-1).div 2}
->n{((n-~n)**0.5-0.5).to_i}

Experimente online! (para selecionar a função, adicione f = na frente)

Unihedron
fonte