Apakah kamu belum tersesat?

31

Tugas Anda adalah mengimplementasikan urutan integer A130826 :

a n adalah yang terkecil bilangan bulat positif sehingga sebuah n - n adalah seluruh kelipatan 3 dan dua kali jumlah pembagi dari (a n - n) / 3 memberikan n th istilah dalam perbedaan pertama urutan yang dihasilkan oleh Flavius Saringan Josephus.

Hilang belum? Sebenarnya ini cukup mudah.

The Flavius Josephus saringan mendefinisikan urutan integer sebagai berikut.

  1. Mulailah dengan urutan bilangan bulat positif dan set k = 2 .

  2. Hapus setiap k th integer urutan, dimulai dengan k th .

  3. Bertambah k dan kembali ke langkah 2.

f n adalah n th bilangan bulat (1-diindeks) yang tidak pernah akan dihapus.

Jika - seperti biasa - σ 0 (k) menunjukkan jumlah pembagi positif dari bilangan bulat k , kita dapat mendefinisikan sebuah n sebagai terkecil positif bilangan bulat sehingga 0 ((a n - n) / 3) = f n + 1 - f n .

Tantangan

Menulis sebuah program atau fungsi yang mengambil bilangan bulat positif n sebagai masukan dan cetak atau mengembalikan sebuah n .

Aturan standar berlaku. Semoga kode terpendek menang!

Contoh yang berhasil

Jika kita menghapus setiap elemen kedua dari bilangan bulat positif, kita dibiarkan

 1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ...

Setelah menghapus setiap elemen ketiga dari sisanya, kita dapatkan

 1  3  7  9 13 15 19 21 25 27 31 33 37 39 ...

Sekarang, menghapus setiap elemen keempat, lalu kelima, lalu keenam membuat kita

 1  3  7 13 15 19 25 27 31 37 39 ...
 1  3  7 13 19 25 27 31 39 ...
 1  3  7 13 19 27 31 39 ...
 1  3  7 13 19 27 39 ...

Baris terakhir menunjukkan istilah f 1 hingga f 7 .

Perbedaan elemen berturut-turut dari istilah-istilah ini adalah

 2  4  6  6  8 12

Membagi perbedaan ke depan ini dengan 2 , kita dapatkan

 1  2  3  3  4  6 

Ini adalah jumlah pembagi target.

  • 4 adalah bilangan bulat pertama k sehingga σ 0 ((k - 1) / 3) = 1 . Faktanya, σ 0 (1) = 1 .
  • 8 adalah bilangan bulat pertama k sehingga σ 0 ((k - 2) / 3) = 2 . Bahkan, σ 0 (2) = 2 .
  • 15 adalah bilangan bulat pertama k sehingga σ 0 ((k - 3) / 3) = 3 . Bahkan, σ 0 (4) = 3 .
  • 16 adalah bilangan bulat pertama k sehingga σ 0 ((k - 4) / 3) = 3 . Bahkan, σ 0 (4) = 3 .
  • 23 adalah bilangan bulat pertama k sehingga σ 0 ((k - 5) / 3) = 4 . Bahkan, σ 0 (6) = 4 .
  • 42 adalah bilangan bulat pertama k sehingga σ 0 ((k - 6) / 3) = 6 . Bahkan, σ 0 (12) = 6 .

Uji kasus

   n     a(n)

   1        4
   2        8
   3       15
   4       16
   5       23
   6       42
   7       55
   8      200
   9       81
  10       46
  11      119
  12      192
  13      205
  14   196622
  15    12303
  16       88
  17      449
  18      558
  19      127
  20     1748
  21   786453
  22       58
  23     2183
  24     3096
  25     1105
  26   786458
  27 12582939
  28      568
  29     2189
  30     2730
Dennis
sumber
14
Kata kunci pada OEIS: bisu ("urutan tidak penting").
orlp
15
Bodoh? Itu bisa menyelamatkan dunia!
Dennis
3
Pun itu ...
Mego

Jawaban:

7

Jelly, 30 29 27 25 byte

Disimpan 2 byte berkat @ Dennis memberitahukan saya tentang Æd, dan 2 byte lagi untuk menggabungkan dua rantai.

