Pendahuluan (dapat diabaikan)

Menempatkan semua bilangan bulat positif dalam urutan regulernya (1, 2, 3, ...) agak membosankan, bukan? Jadi di sini adalah serangkaian tantangan seputar permutasi (perombakan) dari semua bilangan bulat positif. Ini adalah tantangan keenam dalam seri ini (tautan ke tantangan pertama , kedua , ketiga , keempat dan kelima ).

Tantangan ini memiliki tema Paskah yang ringan (karena ini Paskah). Saya mengambil inspirasi dari telur angsa yang sangat dihiasi ini (dan menurut saya agak jelek).

Itu mengingatkan saya pada spiral Ulam , di mana semua bilangan bulat positif ditempatkan dalam spiral berlawanan arah jarum jam. Spiral ini memiliki beberapa fitur menarik yang terkait dengan bilangan prima, tetapi itu tidak relevan untuk tantangan ini.

Kita sampai pada permutasi tantangan ini dari bilangan bulat positif jika kita mengambil angka dalam spiral Ulam dan melacak semua bilangan bulat dalam spiral putaran searah jarum jam , mulai dari 1. Dengan cara ini, kita mendapatkan:

1, 6, 5, 4, 3, 2, 9, 8, 7, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 25, 24, 23, etc.

Jika Anda akan menggambar kedua spiral, Anda akan mendapatkan semacam jaring spiral (kulit telur) tak terbatas ( perhatikan referensi Orde Baru di sana ).

Urutan ini hadir dalam OEIS dengan nomor A090861 . Karena ini adalah tantangan "urutan murni", tugasnya adalah mengeluarkan $a(n)$ untuk diberikan sebagai input, di mana adalah A090861 .$n$$a(n)$

Tugas

Diberikan input integer , output dalam format integer, di mana adalah A090861 .$n$$a(n)$$a(n)$

Catatan: pengindeksan berbasis 1 diasumsikan di sini; Anda dapat menggunakan pengindeksan berbasis 0, jadi , dll. Sebutkan ini dalam jawaban Anda jika Anda memilih untuk menggunakan ini.$a(0) = 1; a(1) = 6$

Uji kasus

Input | Output
---------------
1     |  1
5     |  3
20    |  10
50    |  72
78    |  76
123   |  155
1234  |  1324
3000  |  2996
9999  |  9903
29890 |  29796

Aturan

• Input dan output adalah bilangan bulat.
• Program Anda setidaknya harus mendukung input dalam kisaran 1 hingga 32767).
• Input yang tidak valid (0, float, string, nilai negatif, dll.) Dapat mengakibatkan output yang tidak terduga, kesalahan atau (tidak) perilaku yang didefinisikan.
• Standar I / O aturan berlaku.
• Celah default dilarang.
• Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang

Jelly ,  16 14 11 10 9  8 byte

-1 berkat Lynn (mod-2; logis TIDAK; add untuk diri sendiri: Ḃ¬+-> bitwise OR dengan 1: |1)

|1×r)ẎQi

Tautan monadik yang menerima bilangan bulat n,, yang menghasilkan bilangan bulat a(n),.

Cobalah online! (sangat tidak efisien karena keluar ke layer$\lceil\frac n2\rceil$)

Versi 11-byte, ½‘|1×rƲ€ẎQi, melengkapi semua tapi kasus uji terbesar di bawah 30-an - Cobalah di TIO - batas ini lapisan digunakan untuk $\lceil\frac{\lfloor\sqrt n\rfloor+1}2\rceil$.

Bagaimana?

Permutasi adalah untuk mengambil bilangan asli dalam irisan panjang terbalik [1,5,3,11,5,17,7,23,9,29,11,35,13,...]- bilangan bulat ganjil diselingi dengan bilangan bulat positif kongruen ke lima modulo enam, yaitu [1, 2*3-1, 3, 4*3-1, 5, 6*3-1, 7, 8*3-1, 9, ...].

Ini sama dengan penggabungan dan kemudian deduplicating rentang terbalik di [1..x]mana xjumlah kumulatif dari panjang irisan ini (yaitu maksimum setiap irisan) - [1,6,9,20,25,42,49,72,81,110,121,156,169,...], yang merupakan bilangan bulat ganjil diselingi dengan bilangan genap yang dikalikan dengan diri mereka sendiri yang ditambahkan, yaitu [1*1, 2*3, 3*3, 4*5, 5*5, 6*7, 7*7,...].

Karena perbedaannya lebih besar dari 1 kita dapat menyimpan byte (pembalikan) dengan membangun rentang [x..k]secara langsung, di mana kindeks 1-diindeks dari slice.

$P(n) = v \iff P(v) = n$n|1×r)ẎQị@n|1×r)ẎQi

|1×r)ẎQi - Link: integer, n       e.g. 10
    )    - for each k in [1..n]:  vs = [ 1, 2, 3, 4, 5, 6, 7, 8, 9,10]
