Urutan memantul

19

Mari kita tentukan urutan. Kami akan mengatakan bahwa Sebuah(n) adalah angka terkecil, x , yang memiliki properti berikut:

  • x dann adalah co-prime (tidak berbagi faktor)

  • x tidak muncul sebelumnya dalam urutan

  • |n-x|>1

Tidak seperti kebanyakan urutan, domain dan jangkauan urutan kami adalah bilangan bulat yang lebih besar dari 1.


Mari kita hitung beberapa istilah pertama.

Sebuah(2) , harus paling tidak4, tetapi4dan2berbagi faktor2jadiSebuah(2) harus5.

Sebuah(3) , harus sekurang-kurangnya5tetapi5diambil olehSebuah(2) , jadi paling tidak6, tetapi6berbagi faktor dengan3sehingga minimal7,7memenuhi ketiga persyaratan sehinggaSebuah(3)=7 .

Sebuah(4)

  • 2 Membagikan satu faktor
  • 3 Terlalu dekat
  • 4 Terlalu dekat
  • 5 Terlalu dekat
  • 6 Membagikan faktor
  • 7 Diambil oleh (3)
  • 8 Membagikan faktor
  • 9 itu bagus

Sebuah(5)

  • 2 bagus

Tugas

Dalam tantangan ini Anda harus menulis sebuah program yang mengambil angka lebih besar dari 1 dan mengembalikan Sebuah(n) .

Ini adalah pertanyaan sehingga jawaban akan dinilai dalam byte, dengan lebih sedikit byte yang lebih baik.

Uji Kasus

Berikut adalah pasangan istilah pertama dari urutan (Mereka tentu saja 2 diindeks):

5,7,9,2,11,3,13,4,17,6,19,8,23,22,21,10,25,12,27,16,15,14

Fakta Bonus menyenangkan

Sebagaimana dibuktikan oleh Robert Israel pada Math.se ( link di ) urut ini adalah kebalikan sendiri, yang berarti bahwa Sebuah(Sebuah(n))=n untuk semua n.

OEIS

Setelah mengajukan pertanyaan ini, saya mengirimkan urutan ini ke OEIS dan setelah beberapa hari ditambahkan.

OEIS A290151

Wisaya Gandum
sumber
Berapa banyak nilai yang Anda hitung? (Berbicara tentang bonus)
Socratic Phoenix
@ SocratesPhoenix Saya sudah melakukannya dengan tangan sehingga hanya yang ditunjukkan dalam kasus uji. Saat ini saya sedang melakukan debug program untuk memeriksa nilai yang lebih besar.
Wheat Wizard
1
Seperti halnya saya ... ini tidak berfungsi sekarang, pengindeksan saya tidak aktif (sunting :) dan sekarang berfungsi ... 1000 pertama aman xD
Socratic Phoenix
Apakah Anda tahu batas atas untuk (x)? Misalnya a (x) <u * x untuk sebagian u. Namun beberapa juta nilai pertama aman.
nimi
@nimi Saya tidak tahu batas atas.
Wheat Wizard

Jawaban:

8

Haskell , 61 byte

f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0

Cobalah online!

Saya cukup baru di Haskell, jadi setiap kiat bermain golf sangat dihargai.

Terima kasih kepada Wheat Wizard untuk 2 byte dan nimi untuk 4 byte

Penjelasan:

f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0
f n=                                                          -- define a function f :: Int -> Int
    [i|i<-[2..],                                              -- out of positive integers greater than two
                gcd i n<2,                                    -- gcd of i and n is 1
                          all((/=i).f)[2..n-1],               -- i isn't already in the sequence
                                               abs(n-i)>1]    -- and |n-i| > 1
                                                          !!0 -- take the first element
Mego
sumber
2

Alice , 42 byte

/oi
\1@/2-&whq&[]w].q-H.t*n$K.qG?*h$KW.!kq

Cobalah online!

Penjelasan

/oi
\1@/.........

