Powiązane: Iterowana funkcja phi (n) .

Twoim wyzwaniem jest obliczenie iterowanej funkcji phi:

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

Gdzie φjest funkcja totalna Eulera .

Powiązane OEIS .

Oto jego wykres:

Zasady:

Twoim celem jest wyjście f(n)z n=2celu n=100.

To jest golf golfowy, więc wygrywa najkrótszy kod.

Oto wartości, z którymi możesz sprawdzić:

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 bajty

Dzięki nim za uratowanie 1 bajtu!

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

Wypróbuj online!

sum[1|1<-gcd n<$>[1..n]]daje φ(n)(wzięte z wad , dzięki!)

fjest funkcją rekurencyjną, która oblicza, 1+φ(n)jeśli n nie jest 1, i zwraca, 0jeśli njest 1, ponieważ nie ma już więcej iteracji1

Na koniec f<$>[2..100]tworzy listę fzastosowanych do każdego elementu[2..100]

Haskell , 70 69 68 bajtów

Ta funkcja (\n->sum[1|1<-gcd n<$>[1..n]])jest funkcją totalną, którą wielokrotnie stosujemy w funkcji anonimowej. Dzięki @laikoni za -1 bajtów!

EDYCJA: Właśnie dowiedziałem się, że @xnor użył tej dokładnej funkcji totient w poprzednim wyzwaniu .

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

Wypróbuj online!

MATL , 16 15 bajtów

99:Q"@`_Zptq}x@

Wypróbuj online!

Wyjaśnienie

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)

Stara wersja, 16 bajtów

99:Qt"t_Zp]v&X<q

Wypróbuj online!

Wyjaśnienie

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)

Galaretka , 12 11 10 9 bajtów

³ḊÆṪÐĿ>1S

Wypróbuj online!

-1 bajt dzięki HyperNeutrino!

-1 bajt dzięki Mr. Xcoder!

-1 bajt dzięki Dennisowi

Jak to działa

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

Ponieważ zostało to zrobione przez Dennisa, (co zrozumiałe) nie mam pojęcia, dlaczego to działa, tylko że działa.

APL (Dyalog) , 50 29 25 bajtów

Spójrz, nie ma wbudowanego totemu!

4 bajty zapisane dzięki @ H.PWiz

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

Wypróbuj online!

W jaki sposób?

Najwyraźniej najpierw wybrałem dłuższą (i trudniejszą) formułę totemu. Zobacz historię zmian.

⍳⍵- 1don

⍵∨ - gcd z n

1= - równa 1?

+/ - podsumuj je wszystkie

To jest totient. Cała reszta to opakowanie do liczenia ( 1+∇) i zastosowania do zakresu 2..100( ¨1+⍳99).

Mathematica, 44 bajty

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

-10 bajtów od @Misha Lavrov
-2 bajty od @ user202729

Wypróbuj online!

J REPL, 23 bajty

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

Nie sprawdziłem, ale prawdopodobnie działa to w zwykłym J, jeśli zdefiniujesz to jako rzeczownik (grałem w golfa na moim telefonie na REPL).

Wbudowane, yo.

Powiedziałbym, że są co najmniej 2-3 bajty do zgolenia (off-by-one ze względu na sposób a:działania, konieczność używania |jako noop itp.).

JavaScript (ES6), 115 ... 104 99 bajtów

Kodowanie może być krótsze, ale spróbujmy podejścia czysto matematycznego.

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 bajtów

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

Wypróbuj online!

Python 2 , 82 bajty

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

Wypróbuj online!

Wykorzystuje się obserwacje, które:

• f(a*b) = f(a) + f(b) - 1, z wyjątkiem -1pominięcia, jeśli aib oba są parzyste
• f(p) = f(p-1) + 1kiedy pjest pierwsza, zf(2)=1

Sugerują one, że jeśli nma on faktoryzację pierwotną n = 2**a * 3**b * 5**c * 7**d * 11**e * ..., to wtedy f(n) = max(a,1) + b + 2*c + 2*d + 3*e + ..., gdzie bierze udział każda p>2z faktoryzacjif(p-1) .

Nie jestem pewien, czy nadal się trzymają przeszłości n=100, ale jeśli tak, dają sposób na zdefiniowanie i obliczenie fbez użycia φ.

Bubblegum , 49 bajtów

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                                       +

Wypróbuj online!

PowerShell , 110 bajtów

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

Wypróbuj online!

Podejście matematyczne.

Właściwie, przeglądając go, bardzo podobny do odpowiedzi C , ale rozwijał się niezależnie. Tworzy tablicę 0s, pętle od 2do 100, a następnie oblicza phiprzy użyciu gcdformuły. Część w parens na końcu zarówno zapisuje wynik do $anastępnej rundy, jak i umieszcza kopię w potoku, co daje wynik niejawny.

PowerShell, 112 bajtów

"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"-split'(.)'

Wypróbuj online!

Mocno zakodowane. Ho-hum. Krótszy niż mogłem uzyskać podejście matematyczne o około 10-15 bajtów.

Python 2 , 83 bajty

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

Wypróbuj online!

Kompleksy heurystyczny oszacowanie z sztywno stała, która koryguje każdy oszacowanie jak też -0i -1.

Łuska , 10 17 bajtów

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

Wypróbuj online!

Edycja : +7 bajtów do faktycznego odwzorowania funkcji na żądany zakres, zanim była to tylko funkcja obliczająca A003434 .

Wyjaśnienie

Następujące obliczenia 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

m(....)ḣ100Część tylko map tę funkcję w całym zakresie [2..100], nie wiem, jak brakowało mi tej części przed: S

PHP, 98 bajtów

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

Wypróbuj online!

Wszystkie cyfry spakowałem w ciąg binarny. Po rozpakowaniu, przekształceniu go w tablicę, a następnie ponownym scaleniu tablicy, musiałem tylko przygotować 1,2 i dołączyć 6, ponieważ nie pasowałyby lub spowodowały pojawienie się kodu sterującego.

Perl 6 , 47 bajtów

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

Wypróbuj online!

05AB1E , 11 bajtów

тL¦ε[DNs#sÕ

Wypróbuj online!

Wyjaśnienie

т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 bajtów

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

Nie golfowany:

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

Wypróbuj online!

Aluminium , 87 bajtów

hhhhhdadtqdhcpkkmzyhqkhwzydqhhwdrdhhhwrysrshhwqdrybpkshehhhwrysrarhcpkksyhaydhehycpkkmr

Wypróbuj online!

Wyjaśnienie

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 bajtów (niekonkurencyjny)

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

Wypróbuj na Pyth Herokuapp , ponieważ z jakiegokolwiek powodu nie działa on na TIO.

Nie mam wątpliwości, że jawne rozwiązanie Pyth jest mniejsze, ale chciałem zobaczyć, jak mały mógłbym uzyskać kod poprzez skompresowanie sekwencji i chyba nauczyć się Pyth. Wykorzystuje to fakt, że górna granica sekwencji jest log2(n)+1.

Wyjaśnienie

.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

Skompresowany ciąg otrzymałem przez Ci_.e+1-sl+1ksb"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"3, co jest przeciwieństwem powyższego kodu z kilkoma typami konwersji.

Ohm v2 , 41 bajtów

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

Wypróbuj online!

Dosłownie całkowicie zakodowany ... Właściwie wziąłem powyższą sekwencję, usunąłem wszystko, co nie było liczbą, zinterpretowałem ją jako podstawę 8, a następnie przekształciłem we wbudowaną reprezentację liczby 255 Ohma. Tak robią cytaty. Następnie program po prostu zamienia to ponownie w bazę 8.