Perubahan Pemimpin Faktorisasi yang Rendah

12

tl; dr: Keluarkan nilai-nilai di mana pemimpin faktorisasi berkurang yang berubah.

Setiap bilangan bulat positif memiliki faktorisasi prima yang unik. Sebut saja faktorisasi prima tereduksi hanya daftar banyaknya faktor prima, yang diperintahkan berdasarkan ukuran faktor. Misalnya, faktorisasi utama berkurang 1980adalah [2, 2, 1, 1], karena 1980 = 2 * 2 * 3 * 3 * 5 * 11.

Selanjutnya, mari kita catat seberapa sering masing-masing faktorisasi utama yang berkurang terjadi, melebihi bilangan bulat [1, 2, ..., n]. Misalnya, dalam [1, 2, ..., 10], faktorisasi prima tereduksi berikut terjadi:

[1]: 4 (2, 3, 5, 7)
[2]: 2 (4, 9)
[1, 1]: 2 (6, 10)
[]: 1 (1)
[3]: 1 (8)

Kami akan memanggil pemimpin untuk nmengurangi faktorisasi utama yang paling sering terjadi [1, 2, ..., n]. Oleh karena itu, pemimpin faktorisasi utama yang dikurangi n = 10adalah [1]. Ikatan akan dipatahkan oleh ukuran bilangan bulat terbesar kurang dari atau sama dengan ndengan faktorisasi utama yang dikurangi, dengan bilangan bulat terbesar yang lebih kecil menjadi lebih baik. Misalnya, hingga n = 60, faktorisasi utama tereduksi [1]dan [1, 1]terjadi masing-masing 17 kali. Bilangan bulat maksimum dalam rentang pemberian tersebut [1, 1]adalah 58, sedangkan pemberian bilangan bulat maksimum [1]adalah 59. Oleh karena itu, dengan n = 60, pemimpin faktorisasi utama yang dikurangi adalah [1, 1].

Saya tertarik pada nilai-nilai di nmana pemimpin faktorisasi yang berkurang berubah. Itulah nilai-nilai di nmana pemimpin faktorisasi tereduksi berbeda dari pemimpin faktorisasi tereduksi hingga n-1. Sebagai kasus tepi, kita akan mengatakan bahwa kepemimpinan berubah n = 1, karena seorang pemimpin tidak ada n = 0.

Tantangan Anda adalah menghasilkan.

Urutan awal dari output yang diinginkan adalah:

1, 3, 58, 61, 65, 73, 77, 1279789, 1280057, 1280066, 1280073, 1280437, 1280441, 1281155, 1281161, 1281165, 1281179, 1281190, 1281243, 1281247, 1281262, 1281271, 1281313, 1281365

Gaya keluaran yang diizinkan adalah:

  • Output tak terbatas.
  • kPemimpin pertama berubah, di mana kinputnya.
  • The kperubahan pemimpin th, di mana kadalah input.

k mungkin nol atau satu diindeks.

Ini adalah kode-golf. Jika Anda tidak yakin tentang apa pun, tanyakan di komentar. Semoga berhasil!

isaacg
sumber
Bagaimana dengan pemimpin yang berubah dengan nilai paling banyak / kurang dari k?
user202729
@ user202729 Saya akan mengatakan tidak - yang membuat tantangannya sedikit berbeda.
isaacg
Karena Anda telah menetapkan ide untuk bilangan bulat positif, Anda mungkin ingin mengizinkan orang untuk memulai urutan di 1 atau 3. (atau mengubah "Itu adalah nilai-nilai di nmana pemimpin faktorisasi berkurang berbeda dari pemimpin faktorisasi berkurang berkurang hingga n-1")
Jonathan Allan
@ Jonathanathan Allan Saya tidak mengubah banyak hal, tetapi saya mengklarifikasi bagian yang relevan dari tantangan.
isaacg

Jawaban:

3

Sekam , 18 byte

m←ġ(←►Lk=mȯmLgpṫ)N

Cobalah online! Ini mencetak daftar tanpa batas. Tautan memotong hasil ke 7 nilai pertama, karena program ini sangat tidak efisien dan waktu habis setelah itu pada TIO.

Tanda kurung jelek, tapi aku tidak tahu bagaimana cara menyingkirkannya.

Penjelasan

