Jumlah Integer Berturut-turut

27

Sebelum ada yang mengatakan apa pun, mirip dan mirip . Tapi ini bukan penipuan.


Beberapa bilangan bulat positif dapat ditulis sebagai jumlah setidaknya dua bilangan bulat positif berturut-turut. Sebagai contoh 9=2+3+4=4+5,. Tulis fungsi yang mengambil bilangan bulat positif sebagai inputnya dan mencetak sebagai outputnya urutan terpanjang dari peningkatan bilangan bulat positif berurutan yang menjumlahkannya (format apa pun dapat diterima, meskipun -5 byte jika outputnya adalah urutan peningkatan yang dipisahkan oleh +seperti ditunjukkan di atas) Jika tidak ada urutan seperti itu, maka nomor itu sendiri harus dicetak.

Ini kode golf. Aturan standar berlaku. Kode terpendek dalam byte menang.


Sampel (perhatikan bahwa pemformatan bervariasi)

Input:   9
Output:  2,3,4

Input:   8
Output:  8

Input:   25
Output:  [3,4,5,6,7]
Arcturus
sumber
2
Apakah angka yang dikeluarkan harus dalam urutan tertentu (seperti bertambah)?
xnor
2
Apakah angkanya harus> 0: 6 = 0 + 1 + 2 + 3 atau 6 = 1 + 2 + 3
Damien
5
Sebagai catatan, jika ada tantangan yang berkaitan erat, mengatakan "ini bukan penipuan" tidak akan banyak meyakinkan orang bahwa jika mereka berpikir itu adalah penipuan. Akan lebih bermanfaat jika Anda menjelaskan mengapa menurut Anda itu tidak benar.
Martin Ender
1
@ Damen "positif" biasanya berarti> 0. Jika 0 dimasukkan, itu akan disebut "non-negatif".
Martin Ender
3
cc @Vixen ^ (juga jika angka negatif diizinkan, solusi optimal akan selalu berkisar dari -n+1ke n)
Martin Ender

Jawaban:

11

Python, 67 byte

f=lambda n,R=[1]:n-sum(R)and f(n,[R+[R[-1]+1],R[1:]][sum(R)>n])or R

Strategi aneh langsung: mencari interval R dengan jumlah yang tepat.

  • Jika jumlahnya terlalu kecil, geser titik akhir kanan interval naik satu dengan menambahkan angka tertinggi berikutnya.
  • Jika jumlahnya terlalu besar, geser ke atas titik akhir kiri dengan menghapus elemen terkecil
  • Jika jumlahnya benar, output R.

Karena ujung bawah interval hanya meningkat, interval yang lebih lama ditemukan sebelum yang lebih pendek.

Tidak
sumber
Juga sangat efisien. Tumpukan rekursi akhirnya meluap, misalnya n = 8192.
primo
7

Pyth, 12 10 byte

j\+hfqsTQ}M^SQ2

Panjang kode 15 byte dan memenuhi syarat untuk bonus -5 byte . Cobalah online di Pyth Compiler .

Terima kasih kepada @Jakube untuk bermain golf 2 byte!

Bagaimana itu bekerja

j\+hfqsTQ}M^SQ2    (implicit) Store evaluated input in Q.

            S      Compute [1, ..., Q].
           ^  2    Get all pairs of elements of [1, ..., Q].
         }M        Reduce each pair by inclusive range. Maps [a, b] to [a, ..., b].
    f              Filter; for each pair T:
      sT             Add the integers in T.
     q  Q            Check if the sum equals Q.
                   Keep the pair if it does.
   h               Retrieve the first match.
                   Since the ranges [a, ..., b] are sorted by the value of a,
                   the first will be the longest, in ascending order.
j\+                Join, using '+' as separator.
Dennis
sumber
1
Bagi kita yang tidak tercerahkan di bidang Pyth, dapatkah Anda menambahkan penjelasan? :)
ETHproduk
Saya sudah mengedit jawaban saya.
Dennis
Keren terima kasih! Saya suka teknik Anda.
ETHproduk
1
Input 1000: 30 menit dan terus bertambah ...
primo
3

Mathematica, 73 68 65 56 43 byte

