Relacionado: Função phi (n) iterada .

Seu desafio é calcular a função phi iterada:

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

Onde φestá a função totiente de Euler .

OEIS relacionado .

Aqui está o gráfico:

Regras:

Seu objetivo é gerar saída f(n)de n=2para n=100.

Isso é código-golfe, então o código mais curto vence.

Aqui estão os valores que você pode 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

Obrigado nimi por economizar 1 byte!

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

Experimente online!

sum[1|1<-gcd n<$>[1..n]]dá φ(n)(Retirado de flawr , obrigado!)

fé uma função recursiva que calcula 1+φ(n)se n não é 1e gera 0se nfor 1, pois não há mais iterações a serem tomadas para alcançar1

Por fim, f<$>[2..100]cria uma lista de faplicada a cada elemento do[2..100]

Haskell , 70 69 68 bytes

A função (\n->sum[1|1<-gcd n<$>[1..n]])é a função totiente, que aplicamos repetidamente na função anônima. Obrigado @laikoni por -1 byte!

EDIT: Acabei de descobrir que o @xnor usou essa função exata em um desafio anterior .

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

Experimente online!

MATL , 16 15 bytes

99:Q"@`_Zptq}x@

Experimente online!

Explicação

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)

Versão antiga, 16 bytes

99:Qt"t_Zp]v&X<q

Experimente online!

Explicação

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)

Geléia , 12 11 10 9 bytes

³ḊÆṪÐĿ>1S

Experimente online!

-1 byte graças ao HyperNeutrino!

-1 byte graças ao Sr. Xcoder!

-1 byte graças a Dennis

Como 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 isso foi feito por Dennis, eu (compreensivelmente) não tenho idéia do por que isso funciona, apenas o faz.

APL (Dyalog) , 50 29 25 bytes

Olha, não, nenhum totiente embutido!

4 bytes salvos graças a @ H.PWiz

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

Experimente online!

Quão?

Aparentemente, eu fui primeiro à fórmula mais longa (e mais difícil). Veja o histórico de revisões.

⍳⍵- 1paran

⍵∨ - gcd com n

1= - igual a 1?

+/ - soma todos

Este é o totiente. Todo o resto é invólucro para a contagem ( 1+∇) e a aplicação no intervalo 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

Experimente online!

J REPL, 23 bytes

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

Eu não verifiquei, mas isso provavelmente funciona no J regular, se você o definir como substantivo (joguei isso no meu telefone no REPL).

Built-ins, você.

Eu diria que existem pelo menos 2 a 3 bytes para raspar (um a um por causa do modo como a:funciona, tendo que usar |como noop etc.).

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

A codificação embutida pode ser mais curta, mas vamos tentar uma abordagem puramente matemática.

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

Experimente 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

Experimente online!

Isso usa as observações de que:

• f(a*b) = f(a) + f(b) - 1, exceto que o -1é omitido se ae bambos são pares
• f(p) = f(p-1) + 1quando pé primo, comf(2)=1

Isso implica que, se nhouver fatoração primária n = 2**a * 3**b * 5**c * 7**d * 11**e * ..., então f(n) = max(a,1) + b + 2*c + 2*d + 3*e + ..., onde cada p>2fatoração contribuif(p-1) .

Não tenho certeza se eles continuam se mantendo n=100, mas se o fizerem, eles dão uma maneira de definir e calcular fsem usar φ.

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

Experimente online!

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

Experimente online!

Abordagem matemática.

Na verdade, olhando através dele, muito semelhante à resposta C , mas desenvolvido de forma independente. Cria uma matriz de 0s, passa de 2para 100e depois calcula phiusando a gcdformulação. A parte em parênteses no final salva o resultado na $apróxima rodada e coloca uma cópia no pipeline, o que resulta na saída implícita.

PowerShell, 112 bytes

"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"-split'(.)'

Experimente online!

Codificado. Ho-hum. Mais curto do que eu poderia obter uma abordagem matemática em cerca de 10 a 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

Experimente online!

Combina uma estimativa heurística com uma constante codificada que corrige cada estimativa como um -0ou outro -1.

Casca , 10 17 bytes

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

Experimente online!

Edit : +7 bytes para realmente mapear a função no intervalo solicitado, antes que fosse apenas a função que computa A003434 .

Explicação

O seguinte 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

A m(....)ḣ100peça apenas mapeia essa função no intervalo [2..100], sem saber como eu a perdi antes: S

PHP, 98 bytes

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

Experimente online!

Coloquei todos os dígitos em uma sequência binária. Depois de descompactá-lo, convertê-lo em uma matriz e depois mesclá-la novamente, só precisei preceder o 1,2 e anexar o 6, pois esses não se encaixariam ou causariam a exibição de um código de controle.

Perl 6 , 47 bytes

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

Experimente online!

05AB1E , 11 bytes

тL¦ε[DNs#sÕ

Experimente online!

Explicação

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

Experimente online!

Alumin , 87 bytes

hhhhhdadtqdhcpkkmzyhqkhwzydqhhwdrdhhhwrysrshhwqdrybpkshehhhwrysrarhcpkksyhaydhehycpkkmr

Experimente online!

Explicação

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

Pitão, 38 bytes (não competitivo)

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

Experimente no Pyth Herokuapp , porque não funciona no TIO por qualquer motivo.

Não tenho dúvida de que a solução explícita do Pyth é menor, mas eu queria ver o quão pequeno poderia obter o código compactando a sequência e aprender o Pyth, eu acho. Isso usa o fato de que um limite superior da sequência élog2(n)+1 .

Explicação

.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

Eu recebi a string compactada via Ci_.e+1-sl+1ksb"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"3, que é exatamente o oposto do código acima, com algumas conversões de tipo.

Ohm v2 , 41 bytes

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

Experimente online!

Literalmente completamente codificado ... Na verdade, peguei a sequência acima, retirei tudo o que não era um número, interpretei como base 8 e depois a transformei na representação de número 255 da base de Ohm. É isso que as citações fazem. Então, o programa simplesmente transforma isso na base 8 novamente.