RUð÷‘Ċ×µ/
‘Ç_ÇH0Æd=¥1#×3+

Cobalah online!

Ini mungkin yang paling menyenangkan yang pernah saya alami dengan Jelly. Saya mulai dari baris kedua, yang menghitung f n dari n dengan menggunakan rumus pada Oei, dan cukup indah.

Penjelasan

RUð ÷ 'Ċ × µ / Tautan pembantu untuk menghitung F n . Argumen: n
R Dapatkan angka [1..n]
 U Terbalik
        / Kurangi dengan "membulatkan ke 2 kelipatan berikutnya":
   ÷ Bagi dengan nomor berikutnya
    'Peningkatan untuk melewati beberapa
     Ċ Ceil (mengumpulkan)
      × Kalikan dengan nomor berikutnya

'Ç_ÇH0Æd = ¥ 1 # × 3 + Tautan utama. Argumen: n
'Peningkatan n
 Ç Hitung F n + 1 
   Ç Hitung F n
  _ Kurangi
    H Divide oleh 2
     0 1 # Mulai dari 0, cari kandidat pertama untuk ( n -n) / 3
                   itu memuaskan ...
      Æd σ 0 ((a n -n) / 3)
        = = (F n + 1 -F n ) / 2
            × 3 Kalikan dengan 3 untuk mengubah (a n -n) / 3 menjadi n -n
              + Tambahkan n untuk mengubah n -n menjadi n
PurkkaKoodari
sumber
3

Python 2 , 121 119 118 byte

n=input();r=range(1,4**n);d=s,=r*1,
for k in r:del s[k::k+1];d+=sum(k%j<1for j in r)*2,
print d.index(s[n]-s[n-1])*3+n

Run time harus kira-kira O (16 n ) dengan penggunaan memori O (4 n ) . Mengganti 4**ndengan 5<<n- yang saya pikir sudah cukup - akan meningkatkan ini secara dramatis, tapi saya tidak yakin itu bekerja untuk nilai n yang semena-mena .

Cobalah online!

Perilaku asimptotik dan batas atas suatu n

Tentukan b n sebagai (a n - n) / 3 , yaitu bilangan bulat positif terkecil k sehingga σ 0 (k) = ½ (f n + 1 - f n ) .

Seperti yang tercantum pada halaman OEIS, f n ~ ¼πn 2 , jadi f n + 1 - f n ~ ¼π (n + 1) 2 - ¼πn 2 = ¼π (2n + 1) ~ ½πn .

Dengan cara ini, ½ (f n + 1 - f n ) ~ ¼πn . Jika angka aktual adalah p prima , bilangan bulat positif terkecil dengan pembagi p adalah 2 p-1 , jadi b n dapat diperkirakan dengan 2 c n , di mana c n ~ ~ n .

Oleh karena itu b n <4 n akan tahan untuk n cukup besar , dan mengingat bahwa 2 ¼π n <2 n << (2 n ) 2 = 4 n , saya yakin tidak ada contoh tandingan.

Bagaimana itu bekerja

n=input();r=range(1,4**n);d=s,=r*1,

Ini mengatur beberapa referensi untuk proses berulang kami.

  • n adalah input pengguna: bilangan bulat positif.

  • r adalah daftar [1, ..., 4 n - 1] .

  • s adalah salinan r .

    Mengulangi daftar sekali dengan r*1membuat salinan yang dangkal, jadi memodifikasi s tidak akan mengubah r .

  • d diinisialisasi sebagai tuple (s) .

    Nilai pertama ini tidak penting. Semua yang lain akan memegang jumlah pembagi bilangan bulat positif.

for k in r:del s[k::k+1];d+=sum(k%j<1for j in r)*2,

Untuk setiap bilangan bulat k dari 1 hingga 4 n - 1 , kami melakukan hal berikut.

  • del s[k::k+1]mengambil setiap (k + 1) th integer dalam s - dimulai dengan (k + 1) th - dan menghapus yang slice dari s .

    Ini adalah cara mudah menyimpan interval awal saringan Flavius ​​Josephus dalam s . Ini akan menghitung lebih dari yang diperlukan n + 1 hal awal, tetapi menggunakan satu forloop untuk memperbarui kedua s dan d menyimpan beberapa byte.

  • d+=sum(k%j<1for j in r)*2,menghitung berapa banyak elemen r membagi k secara merata dan menambahkan 0 (k) menjadi d .

    Karena d diinisialisasi sebagai singleton tuple, 0 (k) disimpan pada indeks k .

