Temukan fungsi dengan siklus setiap panjangnya

11

Suatu fungsi dikatakan memiliki siklus panjang n jika ada x dalam domainnya sehingga f n (x) = x dan f m (x) ≠ x untuk 0 <m <n , di mana superscript n menunjukkan n - aplikasi lipat f . Perhatikan bahwa siklus panjang 1 adalah titik tetap f (x) = x .

Tugas Anda adalah mengimplementasikan fungsi bijective dari bilangan bulat ke diri mereka sendiri, yang memiliki tepat satu siklus dari setiap panjang positif n . Fungsi bijective adalah korespondensi satu-ke-satu, yaitu setiap bilangan bulat dipetakan tepat satu kali. Memiliki tepat satu siklus panjang n berarti bahwa ada tepat n nomor yang berbeda x yang f n (x) = x dan f m (x) ≠ x untuk 0 <m <n .

Berikut ini contoh tampilan dari fungsi tersebut di sekitar x = 0 :

x     ... -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7 ...
f(x)  ...  2  4  6 -3 -1  1 -4  0 -2  5  7 -7 -6  3 -5 ...

Kutipan ini berisi siklus dengan panjang 1 hingga 5 :

n   cycle
1    0
2   -2  1
3   -4 -3 -1
4   -5  6  3  7
5   -7  2  5 -6  4
...

Perhatikan bahwa di atas saya menggunakan "fungsi" hanya dalam arti matematika. Anda dapat menulis fungsi atau program lengkap dalam bahasa pilihan Anda, selama itu membutuhkan satu bilangan bulat (ditandatangani) sebagai input dan mengembalikan bilangan bulat tunggal (ditandatangani). Seperti biasa, Anda dapat mengambil input melalui STDIN, argumen baris perintah, argumen fungsi dll. Dan output melalui STDOUT, nilai pengembalian fungsi atau argumen fungsi (keluar), dll.

Tentu saja, banyak bahasa tidak (dengan mudah) mendukung integer presisi sewenang-wenang. Tidak apa-apa jika implementasi Anda hanya bekerja pada kisaran jenis integer asli bahasa Anda, selama itu mencakup setidaknya kisaran [-127, 127] dan itu akan bekerja untuk bilangan bulat sewenang-wenang jika jenis bilangan bahasa diganti dengan arbitrary- bilangan bulat presisi.

Aturan standar berlaku.

Martin Ender
sumber
2
Erat terkait. Walaupun perbedaannya tampak kecil, mereka menyiratkan bahwa tidak ada pendekatan lama yang bekerja tanpa modifikasi yang signifikan, dan khususnya saya tidak berpikir pendekatan pemenang dari tantangan itu dapat diadaptasi sama sekali.
Martin Ender
"memiliki tepat satu siklus dari setiap panjang", "memiliki banyak siklus setiap panjangnya": apakah ini satu-satunya perbedaan yang membedakan mereka dari yang lain?
Abr001am
@ Agawa001 Itulah satu perbedaan, yang lain adalah bahwa tantangan lainnya adalah tentang fungsi pada bilangan bulat positif, sedangkan tantangan ini meminta fungsi pada semua bilangan bulat.
Martin Ender
1
Saya pikir definisi siklus Anda perlu memasukkan n yang minimal. Jika tidak, siklus panjang Anda 2 juga dianggap sebagai siklus panjang Anda 4 dan 6 dan seterusnya.
xnor
@ xnor Whoops, poin bagus.
Martin Ender

Jawaban:

2

Pyth, 27 18 byte

_h?gQ0^2Q*.5@,Q-xh

Penjelasan (Pyth menginisialisasi Qke integer input):

_                       negative of (
                          (
  ?gQ0                      if Q >= 0:
      ^2Q                     2**Q
                            else:
         *.5                  half of
            @        Q          element Q (modulo list length) in
             ,                    the two element list [
              Q                     Q,
                 hQ                 ((Q plus 1)
                x  Q                 XOR Q)
               -    Q               minus Q
                                  ]
 h                        ) plus 1
                        )

Ini memiliki siklus

(−1)
(0, −2)
(1, −3, −4)
(2, −5, −7, −6)
(3, −9, −13, −11, −8)
(4, - 17, −25, −21, −15, −10)
(5, −33, −49, −41, −29, −19, −12)
(6, −65, −97, −81, −57, −57, −37, −23, −14)
(7, −129, −193, −161, −113, −73, −45, −27, −16)
(8, −257, −385, −321, −225 , −145, −89, −53, −31, −18)
(9, −513, −769, −641, −449, −289, −177, −105, −61, −35, −20)

