Zmniejszone zmiany lidera faktoryzacji

12

tl; dr: Wyprowadza wartości, w których zmienia się lider zmniejszonego współczynnika pierwotnego.

Każda dodatnia liczba całkowita ma unikalny rozkład na czynniki pierwsze. Nazwijmy zmniejszoną faktoryzację pierwszą tylko listą mnogości czynników pierwszych, uporządkowaną według wielkości czynników. Na przykład zmniejszone rozkładanie na czynniki pierwsze 1980wynosi [2, 2, 1, 1], ponieważ 1980 = 2 * 2 * 3 * 3 * 5 * 11.

Następnie zanotujmy, jak często zdarza się każde zmniejszone rozkładanie na czynniki pierwsze, w porównaniu do liczb całkowitych [1, 2, ..., n]. Na przykład w [1, 2, ..., 10]następujących przypadkach występują następujące zmniejszone czynniki pierwsze:

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

Wezwamy lidera do nzmniejszonego faktoryzacji liczby pierwszych, który występuje najczęściej [1, 2, ..., n]. Dlatego liderem zredukowanej liczby pierwszych czynników n = 10jest [1]. Więzy zostaną zerwane przez rozmiar największej liczby całkowitej mniejszej lub równej ntej zmniejszonej faktoryzacji pierwotnej, przy czym mniejsza największa liczba całkowita będzie lepsza. Na przykład, aż do n = 60zredukowanych faktoryzacji pierwszych [1]i [1, 1]występują 17 razy. Maksymalna liczba całkowita w podanym zakresie [1, 1]to 58, natomiast maksymalna liczba całkowita [1]to 59. Dlatego z n = 60, liderem o zmniejszonej liczbie pierwszych czynników jest [1, 1].

Interesują mnie wartości, w nktórych zmienia się lider zmniejszonego faktoryzacji podstawowej. Są to wartości, w nprzypadku których lider zredukowanego głównego faktoryzacji różni się od lidera zredukowanego pierwotnego faktoryzacji do n-1. Na marginesie powiemy, że przywództwo zmienia się n = 1, ponieważ lider nie istnieje n = 0.

Twoim wyzwaniem jest produkcja.

Początkowa sekwencja żądanego wyniku to:

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

Dozwolone style wyjściowe to:

  • Nieskończona wydajność.
  • Pierwszy klider zmienia się, gdzie kjest wkład.
  • Zmiana klidera, gdzie kjest wkład.

k może być zero lub jeden indeksowany.

To jest golf golfowy. Jeśli nie jesteś pewien, zapytaj w komentarzach. Powodzenia!

isaacg
źródło
Co z liderem zmienia się z wartością najwyżej / mniej niż k?
user202729,
@ user202729 Zamierzam powiedzieć nie - to sprawia, że ​​wyzwanie jest nieco inne.
isaacg
Ponieważ zdefiniowałeś pomysł na dodatnie liczby całkowite, możesz chcieć pozwolić ludziom rozpocząć sekwencję od 1 lub 3. (lub zmienić „Są to wartości, w nktórych lider zredukowanego głównego faktoryzacji różni się od lidera zredukowanej pierwotnej faktoryzacji do n-1")
Jonathan Allan
@JonathanAllan Nie zmieniam rzeczy, ale wyjaśniłem istotną część wyzwania.
isaacg

Odpowiedzi:

3

Łuska , 18 bajtów

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

Wypróbuj online! Spowoduje to wydrukowanie nieskończonej listy. Link obcina wynik do pierwszych 7 wartości, ponieważ program jest dość nieefektywny, a następnie kończy się w TIO.

Nawiasy są brzydkie, ale nie wiem, jak się ich pozbyć.

Wyjaśnienie

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
źródło
Dlaczego ►=nie działa Nie maxBypreferuje późniejszych elementów?
H.PWiz
@ H.PWiz Problem polega na tym, że w przypadku remisu muszę preferować element maksymalizujący, którego pierwsze wystąpienie w odwróconym zakresie jest najnowszym możliwym lub równoważnie, którego ostatnie wystąpienie w rosnącym zakresie jest najwcześniej możliwe. ►=nie robi ani.
Zgarb
1

JavaScript (ES6), 120 bajtów

Zwraca N-tą zmianę lidera, 1-indeksowaną.

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)

Próbny

Skomentował

Funkcja pomocnicza D () , zwracająca zmniejszoną faktoryzację pierwszą nw odwrotnej kolejności:

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

Główna funkcja:

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
źródło
1

Stax , 24 bajty

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

Ten program nie przyjmuje danych wejściowych i teoretycznie wytwarza nieskończone dane wyjściowe. Mówię „teoretycznie”, ponieważ ósmy element zajmie ponad rok.

Uruchom i debuguj

Odpowiada to reprezentacji ascii tego samego programu.

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

Utrzymuje ostatniego lidera na stosie. Iteracja po liczbach całkowitych, jeśli w reprezentacji czynnikowej występuje odrębny tryb i różni się on od poprzedniego, wypisz go.

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
rekurencyjny
źródło
0

Python 2 , 145 bajtów

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

Wypróbuj online!

Nie golfił

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

Wypróbuj online!

ovs
źródło
0

Galaretka ,  35  34 bajtów

Wydaje mi się, że nadal można grać w golfa

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

Pełny program pobierający ki generujący galaretkową reprezentację pierwszych kpunktów zmiany lidera.

Wypróbuj online!

Jonathan Allan
źródło