print d.index(s[n]-s[n-1])*3+n

Temuan ini indeks pertama f n + 1 - f n di d , yang merupakan terkecil k sehingga 0 (k) = f n + 1 - f n , maka menghitung sebuah n sebagai 3k + 1 dan mencetak hasilnya.

Dennis
sumber
2

Java 8, 336 , 305 , 303 , 287 , 283 279 byte

57 byte dihapus berkat Kritixi Lithos

Golf

class f{static int g(int s,int N){return s<1?N+1:g(s-1,N+N/s);}static int h(int k){int u=0,t=1,i;for(;u!=(g(k,k)-g(k,k-1))/2;t++)for(i=1,u=0;i<=t;)if(t%i++<1)u++;return 3*t-3+k;}public static void main(String[]a){System.out.print(h(new java.util.Scanner(System.in).nextInt()));}}

Tidak disatukan

class f {
    static int g(int s,int N){return s < 1 ? N + 1 : g(s - 1, N + N / s);}

    static int h(int k) {
        int u = 0, t = 1, i;
        // get the first number with v divisors
        while(u != (g(k, k) - g(k, k - 1))/2){
            u = 0;
            for (i = 1; i <= t; i++)
                if (t % i < 1) u++;
            t++;
        }
        // 3*(t-1)+k = 3*t+k-3
        return 3 * t + k - 3;
    }

    public static void main(String[] a) {
        System.out.print(h(new java.util.Scanner(System.in).nextInt()));
    }
}
Bobas_Pett
sumber
Saya pikir parsing argumen command-line sebagai intlebih pendek daripada menggunakan java.util.Scanner. Tetapi bahkan jika Anda menggunakan Scanner, Anda dapat melakukan System.out.print(h(new java.util.Scanner().nextInt()))dan menghapus baris sebelumnya
Kritixi Lithos
@KritixiLithos thx, memperbaiki sekarang ...
Bobas_Pett
Di dalam int h(), Anda dapat mengubahnya ke int v = (g(k,k)-g(k,k-1))/2,u = 0,t = 1;. Anda dapat mengubah if-statement Anda (yang ada di dalam for-loop Anda) dari if(t%i==0)menjadiif(t%i<1)
Kritixi Lithos
Selain itu, Anda dapat mengubah fungsi Anda guntuk kembali menggunakan operator ternary seperti return s==0?N+1:g(s-1,N+N/2)-ish
Kritixi Lithos
2
@KritixiLithos lol pada titik ini Anda harus memposting ini sebagai solusi terpisah Anda sendiri
Bobas_Pett
1

Mathematica, 130 116 106 103 byte

