Verwandte: Iterierte Phi (n) -Funktion .

Ihre Herausforderung besteht darin, die iterierte Phi-Funktion zu berechnen:

f(n) = number of iterations of φ for n to reach 1.

Wo φist Eulersche Phi-Funktion .

Verwandte OEIS .

Hier ist das Diagramm davon:

Regeln:

Ihr Ziel ist die Ausgabe f(n) von n=2bis n=100.

Das ist Code-Golf, also gewinnt der kürzeste Code.

Hier sind die Werte, mit denen Sie vergleichen können:

1, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 3, 4, 4, 5, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 5, 4, 5, 5, 5, 5, 5, 4, 5, 4, 5, 5, 6, 4, 5, 5, 5, 5, 6, 5, 5, 5, 6, 5, 6, 4, 6, 5, 5, 5, 6, 5, 6, 5, 5, 6, 6, 5, 6, 6, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 6, 5, 6, 7, 5, 7, 5, 6, 6, 7, 5, 6, 6, 6, 6, 6, 6, 7, 5, 6, 6

Haskell , 53 52 Bytes

Danke nimi für das Speichern von 1 Byte!

f<$>[2..100]
f 1=0
f n=1+f(sum[1|1<-gcd n<$>[1..n]])

Probieren Sie es online!

sum[1|1<-gcd n<$>[1..n]]gibt φ(n)(aus flawr genommen , danke!)

fist eine rekursive Funktion, die berechnet, 1+φ(n)wenn n nicht ist 1, und 0wenn nist ausgibt1 , da es keine weiteren Iterationen getroffen werden , um zu erreichen sind1

Schließlich f<$>[2..100]erzeugt eine Liste von fApplied auf jedes Element von[2..100]

Haskell , 70-69 68 Bytes

Die Funktion (\n->sum[1|1<-gcd n<$>[1..n]]) ist die Totientenfunktion, die wir in der anonymen Funktion immer wieder anwenden. Danke @laikoni für -1 Byte!

EDIT: Ich habe gerade herausgefunden, dass @xnor diese exakte Totientenfunktion in einer früheren Herausforderung verwendet hat .

length.fst.span(>1).iterate(\n->sum[1|1<-gcd n<$>[1..n]])<$>[2..100]

Probieren Sie es online!

MATL , 16 15 Bytes

99:Q"@`_Zptq}x@

Probieren Sie es online!

Erläuterung

