Änderungen an den Faktorisierungsführern wurden reduziert

12

tl; dr: Gibt die Werte aus, bei denen sich die Führungslinie für die reduzierte Primfaktorisierung ändert.

Jede positive ganze Zahl hat eine eindeutige Primfaktorisierung. Nennen wir die reduzierte Primfaktorisierung einfach die Liste der Multiplikationen der Primfaktoren, geordnet nach der Größe der Faktoren. Die reduzierte Primfaktorzerlegung von zum Beispiel 1980heißt [2, 2, 1, 1], weil 1980 = 2 * 2 * 3 * 3 * 5 * 11.

Als nächstes notieren wir, wie oft jede reduzierte Primfaktorisierung über ganze Zahlen in auftritt [1, 2, ..., n]. Beispielsweise treten in [1, 2, ..., 10]den folgenden Fällen reduzierte Primfaktoren auf:

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

Wir rufen den Anführer zu nder reduzierten Primfaktorisierung auf, die am häufigsten vorkommt [1, 2, ..., n]. Daher ist für die reduzierte Primfaktorzerlegung Führer n = 10ist [1]. Gleichheit wird durch die Größe der größten ganzen Zahl gebrochen, die kleiner oder gleich ndieser reduzierten Primfaktorisierung ist, wobei die kleinere ganze Zahl besser ist. Zum Beispiel bis zu n = 60den reduzierten Primfaktoren [1]und [1, 1]treten jeweils 17 mal auf. Die maximale Ganzzahl in diesem Bereich [1, 1]ist 58, während die maximale Ganzzahl [1]ist 59. Daher ist mit n = 60der reduzierte Primfaktor führend [1, 1].

Ich bin an den Werten interessiert, an ndenen sich der Leader der reduzierten Primfaktorisierung ändert. Dies sind die Werte, bei ndenen sich der Leader der reduzierten Primfaktorisierung von dem Leader der reduzierten Primfaktorisierung bis unterscheidet n-1. Als Randfall werden wir sagen, dass sich die Führung ändert n = 1, weil für keinen Führer existiert n = 0.

Ihre Herausforderung ist die Ausgabe.

Eine Anfangssequenz der gewünschten Ausgabe ist:

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

Zulässige Ausgabestile sind:

  • Unendliche Ausgabe.
  • Der erste kAnführer wechselt, wo kist der Input.
  • Der kdritte Anführer wechselt, wo kist der Input.

k kann null oder eins sein.

Das ist Code-Golf. Wenn Sie sich bei etwas nicht sicher sind, fragen Sie in den Kommentaren. Viel Glück!

isaacg
quelle
Was ist mit dem Leader, der sich mit einem Wert von höchstens / weniger als k ändert?
user202729
@ user202729 Ich werde nein sagen - das macht die Herausforderung ein bisschen zu anders.
Isaacg
Da Sie die Idee für positive ganze Zahlen definiert haben möchten Sie vielleicht Menschen ermöglichen , die Sequenz an beiden 1 oder 3 (oder Änderung zu beginnen „sind diejenigen , die Werte von ndenen der reduzierte Primfaktorzerlegung Führer unterscheidet sich von der reduzierten Primfaktorzerlegung Führer bis zu n-1")
Jonathan Allan
@ JonathanAllan Ich ändere keine Dinge, aber ich habe den relevanten Teil der Herausforderung geklärt.
Isaacg

Antworten:

3

Schale , 18 Bytes

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

Probieren Sie es online! Dies druckt die unendliche Liste. Die Verknüpfung schneidet das Ergebnis auf die ersten 7 Werte ab, da das Programm ziemlich ineffizient ist und danach bei TIO eine Zeitüberschreitung auftritt.

Die Klammern sind hässlich, aber ich weiß nicht, wie ich sie loswerden soll.

Erläuterung

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
quelle
Warum geht das ►=nicht? Bevorzugen Sie maxBykeine späteren Elemente?
H.PWiz
@ H.PWiz Das Problem ist, dass ich im Falle eines Gleichstands das maximierende Element bevorzugen muss, dessen erstes Auftreten im umgekehrten Bereich das spätestmögliche ist , oder gleichwertig, dessen letztes Auftreten im zunehmenden Bereich das frühestmögliche ist . ►=tut beides nicht.
Zgarb
1

JavaScript (ES6), 120 Byte

Gibt die N-te Führungsänderung mit 1 Index zurück.

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

Kommentiert

Hilfsfunktion D () , die die reduzierte Primfaktorisierung von n in umgekehrter Reihenfolge zurückgibt :

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

Hauptfunktion:

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
quelle
1

Stax , 24 Bytes

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

Dieses Programm benötigt keine Eingabe und erzeugt theoretisch eine unendliche Ausgabe. Ich sage "theoretisch", weil das 8. Element mehr als ein Jahr dauern wird.

Führen Sie es aus, und debuggen Sie es

Dies ist die entsprechende ASCII-Darstellung desselben Programms.

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

Es hält den letzten Anführer auf dem Stapel. Durchlaufen Sie ganze Zahlen, und geben Sie sie aus, wenn die Faktordarstellung einen anderen als den letzten Modus aufweist.

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
rekursiv
quelle
0

Python 2 , 145 Bytes

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

Probieren Sie es online!

Ungolfed

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

Probieren Sie es online!

ovs
quelle
0

Gelee ,  35  34 Bytes

Ich fühle mich immer noch golffähig

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

Ein volles Programm nehmen k eine Geleelistendarstellung der ersten kFührungswechselpunkte aufnimmt und ausgibt .

Probieren Sie es online!

Jonathan Allan
quelle