Cases[Range~Array~{#,#},i_/;Tr@i==#,{2},1]&
alephalpha
sumber
1
+1 Saya berakhir dengan solusi serupa tadi malam, tetapi internet saya mati. Anda juga dapat membuat Tuplesekspresi infiks.
LegionMammal978
3

Haskell, 49 48 byte

f n=[[a..b]|a<-[1..n],b<-[a..n],sum[a..b]==n]!!0
Damien
sumber
1
1 byte untuk disimpan: gunakan [...]!!0bukan head[...].
nimi
2

MATLAB, 87 79 byte

Saya tahu sudah ada jawaban MATLAB, tetapi yang satu ini sangat berbeda dalam pendekatan.

x=input('');m=1:x;n=.5-m/2+x./m;l=max(find(~mod(n(n>0),1)));disp(m(1:l)+n(l)-1)

Ini juga berfungsi pada Oktaf . Anda dapat mencoba online di sini . Saya sudah menambahkan kode ke consecutiveSum.mdalam ruang kerja yang ditautkan, jadi masukkan saja consecutiveSumpada prompt perintah, kemudian masukkan nilainya (misalnya 25).

Saya masih bekerja untuk mengurangi itu (mungkin menyesuaikan persamaan yang digunakan sedikit), tetapi pada dasarnya ia menemukan nilai terbesar nyang mmerupakan bilangan bulat, kemudian menampilkan mangka pertama dimulai dengan n.

Jadi mengapa ini berhasil? Yah pada dasarnya ada persamaan matematika yang mengatur semua angka-angka itu. Jika Anda menganggap bahwa semuanya berturut-turut, dan mulai dari titik tertentu, pada dasarnya Anda dapat mengatakan:

n+(n+1)+(n+2)+(n+3)+...+(n+p)=x

Sekarang, dari sini menjadi jelas bahwa urutan pada dasarnya hanya pangka segitiga pertama (termasuk 0'th), ditambahkan ke p+1banyak n. Sekarang jika kita membiarkan m=p+1, kita dapat mengatakan:

m*(n+(m-1)/2)==x

Ini sebenarnya cukup bisa dipecahkan. Saya masih mencari cara kode terpendek untuk melakukannya, saya punya beberapa ide untuk mencoba dan mengurangi kode di atas.


Untuk input 25, outputnya adalah:

3     4     5     6     7
Tom Carpenter
sumber
2
Berkenaan dengan poin Anda tentang angka segitiga, tantangan ini pada dasarnya adalah mencoba untuk menemukan angka segitiga dengan perbedaan positif dari input sehingga indeks angka segitiga dalam urutan 1,3,6,10,...dimaksimalkan.
Arcturus
1

Python 2, 94 byte

n=input()
r=int((2*n)**.5)
while r:
 if~r%2*r/2==n%r:print range(n/r-~-r/2,n/r-~r/2);r=1
 r-=1

Input diambil dari stdin. Solusi ini cocok untuk input yang sangat besar.

Ini mengulangi kemungkinan panjang solusi, r , memiliki r ≤ √ (2n) , dan memeriksa solusi secara eksplisit. Agar ada solusi, jika r aneh, n mod r harus nol, dan jika r genap, n mod r harus r / 2 .


Contoh Penggunaan

$ echo 8192 | python sum-con-int.py
[8192]

$ echo 1000002 | python sum-con-int.py
[83328, 83329, 83330, 83331, 83332, 83333, 83334, 83335, 83336, 83337, 83338, 83339]

$ echo 1000000006 | python sum-con-int.py
[250000000, 250000001, 250000002, 250000003]

Saya sengaja memilih contoh dengan output yang relatif kecil.

primo
sumber
1

Oktaf, 89 Bytes

Ini adalah yang terbaik yang bisa saya lakukan di Octave. Algoritma ini sama dengan xnor.

x=input('');k=i=1;while x;s=sum(k:i);if s<x;i++;elseif s>x;k++;else;x=0;end;end;disp(k:1)

Dalam MATLAB ini akan menjadi 95 byte:

x=input('');k=1;i=1;while x;s=sum(k:i);if s<x;i=i+1;elseif s>x;k=k+1;else x=0;end;end;disp(k:i)

Dalam MATLAB ini berjalan sekitar 0,1 detik untuk input 2000000dan 1 detik untuk input 1000002.

Stewie Griffin
sumber
1

awk, 51 byte

{while($0!=s+=s<$0?++j:-++i);while(++i-j)r=r i"+"}$0=r j

Kode ini 56 byte, minus 5 byte untuk format output. Saya harus menggunakan 4 byte tambahan untuk menghasilkan format itu, jadi saya benar-benar menyimpan 1 byte. Hore! ;)

Ini sebenarnya melakukan kerja keras penjumlahan mulai dari 1 hingga jumlahnya lebih besar dari input. Kemudian mulai mengurangi angka mulai dari 1 hingga jumlahnya lebih kecil dari input. Itu terus mengubah nomor awal dan akhir dengan cara ini sampai menemukan hasil, yang kemudian dicetak.

Contoh penggunaan

echo 303 | awk '{while($0!=s+=s<$0?++j:-++i);while(++i-j)r=r i"+"}$0=r j'

Keluaran contoh

48 + 49 + 50 + 51 + 52 + 53

Saya sudah mencoba ini untuk masukan 1e12dan memberikan hasil yang benar ( 464562+...+1488562) segera. Meskipun butuh beberapa saat mencetaknya tentu saja ...

Cabbie407
sumber
Cinta pendekatan Awk. Saya kesulitan mengerjakan urutan prioritas dalam binding. Maukah Anda memasukkan versi dengan tanda kurung lebih banyak agar lebih jelas? :)
Wildcard
1
Semoga ini bisa membantu: {while($0!=s)s+=(s<$0) ? (++j) : -(++i); while(++i<j)r=r i"+"}$0=r j saya selalu bilangan bulat terakhir yang dikurangkan dari awal rantai, j selalu bilangan bulat terakhir yang ditambahkan di akhir rantai
Cabbie407
0

Japt , 33 byte

Ini menggunakan teknik Pyth Dennis , meskipun jauh lebih lama ...

1oU à2 £W=Xg o1+Xg1¹x ¥U©W} rª ªU

