Znajdź największą liczbę różnych liczb całkowitych, które sumują się do n

18

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą wejściową n(od 1 do limitu twojego języka, włącznie), zwróć lub wypisz maksymalną liczbę różnych dodatnich liczb całkowitych, które sumują się n.

Przypadki testowe

Niech fokreślić prawidłową funkcję w zależności od zadania:

Sekwencja fod 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, ...

Jako większy przypadek testowy:

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

Kod testowy

W przypadku przypadków testowych, które nie zostały wyraźnie podane, dane wyjściowe kodu powinny być zgodne z wynikiem:

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

Wypróbuj online!

Addison Crump
źródło
Czy może być zindeksowany?
całkowicieludzki
1
@totallyhuman „to” jest odpowiedzią? Ponieważ nie chodzi o listę ...
Addison Crump
3
@ totalniehuman Nie. Chodzi o różne partycje określonych liczb.
Addison Crump
5
To jest OEIS A003056 .
Jeppe Stig Nielsen
4
Za każdym razem, gdy wpadam na stos kodegolfa, czuję się nieznaczny. Odpowiedzi i komentarze są czymś więcej niż pokorą. Pytania są zwykle interesujące, ale jego komentarz @JeppeStigNielsen po prostu rzuca ukończone plany, gdy wciąż zastanawiamy się nad powierzchnią podłogi.
KalleMP,

Odpowiedzi:

9

05AB1E , 4 bajty

ÅTg<

Wypróbuj online!

Idealne narzędzie do pracy.

ÅTPlony lista nm ll ţ numery riangular włącznie N (niestety zawiera 0 też w inny sposób byłoby 3 bity), g<dostaje len g p i zmniejsza się.

Pan Xcoder
źródło
8

Galaretka , 6 5 bajtów

R+\»ċ

Wypróbuj online!

Nieco wydajne. Ta sekwencja zwiększa się przy liczbach trójkątnych, więc liczy tylko, ile liczb trójkątnych jest mniejszych niż n .

Wyjaśnienie:

        # 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
źródło
W wyjaśnieniu z pewnością masz na myśli „ile liczb jest mniejszych lub równych n
Luis Mendo
@LuisMendo Zobacz nowe objaśnienie.
DJMcMayhem
6

Haskell , 26 bajtów

-2 bajty dzięki H.PWiz.

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

Wypróbuj online!

Zwraca n-ty element liczb całkowitych, w którym każdy i jest replikowany i + 1 razy.

całkowicie ludzki
źródło
3
Nie mogę powstrzymać się od pytania, czym jest „succ”
Addison Crump
Tak, wiem lol. succoznacza successor.
całkowicieludzki
5

Brain-Flak , 36 bajtów

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

Wypróbuj online!

Wykorzystuje tę samą strukturę co standardowy algorytm podziału, z tym wyjątkiem, że „dzielnik” jest zwiększany za każdym razem, gdy jest czytany.

Nitrodon
źródło
3

Brain-Flak , 82 bajty

Dodano spację dla „Czytelności”

(())

{
    {}

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

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

}{}{}{}

([]<>)

Wypróbuj online!

DJMcMayhem
źródło
Rywalizacja jak zawsze
Wheat Wizard
1
Kto by pomyślał, że połączenie dwóch nieczytelnych języków, Whitespace i Brain-Flak, można uznać za „czytelne”!
caird coinheringaahing
3

R , 28 bajtów

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

Wypróbuj online!

Tworzy wektor 1powtarzanych 2czasów, 2powtarzanych 3czasów, ..., npowtarzanych n+1czasów i przyjmuje nthelement. Spowoduje to błąd pamięci albo dlatego, że 1:njest zbyt duży, albo dlatego, że lista powtarzanych n*(n+1)/2 - 1elementów jest zbyt duża.

R , 29 bajtów

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

Wypróbuj online!

Oblicza wartość bezpośrednio, korzystając ze wzoru znalezionego w odpowiedzi Alephalpha . Powinno to działać bez żadnych problemów, z wyjątkiem możliwie dokładności liczbowej.

R , 30 bajtów

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

Wypróbuj online!

Liczy liczby trójkątne mniejsze lub równe n. Prawdopodobnie spowoduje to błąd pamięci, jeśli 1:njest wystarczająco duży - na przykład przy 1e9jego rzucaniu Error: cannot allocate vector of size 3.7 Gb.

Giuseppe
źródło
2

TI-Basic, 12 bajtów