99:       % Push [1 2 ... 99]
Q         % Add 1 element-wise: gives [2 3 ... 100]
"         % For each k in that array
  @       %   Push k
  `       %   Do...while
    _Zp   %     Euler's totient function
     tq   %     Duplicate, subtract 1. This is the loop condition
  }       %   Finally (execute on loop exit)
  x       %     Delete
  @       %     Push latest k
          %   End (implicit)
          % End (implicit)
          % Display stack (implicit)

Alte Version, 16 Bytes

99:Qt"t_Zp]v&X<q

Probieren Sie es online!

Erläuterung

99:       % Push [1 2 ... 99]
Q         % Add 1 element-wise: gives [1 2 ... 100]
t"        % Duplicate. For each (i.e. do the following 100 times)
  t       %   Duplicate
  _Zp     %   Euler's totient function, element-wise
]         % End
v         % Concatenate vertically. Gives a 100×100 matrix
&X<       % Row index of the first minimizing entry for each column.
          % The minimum is guaranteed to be 1, because the number of
          % iterations is more than sufficient.
q         % Subtract 1. Display stack (implicit)

Jelly , 12 11 10 9 Bytes

³ḊÆṪÐĿ>1S

Probieren Sie es online!

-1 Byte dank HyperNeutrino!

-1 Byte Danke an Mr. Xcoder!

-1 Byte dank Dennis

Wie es funktioniert

³ḊÆṪÐĿ>1S - Main link. No arguments
³         - Yield 100
 Ḋ        - Dequeue. Creates the list [2, 3 ... 99, 100]
    ÐĿ    - For each element, while the results of the next function
          - aren't unique, collect the results...
  ÆṪ      -   Next function: Totient
      >1  - Greater than one?
        S - Sum the columns

Da dies von Dennis gemacht wurde, habe ich (verständlicherweise) keine Ahnung, warum dies funktioniert, nur dass es funktioniert.

APL (Dyalog) , 50 29 25 Bytes

Schau ma, kein eingebauter Totient!

4 Bytes gespart dank @ H.PWiz

{⍵=1:0⋄1+∇+/1=⍵∨⍳⍵}¨1+⍳99

Probieren Sie es online!

Wie?

Anscheinend habe ich mich zuerst für die längere (und schwierigere) Summenformel entschieden. Siehe Revisionsverlauf.

⍳⍵- 1bisn

⍵∨ - GCD mit n

1= - gleich 1?

+/ - Alles zusammen

Dies ist der Totient. Der Rest ist Wrapper für das Zählen ( 1+∇) und Anwenden auf den Bereich 2..100( ¨1+⍳99).

Mathematica, 44 Bytes

(i=-1;#+1//.x_:>EulerPhi[++i;x];i)&~Array~99

-10 Bytes von @Misha Lavrov
-2 Bytes von @ user202729

Probieren Sie es online!

J REPL, 23 Bytes

<:#@(5&p:^:a:)"0|2+i.99

Ich habe nicht überprüft, aber dies funktioniert wahrscheinlich in regulärem J, wenn Sie es als Nomen definieren (ich habe dies auf meinem Telefon auf dem REPL gespielt).

Eingebaute, yo.

Ich würde sagen, dass es mindestens 2-3 Bytes gibt, die abgeschnitten werden müssen (off-by-one aufgrund der Funktionsweise a:, der Verwendung |als Noop usw.).

JavaScript (ES6), 115 ... 104 99 Bytes

Hardcodierung mag kürzer sein, aber versuchen wir es mit einem rein mathematischen Ansatz.

f=n=>n>97?6:(P=(n,s=0)=>k--?P(n,s+(C=(a,b)=>b?C(b,a%b):a<2)(n,k)):s>1?1+P(k=s):1)(k=n+2)+' '+f(-~n)

console.log(f())

Python 2 , 80 Bytes

n,_=r=2,0;exec'r+=r[sum(k/n*k%n>n-2for k in range(n*n))]+1,;print r[n];n+=1;'*99

Probieren Sie es online!

Python 2 , 82 Bytes

l=0,1
exec"n=len(l);p=2\nwhile n%p:p+=1\nl+=l[p-1]+l[n/p]-n%4%3/2,;print l[n];"*99

Probieren Sie es online!

Dabei werden die folgenden Beobachtungen verwendet:

• f(a*b) = f(a) + f(b) - 1, außer das -1weggelassen wird wenn aund bbeide gerade sind
• f(p) = f(p-1) + 1wann pist prime, mitf(2)=1

Dies impliziert, dass, wenn nPrimfaktorisierung vorliegt n = 2**a * 3**b * 5**c * 7**d * 11**e * ..., f(n) = max(a,1) + b + 2*c + 2*d + 3*e + ...jeder p>2Faktor zur Faktorisierung beiträgtf(p-1) .

Ich bin nicht sicher, ob diese weiterhin Bestand haben n=100, aber wenn dies der Fall ist, können sie definiert und berechnet werden, fohne sie zu verwenden φ.

Bubblegum , 49 Bytes

00000000: 5d88 0511 0020 0003 ab2c 024e ff64 e8a3  ].... ...,.N.d..
00000010: 379f 956b f05d 206c 0545 7274 743a b876  7..k.] l.Ertt:.v
00000020: 2267 27f9 9f4d 9b9d fc85 e7e6 994d 6eb0  "g'..M.......Mn.
00000030: 2b                                       +

Probieren Sie es online!

PowerShell , 110 Byte

$a=,0*101;2..100|%{$i=$_;for($z=$j=0;++$j-lt$i;$z+=$k-eq1){for($k=$j;$j%$k-or$i%$k;$k--){}};($a[$i]=$a[$z]+1)}

Probieren Sie es online!

Mathematischer Ansatz.

Eigentlich durchschaut, sehr ähnlich der C-Antwort , aber unabhängig entwickelt. Erstellt ein Array von 0s, durchläuft Schleifen von 2bis 100und berechnet dann phianhand der gcdFormulierung. Der Teil in parens am Ende speichert das Ergebnis $afür den nächsten Durchlauf und platziert eine Kopie in der Pipeline, was zur impliziten Ausgabe führt.

PowerShell, 112 Byte

"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"-split'(.)'

Probieren Sie es online!

Fest codiert. Ho-hum. Kürzere als ich einen mathematischen Ansatz von etwa 10-15 Bytes bekommen könnte.

Python 2 , 83 Bytes

n=2
exec"print len(bin(n))-3+n%2-~n%9/8-(0x951a5fddc040419d4005<<19>>n&1);n+=1;"*99

Probieren Sie es online!

Kombiniert eine heuristische Schätzung mit einer fest codierten Konstante, die jede Schätzung als entweder -0oder korrigiert -1.

Schale , 10 17 Bytes

mö←LU¡Sȯṁε⌋ḣtḣ100

Probieren Sie es online!

Bearbeiten : +7 Byte für die tatsächliche Zuordnung der Funktion über den angeforderten Bereich, bevor nur die Funktion A003434 berechnet wurde .

Erläuterung

Folgendes berechnet A003434 :

←LU¡S(ṁ(ε⌋))ḣ -- takes a number as input, for example: 39
   ¡          -- iterate the following function on the input: [39,24,8,4,2,1,1,1..]
    S(     )ḣ --   with itself (x) and the range [1..x]..
      ṁ(  )   --   ..map and sum the following
        ε⌋    --     0 if gcd not 1 else 1
  U           -- longest unique prefix: [39,24,8,4,2,1]
 L            -- length: 6
←             -- decrement: 5

Das m(....)ḣ100Teil ordnet diese Funktion nur über den Bereich [2..100] zu, wobei ich nicht sicher bin, wie ich diesen Teil zuvor übersehen habe: S

PHP, 98 Bytes

1,2,<?=join(',',str_split(unpack('H*','##3444E4DEEDEEUUEEVEUVUVVFUVVUfVfVVVVVegWVgVffgV')[1]))?>,6

Probieren Sie es online!

Ich habe alle Ziffern in eine Binärzeichenfolge gepackt. Nachdem ich es ausgepackt, in ein Array konvertiert und dann das Array erneut zusammengefügt hatte, musste ich nur die 1,2 voranstellen und die 6 anhängen, da diese nicht passen würden oder einen Steuercode erscheinen ließen.

Perl 6 , 47 Bytes

map {($_,{+grep 1==* gcd $_,^$_}...1)-1},2..200

Probieren Sie es online!

05AB1E , 11 Bytes

тL¦ε[DNs#sÕ

Probieren Sie es online!

Erläuterung

тL¦           # push range [2 ... 100]
   ε          # apply to each
    [         # start a loop
     D        # duplicate the current number
      N       # push the loop iteration counter
       s      # swap one copy of the current number to the top of the stack
        #     # if true, break the loop
         s    # swap the second copy of the current number to the top of the stack
          Õ   # calculate eulers totient

C 112 Bytes

a[101];f(i,j,k,t){for(a[i=1]=0;i++<100;printf("%d ",a[i]=a[t]+1))for(t=j=0;++j<i;t+=k==1)for(k=j;j%k||i%k;k--);}

Ungolfed:

a[101];
f(i,j,k,t){
    for(a[1]=0,i=2;i<=100;i++) {   // initialize
        for(t=j=0;++j<i;t+=k==1)   // count gcd(i, j) == 1 (t = phi(i))
            for(k=j;j%k||i%k;k--); // calculate k = gcd(i, j)
        printf("%d ",a[i]=a[t]+1); // print and store results
    }
}

Probieren Sie es online!

Alumin , 87 Bytes

hhhhhdadtqdhcpkkmzyhqkhwzydqhhwdrdhhhwrysrshhwqdrybpkshehhhwrysrarhcpkksyhaydhehycpkkmr

Probieren Sie es online!

Erläuterung

hhhhhdadt      CONSTANT 100

RANGE FROM 100 to 0
q
  dhc
p

REMOVE 0 AND 1
kk

OVER EACH ELEMENT...
m
  zyh
  q
    kh
    wzyd
    q
      DUPLICATE TOP TWO ELEMENTS...
      hhwdrdhhhwrysrshhw
      GCD...
      qdryb
    p
    ks
    he
    hhhw
    ry
    s
    rarhc
  p
  IS IT ONE? IF SO TERMINATE (FIXPOINT)
  kksyhaydhehyc
p
kk
m
REVERSE THE VALUES
r

Pyth, 38 Bytes (nicht konkurrenzfähig)

.e-+1sl+1kb_jC"Éõ4ÕYHø\\uÊáÛ÷â¿"3

Probieren Sie es auf dem Pyth Herokuapp aus , da es auf TIO aus irgendeinem Grund nicht funktioniert.

Ich habe keinen Zweifel, dass die explizite Pyth-Lösung kleiner ist, aber ich wollte sehen, wie klein ich den Code durch Komprimieren der Sequenz bekommen und Pyth lernen kann, denke ich. Dies nutzt die Tatsache, dass eine Obergrenze der Sequenz ist log2(n)+1.

Erläuterung

.e-+1sl+1kb_jC"Éõ4ÕYHø\\uÊáÛ÷â¿"3
             C"Éõ4ÕYHø\\uÊáÛ÷â¿"   interpret string as base 256 integer
            j                   3  convert to array of base 3 digits
           _                       invert sequence (original had leading 0s)
.e                                 map with enumeration (k=index, b=element)
       +1k                                   k+1
     sl                            floor(log(   ))
   +1                                             +1
  -       b                                         -b

Ich habe die komprimierte Zeichenfolge über Ci_.e+1-sl+1ksb"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"3, die mit ein paar Typkonvertierungen genau das Gegenteil des obigen Codes ist.

Ohm v2 , 41 Bytes

“ ‽W3>€þΣÌιZ§Á HgüυH§u·β}Bā€ΣNπáÂUõÚ,3“8B

Probieren Sie es online!

Buchstäblich vollständig hartcodiert ... Ich habe die obige Sequenz tatsächlich genommen, alles, was keine Zahl war, entfernt, als Basis 8 interpretiert und dann in Ohms integrierte Basis 255-Zahlendarstellung umgewandelt. Das machen die Zitate. Dann verwandelt das Programm das einfach wieder in Basis 8.