Temukan jumlah bilangan bulat berbeda terbesar yang dijumlahkan ke n

18

Tugas

Diberikan bilangan bulat positif masukan n(dari 1 hingga batas bahasa Anda, secara inklusif), kembalikan atau hasilkan jumlah maksimum bilangan bulat positif berbeda yang dijumlahkan n.

Uji Kasus

Mari ftentukan fungsi yang valid sesuai dengan tugas:

Urutan untuk f, mulai dari 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, ...

Sebagai test case yang lebih besar:

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

Kode Uji

Untuk setiap kasus uji yang tidak diberikan secara eksplisit, output kode Anda harus cocok dengan hasil dari yang berikut:

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

Cobalah online!

Addison Crump
sumber
Apakah bisa diindeks 0?
manusiawi
1
@totallyhuman "it" menjadi jawabannya? Karena ini bukan tentang daftar ...
Addison Crump
3
@totallyhuman No. Ini tentang partisi yang berbeda dari angka-angka tertentu.
Addison Crump
5
Ini adalah OEIS A003056 .
Jeppe Stig Nielsen
4
Saya merasa sangat tidak berarti setiap kali saya tersandung ke tumpukan codegolf. Jawaban dan komentarnya lebih dari sekadar merendahkan. Pertanyaan-pertanyaan ini biasanya menarik juga, tetapi dengan komentarnya @JeppeStigNielsen hanya melempar cetak biru yang sudah selesai ketika kita masih merenungkan area lantai.
KalleMP

Jawaban:

9

05AB1E , 4 byte

ÅTg<

Cobalah online!

Alat yang sempurna untuk pekerjaan itu.

ÅTmenghasilkan daftar nomor Å ll T riangular hingga dan termasuk N (sayangnya termasuk 0 juga, jika tidak akan menjadi 3 byte), g<dapatkan len g th dan kurangi.

Tuan Xcoder
sumber
8

Jelly , 6 5 byte

R+\»ċ

Cobalah online!

Agak efisien. Urutan ini bertambah pada angka segitiga, jadi ini hanya menghitung berapa banyak angka segitiga lebih kecil dari n .

Penjelasan:

        # 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
sumber
Dalam penjelasannya, yang Anda maksud adalah "berapa angka yang lebih kecil atau sama dengan n "
Luis Mendo
@LuisMendo Lihat penjelasan baru.
DJMcMayhem
6

Haskell , 26 byte

-2 byte terima kasih kepada H.PWiz.

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

Cobalah online!

Ini mengembalikan elemen ke - n dari seluruh bilangan di mana masing-masing i direplikasi i + 1 kali.

benar-benar manusiawi
sumber
3
Saya tidak bisa tidak bertanya apa itu "succ"
Addison Crump
Ya, saya tahu lol. succsingkatan successor.
totallyhuman
5

Brain-Flak , 36 byte

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

Cobalah online!

Ini menggunakan struktur yang sama dengan algoritma pembagian standar, kecuali bahwa "pembagi" bertambah setiap kali dibaca.

Nitrodon
sumber
3

Brain-Flak , 82 byte

Whitespace ditambahkan untuk "Keterbacaan"

(())

{
    {}

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

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

}{}{}{}

([]<>)

Cobalah online!

DJMcMayhem
sumber
1
Siapa yang mengira bahwa menggabungkan dua bahasa yang tidak dapat dibaca, Whitespace dan Brain-Flak, dapat dianggap "dapat dibaca"!
caird coinheringaahing
3

R , 28 byte

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

Cobalah online!

Menciptakan vektor 1berulang 2kali, 2berulang 3kali, ..., nberulang n+1kali dan mengambil nthelemen. Ini akan kesalahan memori karena1:n terlalu besar atau karena daftar yang diulang dengan n*(n+1)/2 - 1elemen terlalu besar.

R , 29 byte

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

Cobalah online!

Menghitung nilai secara langsung, menggunakan rumus yang ditemukan dalam jawaban alephalpha . Ini harus dijalankan tanpa masalah, selain dari ketepatan angka mungkin

R , 30 byte

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

Cobalah online!

Menghitung angka segitiga kurang dari atau sama dengan n. Ini mungkin kesalahan memori jika 1:ncukup besar - misalnya, saat 1e9melempar Error: cannot allocate vector of size 3.7 Gb.

Giuseppe
sumber
2

TI-Basic, 12 byte

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

JavaScript (Node.js) , 18 byte

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

Cobalah online!