Ini adalah templat standar untuk program yang menggunakan nomor sebagai input, dan mengeluarkan nomor, dimodifikasi untuk menempatkan 1 pada tumpukan di bawah nomor input.

Bagian utama dari program menempatkan setiap nomor k dalam slot a(k)pada pita. Loop dalam menghitung a (k), dan loop luar berulang di atas k sampai a (n) dihitung.

1       push 1
i       take input
2-&w    repeat n-1 times (push return address n-2 times)
h       increment current value of k
q&[     return tape to position 0
]       move right to position 1
w       push return address to start inner loop
]       move to next tape position
.q-     subtract tape position from k
H       absolute value
.t*     multiply by this amount minus 1
n$K     if zero (i.e., |k-x| = 0 or 1), return to start of inner loop
.qG     GCD(k, x)
?       current value of tape at position: -1 if x is available, or something positive otherwise
*       multiply
h$K     if not -1, return to start of inner loop
W       pop return address without jumping (end inner loop)
.!      store k at position a(k)
k       end outer loop
q       get tape position, which is a(n)
o       output
@       terminate
Nitrodon
sumber
1

VB.NET (.NET 4.5), 222 byte

Function A(n)
Dim s=New List(Of Long)
For i=2To n
Dim c=2
While Math.Abs(i-c)<2Or g(c,i)>1Or s.Contains(c)
c+=1
End While
s.Add(c)
Next
Return s.Last
End Function
Function g(a, b)
Return If(b=0,a,g(b,a Mod b))
End Function

Saya harus memutar GCD Anda sendiri. Saya juga tidak tahu bagaimana cara mendapatkannya agar tidak menjadi keseluruhan fungsi.

GCD selalu> = 1, jadi hanya perlu mengabaikan 1

Mengambil hubungan arus pendek di golf karena lebih pendek

Tidak bermain golf

Function Answer(n As Integer) As Integer
    Dim seqeunce As New List(Of Integer)
    For i As Integer = 2 To n
        Dim counter As Integer = 2
        ' took out short-circuiting in the golf because it's shorter
        ' GCD is always >= 1, so only need to ignore 1
        While Math.Abs(i - counter) < 2 OrElse GCD(counter, i) > 1 OrElse seqeunce.Contains(counter)
            counter += 1
        End While
        seqeunce.Add(counter)
    Next
    Return seqeunce.Last
End Function

' roll your own GCD
Function GCD(a, b)
    Return If(b = 0, a, GCD(b, a Mod b))
End Function
Brian J
sumber
Ini mengejutkan saya bahwa .NET tidak memiliki GCD yang dibangun di luar kelas BigInteger.
Mego
1

Mathematica, 111 byte

(s={};Table[m=2;While[m<3#,If[CoprimeQ[i,m]&&FreeQ[s,m]&&Abs[i-m]>1,s~AppendTo~m;m=3#];m++],{i,2,#}];s[[#-1]])&


Cobalah online! 2..23 (mode jangkauan)

Cobalah online! atau 150 (nilai berbeda)

J42161217
sumber
0

05AB1E , 26 byte

2IŸεDU°2Ÿ¯KʒX¿}ʒXα1›}θDˆ}θ

Cobalah secara online atau hasilkan yang pertamanistilah sebagai daftar . (CATATAN: °jelas sangat lambat, jadi diganti dengan T*di tautan TIO (10n dari pada 10n).)

Penjelasan:

2IŸ               # Create a list in the range [2, input]
   ε              # Map each value `y` to:
    DU            #  Store a copy of `y` in variable `X`
    °2Ÿ           #  Create a list in the range [10**`y`,2]
       ¯K         #  Remove all values already in the global_array
       ʒX¿}       #  Only keep values with a greatest common divider of 1 with `X`
       ʒXα1›}     #  Only keep values with an absolute difference larger than 1 with `X`
             θ    #  After these filters: keep the last (the smallest) element
              Dˆ  #  And add a copy of it to the global_array
                # After the map: only leave the last value
                  # (and output the result implicitly)
Kevin Cruijssen
sumber