int(√(2Ans+1/4)-.5
Timtech
źródło
2

JavaScript (Node.js) , 18 bajtów

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

Wypróbuj online!

Unihedron
źródło
Czy to zawsze jest poprawne? Nie jestem pewien floor((sqrt(8x+4)-1)/2)(twoja formuła) i floor((sqrt(8x+1)-1)/2)(poprawna formuła) dają taki sam wynik dla każdego x.
ETHprodukcje
@ETHproductions Mógłbym blefować i powiedzieć „tak”, ale myślę, że bardziej uczciwą odpowiedzią jest to, że powinieneś spróbować rozwinąć własną hipotezę i dowiedzieć się, czy / dlaczego odzwierciedla tę samą formułę. Sam nie wpadłem na takie podejście (nauczyłem się go z innej strony), ale trochę się z tym bawiłem. To bardzo interesujące podejście i nie chcę tak wcześnie analizować żaby.
Unihedron
Hmm Nie jestem pewien, jak to udowodnić bezpośrednio, ale napisałem brutalny forcer, który nie znajduje żadnych niepowodzeń poniżej 100 milionów.
ETHproductions
2

Japt , 8 bajtów

Zamknięte rozwiązanie formuły.

*8Ä ¬É z

Spróbuj


Wyjaśnienie

Pomnóż przez 8, dodaj 1 ( Ä), uzyskaj pierwiastek kwadratowy ( ¬), odejmij 1 ( É) i podziel wynik przez 2 ( z).


Alternatywnie, 8 bajtów

Port rozwiązania galaretki DJMcMayhem .

õ å+ è§U

Spróbuj

Wygeneruj tablicę liczb całkowitych ( õ) od 1 do wejścia, łącznie zmniejsz ( å) dodając ( +) i zlicz ( è) elementy, które są mniejsze lub równe ( §) wejściowi ( U).

Kudłaty
źródło
2

Brain-Flak , 70 56 48 bajtów

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

Wypróbuj online!

Wyjaśnienie

Główną częścią tego jest następujący fragment, który napisałem:

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

Nie zrobi to nic, jeśli TOS będzie dodatni i w przeciwnym razie zmieni stosy. To jest super nieczyste, ale działa. Teraz główna część programu odejmuje coraz większe liczby od danych wejściowych, dopóki dane wejściowe nie będą dodatnie. Akumulator uruchamiamy od 1 za każdym razem odejmując o 1 więcej niż akumulator od wejścia.

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

Możemy to umieścić we fragmencie powyżej

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

To jest umieszczone w pętli, aby działało, dopóki nie zmienimy stosów. Po zakończeniu pętli odzyskujemy akumulator, zmieniając stosy i usuwając śmieci.

Kreator pszenicy
źródło
1
Trochę konkurencji
Nitrodon
2

Pyth , 7 bajtów

lh{I#./

Wypróbuj online!

Filtruj - zachowuj partycje całkowite, które nie Iróżnią się od deduplikacji, chwyć head i uzyskaj jego length.

Dowód ważności

Niezbyt rygorystyczne ani dobrze sformułowane.

Niech a = 1 + A 2 + ... + a n i b = 1 + b 2 + ... + B m dwa oddzielne przegrody o tej samej liczby całkowitej N . Zakładamy, że A jest najdłuższą unikalną partycją. Po my deduplikuj B , czyli zastąpienie wielu wystąpień tej samej liczby całkowitej ze tylko jeden z nich, wiemy, że suma B jest mniejsza niż N . Ale wiemy również, że wynik funkcji rośnie (nie ściśle), więc możemy wywnioskować, że najdłuższa unikalna partycja A zawsze ma co najmniej taką samą liczbę elementów, jak liczba unikalnych elementów w innych partycjach.

Pan Xcoder
źródło
2

Trójkątność , 49 bajtów

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

Wypróbuj online!

Jak to działa

Trójkątność wymaga, aby kod miał trójkątny rozkład kropek. Oznacza to, że długość każdego wiersza musi być równa liczbie wierszy pomnożonej przez 2 i zmniejszonej, a każdy wiersz musi mieć (z każdej strony) liczbę kropek równą swojej pozycji w programie (dolny wiersz to wiersz 0, ten powyżej to rząd 1 i tak dalej). Jest tylko kilka poleceń, a każdy znak inny niż wymieniony na stronie „Wiki / Commands” jest traktowany jako brak działania (zewnętrzne kropki nie wpływają w żaden sposób na program, o ile ogólny kształt programu pozostaje prostokątny).

Zauważ, że w przypadku poleceń dwuparametrowych użyłem a i b w całym objaśnieniu. Mając to na uwadze, zobaczmy, co robi rzeczywisty program, po usunięciu wszystkich obcych znaków, które składają się na dopełnienie:

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

Alternatywne rozwiązanie i krótsze, jeśli wypełnienie nie byłoby konieczne:

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

Wypróbuj online!

Pan Xcoder
źródło
2

PowerShell 3.0, 45 bajtów

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

Wezwanie matematyczne boli, a zaokrąglanie przez bankiera PS jest faktycznym diabłem (stąd potrzeba wyrażenia regularnego, aby obciąć bajt), ale wydaje się to całkiem w porządku.

Veskah
źródło
2

Java (JDK) , 28 bajtów

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

Wypróbuj online!

Ponieważ przykład nie był tak naprawdę dobrze golfowany: str

Kredyty

Olivier Grégoire
źródło
1
28 bajtówPonieważ twój kod naprawdę nie był dobrze golfowany ”; p
Kevin Cruijssen
@KevinCruijssen Cóż, teraz jest! : o
Olivier Grégoire
1

Galaretka , 7 bajtów

ŒPfŒṗṪL

Działa z grubsza w czasie O (2 n ) .

Wypróbuj online!

Jak to działa

Œ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
źródło
1

JavaScript (ES7), 22 19 bajtów

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

-3 bajty dzięki produktom ETH.


Spróbuj

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>


Wyjaśnienie

Pomnóż wartość wejściową przez 8 i dodaj 1, podnieś ją do potęgi .5, dając nam pierwiastek kwadratowy, odejmij 1 i bitowo przesuń wynik o 1.

Kudłaty
źródło
Czy możesz podać wyjaśnienie? Od jakiegoś czasu nie robiłem Javascript
FantaC
Jak n=>(8*n+1)**.5-1>>1zaoszczędzić 3 bajty? (nie testowałem)
ETHproductions
Wygrałem to w JS: codegolf.stackexchange.com/a/152558/21830
Unihedron
@ETHproductions - wygląda na to, że to działa, dzięki.
Kudłaty
@ tfbninja, myślałem, że to dość oczywiste, ale wyjaśnienie dodane.
Kudłaty
1

Python 2/3, 32 bajty

Implementacja formuły zamkniętej w języku Python

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

Podział liczb całkowitych //2zaokrągla się do zera, więc nie jest floor( )wymagany

Karl der Kaefer
źródło
1
Witamy w PPCG! Czy to musi from math import sqrtdziałać? Jeśli tak, należy go uwzględnić w bajcie. (W takim przypadku lambda n:int((math.sqrt(1+8*n)-1)//2) import math jest nieco krótszy. )
Steadybox
29 bajtów
FlipTack,
Tak, import musi działać, więc powinien zostać uwzględniony w liczbie bajtów.
mbomb007
1

Haskell , 28 bajtów

Trochę nudno, ale to znacznie krótsze niż inne rozwiązanie Haskell i ma naprawdę fajny, bezcelowy wyraz. Niestety nie mogłem go skrócić, gdyby system typów nie przeszkadzał:

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

Wypróbuj online!

Pointfree, 33 bajty

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

Alternatywnie 33 bajty

Taka sama długość jak wersja bez pointa, ale o wiele bardziej interesująca.

g n=sum[1|x<-scanl1(+)[1..n],n>x]
ბიმო
źródło
Udało mi się związać formułę , naprawiając głupie błędy!
całkowicieludzki
@totallyhuman: Fajnie, teraz twoje też jest o wiele ładniejsze :)
ბიმო
1

Droga Mleczna , 12 bajtów

'8*1+g1-2/v!

Wyjaśnienie

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
źródło
1

Pyt , 7 5 bajtów

Đř△>Ʃ

Wyjaśnienie:

                      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)



Szybciej, ale dłużej

Pyt , 11 9 bajtów

Đ2*√⌈ř△>Ʃ

Wyjaśnienie:

Đ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



Alternatywny sposób - port odpowiedzi Kudłaty

Pyt , 8 7 bajtów

8*⁺√⁻2÷
mudkip201
źródło
1

J , 11 bajtów

2&!inv<.@-*

Wypróbuj online!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor
FrownyFrog
źródło
Podoba mi się ten trik z *produkcją 1
Jonah
1

Biała spacja , 111 bajtów

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

Litery S(spacja), T(tab) i N(nowa linia) dodane tylko jako wyróżnienia.
[..._some_action]dodano tylko jako wyjaśnienie.

Wypróbuj online (tylko z surowymi spacjami, tabulatorami i nowymi wierszami).

Objaśnienie w pseudo-kodzie:

Korzysta ze wzoru:

fan=8n+1-12)

UWAGA: Białe znaki nie mają wbudowanego pierwiastka kwadratowego, więc musimy to zrobić ręcznie.

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
źródło
0

Vitsy , 16 bajtów

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

Wypróbuj online!

Równie dobrze mogę dodać własny wkład do miksu. Jest to krótsze niż rozwiązanie iteracji partycji w Vitsy.

Addison Crump
źródło
0

Oaza , 14 bajtów

n8*1+1tm1%_b+0

Wypróbuj online!

W jaki sposób?

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

             0  f(0) is 0

Jest to rozwiązanie rekurencyjne, które zwiększa wynik, gdy napotka trójkątny indeks, zaczynając od 0 dla wejścia 0.

Uriel
źródło
0

Rubinowy , 27 bajtów

Trzy za cenę jednego. Jestem rozczarowany, że nie mogę skrócić się.

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

Wypróbuj online! (aby wybrać funkcję, dodaj f = przed nią)

Unihedron
źródło