Find a Fixed Point

Question

Given an integer \$x_1\$ and some black box function \$f: Z → Z\$ find a fixed point of \$f\$ in the sequence defined by \$x_{k+1} := f(x_k)\$.

Details

• A value \$x\$ is said to be a fixed point of \$f\$ if \$x = f(x)\$.

For instance if \$f(x) = \text{round}(\frac{x}{\pi})\$ and we have a starting point \$x_1 = 10\$ then we get \$x_2 = f(x_1) = f(10) = 3\$, then \$x_3 = f(x_2) = f(3) = 1\$, then \$x_4 = f(x_3) = f(1) = 0\$, and finally \$x_5 = f(x_4) = f(0) = 0\$ which means the submission should return \0ドル\$.

• You can assume that the generated sequence actually contains a fixed point.
• You can use the native type for integers in place of \$Z\$.
• 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

• phflack: 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
• flawr: @phflack The blackbox only has to converge for the given input.
• user202729: 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: Note 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.
• user58988: 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?

Answer 1

Actually, 1 byte

Y

Try it online!

Y is the fixed point function in Actually. In the TIO example, the function is shown being taken as a string, and £ is used to transform it to a function on the stack. It's also possible to just push the function to the stack like so. These are the only two ways to get a function input in Actually.

• Erik the Outgolfer: You just knew that some day this challenge was going to be posted, didn't you? :P
• user45941: @EriktheOutgolfer I've actually used Y for several challenges. I'm apparently extremely precognizant :P

Answer 2

APL (Dyalog), 2 bytes

⍣=

Try it online!

NB: I define O←⍣= in the the input section due to a bug in that derived monadic operators can't be defined in the way that TIO likes to define things.

⍣ Is an operator that can be used like (function⍣condition) ⍵

It applies the function, f, to ⍵ until (f ⍵) condition ⍵ returns true.

⍣= is a derived monadic operator that takes a monadic function, f, as its left argument and applies it to its right argument, ⍵, until f ⍵ = ⍵

• Adám: Maybe note that ⍣= is a derived monadic operator which takes a function as left operand and finds the fix point on the given initial value. I would use a different letter for ⍣= than f as it is an operator, not a function.
• Adám: Yeah. I would. It is confusing that you call the "input" function f in your description, but then on TIO, f is your solution operator. You can also move the O←⍣= up in the Code field to let it be counted and to point out that that is the actual solution, and that the rest (Input) is just testing it.
• Adám: Looks like a bug to me. I'll speak with relevant colleague tomorrow.
• H.PWiz: @Adám Updated. Let me know if the bug gets fixed

Answer 3

Haskell, 17 bytes

until=<<((==)=<<)

Try it online!

• Laikoni: In case someone is interested: here is an explanation why until=<<((==)=<<) finds a fix point of a given function.

Answer 4

MATLAB, 41 bytes

function x=g(f,x);while f(x)-x;x=f(x);end

There is also this beauty that does not need function files. Unfortunately it is a little bit longer:

i=@(p,c)c{2-p}();g=@(g,f,x)i(f(x)==x,{@()x,@()g(g,f,f(x))});q=@(f,x)g(g,f,x)

Try it online!

• flawr: This answer was meant as an example and does not prevent anyone from answering.
• Sanchises: Of course, if you called this Octave, you could remove two ;s. Try it online!.
• Sanchises: And in your anonymous function, you can remove the @() before x for 50 bytes. Kudos too for the way you wrap your helper function (with the g(g) in the end), I only managed to do 51 bytes @(g,x)(f=@(r,z){@()r(r,m),z}{(m=g(z)==z)+1}())(f,x). I'm wondering if there's any combination of both approaches that's shorter still.

Answer 5

Mathematica, 11 bytes

#2//.x_:>#&

Try it online!

Mathematica, 10 bytes

FixedPoint

Try it online!

Answer 6

Standard ML (MLton), 30 bytes

fun& $g=if$ =g$then$else&(g$)g

Try it online! Use as & n blackbox.

The black box functions are defined as following:

fun blackbox1 x = floor(Math.sqrt(Real.fromInt(abs x)))
fun blackbox2 x = c(c(c(x))) 
and c x = if x mod 2 = 0 then x div 2 else 3*x+1
fun blackbox3 _ = ~42
fun blackbox4 x = 2-x