Cobalah online! Peringatan: Untuk input yang lebih besar (<= 20), perlu beberapa saat untuk menyelesaikan, dan membekukan browser Anda hingga benar.

Tanpa penjelasan dan penjelasan

1oU à2 £    W=Xg o1+Xg1¹ x ¥ U© W} rª  ª U
1oU à2 mXYZ{W=Xg o1+Xg1) x ==U&&W} r|| ||U

          // Implicit: U = input integer
1oU à2    // Generate a range from 1 to U, and take all combinations of length 2.
mXYZ{     // Map each item X in this range to:
W=Xg o    //  Set variable W to the range of integers starting at the first item in X,
1+Xg1)    //  and ending at 1 + the second item in X.
x ==U&&W  //  If the sum of this range equals U, return W; otherwise, return false.
r||       // Reduce the result with the || operator, returning the first non-false value.
||U       // If this is still false, there are no consecutive ranges that sum to U,
          // so resort to U itself.
          // Implicit: output last expression

Versi penghasil bonus: (38 byte - 5 = 33)

1oU à2 £W=Xg o1+Xg1¹x ¥U©W} rª ªU² q'+
Produksi ETH
sumber
0

Julia, 92 byte

x->(t=filter(i->all(j->j==1,diff(sort(i))),partitions(x));collect(t)[indmax(map(length,t))])

Ini adalah fungsi anonim yang menerima integer dan mengembalikan array. Untuk menyebutnya, berikan nama, misf=x->... .

Tidak Disatukan:

function f(x::Integer)
    # Get all arrays of integers that sum to x
    p = partitions(x)

    # Filter these down to only consecutive runs by checking whether
    # all differences are 1
    t = filter(i -> all(j -> j == 1, diff(sort(i))), p)

    # Find the index of the longest element of t
    i = indmax(map(length, t))

    return collect(t)[i]
end
Alex A.
sumber
0

Ruby, 94 byte

->n{([*1..n].permutation(2).map{|i,j|[*i..j]if(i..j).reduce(:+)==n}-[p]).max_by{|k|k.size}||n}

Tidak Disatukan:

-> n {
  ([*1..n].permutation(2).map { |i,j|   # Finds all the possible sets of size 2
     [*i..j] if(i..j).reduce(:+) == n   # Adds a set to an array if sum of the set is n.
   }-[p]                                # Removes nil from the array
  ).max_by { |k|                        # Finds the longest sequence
    k.size
  } || n                                # Returns n if no sequence found.
}

Pemakaian:

->n{([*1..n].permutation(2).map{|i,j|[*i..j]if(i..j).reduce(:+)==n}-[p]).max_by{|k|k.size}||n}[25]
=> [3, 4, 5, 6, 7]
Vasu Adari
sumber
0

Serius, 53 - 5 = 48 byte

