13
1
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 – 2017-12-04T16:04:08.247
1
I've edited in the kolmogorov-complexity tag, as this is essentially outputting a fixed value
– caird coinheringaahing – 2017-12-04T16:10:23.293[tags:kolmogorov-complexity] is correct in this case, though it is (probably) much shorter to implement the function. If you ask the question backwards (given the values, write a program printing the values) there will probably be no-one figure that out. – user202729 – 2017-12-04T16:19:38.623
@user202729 Oh god, that sounds very complicated. Hm... – Simply Beautiful Art – 2017-12-04T16:20:56.937
Which "that" are you referring to? – user202729 – 2017-12-04T16:22:47.323
@user202729 The reverse engineering/question backwards. – Simply Beautiful Art – 2017-12-04T16:23:40.287
@user202729 You think nobody would look up the values in the OEIS first thing? – Misha Lavrov – 2017-12-04T16:29:25.327
Hm, if
f^-1(n)
returns the set of values such thatf(x) = n
, I wonder if this set is finite for alln
. – Simply Beautiful Art – 2017-12-04T16:30:36.543@MishaLavrov Ok, without OEIS lookup, it is hard. A3434.
– user202729 – 2017-12-04T16:31:05.6701@SimplyBeautifulArt First prove that there are finitely many values
x
such thatphi(x)
is a particular fixed number. – user202729 – 2017-12-04T16:31:46.8032This 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 – 2017-12-04T16:35:52.977@SimplyBeautifulArt According to Wikipedia, we have a lower bound on
– Misha Lavrov – 2017-12-04T16:37:26.353φ(n)
on the order ofn/log log n
, so there's only a finite range in which a particular value off
can be achieved.1: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 – 2017-12-04T16:37:30.073
Ah, nice find @MishaLavrov – Simply Beautiful Art – 2017-12-04T16:37:54.253
@SimplyBeautifulArt not really, my language of choice can handle the wrapper pretty easily. But it feels like an overhead (somewhat redisual). Anyway, good challenge – Uriel – 2017-12-04T16:43:36.430
Do we need to separate the numbers or is an output of
122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566
allowed? – ovs – 2017-12-04T18:21:40.750@ovs they need to be separated somehow. – Simply Beautiful Art – 2017-12-04T18:44:09.297