Unihedron
sumber
Apakah ini selalu benar? Saya tidak yakin floor((sqrt(8x+4)-1)/2)(rumus Anda) dan floor((sqrt(8x+1)-1)/2)(rumus yang benar) memberikan hasil yang sama untuk setiap x.
ETHproduk
@ ETHproductions Saya bisa menggertak dan berkata "ya", tapi saya pikir jawaban yang lebih jujur ​​adalah Anda harus mencoba mengembangkan hipotesis Anda sendiri dan mencari tahu / mengapa itu mencerminkan formula yang sama. Saya tidak datang dengan pendekatan ini sendiri (saya mempelajarinya dari situs yang berbeda) tetapi saya sedikit mempermainkannya. Ini pendekatan yang sangat menarik dan saya tidak ingin membedah katak begitu awal.
Unihedron
Hmm. Saya tidak yakin bagaimana membuktikannya secara langsung, tetapi saya menulis brute-forcer yang tidak menemukan kegagalan di bawah 100 juta.
ETHproduksi
2

Japt , 8 byte

Solusi formula tertutup.

*8Ä ¬É z

Cobalah


Penjelasan

Kalikan dengan 8, tambahkan 1 ( Ä), dapatkan akar kuadrat ( ¬), kurangi 1 ( É) dan bagilah hasilnya dengan 2 ( z).


Alternatif, 8 byte

Pelabuhan solusi Jelly DJMcMayhem .

õ å+ è§U

Cobalah

Hasilkan array bilangan bulat ( õ) dari 1 ke input, secara kumulatif mengurangi ( å) dengan menambahkan ( +) dan menghitung ( è) elemen yang kurang dari atau sama dengan ( §) input ( U).

Shaggy
sumber
2

Brain-Flak , 70 56 48 byte

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

Cobalah online!

Penjelasan

Bagian utama dari ini adalah cuplikan berikut yang saya tulis:

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

Ini tidak akan melakukan apa-apa jika KL positif dan akan beralih tumpukan. Hal ini yang super tumpukan haram tetapi bekerja. Sekarang bagian utama dari program mengurangi jumlah yang semakin besar dari input sampai inputnya tidak positif. Kami memulai akumulator pada 1 setiap kali mengurangi 1 lebih dari akumulator dari input.

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

Kita bisa memasukkannya di dalam cuplikan di atas

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

Itu dimasukkan ke dalam loop sehingga dijalankan sampai kita berganti tumpukan. Setelah loop selesai, kami mengambil akumulator dengan menukar tumpukan dan menghapus sampah.

Wisaya Gandum
sumber
2

Pyth , 7 byte

