Urutan jumlah bilangan bulat yang tidak ada dalam urutan

28

Latar Belakang

Pertimbangkan urutan yang didefinisikan sebagai berikut:

  • Elemen pertama adalah 0;
  • Elemen kedua adalah 4;
  • Dari elemen ketiga dan seterusnya, nilainya dapat dihitung dengan:
    • Mengambil himpunan bilangan bulat dari 0 hingga elemen sebelumnya dari urutan (inklusif atau eksklusif, itu tidak masalah);
    • Menghapus semua bilangan bulat yang sudah muncul sebelumnya dalam urutan dari set;
    • Menambahkan elemen sisa set; itulah nilai yang Anda inginkan.

Menariknya, urutan ini tampaknya belum berada di OEIS .

Tugas

Tulis program atau fungsi yang mengambil integer n sebagai input, dan output elemen ke- n dari urutan.

Uji kasus

Beberapa elemen pertama dari urutan adalah:

  • 0
  • 4
  • 6 (1 + 2 + 3)
  • 11 (1 + 2 + 3 + 5)
  • 45 (1 + 2 + 3 + 5 + 7 + 8 + 9 + 10)
  • 969 (1 + 2 + 3 + 5 + 7 ... 10 + 12 ... 44)
  • 468930 (1 + 2 + 3 + 5 + 7 ... 10 + 12 ... 44 + 46 ... 968)

Klarifikasi

  • Secara teori, program Anda dapat menangani n sembarang jika dijalankan pada varian bahasa Anda yang memiliki bilangan bulat besar tanpa batas dan akses ke jumlah memori yang tidak terbatas. (Bahasa tanpa bignum tidak mungkin bisa mendapatkan lebih dari 468930, tapi itu bukan alasan untuk menuliskan kode jawaban).
  • Anda dapat memilih pengindeksan berbasis-0 atau berbasis-1 untuk urutan (misalnya terserah Anda apakah n = 1 mengembalikan elemen pertama, n = 2 elemen kedua, dan seterusnya; atau apakah n = 0 mengembalikan elemen pertama , n = 1 elemen kedua, dan seterusnya).
  • Tidak ada persyaratan pada algoritma yang Anda gunakan, atau pada efisiensinya; Anda dapat mengimplementasikan definisi urutan secara langsung (meskipun itu benar-benar tidak efisien), dan Anda juga dapat menerapkan algoritma berbeda yang mengarah ke hasil yang sama.

Kondisi kemenangan

Ini adalah , sehingga program terpendek yang benar, diukur dalam byte, menang.

Grzegorz Oledzki
sumber
1
Mengapa tidak mengizinkan keluaran tanpa batas alih-alih mengambil input?
John Dvorak
2
@JanDvorak: Karena itu memaksa semua program untuk menggunakan algoritma yang menghasilkan setiap istilah; metode penulisan pertanyaan ini bergantung pada para penjawab apakah mereka ingin melakukan itu, atau apakah mereka ingin menggunakan formula bentuk-tertutup (dengan asumsi ada satu). Jadi itu memberi lebih banyak pilihan strategi dalam menyelesaikan pertanyaan.
1
Saya berasumsi urutannya tidak ada karena 0,4 adalah offset yang aneh
boboquack
1
@ boboquack With (0,3), (0,2), (1,4) atau variasi serupa, urutannya akan konstan setelah beberapa istilah.
Dennis
Apakah tag [matematika] masuk akal untuk ini?
mbomb007

Jawaban:

10

Jelly , 13 12 9 byte

rSạo4¥ð@¡

Menggunakan pengindeksan berbasis 0.

Cobalah online!

Bagaimana itu bekerja

rSạo4¥ð@¡  Main link. No arguments. Implicit argument: 0

      ð    Collect everything to the left into a chain and start a new, dyadic one.
           The arity of the first chain is unknown at this point, as it isn't
           prefixed by ø, µ, or ð.
       @   Swap the arguments of the first chain. Swapping  arguments is only
           implemented for dyadic links, so this makes the chain dyadic.
        ¡  Read an integer n from STDIN and execute the chain n times. Taking the
           argument swap into account, the chain is executed first with 0 as left
           and right argument, then with the previous right argument as left
           argument and the previous return value as right argument.
           The return value of the last call is the return value of the quicklink
           and becomes the implicit output.

           Let's call the left argument x and the right argument y.