|1       -   bitwise-OR (k) with 1     [ 1, 3, 3, 5, 5, 7, 7, 9, 9,11]
  ×      -   multiply (by k)           [ 1, 6, 9,20,25,42,49,72,81,110]
   r     -   inclusive range (to k)    [[1],[6..2],[9..3],[20..4],...,[110..10]]
     Ẏ   - tighten                     [1,6,5,4,3,2,9,8,7,6,5,4,3,20,...,4,......,110,...,10]
      Q  - de-duplicate                [1,6,5,4,3,2,9,8,7,20,...,10,......,110,...82]
       i - first index with value (n)  20

JavaScript (ES7),  46 45  41 byte

Diindeks 0.

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Cobalah online!

Bagaimana?

Ini didasarkan pada rumus 1-diindeks yang digunakan dalam program contoh A090861 .

$x_n$$0$

$$x_n=\left\lfloor\frac{\sqrt{n-1}+1}{2}\right\rfloor$$

Cobalah online!

$k_n$$6$$-2$

$$k_n=\begin{cases} -2&\text{if }n\le 4{x_n}^2+2x_n\\ 6&\text{otherwise} \end{cases}$$

Cobalah online!

$a_n$

$$a_n=8{x_n}^2+k_nx_n+2-n$$

Cobalah online!

Yang dapat diterjemahkan ke dalam:

n=>8*(x=(n-1)**.5+1>>1)*x+(n<=4*x*x+2*x?-2:6)*x+2-n

Membuatnya 0-diindeks menghemat 5 byte segera:

n=>8*(x=n**.5+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n

Rumus ini dapat lebih disederhanakan dengan menggunakan:

$${x'}_n=2\times\left\lfloor\frac{\sqrt{n}+1}{2}\right\rfloor$$

yang dapat dinyatakan sebagai:

x=n**.5+1&~1

mengarah ke:

n=>2*(x=n**.5+1&~1)*x+(n<x*x+x?-1:3)*x+1-n

dan akhirnya:

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Bahasa Wolfram (Mathematica) , 60 byte

8(s=⌊(⌊Sqrt[#-1]⌋+1)/2⌋)^2-#+2+If[#<=4s^2+2s,-2,6]s&

Cobalah online!

MATL , 12 11 byte

Eq1YL!tPG=)

Cobalah online!

Sangat tidak efisien memori. Prepending X^kmembuatnya lebih efisien .

C # (Visual C # Interactive Compiler) , 67 byte

n=>8*(x=(int)Math.Sqrt(--n)+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n;int x;

Cobalah online!

Python 3.8, 104 74 65 60 57 byte

lambda n:(-2,6)[n>4*(x:=(n**.5+1)//2)*x+2*x]*x+2+~n+8*x*x

Sunting: Terima kasih kepada Johnathan Allan untuk memperolehnya dari 74 hingga 57 byte!

Solusi ini menggunakan pengindeksan berbasis 0.

Python 3.8 (pra-rilis) , 53 byte

Port langsung dari jawaban JavaScript Arnauld , pilih itu, dan / atau jawaban Mathematica J42161217 , dan / atau jawaban Python Kapocsi :)

lambda n:((x:=int(n**.5+1)&-2)*2-(n<x*x+x)*4+3)*x+1-n

Diindeks 0.

Cobalah online!

Befunge, 67 57 byte

Solusi ini mengasumsikan pengindeksan berbasis 0 untuk nilai input.

p&v-*8p00:+1g00:<
0:<@.-\+1*g00+*<|`
0g6*\`!8*2+00g4^>$:0

Cobalah online!

Penjelasan

Kita mulai dengan menghitung "radius" di mana input n ditemukan dengan loop:

radius = 0
while n > 0
  radius += 1
  n -= radius*8

Pada akhir loop, nilai n sebelumnya adalah offset ke spiral pada radius itu:

offset = n + radius*8

Kita kemudian dapat menentukan apakah kita berada di bagian atas atau bawah spiral sebagai berikut:

bottom = offset >= radius*6

Dan begitu kita memiliki semua detail ini, nilai spiral dihitung dengan:

value = ((bottom?10:2) + 4*radius)*radius + 1 - offset

Jari-jari adalah satu-satunya nilai yang kita perlu simpan sebagai "variabel", membatasi nilai maksimum 127 di Befunge-93, sehingga algoritma ini dapat menangani input hingga 65024.

Japt , 15 byte

Solusi Port of Jonathan's Jelly. 1-diindeks.

gUòȲ+X*v)õÃcÔâ

Cobalah

gUòȲ+X*v)õÃcÔâ     :Implicit input of integer U
g                   :Index into
 Uò                 :  Range [0,U]
   È                :  Map each X
    ²               :    Square X
     +X*            :    Add X multiplied by
        v           :    1 if X is divisible by 2, 0 otherwise
         )          :    Group result
          õ         :    Range [1,result]
           Ã        :  End map
            c       :  Flatten
             Ô      :    After reversing each
              â     :  Deduplicate

C ++ (gcc) , 88 byte

#import<cmath>
int a(int n){int x=(sqrt(n-1)+1)/2;return x*(8*(x+(n>4*x*x+2*x))-2)+2-n;}

1-diindeks; menggunakan rumus pada halaman OEIS, tetapi dimanipulasi untuk menyimpan beberapa byte.

Cobalah online!