# Iterated phi sequence

Related: Iterated phi(n) function.

Your challenge is to compute the iterated phi function:

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


Where φ is Euler's totient function.

Related OEIS.

Here's the graph of it:

### Rules:

Your goal is to output f(n) from n=2 to n=100.

This is code-golf, so shortest code wins.

Here's the values you can check against:

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

• @LuisMendo Fixed, and also added graph + values to check against. :-) – Simply Beautiful Art Dec 4 '17 at 16:04
• I've edited in the kolmogorov-complexity tag, as this is essentially outputting a fixed value – caird coinheringaahing Dec 4 '17 at 16:10
• @SimplyBeautifulArt First prove that there are finitely many values x such that phi(x) is a particular fixed number. – user202729 Dec 4 '17 at 16:31
• This is a nice challenge, but I think it would be better to just ask for a solution to implement f(n), rather than run it on a range of fixed numbers. This also makes a difference between languages with ability to apply functions on ranges with less bytes (partly chameleon challenge?) – Uriel Dec 4 '17 at 16:35
• :P Are you implying I should change the challenge to give you an advantage? Regardless of how these rules are stated, some languages will have an advantage and some won't. @Uriel – Simply Beautiful Art Dec 4 '17 at 16:37

Thanks nimi for saving 1 byte!

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


Try it online!

sum[1|1<-gcd n<$>[1..n]] gives φ(n) (Taken from flawr, thanks!) f is a recursive function that calculates 1+φ(n) if n is not 1, and outputs 0 if n is 1, as there are no more iterations to be taken to reach 1 Finally f<$>[2..100] creates a list of f applied to each element of [2..100]

# Haskell, 70 69 68 bytes

### PowerShell, 112 bytes

"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"-split'(.)'


Try it online!

Hard-coded. Ho-hum. Shorter than I could get a mathematical approach by about 10-15 bytes.

• I wonder whether you actually need a separator, as all the numbers are single digits:) – flawr Dec 4 '17 at 17:02
• Can you show us your mathematical approach? It looks much more interesting certainly :P – Conor O'Brien Dec 5 '17 at 15:18
• @ConorO'Brien Luckily enough, I was able to look at it with fresh eyes this morning and golf the mathematical approach below the hard-coded approach. – AdmBorkBork Dec 5 '17 at 16:11

# Python 2, 83 bytes

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


Try it online!

Combines a heuristic estimate with a hardcoded constant that corrects each estimate as either -0 or -1.

# Husk, 10 17 bytes

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


Try it online!

Edit: +7 bytes for actually mapping the function over the range that was asked for, before it was only the function computing A003434.

### Explanation

The following computes 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


The m(....)ḣ100 part just map that function over the range [2..100], not sure how I missed that part before :S

# PHP, 98 bytes

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


Try it online!

I packed all digits into a binary string. After unpacking it, converting it to a an array and then mergin the array again, i only had to prepend the 1,2 and append the 6 as those wouldnt fit or caused a control code to appear.

# Perl 6, 47 bytes

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


Try it online!

# 05AB1E, 11 bytes

тL¦ε[DNs#sÕ


Try it online!

Explanation

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


Try it online!

# Alumin, 87 bytes

hhhhhdadtqdhcpkkmzyhqkhwzydqhhwdrdhhhwrysrshhwqdrybpkshehhhwrysrarhcpkksyhaydhehycpkkmr


Try it online!

## Explanation

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 (not competitive)

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


Try it on the Pyth Herokuapp, because it doesn't work on TIO for whatever reason.

I have no doubt the explicit Pyth solution is smaller, but I wanted to see how small I could get the code by compressing the sequence, and learn Pyth I guess. This uses the fact that an upper bound of the sequence is log2(n)+1.

## Explanation

.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
.e                                 map with enumeration (k=index, b=element)
+1k                                   k+1
sl                            floor(log(   ))
+1                                             +1
-       b                                         -b


I got the compressed string via Ci_.e+1-sl+1ksb"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"3, which is just the opposite of the code above with a few type conversions.

• Why noncompeting? – Simply Beautiful Art Dec 5 '17 at 18:18
• @SimplyBeautifulArt didn't really mean noncompeting in the formal sense; edited the title to make that more clear – stellatedHexahedron Dec 5 '17 at 18:34

# Ohm v2, 41 bytes

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


Try it online!

Literally completely hardcoded... I actually took the sequence above, stripped everything that wasn't a number, interpreted it as base 8, then turned it into Ohm's built-in base 255 number representation. That's what the quotes do. Then, the program simply turns that into base 8 again.