r            Range; yield [x, ..., y].
 S           Compute the sum of all integers in the range.
     ¥       Convert the two atoms to the left into a dyadic chain, and call that
             chain with arguments x and y.
   o4          Take the logical OR of x and 4, replacing a 0 with 4 and leaving
               positive integers untouched.
  ạ          Take the absolute difference of the sum to the left and the result of
             the logical OR to the right.
Dennis
sumber
10

Python, 66 60 byte

Terima kasih kepada @Dennis karena mencukur 6 byte!

f=lambda n:n>2and(f(n-1)-~f(n-2))*(f(n-1)-f(n-2))/2or(5-n)*n

Ini bukan potongan kode golf yang pernah ada, tetapi menggunakan rumus yang saya buat:

masukkan deskripsi gambar di sini

Di mana xdi sisi kanan adalah f(n - 1), dan yini f(n - 2).

Penjelasan:

Jumlah bilangan bulat berkelanjutan dari ahingga b(inklusif) dapat dijelaskan dengan rumus ini:

amount * average

Di mana amount(jumlah angka) digambarkan seperti ini:

((a - b) - 1)

Dan average(rata-rata semua angka) dijelaskan seperti ini:

(a + b) / 2

Jadi rumus lengkapnya sekarang:

  ((a - b) - 1)(a + b) / 2
= (a - b - 1)(a + b) / 2

Cara kita menerapkan formula ini ke dalam rumus akhir ini adalah untuk menggantikan auntuk f(n - 1), buntuk f(n - 2), yang pada dasarnya menghitung jumlah dari semua syarat baru, dan tambahkan lagi f(n - 1)(yang sekarang a) pada, yang merupakan jumlah dari semua istilah sebelumnya.

Menggabungkannya bersama-sama, kita dapatkan:

  a + ((a - b - 1)(a + b) / 2)
= a + ((a^2 + ab - ab - b^2 - a - b) / 2)
= a + ((a^2 - b^2 - a - b) / 2)
= (a^2 - b^2 - a - b + 2a) / 2
= (a^2 - b^2 + a - b) / 2
= ((a + b)(a - b) + (a - b)) / 2
= (a + b + 1)(a - b) / 2

Ganti adengan xdan bdengan y, dan hai presto, Anda harus rumus di atas.

clismique
sumber
9

Mathematica, 49 48 byte