Ungolfed version:

fun fixpoint n g = if n = g n then n else fixpoint (g n) g

• vijrox: Good to see SML in the wild! We use it for our functional programming class at our university.

Answer 7

R, (削除) 36 (削除ここまで) 35 bytes

thanks to JayCe for golfing down a byte

function(f,x){while(x-(x=f(x)))0;x}

Try it online!

Verify the example functions!

R port of flawr's solution.

• JayCe: For what it's worth... function(f,x){while(x-(x=f(x)))0;x} saves one byte.
• Giuseppe: Oh, 0, nice. Thanks much!

Answer 8

Python 2, (削除) 39 (削除ここまで) (削除) 37 (削除ここまで) 33 bytes

thanks to @Mr.Xcoder for -2 bytes

s=lambda k:s(f(k))if k-f(k)else k

Try it online!

assumes the black-box function to be named f

• mbomb007: Doesn't the function need to be passed as a parameter? I don't think pre-defined variables is an accepted input method.
• FlipTack: I'm not sure you're allowed to assume the function is f, isn't that a form of assuming input is in a variable? (edit: ninja'd by mbomb)
• ovs: @mbomb007 There is a consensus which allows it for black-box functions

Answer 9

JavaScript (Node.js), (削除) 25 (削除ここまで) (削除) 22 (削除ここまで) 21 bytes

thanks Herman Lauenstein for showing me this consensus
thanks to @l4m2 for -1 byte

Assumes the black-box function to be named f.

g=k=>f(k)-k?g(f(k)):k

Try it online!

• Endenite: This can be shortened if black-box functions to be taken as input can be assumed to be predefined under a given name
• l4m2: f(k)-k instead of

Answer 10

Jelly, 3 bytes

vÐL

Try it online!

Takes the left argument as a string representing a Jelly link (2_ for instance), and the right argument as an integer

How it works

 ÐL - While the output is unique...
v - Evaluate the function with the argument given

Answer 11

Brain-Flak, 24 bytes

(()){{}(({})<>[({})])}{}

Try it online!

(for the black box function x -> 2-x in the example below)

The provided black box function should be a program, that given x on the top of the stack, pop x and push f(x) - in other word, it should evaluate the function f on the value on the top of the stack.

Equivalent Mini-Flak is 26 bytes (thanks to Wheat Wizard for saving 2 bytes):

(()){{}(({})( )[{}({})])}{}
 ^ put the function f here

(not counting the comments and spaces)

