Hitung minimum

12

Latar Belakang

Pertimbangkan urutan berikut ( A051935 di OEIS):

  • Mulai dengan istilah .2
  • Temukan bilangan bulat terendah lebih besar dari sehingga adalah bilangan prima.2 2 + nn22+n
  • Temukan bilangan bulat terendah lebih besar dari sehingga adalah prima dll. n 2 + n + n nn2+n+n

Definisi yang lebih formal:

an={2if n=0min{xNx>an1 and (x+i=0n1ai) is prime}otherwise

Beberapa syarat pertama dari urutan ini adalah (harap lihat ini sebagai kasus uji):

2, 3, 6, 8, 10, 12, 18, 20, 22, 26, 30, 34, 36, 42, 44, 46, 50, 52, 60, 66, 72, 74, ...

Tugas

Tugas Anda adalah untuk menghasilkan urutan ini dengan salah satu cara berikut:

  • Keluarkan persyaratannya tanpa batas.
  • Diberikan n , menghasilkan istilah an ( nth , 0 atau 1 diindeks).
  • Diberikan n , keluaran {a1,a2,,an} ( istilah n pertama n).

Anda dapat bersaing dalam bahasa pemrograman apa pun dan dapat mengambil input dan memberikan output melalui metode standar apa pun , sambil memperhatikan bahwa celah ini dilarang secara default. Ini adalah , jadi pengiriman terpendek (dalam byte) untuk setiap bahasa menang.

Tuan Xcoder
sumber
4
Kiat yang harus dihindari saat menulis tantangan: Bilangan prima . Anda bisa menggunakan sesuatu yang lain selain keutamaan.
Okx
3
@Okx Saya punya beberapa alasan ketika memilih primality saat ini: 1) Ada beberapa algoritma pintar yang spesifik untuk urutan ini, seperti yang diterapkan Dennis 2) Sudah ada entri OEIS untuk ini
Tn. Xcoder

Jawaban:

4

Brachylog , 13 byte

~l.<₁a₀ᵇ+ᵐṗᵐ∧

Cobalah online!

Output adalah daftar n pertama syarat urutan.

?~l.<₁a₀ᵇ+ᵐṗᵐ∧    Full code (? at beginning is implicit)

?~l.              Output is a list whose length is the input
    <₁            Output is an increasing list
      a₀ᵇ+ᵐ       And the cumulative sum of the output
           ṗᵐ     Consists only of prime numbers
             ∧    No further constraints on output

Explanation for a₀ᵇ+ᵐ:
a₀ᵇ               Get the list of all prefixes of the list
                  Is returned in increasing order of length
                  For eg. [2, 3, 6, 8] -> [[2], [2, 3], [2, 3, 6], [2, 3, 6, 8]]
   +ᵐ             Sum each inner list  -> [2, 5, 11, 19]
sundar - Pasang kembali Monica
sumber
4

Python 2 , 63 62 byte

n=f=a=b=1
while 1:
 f*=n;n+=1;a+=1
 if~f%n<a-b:print a;b=a;a=0

Cobalah online!

Dennis
sumber
4

Jelly , 11 9 byte

0Ḥ_ÆnɗСI

Ini adalah program lengkap yang menggunakan n sebagai argumen dan mencetak n istilah pertama dari urutan tersebut.

Cobalah online!

Bagaimana itu bekerja

0Ḥ_ÆnɗСI  Main link. Argument: n

0          Set the return value to 0.
      С   Accumulating iterate. When acting on a dyadic link d and called with
           arguments x and y, the resulting quicklink executes
           "x, y = d(x, y), x" n times, returning all intermediate values of x.
           Initially, x = 0 and  y = n.
     ɗ       Drei; combine the three links to the left into a dyadic chain.
 Ḥ             Unhalve; double the left argument.
  _            Subtract the right argument.
   Æn          Compute the next prime.
           This computes the partial sums of the sequence a, starting with 0.
        I  Increments; compute the forward differences.
Dennis
sumber
3

05AB1E v2 , 10 byte

2λλOD₁+ÅNα

Cobalah online!

Ini hanya berfungsi dalam versi non-legacy, penulisan ulang Elixir. Menghasilkan aliran bilangan bulat tanpa batas. Ada beberapa bug dengan tes utama yang telah diperbaiki dalam komit terbaru, tetapi belum tayang langsung di TIO. Ini bekerja secara lokal. Berikut ini adalah GIF dari eksekusi pada mesin saya, dimodifikasi untuk menampilkan beberapa istilah pertama daripada seluruh aliran.

