Integer positif terkecil yang merupakan koprime ke dua pendahulu terakhir dan belum muncul; a (1) = 1, a (2) = 2

10

Definisi

  • Dua bilangan bulat adalah koprime jika tidak berbagi pembagi umum positif selain 1.
  • a(1) = 1
  • a(2) = 2
  • a(n)adalah bilangan bulat positif terkecil yang coprime ke a(n-1)dan a(n-2)dan belum muncul, untuk bilangan bulat n >= 3.

Tugas

  • Diberikan bilangan bulat positif n, keluaran / cetak a(n).

Contoh

  • a(11) = 6karena 6coprime dengan dua pendahulu terakhir (yaitu, 11dan 13) dan 6belum pernah muncul sebelumnya.

Catatan

  • Perhatikan bahwa urutannya tidak naik, artinya suatu elemen bisa lebih kecil dari pendahulunya.

Spesifikasi

  • Anda harus menggunakan 1-diindeks.

Testcases

n      a(n)
1      1
2      2
3      3
4      5
5      4
6      7
7      9
8      8
9      11
10     13
11     6
12     17
13     19
14     10
15     21
16     23
17     16
18     15
19     29
20     14
100    139
1000   1355
10000  13387
100000 133361

Mencetak gol

  • Karena coprime berarti bahwa dua angka hanya berbagi satu pembagi ( 1), dan 1merupakan angka kecil, kode Anda harus sekecil mungkin dalam hal byte-count.

Referensi

Biarawati Bocor
sumber
4
Itu "alasan" untuk kode pendek ...
Luis Mendo
1
Saya bertanya-tanya mengapa ini diturunkan. Tentunya bukan karena alasan yang mengerikan?
Conor O'Brien
@Coror Bukan aku. Sebenarnya saya terbalik. Saya harap orang-orang akan melihat alasan dan komentar saya sebagai lelucon
Luis Mendo
3
Masalah dengan justifikasi "lucu" untuk kode golf ini adalah saya perlu membaca lelucon buruk yang mencakup empat baris hanya untuk mengetahui bahwa ini adalah kode standar golf. Itu hanya mengaburkan aturan tantangan tanpa alasan yang jelas.
Martin Ender
1
@ ConorO'Brien Tidak semua browser selalu menampilkan judul (dan kemudian ada aplikasi seluler), dan kami biasanya menggambarkan skor di pos selain menggunakan tag, karena tag itu sendiri tidak berarti apa-apa bagi orang yang baru ke situs. Meskipun saya saya akrab dengan jenis tantangan tag kami, saya tidak pernah membacanya untuk mengetahui bagaimana tantangan yang mencetak gol tetapi cobalah untuk menemukan bahwa dalam tubuh tantangan. Tag ini untuk kategorisasi, pencarian, dan informasi spesifik tipe tantangan di wiki tag.
Martin Ender

Jawaban:

5

Python 3.5, 160 141 126 124 121 109 byte

Ini adalah implementasi sederhana dari definisi urutan. Saran bermain golf diterima.

Sunting: -17 bytes berkat Leaky Nun. -9 byte terima kasih kepada Peter Taylor. -6 byte berkat Sp3000 dan beralih ke Python 3.5.

import math;f=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+math.gcd(c,r[0]*r[1])<2and f(n-1,[c]+r)or f(n,r,c+1)

Tidak melakukan pelanggaran:

import math
def f(n, r=[2,1], c=3):
    if n<2:
        return r[1]
    elif (c in r) + math.gcd(c,r[0]*r[1]) < 2:
        return f(n-1, [c]+r)
    else:
        return f(n, r, c+1)
Sherlock9
sumber
Untuk Python 3.5+, import mathmaka g=math.gcdharus lebih pendek daripada mendefinisikan Anda sendiri g. Untuk sebelum 3.5, Anda dapat melakukan from fractions import*untuk gcd.
Sp3000
Jika Anda menginisialisasi c=3di dalam loop, Anda hanya perlu melakukannya sekali. Menurut perhitungan saya, Anda menyimpan 3 karakter.
Peter Taylor
Ada juga penghematan 2-char dari membangun array sebaliknya: Anda harus menggunakan r=[c]+rdaripada +=, tetapi tiga indeks negatif menjadi positif. Dan kemudian ada penghematan 2-char lebih lanjut dari penulisan ulang sebagai lambda, meskipun itu perubahan yang cukup drastis: from fractions import*;F=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+gcd(r[0]*r[1],c)<2and F(n-1,[c]+r)or F(n,r,c+1)dan tidak perlu printkarena tidak lagi program penuh.
Peter Taylor
2

MATL , 28 27 byte

2:i:"`@ym1MTF_)Zdqa+}@h]]G)

Kode lambat, tetapi memberikan hasil yang benar.

Cobalah online! Atau verifikasi sepuluh kasus pertama .

Modifikasi kecil dari kode menghasilkan plot urutan:

2:i:"`@ym1MTF_)Zdqa+}@h]]G:)XG

Lihat sebagai seni ASCII , atau dengan output grafis dalam kompiler offline:

masukkan deskripsi gambar di sini

masukkan deskripsi gambar di sini

Penjelasan