Take the function (inside the <>) and a number x0 from input. (note that Brain-Flak is an esoteric language and can't take functional argument as input)

---

Example blackbox functions:

x -> 2-x: Try it online!

---

Explanation:

(()){{}(({})<f>[({})])}{} Main program.
 Implicit input from stdin to stack.
( ) Push
 () literal number 1.
 Now the content of the stack: [1, x0]
 { } While stack top ≠ 0:
 current stack content: [something ≠ 0, x]
 {} Pop stack top (something). stack = [x]
 ( ) Push
 ({}) Stack top = x. Current stack = [x]
 f Evaluate f. Current stack = [f(x)]
 < > (suppress the value of f(x), avoid adding it)
 [ ] plus the negative of
 ({}) the top of the stack ( = -f(x) )
 In conclusion, this change (x) on the stack to
 (f(x)), and then push (x + -f(x))
 If it's 0, break loop, else continue.
 {} Pop the redundant 0 on the top.
 Implicit output stack value to stdout.

Answer 12

Swift, (削除) 47 (削除ここまで) 42 bytes

func h(_ n:Int){f(n)==n ?print(n):h(f(n))}

Naive approach, assumes that the black box function is named f

• Mr. Xcoder: I am in doubt regarding your second attempt, because it is a complex closure and its type is ambiguous unless you explicitly cast it to {...}as(<parameter types>)-><return type>. If you don't specify its return type, it will throw build-time errors so I don't think it is valid as of now (note that the cast must be included in the byte count). Your first submission is fine, though.

Answer 13

C (gcc), 40 bytes

f(n,b)int(*b)(_);{n=n^b(n)?f(b(n),b):n;}

Try it online! Note that the flags are not necessary, they are there to aid with testing the fixpoint function defined above.

This is a function that takes an int n and a function pointer b : int → int. Abusing the fact that writing to the first variable argument sets the eax register, which is equivalent to returning^†. Otherwise, this is pretty standard as far as C golf goes. n^b(n) checks for the inequality of n and the black box applied to n. When unequal, it calls the fixpoint function f again recursively with the application and black box as arguments. Otherwise, it returns the fixpoint.

^{†Citation needed, I vaguely remember reading this somewhere and google seems to confirm my suspicions}

It declares input with K&R-style parameter typing:

f(n, b)
int(*b)(_);
{
 n=n^b(n)?f(b(n),b):n;
}

The arcane bit on the second line above declares b to be a function pointer that takes an integer parameter—the default type of _ is assumed to be an integer. Similarly, n is assumed to be an integer, and f is assumed to return an integer. Hooray for implicit typing?

Answer 14

Clean, 46 bytes

import StdEnv
p x=hd[n\\n<-iterate f x|f n==n]

Assumes the function is defined as f :: !Int -> Int

It takes the head of the infinite list of applications of f f f ... x filtered for those elements where f el == el.

Try it online!

If you want to change the function in the TIO, Clean's lambda syntax is:

\argument = expression

(actually it's far more complicated, but thankfully we only need unary functions)

Answer 15

APL (Dyalog Unicode), 14 bytes

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}

Try it online!

The function at the header is equivalent to f(x) = floor(sqrt(abs(x)))

Thanks @Adám for pointing out that the original answer wasn't valid according to PPCG consensus.

How it works:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} ⍝ Main 'function' (this is actually an operator)
 : ⍝ if
 ⍵=⍺⍺⍵ ⍝ the right argument (⍵) = the left function (⍺⍺, which is f) of ⍵
 ⍵ ⍝ return ⍵
 ⋄ ⍝ else
 ∇⍺⍺⍵ ⍝ return this function (∇) with argument f(⍵)

• user58988: {⍵=f⍵:⍵⋄∇(f⍵)} would be ok for separate anonymous function from its name (n)
• Adám: This assumes that f is preassigned, which I think is prohibited by PPCG consensus. {⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} would be a valid operator solution.

Answer 16

Octave, 37 bytes

function x=g(f,x);while x-(x=f(x))end

Try it online!

Octave has inline assignment but MATLAB doesn't, so this is a golfier Octave port of flawr's solution.

It also ports nicely to R.

Answer 17

Kotlin, 50 bytes

{f,k->var a=k;var b=a+1;while(b!=a){b=a;a=f(a)};a}

Try it online!

Answer 18

Forth (gforth), 36 bytes

This version just assumes f is predefined. It's not as cool as the solution below it. Both programs exit with a stack overflow if not found, or a stack underflow if found (after printing the result).

Try it online

: g dup f over = IF . THEN recurse ;

---

Forth (gforth), 52 bytes

This allows a function's execution token to be passed as a parameter, and is definitely the cooler solution.

: g 2dup execute rot over = IF . THEN swap recurse ;

Try it online

Explanation:

: g \ x1 f Define g. Params on the stack. f is on top
2dup execute \ x1 f x2 duplicate both params, execute f(x1)
rot over \ f x2 x1 x2 move x1 to top and copy x2 to top
= IF . THEN compare, if equal, print
swap recurse ; otherwise, recurse

Answer 19

Ruby, (削除) 31 (削除ここまで) 28 bytes

->x,f{x=f[x]until x==f[x];x}

Try it online!

• G B: 25 bytes - ->x,f{1while x!=x=f[x];x}

Answer 20

tinylisp repl, 28 bytes