Siklus panjang n diberikan oleh

( n - 2,
−2 ^ ( n - 2) ⋅1 - 1,
−2 ^ ( n - 3) ⋅3 - 1,
−2 ^ ( n - 4) ⋅5 - 1,
…,
−2 ^ 2 ⋅ (2 · n - 7) - 1,
−2 ^ 1⋅ (2 · n - 5) - 1,
−2 ^ 0⋅ (2 · n - 3) - 1).

Setiap bilangan bulat k ≥ −1 muncul sebagai elemen pertama dari siklus ( k + 2). Untuk setiap bilangan bulat k <−1, kita dapat secara unik menulis 1 - k = 2 ^ i ⋅ (2⋅ j + 1) untuk beberapa i , j ≥ 0; maka k muncul sebagai ( j + 2) th elemen dari ( i + j + 2) -siklus.

Anders Kaseorg
sumber
5

MATL , 47 byte

E|G0<-QXJ:tQ*2/0hStJ<f0))Q2MQ)&:J6M-)2/ttk>Eq*k

Cobalah online!

Penjelasan umum

Fungsi 2 di bawah ini sama dengan yang digunakan dalam jawaban @ Sp3000 untuk tantangan terkait. Terima kasih kepada @ Agawa001 karena memperhatikan.

Fungsinya adalah komposisi tiga:

  1. Bijection dari Z (bilangan bulat) ke N (naturals).
  2. Bijeksi dari N ke N dengan karakteristik yang diinginkan (satu siklus dari setiap panjang).
  3. Invers fungsi 1.

Fungsi 1 dan 3 digunakan karena lebih mudah (saya pikir) untuk mencapai perilaku yang diinginkan di N daripada di Z .

Fungsi 2 adalah sebagai berikut: baris atas adalah domain, baris bawah adalah kode. Koma digunakan untuk kejelasan:

1,  2  3,  4  5  6,  7  8  9  10  ...
1,  3  2,  6  4  5, 10  7  8   9  ...

Blok pertama (dari atas 1ke bawah 1) adalah siklus dengan panjang 1. Blok kedua (dari 2 3ke 3 2) adalah siklus dengan panjang 2, dll. Di setiap blok, bagian bawah (gambar fungsi) adalah bagian atas yang digeser secara melingkar. satu langkah ke kanan.

Fungsi 1 adalah sebagai berikut:

 -5  -4  -3  -2  -1   0  +1  +2  +3  +4  ...
+10  +8  +6  +4  +2  +1  +3  +5  +7  +9  ...

Fungsi 3 sama dengan 1 dengan dua garis ditukar.

Contohnya