lh{I#./

Cobalah online!

Filter-menjaga partisi integer yang Iberbeda atas deduplikasi, ambilh ead dan dapatkanl ength.

Bukti validitas

Tidak terlalu ketat dan tidak beralasan.

Mari A = a 1 + a 2 + ... + a n dan B = b 1 + b 2 + ... + b m menjadi dua partisi yang berbeda dari integer yang sama N . Kami akan menganggap bahwa A adalah partisi unik terpanjang . Setelah kami menghapus duplikat B , yaitu, menggantikan beberapa kejadian integer yang sama dengan hanya satu dari mereka, kita tahu bahwa jumlah B kurang dari N . Tetapi kita juga tahu bahwa hasil fungsi meningkat (tidak ketat), sehingga kita dapat menyimpulkan bahwa partisi unik terpanjang A selalu memiliki setidaknya jumlah elemen yang sama dengan jumlah item unik di partisi lain.

Tuan Xcoder
sumber
2

Triangularity , 49 byte

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

Cobalah online!

Bagaimana itu bekerja

Triangularity memerlukan kode untuk memiliki distribusi titik-titik. Artinya, panjang setiap baris harus sama dengan jumlah baris dikalikan 2 dan dikurangi, dan setiap baris harus memiliki (di setiap sisi) sejumlah titik yang sama dengan posisinya dalam program (baris bawah adalah baris 0, yang di atasnya adalah baris 1 dan seterusnya). Hanya ada beberapa perintah, dan karakter apa pun selain yang terdaftar di halaman 'Wiki / Perintah' diperlakukan sebagai no-op (titik-titik asing tidak mempengaruhi program dengan cara apa pun, selama bentuk keseluruhan program tetap persegi panjang).

Perhatikan bahwa untuk perintah dua argumen, saya telah menggunakan a dan b di seluruh penjelasan. Ingatlah itu, mari kita lihat apa yang sebenarnya dilakukan program, setelah menghapus semua karakter asing yang membentuk padding:

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

Solusi alternatif, dan lebih pendek jika padding tidak diperlukan:

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

Cobalah online!

Tuan Xcoder
sumber
2

PowerShell 3.0, 45 byte

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

Panggilan matematika itu menyakitkan dan pembulatan bankir PS adalah iblis yang sebenarnya (karenanya perlu regex untuk memotong untuk menyimpan byte) tetapi ini tampaknya cukup baik-baik saja.

Veskah
sumber
2

Java (JDK) , 28 byte

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

Cobalah online!

Karena contohnya benar-benar tidak golf dengan baik: p

Kredit

Olivier Grégoire
sumber
1
28 byte " Karena kode Anda benar-benar tidak
golf dengan
@KevinCruijssen Baiklah, sekarang! : o
Olivier Grégoire
1

Jelly , 7 byte

ŒPfŒṗṪL

Berjalan kira-kira masuk O (2 n ) .

Cobalah online!

Bagaimana itu bekerja

Œ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
sumber
1

JavaScript (ES7), 22 19 byte

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

-3 byte terima kasih untuk ETHproductions.


Cobalah

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>


Penjelasan

Lipat gandakan input dengan 8 dan tambahkan 1, naikkan ke pangkat .5, beri kami akar kuadrat, kurangi 1 dan bithift hasilnya tepat dengan 1.

Shaggy
sumber
Bisakah Anda memasukkan penjelasan? Saya belum pernah melakukan Javascript untuk sementara waktu
FantaC
Bagaimana jika n=>(8*n+1)**.5-1>>1 menyimpan 3 byte? (belum diuji)
ETHproduksi
Saya mengungguli ini di JS: codegolf.stackexchange.com/a/152558/21830
Unihedron
@ ETHproductions - sepertinya itu bekerja, terima kasih.
Shaggy
@ tfbninja, saya akan berpikir cukup jelas tetapi penjelasan ditambahkan.
Shaggy
1

Python 2/3, 32 byte

Implementasi python dari formula form tertutup

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

//2Putaran bilangan bulat mengarah ke nol, jadi tidak floor( )diperlukan

Karl der Kaefer
sumber
1
Selamat datang di PPCG! Apakah ini perlu from math import sqrtbekerja? Jika demikian, itu harus dimasukkan dalam bytecount. (Dalam hal lambda n:int((math.sqrt(1+8*n)-1)//2) import math ini sedikit lebih pendek. )
Steadybox
29 byte
FlipTack
Ya, ini membutuhkan impor untuk berfungsi, sehingga harus dimasukkan dalam jumlah byte.
mbomb007
1

Haskell , 28 byte

Agak membosankan, tetapi ini cukup pendek daripada solusi Haskell lainnya dan memiliki ekspresi pointfree yang sangat bagus. Sayangnya saya tidak bisa mendapatkannya lebih pendek tanpa sistem jenis menghalangi:

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

Cobalah online!

Pointfree, 33 byte

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

Atau, 33 byte

Panjangnya sama dengan versi pointfree, tetapi jauh lebih menarik.

g n=sum[1|x<-scanl1(+)[1..n],n>x]
ბიმო
sumber
Saya berhasil mengikat formula dengan memperbaiki beberapa kesalahan bodoh!
manusiawi
@totallyhuman: Bagus, sekarang milikmu juga jauh lebih baik :)
ბიმო
1

Bimasakti , 12 byte

'8*1+g1-2/v!

Penjelasan

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
sumber
1

Pyt , 7 5 byte

Đř△>Ʃ

Penjelasan:

                      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)



Lebih cepat, tapi jauh

Pyt , 11 9 byte

Đ2*√⌈ř△>Ʃ

Penjelasan:

Đ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



Cara alternatif - port jawaban Shaggy

Pyt , 8 7 byte

8*⁺√⁻2÷
mudkip201
sumber
1

J , 11 byte

2&!inv<.@-*

Cobalah online!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor
FrownyFrog
sumber
Saya suka trik dengan *menghasilkan 1
Jonah
1

Ruang putih , 111 byte

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

Huruf S(spasi), T(tab), dan N(baris baru) ditambahkan hanya sebagai penyorotan.
[..._some_action]ditambahkan sebagai penjelasan saja.

Cobalah online (dengan spasi, tab, dan hanya baris baru).

Penjelasan dalam pseudo-code:

Gunakan rumus:

fn=8n+1-12

CATATAN: Ruang kosong tidak memiliki built-root kuadrat, jadi kita harus melakukan ini secara manual.

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
sumber
0

Vitsy , 16 byte

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

Cobalah online!

Mungkin juga menambah kontribusi saya sendiri ke dalam campuran. Ini lebih pendek daripada solusi iterasi partisi di Vitsy.

Addison Crump
sumber
0

Oasis , 14 byte

n8*1+1tm1%_b+0

Cobalah online!

Bagaimana?

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

             0  f(0) is 0

Ini adalah solusi rekursif yang meningkatkan hasil ketika bertemu indeks segitiga, dimulai dengan 0 untuk input 0.

Uriel
sumber
0

Rubi , 27 byte

Tiga untuk harga satu. Saya kecewa karena saya tidak bisa lebih pendek.

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

Cobalah online! (untuk memilih fungsi, tambahkan f = di depannya)

Unihedron
sumber