(d P(q((x)(i(e(f x)x)x(P(f x

Assumes that the function f is predefined.

Try it online! (The example function is f(x) = (x*2) mod 10.)

Ungolfed

(load library)
(def P
 (lambda (x)
 (if (equal? (f x) x)
 x
 (P (f x)))))

If f(x) equals x, then x is a fixed point; return it. Otherwise, recursively look for a fixed point starting from f(x) instead of x.

Answer 21

APL NARS 65 chars

r←(f v)n;c
 c←0⋄→B
E: r←∞⋄→0
A: n←r
B: r←f n⋄c×ばつ⍳c>1e×ばつ⍳r≠n

v operator would return ∞ (or possibly -oo or Nan) for error, else one value x with x=f(x). In test f=floor(sqrt(abs(x))), f1=2-x, f2=c(c(c(x))) with c=x%2==0?x/2:3*x+1

 f←⌊∘√∘|
 f v 0
0
 f v 9
1
 f1←{2-⍵}
 f1 v 1
1
 f1 v ̄10
∞
 f1 v 2
∞
 c1←{0=×ばつ⍵}
 f2←c1∘c1∘c1
 f2 v 1
1
 f2 v 2
2
 f2 v 7
2
 f2 v 82
4

Answer 22

Clojure, (削除) 45 (削除ここまで) 43 bytes

Well, this is the shortest and ugliest:

#(loop[a + b %2](if(= a b)a(recur b(% b))))

+ is there instead of a number so that it is not equal to any value of x0.

55 bytes and functional:

#(reduce(fn[a b](if(= a b)(reduced a)b))(iterate % %2))

Example:

(def f #(...))
(defn collaz [x] (if (even? x) (-> x (/ 2)) (-> x (* 3) (+ 1))))
(f (->> collaz (repeat 3) (apply comp)) 125)
; 1

Answer 23

Java 8, 42 bytes

This takes a Function<Integer, Integer> or IntFunction<Integer> and an int or Integer (curried) and returns the fixed point.

f->i->{while(i!=(i=f.apply(i)));return i;}

Try It Online

Takes advantage of the fact that Java evaluates subexpressions from left to right (so the old i is compared to the new), a property which I was unaware of while writing this!

Answer 24

x86 opcode, 8 bytes

fun:
 call edx ; 2B
 cmpxchg eax, ecx ; 3B, on 8086 use xchg and cmp instead
 jnz fun ; 2B
 ret ; 1B

Take input: ecx (value x0), edx (function address, take input from ecx, write result to eax without modifying the value of ecx and edx)

8086 opcode, 7 bytes (but slow)

 xor cx, cx
 call dx
 loop $-2
 ret

If there exists a fixed point, looping 65536 times always drive it there.
Take input: ax (initial value x0), dx (function address, take input from ax, write output to ax without modifying the value of cx and dx).
Output the fixed point in register ax.

• user202729: It would certainly help if you make the answer more readable.
• l4m2: more edit to make it correct

Answer 25

J, 3 bytes

^:_

Try it online!

When a conjunction in J is missing an operand, it becomes an adjective. This program produces an adjective which takes as an argument a verb. ^: is the power or "repeat" verb, and the idiom f^:_, that is, f repeated infinitely, is J's limit application, which exactly solves this challenge:

An infinite power n produces the limit of the application of u .

Answer 26

dc, 30 bytes

[pq][Smrd3Rd3Rxd3R=mLmlmx]dsmx

Try it online!

Takes as input the function in the form of a macro and initial value on the stack(pushed in that order). Prints the fixed point.

Answer 27

Perl 5, 18 + 1 (-p)

$_=f$_ while$_^f$_

try it online

Answer 28

Vyxal, 1 byte

Ẋ

Try it Online!

Builtin lol

Answer 29

J-uby, 3 bytes

J-uby has a built-in operator for this:

:!~

Attempt This Online!

Answer 30

Japt, 14 bytes

gOvV
\W?U:ßW

Try it

Japt doesn't have any built-in "repeat until the output is constant" functionality, or the ability to take functions directly as input. This program takes x as the first input, and a string defining a Japt function as the second input.

Explanation:

/n # Store first input as U
/n # Store second input as V
gOvV
 OvV # Interpret V as Japt code
g # Apply that function to U
 # Store the result as W
\W # Check whether U and W are the same
 ?U # If they are, output U
 :ßW # Otherwise repeat the program with W and V as the inputs

A theoretical alternative would work if the function were assumed to already be stored in V, but there isn't really a good way to actually accomplish that in Japt so it's not really a reasonable input method.

• Shaggy: Consensus allows for black box functions to be assigned to pre-defined variables, allowing you to get rid of the eval. Add in a couple of tweaks and you can get this down to 10 bytes