Gambar 3adalah -5. Pertama 3dipetakan 7oleh fungsi 1; kemudian 7dipetakan 10oleh fungsi 2; kemudian 10dipetakan ke -5` oleh fungsi 3.

Siklus panjang-1 adalah 0. Siklus panjang-2 adalah -1 1. Siklus-3 panjang -3 2 -2, dll.

Kode dijelaskan

Fungsi 1 dan 3 sangat mudah.

Fungsi 2 berfungsi dengan menemukan titik akhir yang lebih rendah dari blok input yang sesuai. Misalnya, jika input ke fungsi ini 9ditemukan 7(lihat blok di atas). Kemudian mengambil titik akhir atas, yang ada 10dalam contoh. Pergeseran melingkar blok dicapai berkat pengindeksan modular berbasis 1 MATL.

         % FUNCTION 1
         % Implicit input
E|       % Multiply by two. Absolute value
G0<      % 1 if input is negative, 0 otherwise
-        % Subtract
Q        % Add 1
XJ       % Copy to clipboard J. Used as input to the next function

         % FUNCTION 2
:        % Range [1 2 ... J], where J denotes the input to this function
tQ*      % Duplicate, increment by 1, multiply
2/       % Divide by 2
0hS      % Prepend a 0. This is needed in case J is 0
tJ<f     % Duplicate. Find indices that are less than the input J
0)       % Pick the last index.
)        % Apply as index to obtain input value that ends previous block
Q        % Add 1: start of current block
2M       % Push the two arguments to second-to-last function call
Q)       % Add 1 and use as index: end of current block
&:       % Inclusive binary range: generate input block 
J        % Push J (input to function 2)
6M-      % Subtract start of block
)        % Apply as index (1-based, modular). This realizes the shifting

         % FUNCTION 3
2/       % Divide by 2
ttk>     % Duplicate. 1 if decimal part is not 0; 0 otherwise
Eq       % Multiply by 2, add 1
*        % Multiply
k        % Round down
         % Implicit display
Luis Mendo
sumber
ini adalah twist dari fungsi sp3000 kan?
Abr001am
@ Agawa001 Oh benarkah? Saya tidak melihat tantangan lainnya. Saya akan memeriksanya
Luis Mendo
Oh Pasti begitu. Setidaknya itu menjelaskan bahwa alasan saya, jika bukan yang asli, benar :-)
Luis Mendo
mengherankan bagaimana lebih dari satu pikiran dibingkai secara erat untuk memancarkan ide-ide dekat.
Abr001am
4

Python 2, 55 byte

g=lambda n,k=1:n/k and~g(~n+k*(n>0),k+1)+k*(n>0)or-~n%k

59 byte:

g=lambda n,k=1:n<0and~g(~n,2)or n/k and k+g(n-k,k+2)or-~n%k

Menciptakan siklus

[0]
[-1, -2]
[1, 2, 3]
[-3, -4, -5, -6]
[4, 5, 6, 7, 8]
...

Dimodifikasi dari solusi saya pada tantangan sebelumnya , yang dimodifikasi dari konstruksi Sp3000 .

Fungsinya

g=lambda n,k=1:n/k and k+g(n-k,k+2)or-~n%k

membuat siklus ukuran aneh dari angka non-negatif

[0]
[1, 2, 3]
[4, 5, 6, 7, 8]
...

Untuk menemukan ukuran siklus yang benar k, geser input nturun k=1,3,5,7,...hingga hasilnya dalam interval [0,k). Siklus interval ini dengan operasi n->(n+1)%k, lalu batalkan semua pengurangan yang dilakukan pada input. Ini diimplementasikan secara rekursif oleh k+g(n-k,k+2).

Sekarang, kita perlu yang negatif untuk membuat siklus genap. Perhatikan bahwa jika kita memodifikasi guntuk memulai dengan k=2di g, kita akan mendapatkan siklus bahkan ukuran

[0, 1]
[2, 3, 4, 5]
[6, 7, 8, 9, 10, 11]
...

Ini biject ke negatif melalui bit-melengkapi ~. Jadi, ketika nnegatif, kami hanya mengevaluasi g(n)sebagai ~g(~n,2).

Tidak
sumber
Saya tidak tahu apakah itu membantu, tetapi ktampaknya cara lain untuk menghitung Math.floor(Math.sqrt(n))*2+1.
Neil
@Neil Saya melihat ke dalam menentukan batas-batas dan ukuran siklus secara hitung dan bahkan melakukan seluruh perhitungan seperti itu, tetapi ungkapan-ungkapan ini panjang dengan Python dan saya menemukan rekursi menjadi lebih pendek.
xnor
3

Python 3, 110 byte

Saya masih belum menemukan cara mendapatkan lambda di sana

jika n adalah angka segitiga [1,3,6,10,15,21,28, dll ...] maka f (n) adalah urutan dalam daftar dikalikan dengan yang negatif. jika angkanya negatif, berikan 1 + angka segitiga terkecil berikutnya. selain itu, increment.

Contoh: 5 bukan angka segitiga, jadi tambahkan 1.

Iterasi berikutnya, kita memiliki 6. 6 adalah angka segitiga, dan ini adalah ke-3 dalam daftar, jadi keluarlah -3.

Program memberikan daftar ini

panjang 1: [0]

panjang 2: [1, -1]

panjang 3: [2,3, -2]

panjang 4: [4,5,6, -3]

panjang 5: [7,8,9,10, -4]

x=int(input())
if x<0:print((x**2+x)/2+1)
else:
 a=((8*x+1)**.5-1)/2
 if a%1:print(x+1)
 else:print(-a)

Sunting: Terima kasih lagi kepada @TuukkaX karena telah menghapus kelebihan karakter.

Magenta
sumber
1
Anda dapat mengubah 0.5ke .5dan input('')ke input().
Yytsi
2

Python 3, 146 byte

Untuk setiap angka lebih besar dari 0, bahkan ada loop (len 2,4,6,8 ...), dan kurang dari 0, loop aneh (1,3,5,7). 0 peta ke 0.

(-3, -2, -1), (0), (1,2), (3,4,5,6)

peta ke

(-2, -1, -3), (0), (2,1), (6,3,4,5)

f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5)
x=int(input());n=f(x)
if x>0:b=n*(n-2)/4
else:b=-((n+1)/2)**2
print(b+1+(x-b-2)%n)

Sunting: @TuukkaX lepas landas 8 byte dari solusi sebelumnya. Dan 3 lainnya.

Magenta
sumber
1
Saya pikir Anda dapat menghapus spasi putih sebelum pernyataan if di baris pertama. Dan mibisa diubah menjadi sesuatu yang lebih kecil, seperti b.
Yytsi
Berikut adalah program yang sama dengan turun f=lambda x:1+2*int(abs(x)**0.5)if x<1 else 2*int(x**0.5+0.5) x=int(input()) n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
golf
1
Terima kasih, @TuukkaX. Saya lupa tentang variabel 2 karakter 'mi'.
Magenta
1
Saya juga berubah input('')menjadi input(). Kutipan tidak berguna karena kita tidak perlu mencetak apa pun ke konsol ketika kita hanya ingin mendapatkan input.
Yytsi
1
Bahkan lebih pendek. Menghilangkan nol sebelum titik-titik. f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5) x=int(input());n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
Yytsi
2

Matlab (423)

function u=f(n),if(~n)u=n;else,x=abs(n);y=factor(x);for o=1:nnz(y),e=prod(nchoosek(y,o)',1);a=log(x)./log(e);b=find(a-fix(a)<exp(-9),1);if ~isempty(b),k=e(b);l=fix(a(b));break;end;end,if(abs(n)==1)k=2;l=0;end,if(k==2)l=l+1;x=x*2;end,e=dec2base(l,k)-48;o=xor(e,circshift(e,[0 1]));g=~o(end);if(~o|nnz(o==1)~=numel(e)-g),u=n*k;else,if((-1)^g==sign(n)),u=sign(n)*k^(base2dec([e(2:end-1) 1]+48,k)-(k==2));else,u=n*k;end,end,end
  • Non-bersaing karena itu memecahkan rekor yang bagus untuk menjadi peringkat untuk peringkat terakhir, sementara aku berjuang untuk memperpendeknya sebisa mungkin.

  • Beberapa bug nonesensikal mengenai akurasi dalam matlab yang saya tidak bisa menemukan jalan keluar kecuali membuat kode saya sarkastik besar, di sisi lain pemetaan yang saya pilih adalah dalam hal facor utama dan logaritma n-ary.

Eksekusi

 f(2)

 1

 f(1)

 2

 f(-2)

 -4

 f(-4)

 -8

 f(-8)

 -1

 f(0)

 0



 ----------------------------

Penjelasan

  • Knonwing, pertama, bahwa angka apa pun dapat ditulis sebagai produk eksponen bilangan prima N=e1^x1*e2^x2...dari pangkalan ini saya memilih untuk memetakan gambar siklus Cyang diekstraksi dari eksponen terbesar dari faktor terkecil (tidak harus prima) bahwa N adalah kekuatan sempurna dari .

  • dalam kata-kata yang lebih sederhana, misalkan N=P^xP adalah akar sempurna terkecil, xmenunjukkan tepat dua istilah penting untuk siklus:, x=Ʃ(r*P^i)istilah Padalah basis siklus juga akar sempurna untuk bilangan utama N, dan kmerupakan derajat siklus C=p^k, di mana ibervariasi antara 1 dan k, koefisien rbertambah dengan 1 dan dibatasi oleh P-1 untuk pra-gambar berikut sampai semua koefisien diatur ke r = 1, jadi kami beralih ke awal siklus itu.

  • Untuk menghindari tabrakan antar siklus, pilihan eksponensial bilangan prima daripada produknya akurat, karena sebagai contoh dua siklus basa 3dan 2titik temu di antaranya 3*2, jadi ini dihindari karena siklus ditentukan oleh derajatnya lebih dari derajatnya. basis, dan untuk titik temu ada siklus basis 6dan derajat 1 lainnya.

  • Angka negatif menempatkan pengecualian, karena untuk itu, saya memesan derajat ganjil untuk angka negatif, dan bahkan derajat untuk sisanya. Bagaimana ?

    untuk setiap angka N yang tertanam dalam suatu siklus P^k, ditulis sebagai P^(a0*P^i0+a1*P^i1+...), jumlah (a0*P^i0+a1*P^i1+...)tersebut ditransaksikan dalam basis P-ary sebagai a0,a1,...., untuk memperjelas poin ini jika (p = 2) urutannya harus dalam basis biner. Seperti diketahui sebelumnya tanpa menetapkan kondisi derajat positif / negatif dan (+/- 1) pengecualian, angka N berada di tepi siklus derajat kjika dan hanya jika urutan Aditulis sebagai 1111..{k+1}..10atau 111..{k}..1untuk semua pangkalan, jika tidak tidak diperlukan rotasi, dengan demikian menetapkan kondisi negatif / positif untuk masing-masing derajat ganjil / genap k/k'untuk keduanya membuat urutan ganjil yang ditulis dalam formulir 101..{k}..100, urutan genap ditulis dalam bentuk 101..{k'}..10untuk tepi awal dari masing-masing siklus angka negatif / positif masing-masing .

    Contoh:

    Mengambil angka N=2^10,, x=10=2^1+2^3urutan A ditulis A=1010, jenis urutan ini menunjukkan tepi terbatas dari siklus bilangan positif, yaitu C=2^3, sehingga gambar berikutnya adalah dari ujung awal A=011yang 8, Tapi , dengan standarisasi hasil ini menjadi (+ / -) 1 pengecualian 2^10/2peta ke 8/2dan gambar sebelumnya tidak boleh diputar.

    Mengambil nomor N=-3^9,, x=9=3^2urutan A ditulis A=100, jenis urutan ini gejala tepi terbatas dari siklus bilangan negatif, yaitu C=3^1, sehingga gambar berikutnya adalah dari ujung awal A=01yang 3, Tapi, dengan mengadaptasi hasil ini ke negatif / positif -3^9peta kondisi untuk -3.

  • untuk pasangan (-/+)1, saya membayangkan untuk mengganggunya dalam jumlah basis siklus 2, dengan kedok bahwa urutan biasa dari kelompok siklik {2,4}{8,16,32,64}..dibuat dalam bentuk lain {1,2}{4,8,16,32}.., ini mencegah hilangnya elemen sebelumnya, dan operasi yang dilakukan hanya bergeser dengan muncul elemen baru di.


Hasil:

menjalankan lembar-kode kecil ini untuk memverifikasi rentang angka siklik pertama yang masuk akal:

for (i=1:6) 
index=1;if(max(factor(i))>=5) index=0;end
for ind=0:index
j=f(((-1)^ind)*i); while(((-1)^ind)*i~=j)fprintf('%d ',j);j=f(j);end,fprintf('%d \n',(-1)^ind*i),pause,end,
end

Ini mengarah ke hasil ini

 2 1 
 -2 -4 -8 -1 
 1 2 
 -4 -8 -1 -2 
 9 27 3 
 -9 -27 -81 -243 -729 -2187 -6561 -19683 -3 
 8 16 32 64 128 256 512 4 
 -8 -1 -2 -4 
 25 125 625 3125 5 
 36 216 1296 7776 46656 6 
 -36 -216 -1296 -7776 -46656 -279936 -1679616 -10077696 -60466176 -362797056 -2.176782e+009 -1.306069e+010 ??? Error using ==> factor at 27

Yang terakhir adalah segmentasi-kesalahan tetapi cocok dengan rentang [-127.127] standar yang ditandatangani integer.

Abr001am
sumber
Saya menggunakan teknik ini beberapa waktu yang lalu untuk mendefinisikan fungsi hash dalam program C lama saya, itu berfungsi dengan baik!
Abr001am
0

JavaScript (ES6), 73 byte

f=(n,i=0,j=0,k=0,l=1,m=i<0?-i:~i)=>n-i?f(n,m,k++?j:i,k%=l,l+!k):++k-l?m:j

Bekerja dengan menghitung urutan (0, -1, 1, -2, 2, -3, 3, ...) hingga ditemukan n, menghitung siklus saat berjalan. iberisi entri saat ini; jberisi awal dari siklus saat ini, kindeks dalam siklus, lpanjang siklus saat ini dan mentri berikutnya dalam urutan. Setelah kami menemukan nkami kemudian mengambil jjika kita berada di akhir siklus atau mjika tidak.

Neil
sumber