±2=4;±1=0;±n_:=Tr@Range@±(n-1)-Tr@Array[±#&,n-1]
(* or *)
±2=4;±1=0;±n_:=-Tr@Array[(k=±#)&,n-1]+Tr@Range@k

Menggunakan pengodean CP-1252. Menentukan fungsi PlusMinus (±). 1-diindeks.

Penjelasan

±2=4;±1=0;±n_:=Tr@Range@±(n-1)-Tr@Array[±#&,n-1]

±2=4;±1=0;                                        (* Define ±1 and ±2 *)
          ±n_:=                                   (* ±n equals ... *)
               Tr@Range@±(n-1)                    (* Sum of (1, 2, ..., ±(n-1)) ... *)
                              -Tr@Array[±#&,n-1]  (* Minus the sum of previous terms *)
JungHwan Min
sumber
8

Oasis , 11 byte

Kode:

+>bc-*2/640


Penjelasan:

Untuk memvisualisasikan hubungan f n , mari kita ambil contoh f 5 . Untuk menghitung f 5 , mari kita lihat jumlah berikut:

1 + 2 + 3 + 5 + 7 + 8 + 9 + 10

Bagian tebal sama dengan f 4 . Bagian 7 + 8 + 9 + 10 adalah kisaran [f n-2 + 1, f n-1 - 1] . Itu membuat rumus f n-1 + Σ [f n-2 + 1 ... f n-1 - 1] ( tautan Wolfram ):

f n = 0,5 × (f n-1 2 - f n-2 2 + f n-1 - f n-2 )

Yang dapat ditulis ulang untuk:

f n = 0,5 × ((f n-1 - f n-2 ) (f n-1 + f n-2 ) + (f n-1 - f n-2 ))

f n = 0,5 × ((f n-1 - f n-2 ) (f n-1 + f n-2 + 1))

Rumus yang mana yang akan kita gunakan dalam kode:


Penjelasan kode

Bagian 640memberi kita kasus dasar:

a(0) = 0
a(1) = 4
a(2) = 6

Kode yang akan dieksekusi (yang mendefinisikan a (n) ):

+>bc-*2/

+          # Add a(n + 1) and a(n + 2) implicitly
 >         # Add one to get a(n + 1) + a(n + 2) + 1
  b        # Push a(n + 1)
   c       # Push a(n + 2)
    -      # Subtract from each other
     *     # Multiply with the previous result
      2/   # Halve the result

Cobalah online!

Adnan
sumber
3
Penjelasan? Ini membuat saya lebih penasaran daripada banyak jawaban lainnya.
@ ais523 Saya telah menambahkan penjelasan.
Adnan
5

Julia, 39 33 32 byte

!n=n<3?5n-n^2:sum(!(n-2)+1:!~-n)

Berbasis 0.

Berkat @ Dennis, disimpan 6 byte.

Berkat @ GlenO, tersimpan satu byte.

Cobalah online!

Jawaban sebelumnya 1- berdasarkan:

!n=n<4?2(n>1)n:sum(!(n-2)+1:!~-n)

Cobalah online!

Berbasis 1 jawaban ungolfed sebelumnya:

f(n)=n<4?n<2?0:n*2:sum(f(n-2)+1:f(n-1))

Cobalah online!

rahnema1
sumber
1
Untuk menyimpan byte tambahan, gunakan n<3?5n-n^2:bukan n<4?2(n>1)n:- perhatikan bahwa ia beralih menggunakan pengindeksan berbasis 0.
Glen O
@ GlenO Terima kasih, 1 byte disimpan!
rahnema1
4

JavaScript (ES6), 47 byte

f=(n,b=4,a=6)=>n?--n?f(n,a,(a+b+1)*(a-b)/2):b:0

Menggunakan relasi perulangan f(n) = sum(range(f(n-2) + 1, f(n-1) + 1))untuk n> 2.

Neil
sumber
4

PowerShell , 84 89 88 87 byte

$OFS='+'
for($a=0,4;$a.Count-le($n="$args")){$a+=("$(1..$a[-1])"|iex)-("$a"|iex)}$a[$n]

Cobalah online!

Penjelasan

Pengindeksan berbasis 0. Hanya bekerja melalui n = 6(pada mesin Windows saya crash dengan stack overflow untuk n = 7).

Menggunakan metode yang sama dengan jawaban JungHwan Min (jumlah kisaran minus jumlah istilah sebelumnya).

Menjumlahkan rentang / array di PowerShell panjang, jadi saya menggunakan trik bergabung dengan array +untuk membuat ekspresi panjang (seperti 1+2+3+4...etc) dan kemudian mengirimkannya melalui iex( Invoke-Expression).

Karena saya perlu melakukannya dua kali, daripada menggunakan -joinsaya mengatur variabel khusus $OFS, yang merupakan pemisah bidang keluaran. Saat Anda merangkaikan array, ini adalah karakter yang digunakan untuk menggabungkan elemen; itu default ke spasi. Jadi dengan mengaturnya ke +(sekali), saya bisa mengganti sesuatu $a-join'+'|iexdengan "$a"|iex.

Sebuah forloop sederhana terus berjalan hingga jumlah urutan kurang dari atau sama dengan integer input, lalu saya mengembalikan $nelemen th.

briantis
sumber
@ AdmBorkBork sangat bagus! Saya benar-benar berpikir itu layak untuk jawaban yang berbeda; metode ini cukup berbeda sehingga tidak akan terasa seperti milik saya jika saya menggunakannya.
briantist
1
@ AdmBorkBork bagus, +1, dan saya belajar satu hal dari itu: tidak ;diperlukan setelah forloop. Tidak pernah menyadari itu sebelumnya.
briantist
3

MATL , 17 16 byte

OKi:"tP:yX-sv]G)

1pengindeksan berbasis digunakan. Kode ini sangat tidak efisien. Untuk n = 6itu sudah melebihi batas memori kompiler online.

Cobalah online!

Bagaimana itu bekerja

O       % Push 0
K       % Push 4
i       % Input n
:"      % Do the following n times
  t     %   Push a copy of the top array (or number)
  P:    %   Range from 1 to the last element of array
  y     %   Push a copy of the second-top number/array
  X-    %   Set difference
  s     %   Sum
  v     %   Concatenate everything into a column vector
]       % End
G)      % Get n-th entry of the array. Implicity display

Selama 20 byte , versi berikut ini menghindari batasan memori. Tetapi masih ada batasan tipe data ( doubletipe hanya dapat menjamin bahwa integer terwakili secara akurat hingga 2^53), sehingga hasilnya hanya valid hingga n = 8.

OKi:"t0)tQ*2/ys-v]G)

Coba juga online !

Luis Mendo
sumber
2

Haskell , 42 byte

f 0=0
f 1=4
f 2=6
f n=sum[1+f(n-2)..f$n-1]

Cobalah online!

Hal ini secara langsung mengimplementasikan kekambuhan bahwa untuk n>2, f(n)sama f(n-1)ditambah jumlah interval terbuka dari f(n-2)ke f(n-1)mana lagi adalah sama dengan jumlah dari interval setengah terbuka dari f(n-2)ke f(n-1)inklusif.

f(0) = 0
f(1) = 4
f(2) = 6 = 1+2+3
f(3) = 11 = 1+2+3+5 = 6 + 5 = 6 + sum]4,6[ = f(2)+ sum]f(1),f(2)[ = sum]f(1),f(2)]
...
f(n) = sum]f(n-2),f(n-1)] = sum[f(n-2)+1,f(n-1)]
Laikoni
sumber
2