Bagaimana itu bekerja

Menentukan urutan tak terbatas rekursif dengan kasus dasar . The Struktur adalah di antara fitur yang sangat keren baru 05AB1E ini. Secara singkat, dibutuhkan fungsi , pengaturan untuk argumen integer yang diberikan, dalam hal ini .a ( n ) a ( 0 ) 22λa(n)a(0)2

λO

Dalam bagian kode ini, λperan berbeda. Sudah berada di dalam lingkungan rekursif, ia malah menghasilkan , daftar semua hasil sebelumnya. Kemudian, jumlahkan mereka.[a(0),a(1),,a(n1)]O

D₁+

Gandakan jumlahnya untuk digunakan nanti dan tambahkan ke salinan kedua.a(n1)

ÅN

Menghasilkan prime terendah yang lebih tinggi daripada jumlah di atas.

α

Akhirnya, ambil perbedaan mutlak antara prime dihitung di atas dan salinan pertama dari jumlah yang dihitung sebelumnya (jumlah semua iterasi sebelumnya).

Aliran kemudian dicetak secara implisit ke STDOUT tanpa batas.

Tuan Xcoder
sumber
2

Perl 6 , 45 byte

2,{first (*+@_.sum).is-prime,@_[*-1]^..*}...*

Cobalah online!

Mengembalikan daftar malas yang menghasilkan urutan tanpa akhir.

Penjelasan:

Ini menggunakan operator Sequence ...yang mendefinisikan urutan sebagai:

2,  # The first element is 2
  {  # The next element is:
    first  # The first value that:
          (*+@_.sum).is-prime,  # When added to the sum is a prime
          @_[*-1]^..*  # And is larger than the previous element
  }
...*  # And continue the sequence indefinitely
Jo King
sumber
2

Ruby -rprime , 34 byte

2.step{|i|$.+=p(i)if($.+i).prime?}

Cobalah online!

Output tanpa batas.

Kirill L.
sumber
2

JavaScript (ES6), 63 byte

Mengembalikan istilah , 1-diindeks.nth

n=>(k=0,s=1,g=d=>s%d?g(d-1):d<2?--n?g(s-=k-(k=s)):s-k:g(s++))()

Cobalah online!

Arnauld
sumber
2

Pyth ,12 11 byte

.f&P-;Z=-;Z

Cobalah online!

Disimpan 1 byte berkat isaacg.

Menghasilkan angka pertama nseperti itu, menggunakan indeks berbasis 1.

.fmenemukan kbilangan bulat pertama yang memenuhi kriteria tertentu mulai dari nol. Di sini, kriterianya adalah bahwa bilangan prima sebelumnya yang kami hitung ;, ditambah bilangan saat ini Z,, adalah bilangan prima ( P). Jika ya, kami juga memperbarui prime yang terakhir dihitung menggunakan perilaku hubungan singkat dari logika dan fungsi ( &). Sayangnya .fvariabel default adalah Zyang biaya satu byte dalam pembaruan.

Trik yang ditemukan oleh isaacg adalah untuk menyimpan negasi dari prime terakhir dan menguji pada itu minus nilai saat ini. Ini lebih pendek di Pyth karena pemeriksaan awal kelebihan beban: pada bilangan positif ia menemukan factorisation prima sedangkan pada bilangan negatif menentukan apakah nilai positif bilangan prima.

Ini kurang lebih diterjemahkan menjadi:

to_find = input()
last_prime = 0
current = 0
results = []
while to_find > 0:
    if is_prime( current + last_prime ):
        results.append( current )
        to_find -= 1
        last_prime += current
    current += 1
print results
FryAmTheEggman
sumber
Ganti _+dengan -dan +dengan -untuk -1 byte.
isaacg
@isaacg Itu cukup pintar! Saya akan mengeditnya.
FryAmTheEggman
2

MATL , 21 byte

O2hGq:"t0)yd0)+_Yqh]d

Cobalah online!

Keluaran adalah n pertama dari sekuens.

Penjelasan:

Membangun daftar bilangan prima (dengan awal 0), dan pada akhirnya menemukan mengembalikan perbedaan antara bilangan prima berturut-turut dalam daftar.

              % Implicit input, say n
O2h           % Push P = [0, 2] on the stack 
Gq:"          % for loop: 1 to n-1
  t0)           % Take the last element of P
                %  Stack: [[0, 2], [2]] (in first iteration)
  yd0)          % Take the difference between the last
                %   two elements of P
                %  Stack: [[0, 2], [2], [2]]
  +             % Add those up
                %  Stack: [[0, 2], [4]]
  _Yq           % Get the next prime higher than that sum
                %  Stack: [[0, 2], [5]]
  h             % Concatenate that to the list P
                %  Stack: [[0, 2, 5]]
]             % End for loop
d             % Get the differences between successive elements of
              %   the final list P