,;;;╝`;u@n╟(D;)`n(XXk`iu@u@x;Σ╛=[])Ii`╗`ñ╜M`M;░p@X'+j

Hex Dump

2c3b3b3bbc603b75406ec728443b29606e2858586b60697540754
0783be4be3d5b5d29496960bb60a4bd4d604d3bb0704058272b6a

Cobalah secara Online!

Ini adalah pendekatan brute force, mirip dengan Dennis's Pyth.

Semuanya hingga khanya membaca input nke register 1 dan kemudian membuat daftar [[1],[2,2],[3,3,3],[4,4,4,4],...]hingga n n.

Bit selanjutnya adalah fungsi yang disimpan dalam register 0 yang mengambil pasangan, menambah kedua elemen, mengubahnya menjadi suatu rentang, menemukan jumlah kisaran, dan memeriksa apakah jumlah itu adalah nilai dalam register 1. Jika ya, ia mengembalikan rentang yang sesuai, dan jika tidak, ia mengembalikan daftar kosong.

Bagian hingga kemunculan terakhir Msuatu fungsi di atas daftar daftar yang diuraikan di atas, lakukan enumeratepada setiap daftar, lalu pemetaan fungsi yang tersimpan di atasnya. Ketika selesai, kami memiliki daftar daftar yang masing-masing kosong atau kisaran yang dijumlahkan n.

;░menghapus daftar kosong. p@Xmengambil daftar pertama yang tersisa ( 0@Ejuga berfungsi). '+jmenempatkan +antara masing-masing nomor karena mengkonversi daftar ke string untuk bonus.

kuintopia
sumber
0

ES6, 72 byte

n=>{for(l=u=1;n;)n>0?n-=u++:n+=l++;return[...Array(u).keys()].slice(l);}

Port langsung dari solusi awk @ Cabbie407, tetapi tanpa bonus format, karena ini penalti di sini.

Neil
sumber
0

Python 3, 239 236 215 203 byte

Ini sedikit rumit. Saya harus bermain golf nanti.

def x(n):
 r=[n]
 for i in range(2,n):
  t=[]
  if i%2*(n%i<1):t=[j+n//i-i//2for j in range(i)]
  elif i%2<1and n%i==i//2:t=[j+n//i-i//2+1for j in range(i)]
  if t[:1]>[0]*(sum(t)==n):r+=t,
 return r[-1]

Itu kkarena jika Anda memeriksa t[0]kosong t, Python membuat suara kasar pada Anda. Sekali lagi, ini perlu bermain golf. Terima kasih t[:1], tidak ada lagi suara kasar! Anda hanya perlu memeriksa terhadap array lain.

Sherlock9
sumber
0

Jelly , 8 byte (tidak bersaing)

ẆS⁼¥Ðf⁸Ṫ

Cobalah online!

Jika saya mengerti dengan benar, ini bisa menjadi versi (11-5 = 6) -byte:

ẆS⁼¥Ðf⁸Ṫj”+
Erik the Outgolfer
sumber
Demi kepentingan, ada 12 solusi serupa (termasuk yang ini) dengan menukar persamaan non-vektor untuk persamaan vektor, mengubah argumen kiri ke argumen pertama atau ke identitas, dan bertukar sama dengan tidak-sama dan filter-in untuk filter-out untuk vektorisasi dan non-vektorisasi. : O
HyperNeutrino
Katakanlah saya memposting yang paling masuk akal, tetapi dengan optimasi kecepatan.
Erik the Outgolfer
0

05AB1E , 11 - 5 = 6 byte (tidak bersaing)

Mengambil bonus itu tentu saja :)

LŒʒOQ}é¤'+ý

Cobalah online!

LŒʒOQ}é¤'+ý  Argument: n
LŒ           Sublists of range 1 to n
  ʒOQ}       Filter by total sum equals n
      é¤     Get longest element
        '+ý  Join on '+'
kalsowerus
sumber
0

PHP, 70 byte

while(fmod($q=sqrt(2*$argn+(++$p-.5)**2)-.5,1));print_r(range($p,$q));

Jalankan sebagai pipa dengan -nRatau coba online .

bertambah phingga menemukan solusi integer untuk argument==(p+q)*(q-p+1)/2,
lalu mencetak rentang dari phingga q.

Titus
sumber
0

Excel VBA, 119 - 5 = 114 Bytes

Subrutin yang mengambil input ndari integer tipe yang diharapkan dan menampilkan urutan terpanjang dari angka berurutan yang menjumlahkannya ke sel[A1]

Sub a(n)
For i=1To n
s=0
For j=i To n
s=s+j
If s=n Then:For k=i To j-1:r=r &k &"+":Next:[A1]=r &j:End
Next
Next
End Sub
Taylor Scott
sumber