3Catch@Do[f=#2⌈#/#2+1⌉&~Fold~Reverse@Range@#&;If[Tr[2+0Divisors@k]==f[#+1]-f@#,Throw@k],{k,∞}]+#&

atau

3Catch@Do[f=#2⌈#/#2+1⌉&~Fold~Reverse@Range@#&;If[2DivisorSum[k,1&]==f[#+1]-f@#,Throw@k],{k,∞}]+#&

Akhirnya hampir identik dengan kode Jelly @ Pietu1998 ...

Penjelasan

Catch@

Catchapa pun yang Throw-d (dilempar).

Do[ ... ,{k,∞}]

Loop tak terbatas; kmulai dari 1dan menambah setiap iterasi.

f= ...

Tetapkan f:

Reverse@Range@#

Temukan {1, 2, ... , n}. Balikkan itu.

#2⌈#/#2+1⌉&

Fungsi yang menampilkan ceil (n1 / n2 + 1) * n2

f= ... ~Fold~ ... &

Tetapkan ffungsi yang secara rekursif menerapkan fungsi di atas ke daftar dari dua langkah di atas, menggunakan setiap output sebagai input pertama dan setiap elemen daftar sebagai input kedua. "Output" awal (input pertama) adalah elemen pertama dari daftar.

Tr[2+0Divisors@k]==f[#+1]-f@#

Periksa apakah dua kali jumlah pembagi ksama dengan f (n + 1) - f (n).

If[ ... ,Throw@k]

Jika kondisinya True, Thrownilai k. Jika tidak, lanjutkan pengulangan.

3 ... +#&

Lipat gandakan hasilnya dengan 3 dan tambahkan n.

Versi 130 byte

Catch@Do[s=#+1;a=k-#;If[3∣a&&2DivisorSigma[0,a/3]==Differences[Nest[i=1;Drop[#,++i;;;;i]&,Range[s^2],s]][[#]],Throw@k],{k,∞}]&
JungHwan Min
sumber
1

Perl 6 , 154 149 136 107 byte

->\n{n+3*first ->\o{([-] ->\m{m??&?BLOCK(m-1).rotor(m+0=>1).flat!!1..*}(n)[n,n-1])/2==grep o%%*,1..o},^Inf}

Tidak Disatukan:

-> \n {                    # Anonymous sub taking argument n
  n + 3 * first -> \o {    # n plus thrice the first integer satisfying:
    (                      #
      [-]                  #
      -> \m {              # Compute nth sieve iteration:
        m                  # If m is nonzero,
          ?? &?BLOCK(m-1).rotor(m+0=>1).flat # then recurse and remove every (m+1)-th element;
          !! 1..*          # the base case is all of the positive integers
      }                    #
      (n)                  # Get the nth sieve
      [n,n-1]              # Get the difference between the nth and (n-1)th elements (via the [-] reduction operator above)
    ) / 2                  # and divide by 2;
    ==                     # We want the number that equals
    grep o %% *, 1..o      # the number of divisors of o.
  }
  ,^Inf
}
Sean
sumber
1

05AB1E ,35 34 39 byte

1Qi4ë[N3*¹+NÑg·¹D>‚vyy<LRvy/>îy*}}‚Æ(Q#

Terlihat mengerikan, begitu juga kinerja runtime. Diperlukan beberapa detik untuk input yang menghasilkan nilai kecil. Jangan coba angka seperti 14; pada akhirnya akan menemukan hasilnya tetapi akan butuh waktu lama.

Penjelasan

Ini berfungsi sebagai 2 program yang disebut berurutan. Yang pertama menghitung F n + 1 - F n dan yang kedua menentukan sebuah n berdasarkan definisi, menggunakan pendekatan bruteforce.

F n + 1 - F n dievaluasi untuk setiap iterasi meskipun loop invarian. Itu membuat waktu kode tidak efisien, tetapi membuat kode lebih pendek.

Cobalah online!

Osable
sumber
Saya tidak yakin saya mengerti. Mengapa tidak bisa menghitung ayakan di atas 65.536?
Dennis
Itu berasal dari fakta bahwa ia menghasilkan semua bilangan bulat antara 0 dan 65536 ( žHL) dan kemudian menyaring nilai-nilai yang tidak memenuhi batasan saringan. Saya pikir bagian pertama dari program ini harus sepenuhnya ditulis ulang dengan pendekatan yang sama sekali berbeda untuk membuatnya golf.
Osable
Kecuali ada batasan (seperti integer lebar tetap) yang mencegah Anda melakukannya, jawaban diharapkan bekerja untuk input apa pun, mengingat waktu dan memori yang cukup.
Dennis
Itu sebabnya saya datang dengan algoritma ayakan lain. Mungkin golf, tetapi saya belum menemukan yang lebih baik di 05AB1E. Namun ada contoh tandingan given enough time and memory, karena saya sudah melihat beberapa jawaban pada pertanyaan lain yang berjalan sangat lambat sehingga hampir tidak mungkin untuk mengatakan apakah mereka menghasilkan output yang tepat atau tidak. Untuk alasan ini saya menempatkan perhitungan saringan selain dari loop dan harganya 2 byte.
Osable
Tidak perlu membuat kode Anda efisien. Anda dapat menjadikan implementasi golf / lambat sebagai kiriman Anda dan memasukkan yang lebih cepat / lebih lama sebagai catatan tambahan. Saya khawatir saya harus menekankan batas dinamis, meskipun biayanya satu byte.
Dennis