Haskell, 31 byte

m#s=m:s#sum[m+1..s]
((0:4#6)!!)

Contoh penggunaan: ((0:4#6)!!) 6-> 468930. Cobalah online! .

Rekursi sederhana, yang melacak elemen maksimum msejauh ini dan nilai selanjutnya s.

nimi
sumber
Setiap kali saya menghadapi tantangan baru, seseorang selalu membuat jawaban haskell lebih baik daripada yang pernah saya buat XD
theonlygusti
Saya selalu tiba di beberapa tantangan matematika, berpikir, "Hei akhirnya saya bisa mencoba haskell!" CMD-F 'Haskell' - oh tunggu dulu, jawaban ini ... tunggu, apa? Menyerah pada
haskell
2

JavaScript, 123 119 byte

(a,i=x=y=0)=>{r=[0,4];while(r.length<a){x++;y=0;for(i=0;i<r[x];i++){if(!r.includes(i)){y+=i;}}r.push(y)}return r[a-1];}

Cobalah online! Solusi ini berbasis 1 f(1) => 0,.

steenbergh
sumber
2

Perl 6 ,  52 49 44  35 byte

{(|(0,4 X 0),{[+](^.[0])-.[1],.[0]+.[1]}...*)[$_;0]}

Cobalah

{(0,(4,0),{[+](^.[0])-.[1],.[0]+.[1]}...*)[$_;0]}

Cobalah

{(0,(4,0),{[+](^.[0])-.[1],.sum}...*)[$_;0]}

Cobalah

{(0,4,6,{[+] $^a^..$^b}...*)[$_]}

Cobalah

Diperluas:

{ # bare block lambda with implicit parameter 「$_」

  (
    # generate a sequence

    0, 4, 6,      # seed the sequence

    {             # lambda with placeholder parameters 「$a」 「$b」
      [+]         # reduce with 「&infix:<+>」
          $^a     # n-2
          ^..     # Range that excludes the first value
          $^b     # n-1
    }
    ...           # keep generating values until
    *             # never stop

  )[ $_ ]         # get the value that was asked for (0 based index)
}
Brad Gilbert b2gills
sumber
2

PowerShell , 77 73 byte

param($n)$a=0,4;1..$n|%{$a+=(0..$a[-1]|?{$_-notin$a})-join'+'|iex};$a[$n]

Cobalah online!

Menerapkan algoritma seperti yang didefinisikan, dan diindeks 0. Input 6terlalu banyak untuk ditangani oleh TIO.

Setel $amenjadi array [0,4]. Loop dari 1hingga input $n. Dalam loop, kami mengambil rentang angka dari 0hingga jumlah terbesar yang kami miliki $a[-1], dan menggunakan Where-Objectklausa |?{...}untuk menarik hanya angka-angka yang belum ada. Array angka itu -joindiedit bersama dengan +s, lalu diumpankan ke iex(kependekan dari Invoke-Expressiondan mirip dengan eval) Nilai itu kemudian array-concatenated ke akhir $a. Akhirnya, kita keluar dari loop kita, dan mengambil $nnomor ke dalam array kita. Angka itu ditinggalkan di jalur pipa, dan hasilnya tersirat.

AdmBorkBork
sumber
1

Batch, 108 byte

@if %1==0 echo 0&exit/b
@set/ab=4,a=6
@for /l %%i in (2,1,%1)do @set/ac=(a+b+1)*(a-b)/2,b=a,a=c
@echo %b%

Port jawaban JavaScript saya.

Neil
sumber
1

dc , 47 byte

?d1-scd/4*dd[d1+*2/r-dsn+dlnlc1-dsc0<x]sxlc0<xp

Bekerja dengan bilangan bulat sebesar yang Anda inginkan, hingga kapasitas memori komputer.

Cobalah online!

Pengindeksan berbasis 0, input pada stdin, output pada stdout. (Ada juga output pada stderr, yang harus diabaikan.)

Sampel berjalan:

$ for ((j=0;j<12;j++)){ echo -n "$j ";dc -f sumseq.dc <<<"$j";echo;} 2>/dev/null
0 0

1 4

2 6

3 11

4 45

5 969

6 468930

7 109947436950

8 6044219445882138462810

9 18266294354989892462984673364511343859409730

10 166828754731567805766174036610844675771635260155825966927845486666328\
837158267993261860

11 139159167026428037700805570917048711514125048327321592278500415852500\
422178720517080334552793040951056255170819719745908378102737875659900\
61575545777065220385544711322919415

Ini menggunakan algoritma yang sama dengan solusi berikut dalam bash, yang (sedikit) lebih mudah dibaca:

Bash murni, 60 byte

for((n=s=$1?4:0,k=1;k<$1;k++,s+=(n=n++*n/2-s))){ :;}
echo $n

Tetapi program bash hanya bekerja untuk input hingga 7, karena itu melebihi bilangan bulat integer di luar itu.

Mitchell Spector
sumber
0

Pyth - 15 byte

ePu+Gs-UeGGQ,Z4

Test Suite .

Maltysen
sumber
0

C # - 74 byte

int A(int f){int e=4,i=1,s=0;for(;i++<f;)e=e*-~e/2-(s+=e);return f>0?e:0;}

Tidak Terkumpul:

int A(int f)
{
    int e = 4, 
        i = 1, 
        s = 0; // e is the last element, s is the sum of all previous elements
    for (; i++ < f; ) // calculate for indexes 1 through max (don't need the index, just a correct number of loop cycles)
        e = e * -~e / 2 - (s += e); // -~e => (e + 1), higher precedence to remove parentheses
    return f > 0 ? e : 0; //handle input 0 as a special case, which is 0
}

Mungkin ada cara untuk mengonversikan ini ke lambda untuk menyimpan lebih banyak lagi, atau sesuatu menggunakan .Aggregate Function. Meskipun saat ini saya tidak memiliki impor, jadi mungkin itu sama?

Brian J
sumber
0

> <> , 43 + 3 = 46 byte

Manfaatkan formula yang disajikan dalam jawaban Adnan dan Qwerp-Derp .

:2(?^&46v
}v?=&:&l<,2*{-$@:}+1+@:{::
*>n;>4

Mengharapkan input akan ada di stack, jadi +3 byte untuk -vflag.

Cobalah online!

Sok
sumber