m←ġ(←►Lk=mȯmLgpṫ)N  No input.
                 N  The list of natural numbers [1,2,3,4,..
  ġ(            )   Group into slices according to this function.
                    Each slice corresponds to a run of numbers with equal return values.
    ←►Lk=mȯmLgpṫ    Function: from n, compute the reduced factorization leader in [1..n].
                     As an example, take n = 12.
               ṫ     Reversed range: [12,11,10,9,8,7,6,5,4,3,2,1]
         m           Map over this range:
              p       Prime factorization: [[2,2,3],[11],[2,5],[3,3],[2,2,2],[7],[2,3],[5],[2,2],[3],[2],[]]
             g        Group equal elements: [[[2,2],[3]],[[11]],[[2],[5]],[[3,3]],[[2,2,2]],[[7]],[[2],[3]],[[5]],[[2,2]],[[3]],[[2]],[]]
          ȯmL         Take length of each run: [[2,1],[1],[1,1],[2],[3],[1],[1,1],[1],[2],[1],[1],[]]
       k=            Classify by equality: [[[2,1]],[[1],[1],[1],[1],[1]],[[1,1],[1,1]],[[2],[2]],[[3]],[[]]]
                     The classes are ordered by first occurrence.
     ►L              Take the class of maximal length: [[1],[1],[1],[1],[1]]
                     In case of a tie, ► prefers elements that occur later.
    ←                Take first element, which is the reduced factorization leader: [1]
                    The result of this grouping is [[1,2],[3,4,..,57],[58,59,60],[61,62,63,64],..
m←                  Get the first element of each group: [1,3,58,61,65,73,77,..
Zgarb
sumber
Kenapa ►=tidak bekerja? Tidak maxBysuka elemen yang lebih baru?
H.PWiz
@ H.PWiz Masalahnya adalah dalam kasus seri, saya perlu memilih elemen memaksimalkan yang kemunculan pertamanya dalam rentang terbalik adalah yang terbaru , atau yang setara, yang kemunculan terakhirnya dalam rentang kenaikan adalah yang paling awal . ►=tidak melakukan keduanya.
Zgarb
1

JavaScript (ES6), 120 byte

Mengembalikan perubahan pemimpin ke-N, 1-diindeks.

N=>(F=m=>N?F((F[k=(D=(n,d=2,j)=>d>n?j:n%d?D(n,d+1)+(j?[,j]:[]):D(n/d,d,-~j))(++n)]=-~F[k])>m?F[N-=p!=k,p=k]:m):n)(n=p=0)

Demo

Berkomentar

Fungsi pembantu D () , mengembalikan faktorisasi prima tereduksi dari n dalam urutan terbalik:

D = (n, d = 2, j) =>             // n = input, d = divisor, j = counter
  d > n ?                        // if d is greater than n:
    j                            //   append j and stop recursion
  :                              // else:
    n % d ?                      //   if d is not a divisor of n:
      D(n, d + 1) + (            //     recursive call with n unchanged and d = d + 1
        j ?                      //     if j is not undefined:
          [,j]                   //       append a comma followed by j
        :                        //     else:
          []                     //       append nothing
      )                          //
    :                            //   else:
      D(n / d, d, -~j)           //     recursive call with n divided by d and j = j + 1

Fungsi utama:

N =>                             // N = target index in the sequence
  (F = m =>                      // m = # of times the leader has been encountered
    N ?                          // if N is not equal to 0:
      F(                         //   do a recursive call to F():
        (F[k = D(++n)] =         //     increment n; k = reduced prime factorization of n
                         -~F[k]) //     increment F[k] = # of times k has been encountered
        > m ?                    //     if the result is greater than m:
          F[N -= p != k,         //       decrement N if p is not equal to k
                         p = k]  //       update p and set m to F[p]
        :                        //     else:
          m                      //       let m unchanged
      )                          //   end of recursive call
    :                            // else:
      n                          //   stop recursion and return n
  )(n = p = 0)                   // initial call to F() with m = n = p = 0
Arnauld
sumber
1

Stax , 24 byte

Ç▓Δk/‼&²Θºk∙♥╜fv╛Pg8╝j♀§

Program ini tidak memerlukan input dan secara teoritis menghasilkan output tanpa batas. Saya katakan "secara teoritis" karena elemen ke-8 akan membutuhkan waktu lebih dari setahun.

Jalankan dan debug itu

Representasi ascii yang sesuai dari program yang sama adalah ini.

0WYi^{|n0-m|=c:uny=!*{i^Q}Md

Itu membuat pemimpin terakhir di tumpukan. Iterasi bilangan bulat, jika ada mode yang berbeda dalam representasi faktor, dan itu berbeda dari yang terakhir, keluarkan.

0                               push zero for a placeholder factorization
 W                              repeat the rest of the program forever
  Y                             store the last factorization in the y register
   i^                           i+1 where i is the iteration index
     {    m                     using this block, map values [1 .. i+1]
      |n0-                          get the prime exponents, and remove zeroes 
           |=                   get all modes
             c:u                copy mode array and test if there's only one
                ny=!            test if mode array is not equal to last leader
                    *           multiply; this is a logical and
                     {   }M     if true, execute this block
                      i^Q       push i+1 and print without popping
                           d    discard the top of stack
                                    if it was a leader change, this pops i+1
                                    otherwise it pops the mode array
                                at this point, the last leader is on top of 
                                the stack
rekursif
sumber
0

Python 2 , 145 byte

m=i=0;f=[]
while 1:
 i+=1;a=i;d=[0]*-~i;k=2
 while~-a:x=a%k>0;k+=x;a/=x or k;d[k]+=1-x
 k=filter(abs,d);f+=k,;c=f.count
 if c(k)>c(m):print i;m=k

Cobalah online!

Tidak disatukan

m=0                    # reduced prime factorizations leader
i=0                    # current number
f=[]                   # list of reduced prime factorizations
while 1:               # Infinite loop:
  i+=1                 #   next number
  a=i                  #   a is used for the prime factorization
  d=[0]*-~i            #   this lists stores the multiplicity
  k=2                  #   current factor
  while~-a:            #   As long as a-1 != 0:
    x=a%k>0            #      x := not (k divides a)
    k+=x               #      If k does not divide a, go to the next factor
    a/=x or k          #      If k does not divide a,
                       #         divide a by 1,
                       #         else divide it by k
    d[k]+=1-x          #      add 1 to the multiplicity of k if k divides a
  k=filter(abs,d)      #   Only keep non-zero multiplicities
                       #     k is now the reduced prime factorization of i
  f+=k,                #   append k to the list of reduced prime factorizations
  c=f.count            #   c(x) := number of occurences of x in f
  if c(k)>c(m):        #   has the current reduced prime factorization
                       #    appeared more often than the leader?
    print i;m=k        #     print the current number, set new leader

Cobalah online!

ovs
sumber
0

Jelly ,  35  34 byte

Saya merasa masih golf

ÆEḟ0µ€ĠL€M⁸’ߤ¹Ṗ?
®‘©Ç€F0;ITµL<³µ¿

Program lengkap yang mengambil kdan mengeluarkan representasi daftar Jelly dari kpoin perubahan pemimpin pertama .

Cobalah online!

Jonathan Allan
sumber