Relacionado: Función phi (n) iterada .

Su desafío es calcular la función phi iterada:

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

Dónde φ está la función totient de Euler ?

Relacionado OEIS .

Aquí está el gráfico de la misma:

Reglas:

Su objetivo es salir f(n)den=2 a n=100.

Este es el código de golf, por lo que gana el código más corto.

Aquí están los valores con los que puede verificar:

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

Gracias nimi por guardar 1 byte!

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

Pruébalo en línea!

sum[1|1<-gcd n<$>[1..n]]da φ(n)(tomado de flawr , ¡gracias!)

fes una función recursiva que calcula 1+φ(n)si n no es 1, y genera 0si nes1 , ya que no hay más iteraciones para alcanzar1

Finalmente f<$>[2..100]crea una lista de faplicados a cada elemento de[2..100]

Haskell , 70 69 68 bytes

La función (\n->sum[1|1<-gcd n<$>[1..n]]) es la función totient, que aplicamos repetidamente en la función anónima. Gracias @laikoni por -1 byte!

EDITAR: Acabo de descubrir que @xnor usó esta función totient exacta en un desafío anterior .

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

Pruébalo en línea!

MATL , 16 15 bytes

99:Q"@`_Zptq}x@

Pruébalo en línea!

Explicación

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)

Versión anterior, 16 bytes

99:Qt"t_Zp]v&X<q

Pruébalo en línea!

Explicación

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)

Jalea , 12 11 10 9 bytes

³ḊÆṪÐĿ>1S

Pruébalo en línea!

-1 byte gracias a HyperNeutrino!

-1 byte gracias al Sr. Xcoder!

-1 byte gracias a Dennis

Cómo funciona

³ḊÆṪÐĿ>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

Como esto fue hecho por Dennis, yo (comprensiblemente) no tengo idea de por qué esto funciona, solo que lo hace.

APL (Dyalog) , 50 29 25 bytes

¡Mira, no hay un paciente incorporado!

4 bytes guardados gracias a @ H.PWiz

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

Pruébalo en línea!

¿Cómo?

Aparentemente fui por la fórmula totient más larga (y más difícil) primero. Ver historial de revisiones.

⍳⍵- 1an

⍵∨ - mcd con n

1= - igual a 1?

+/ - suma todos

Este es el totient. Todo lo demás es envoltorio para contar ( 1+∇) y aplicar en el rango 2..100( ¨1+⍳99).

Mathematica, 44 bytes

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

-10 bytes de @Misha Lavrov
-2 bytes de @ user202729

Pruébalo en línea!

J REPL, 23 bytes

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

No lo he comprobado, pero esto probablemente funciona en J normal si lo define como un sustantivo (jugué golf en mi teléfono en el REPL).

Empotrados, yo.

Yo diría que hay al menos 2-3 bytes para eliminar (off-by-one debido a la forma en que a:funciona, tener que usar |como noop, etc.).

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

La codificación rígida puede ser más corta, pero intentemos un enfoque puramente matemático.

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

Pruébalo en línea!

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

Pruébalo en línea!

Esto utiliza las observaciones que:

• f(a*b) = f(a) + f(b) - 1, excepto que -1se omite si ay bson ambos pares
• f(p) = f(p-1) + 1cuando pes primo, conf(2)=1

Esto implica que si ntiene factorización prima n = 2**a * 3**b * 5**c * 7**d * 11**e * ..., entonces f(n) = max(a,1) + b + 2*c + 2*d + 3*e + ..., donde cada uno p>2en la factorización contribuyef(p-1) .

No estoy seguro de si estos continúan reteniendo el pasado n=100, pero si lo hacen, dan una forma de definir y calcular fsin usar φ.

Chicle , 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                                       +

Pruébalo en línea!

PowerShell , 110 bytes

$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)}

Pruébalo en línea!

Enfoque matemático.

En realidad, al mirarlo, es muy similar a la respuesta C , pero se desarrolló de forma independiente. Crea una matriz de 0s, bucles desde 2hasta 100, luego calcula phiutilizandogcd formulación. La parte en parens al final guarda el resultado en $ala siguiente ronda y coloca una copia en la tubería, lo que resulta en la salida implícita.

PowerShell, 112 bytes

"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"-split'(.)'

Pruébalo en línea!

Codificado duro. Ho-hum Más corto de lo que podría obtener un enfoque matemático de aproximadamente 10-15 bytes.

Python 2 , 83 bytes

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

Pruébalo en línea!

Combina una estimación heurística con una constante codificada que corrige cada estimación como -0o -1.

Casco , 10 17 bytes

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

Pruébalo en línea!

Editar : +7 bytes para mapear realmente la función en el rango que se solicitó, antes de que fuera solo la función que computaba A003434 .

Explicación

Lo siguiente calcula 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

La m(....)ḣ100parte solo asigna esa función en el rango [2..100], no estoy seguro de cómo me perdí esa parte antes: S

PHP, 98 bytes

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

Pruébalo en línea!

Empaqué todos los dígitos en una cadena binaria. Después de desempacarlo, convertirlo en una matriz y luego fusionar la matriz nuevamente, solo tuve que anteponer el 1,2 y agregar el 6 ya que no encajarían o provocarían que apareciera un código de control.

Perl 6 , 47 bytes

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

Pruébalo en línea!

05AB1E , 11 bytes

тL¦ε[DNs#sÕ

Pruébalo en línea!

Explicación

т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--);}

Sin golf:

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
    }
}

Pruébalo en línea!

Aluminio , 87 bytes

hhhhhdadtqdhcpkkmzyhqkhwzydqhhwdrdhhhwrysrshhwqdrybpkshehhhwrysrarhcpkksyhaydhehycpkkmr

Pruébalo en línea!

Explicación

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 (no competitivo)

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

Pruébelo en Pyth Herokuapp , porque no funciona en TIO por el motivo que sea.

No tengo dudas de que la solución explícita de Pyth es más pequeña, pero quería ver qué tan pequeño podría obtener el código al comprimir la secuencia y aprender Pyth, supongo. Esto utiliza el hecho de que un límite superior de la secuencia eslog2(n)+1 .

Explicación

.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

Obtuve la cadena comprimida a través Ci_.e+1-sl+1ksb"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"3, que es justo lo contrario del código anterior con algunas conversiones de tipo.

Ohm v2 , 41 bytes

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

Pruébalo en línea!

Literalmente completamente codificado ... De hecho, tomé la secuencia anterior, eliminé todo lo que no era un número, lo interpreté como base 8, luego lo convertí en la representación de número 255 de Ohm incorporada. Eso es lo que hacen las citas. Luego, el programa simplemente convierte eso en base 8 nuevamente.