24
Given an integer x1
and some black box function f: ℤ → ℤ
find a fixed point of f
in the sequence defined by xk+1 := f(xk)
.
Details
A value
x
is said to be a fixed point off
ifx = f(x)
.For instance if
f(x) := round(x/pi)
and we have a starting pointx1 = 10
then we getx2 = f(x1) = f(10) = 3
, thenx3 = f(x2) = f(3) = 1
, thenx4 = f(x3) = f(1) = 0
, and finallyx5 = f(x4) = f(0) = 0
which means the submission should return0
.- You can assume that the generated sequence actually contains a fixed point.
- You can use the native type for integers in place of
ℤ
. - You can use any language for which there are defaults for black box functions input in the standard IO meta post. If there are no such default for your language feel free to add one in the sense of the definition of black box functions, and make sure to link your proposals in that definition. Also don't forget to vote on them.
Examples
f(x) = floor(sqrt(abs(x)))
0 -> 0, all other numbers -> 1
f(x) = c(c(c(x))) where c(x) = x/2 if x is even; 3*x+1 otherwise
all positive numbers should result in 1,2 or 4 (Collatz conjecture)
f(x) = -42
all numbers -> -42
f(x) = 2 - x
1 -> 1
Note that while it's implied in the details that the black box function will converge on the fixed point, the last example says otherwise – phflack – 2017-12-08T20:03:59.167
1@phflack The blackbox only has to converge for the given input. – flawr – 2017-12-08T20:09:21.010
Oh, originally I thought that the submission is not given x_0, which caused me some confusion. I thought a solution should be (Jelly)
~Nƭ⁻Ç$¿
, which is something like, (pseudo code)for x in [0, -1, 1, -2, 2, -3, 3, -4, 4, ...]: if (x == f(x)): break; print(x);
. That may worth another challenge. – user202729 – 2017-12-09T04:44:55.7931Note for future visitors: Finding any fixed point doesn't work, you must find a fixed point reachable from x_0. It's guaranteed that there exists one. – user202729 – 2017-12-09T04:46:13.690
And if not exist a fixed point, for a function f, and one initial value x0... What should be the value it have to return? And if x0=0 and f=int(9/(x-1)) with for x1=x0+1 f(x1)=f(1) is already one error... What should return the operator for that f , x0? – RosLuP – 2017-12-11T08:33:52.957
@RosLuP Your program just has to work if there is such a fixed point (see second bullet point in the details) – flawr – 2017-12-11T10:36:08.097
What if the program just repeatedly apply <the number of values in the native integer data type> times the function
f
onx_0
? Is that abuse of native integer data type? – user202729 – 2017-12-14T07:05:56.610Yes, you can assume that the numbers required to compute the sequence are all in a reasonable range. – flawr – 2017-12-14T11:15:17.183