sundar - Pasang kembali Monica
sumber
2

Haskell , 67 byte

(1#1)2 2
(p#n)s k|p`mod`n>0,n-s>k=k:(p#n)n(n-s)|w<-p*n=(w#(n+1))s k

Cobalah online!

(1#1)2 2adalah fungsi yang tidak mengambil input dan menghasilkan daftar yang tidak terbatas.


jawaban lama:

Haskell , 88 83 78 76 byte

Tes primality berasal dari jawaban ini dan ditingkatkan oleh Christian Sievers (-2 bytes).

-5 byte terima kasih kepada WW .

2#2
(p#s)n|n<1=p|w<-until(\m->mod(product[1..m-1])m>0)(+1)$s+p+1=(w-s)#w$n-1

Cobalah online!

ovs
sumber
Anda bisa melakukannya tanpa ^2. Itu akan mengubah predikat dari pengujian prima ke pengujian prima atau 4 , yang tidak masalah dalam aplikasi ini.
Christian Sievers
2

05AB1E (warisan) , 12 byte

0U[XN+DpiN,U

Cobalah online!

Penjelasan

0U              # initialize X as 0
  [             # start an infinite loop
   XN+          # add X to N (the current iteration number)
      Dpi       # if the sum is prime:
         N,     #   print N
           U    #   and store the sum in X

Ada beberapa solusi 12-byte yang berbeda.
Yang satu ini bisa jadi 10 byte jika kita memiliki variabel yang dapat digunakan diinisialisasi sebagai 0 (bukan 1 dan 2).

Emigna
sumber
1

Python 2 , 119 byte

f=lambda n,k=1,m=1:m%k*k>n or-~f(n,k+1,m*k*k)
def g(i):
 r=[2]
 for j in range(i):r+=[f(sum(r)+r[-1])-sum(r)]
 return r

Cobalah online!

Fungsi Prime berikutnya f () diambil dari jawaban ini .

Fungsi g () mengambil bilangan bulat non-negatif dan mengembalikan daftar semua item dalam urutan hingga indeks itu.

Triggernometri
sumber
-7 byte .
Tn. Xcoder
1

Python 2 , 99 98 byte

def f(n,s=2,v=2):
 k=s-~v
 while any(k%i<1for i in range(2,k)):k+=1
 return n and f(n-1,k,k-s)or v

Cobalah online!

1 byte thx ke Tn . Xcoder .

Chas Brown
sumber
1
Saya tahu ... Saya tahu ... Saya dan pedantry trik bitwise saya :) Tetapi Anda dapat menyimpan byte dengan k=s-~v.
Tn. Xcoder
@Pak. Xcoder: Sihir bitwise tidak suci Anda akan menjadi akhir dari Anda! :)
Chas Brown
1

Haskell , 101 99 97 byte

Fungsi ltidak mengambil argumen dan mengembalikan daftar tanpa batas. Tidak sesingkat pendekatan langsung oleh @ovs (dan saya jelas mencuri beberapa bagian dari jawaban mereka), tapi mungkin masih bisa golf?

Terima kasih @ H.Wiz untuk -2 byte!

import Data.List
p m=mod(product[1..m-1])m>0
l=2:[until(p.(+sum a))(+1)$last a+1|a<-tail$inits l]

Cobalah online!

cacat
sumber
1

Python 2 , 82 80 byte

s=p=2
i=input()
P=n=1
while i:
 P*=n;n+=1
 if P%n>0<n-s-p:p=n-s;s=n;i-=1
print p

Cobalah online!

Ini menghasilkan nomor urutan n (berdasarkan-0). Dengan memindahkan printloop, ini dapat dimodifikasi untuk menampilkan nitem pertama pada bytecount yang sama: Coba online!

ovs
sumber
1

C (gcc) , 100 99 byte

p(r,i,m,a,l){for(l=m=a=0;a-r;)m+=i=p(a++);while(r*!l)for(++i,l=a=2;a-m-i;)l=(m+i)%a++?l:0;r=r?i:2;}

Cobalah online!

Jonathan Frech
sumber
0

Japt, 17 byte

Menghasilkan nistilah th, 0-diindeks.

@_+T j}aXÄT±X}g2ì

Cobalah

Shaggy
sumber