2:         % Push [1 2] to initiallize the sequence
i:         % Input n. Push [1 2 ... n]
"          % For loop: repeat n times
  `        %   Do while loop
    @      %     Push iteration index, starting at 1. This is the candidate number
           %     to extend the sequence
    y      %     Duplicate vector containing the sequence so far
    m      %     Is member? Gives true if the candidate is in the sequence
    1M     %     Push candidate and vector again
    TF_)   %     Get last two elements of the vector
    Zd     %     GCD between the candidate and those two elements. Produces a
           %     two-element vector
    qa     %     True if any of the two results exceeds 1, meaning
           %     the candidate is not coprime with the latest two sequence values
    +      %     Add. This corresponds to logical "or" of the two conditions, namely
           %     whether the candidate is member of the sequence so far, and
           %     whether it is not coprime with the latest two. In either case
           %     the do...while must continue with a next iteration, to try a new
           %     candidate. Else the loop is exited, and the current candidate
           %     is the new value of the sequence
  }        %   Finally (execute when the loop is exited)
    @h     %     Push current candidate and concatenate to the sequence vector
  ]        %   End do...while
]          % End for
G)         % Get n-th value of the sequence. Implicitly display
Luis Mendo
sumber
1

C, 185 byte

G(a,b){return a%b?G(b,a%b):b;}
i,j,k;f(n){int a[n+2];for(i=0;i++<n;){a[i]=i<3?i:0;for(j=2;!a[i];++j){for(k=i;--k;){if(a[k]==j)++j,k=i;}a[G(a[i-1],j)*G(a[i-2],j)<2?i:0]=j;}}return a[n];}
orlp
sumber
1

Sebenarnya , 38 37 35 33 31 30 byte

Ini adalah implementasi sederhana dari definisi fungsi. Saran bermain golf diterima. Cobalah online!

Sunting: -3 bytes berkat Leaky Nun.

2R#╗,;`1";2±╜tπg@╜í+Y"£╓╖`nD╜E

Tidak melakukan pelanggaran:

2R#╗    Push [1,2] and store it in register 0
,;      Take input and duplicate
`1      Start function, push 1
  "       Start string
  ;       Duplicate i
  2±╜t    Push (list in register 0)[-2:]
  πg      gcd(i, product of list[-2:])
  @╜í     Rotate the gcd and bring up i, check for i in list (0-based, -1 if not found)
  +Y      Add the gcd and the index, negate (1 if coprime and not found in list, else 0)
  "£      End string, turn into a function
╓       Push first (1) values where f(x) is truthy, starting with f(0)
╖`      Append result to the list in register 0, end function
n       Run function (input) times
D╜E     Return (final list)[n-1]
Sherlock9
sumber
1
Banyak manipulasi tumpukan
Leaky Nun
0

Haskell, 81 73 byte

c l@(m:n:_)=m:c([x|x<-[1..],gcd(m*n)x<2,all(/=x)l]!!0:l)
((0:1:c[2,1])!!)

Contoh penggunaan: ((0:1:c[2,1])!!) 12-> 17.

Buat daftar semua a(n), mulai dengan 0memperbaiki indeks berbasis 1 dan 1dan diikuti oleh c[2,1]. cmengambil kepala dari daftar argumen itu ldiikuti oleh panggilan rekursif dengan kemudian nomor berikutnya yang cocok (co-prime, tidak terlihat sebelumnya) ditambahkan di depan l. Pilih nelemen ke-10 dari daftar ini.

nimi
sumber
0

R, 141 byte

 f=Vectorize(function(n)ifelse(n>3,{c=3;a=f(n-1);b=f(n-2);d=f(4:n-3);while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)c=c+1;c},n))

ungolfed

f=Vectorize( function(n)     #build a recursive function. Vectorize allows
    if(n>3) {                #the function to be called on vectors.
        c=3                  #Tests size. Builds some frequent variables.
        a=f(n-1)
        b=f(n-2)
        d=f(4:n-3)           #Should really golf this out, but its horribly slow.
        while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)
              c=c+1          #If we are coprime and not already seen. add.
        c
     } else n)               #First three are 1,2,3.
pengguna5957401
sumber
0

Mathematica, 97 90 byte

a@1=1;a@2=2;a@n_:=SelectFirst[Range[2n],GCD[a[n-1]a[n-2],#]<2&&!MemberQ[a/@Range[n-1],#]&]

Berdasarkan dugaan saya itu a(n) < 2n untuk semua n.

Untuk menjalankan lebih cepat, tambahkan a@n=setelah yang asli :=sehingga fungsi tidak perlu menghitung ulang nilai sebelumnya .

Disimpan 7 byte berkat Sherlock9 (jika gcd(a,b)=1kemudian gcd(ab,m) = gcd(a,m)*gcd(b,m))


sumber
Ini bukan dugaan, karena ada tertulis di halaman OEIS bahwa " ABS(a(n)-n) < n"
Leaky Nun
@ LeakyNun Terima kasih. Halaman OEIS turun sampai beberapa saat yang lalu, dan saya khawatir tentang kemungkinan balasan yang besar n.
0

Pyth, 23 byte

eu+Gf&-TGq1iT*F>2G1tQ]1

Suite uji

Implementasi yang cukup mudah, tetapi dengan beberapa trik golf yang bagus.

eu+Gf&-TGq1iT*F>2G1tQ]1
 u                 tQ]1    Apply the following function input - 1 times,
                           where G is the current state (List of values so far)
  +G                       Add to G
    f             1        The first number, counting up from 1
      -TG                  That has not been seen so far
     &                     And where
               >2G         The most recent two numbers
             *F            Multiplied together
           iT              Gcd with the current number being checked
         q1                Equals 1
e                          Output the final element of the list.
isaacg
sumber