Jumlah terkecil yang tidak digunakan berbagi faktor

11

Ini adalah pertanyaan yang lumrah. Saya akan menentukan urutan dan Anda golf beberapa kode untuk menampilkan entri yang diberi indeks.

  • Item pertama dalam urutan adalah 2.

  • Item ke-n dalam urutan adalah bilangan bulat positif terkecil selain dari n dan 1 berbagi setidaknya satu faktor dengan n (selain 1) yang belum muncul dalam daftar.

Uji kasus

Berikut adalah 25 item pertama dalam urutan:

1  2
2  4
3  6
4  8
5  10
6  3
7  14
8  12
9  15
10 5
11 22
12 9
13 26
14 7
15 18
16 20
17 34
18 16
19 38
20 24
21 27
22 11
23 46
24 21
25 30

Terkait (diimbangi oleh satu) OEIS

code-golf number sequence permutations Ad Hoc Garf Hunter
sumber

Jawaban:

5

Jelly , 19 byte

R»2ɓ²Rg⁸>1Tḟ⁸ḟḢṭµ/Ṫ

Cobalah online!

Dennis
sumber
Saya sangat senang bahwa Anda membuat Anda
bermain golf
3

Python 3 , 118 117 byte

-1 byte terima kasih kepada Cameron Aavik !

import math
def f(n,i=3):
 if n<2:return 2
 while 1:
  if math.gcd(n,i)>1>(i in map(f,range(n)))<i!=n:return i
  i+=1

Cobalah online!

Kode ini sangat tidak efisien (itu brute-memaksa nilai yang tidak ada di hasil sebelumnya, dan menghitung hasil sebelumnya lagi pada setiap nilai baru), jadi itu berfungsi dengan baik tetapi saya tidak akan merekomendasikan menjalankannya dalam jumlah besar.

notjagan
sumber
2
Kiat kecil: Anda dapat menyimpan baris baru dengan membuatnya def f(n,i=3):dan menghapus i=3garis
Cameron Aavik
115 byte .
Jonathan Frech
2

Haskell , 60 59 byte

EDIT:

  • -1 byte: @xnor menunjukkan all(/=x)lebih pendek dari x`notElem`.

f mengambil integer dan mengembalikan integer.

f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:map f[1..n-1]]!!0

Cobalah online!

Ini adalah waktu yang sangat eksponensial, jadi TIO keluar setelah 21, sementara GHCi yang saya interpretasikan mencapai 22 sebelum saya menghentikannya sekarang. Versi 9 byte yang lebih panjang ini menghafal ke dalam daftar dengan mudah naik ke ribuan:

f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:take(n-1)l]!!0
l=f<$>[1..]

Cobalah online!

  • f nmenggunakan pemahaman daftar untuk menghasilkan kandidat x, mengambil yang lulus pertama dengan !!0.
  • gcd x n>1memeriksa itu xdan nmemiliki faktor umum.
  • ||n<2dibebaskan n==1dari persyaratan faktor.
  • all(/=x)$n:map f[1..n-1]memeriksa yang xbukan nmerupakan elemen urutan sebelumnya.
Ørjan Johansen
sumber
@WheatWizard Hm, mungkin tidak ada perbedaan dalam hal itu. Hanya terbiasa melakukannya secara default. Ini adalah salah satu dari beberapa fungsi alfanumerik yang memiliki fixity yang didefinisikan agar sesuai dengan cara itu.
Ørjan Johansen
1
all(/=x)$adalah 1 lebih pendek di sana
xnor
2

Tidak ada built-in untuk GCD di C #, jadi ...

C # (.NET Core) , 197 196 194 byte

n=>{if(n<2)return 2;var p=new int[n-1];int i=0,a,b;for(;i<n-1;)p[i]=f(++i);for(i=2;;i++)if(n!=i){for(a=n,b=i;a*b>0;)if(a>b)a%=b;else b%=a;if(b!=1&a!=1&!System.Array.Exists(p,e=>e==i))return i;}}

Cobalah online!

Sekali lagi, jangan menggunakan kode ini untuk menghitung angka dalam urutan untuk n>30...

  • -1 byte dengan mengubah whileloop GCD untuk forloop.
  • -2 byte terima kasih kepada Kevin Cruijssen! Yang bagus!
Charlie
sumber
1
a>0&b>0dapat a*b>0
bermain golf