# Find a Fixed Point

Given an integer $$\x_1\$$ and some black box function $$\f: ℤ → ℤ\$$ 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 $$\ℤ\$$.
• 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 Dec 8, 2017 at 20:03
• @phflack The blackbox only has to converge for the given input. Dec 8, 2017 at 20:09
• 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. Dec 9, 2017 at 4:44 • 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. Dec 9, 2017 at 4:46 • 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? – user58988 Dec 11, 2017 at 8:33 ## 32 Answers # 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. • You just knew that some day this challenge was going to be posted, didn't you? :P Dec 8, 2017 at 20:01 • @EriktheOutgolfer I've actually used Y for several challenges. I'm apparently extremely precognizant :P – user45941 Dec 8, 2017 at 20:08 # 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 ⍵ = ⍵ • 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 Dec 10, 2017 at 21:13 • 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 Dec 10, 2017 at 21:20 • Looks like a bug to me. I'll speak with relevant colleague tomorrow. – Adám Dec 10, 2017 at 21:56 • @Adám Updated. Let me know if the bug gets fixed Dec 12, 2017 at 18:35 ## Haskell, 17 bytes until=<<((==)=<<)  Try it online! • In case someone is interested: here is an explanation why until=<<((==)=<<) finds a fix point of a given function. Dec 9, 2017 at 10:12 # 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! • This answer was meant as an example and does not prevent anyone from answering. Dec 8, 2017 at 21:04 • Of course, if you called this Octave, you could remove two ;s. Try it online!. Dec 14, 2017 at 8:37 • 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. Dec 14, 2017 at 8:55 # Mathematica, 11 bytes #2//.x_:>#&  Try it online! # Mathematica, 10 bytes FixedPoint  Try it online! # 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

• Good to see SML in the wild! We use it for our functional programming class at our university. Dec 10, 2017 at 20:29

# 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.

• For what it's worth... function(f,x){while(x-(x=f(x)))0;x} saves one byte. Jul 12, 2018 at 16:55
• Oh, 0, nice. Thanks much! Jul 12, 2018 at 19:07

# Python 2, 3937 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

• Doesn't the function need to be passed as a parameter? I don't think pre-defined variables is an accepted input method. Dec 8, 2017 at 22:37
• 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) Dec 8, 2017 at 22:37
• @mbomb007 There is a consensus which allows it for black-box functions
– ovs
Dec 8, 2017 at 22:41

# JavaScript (Node.js), 2522 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!

# 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


# 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.


# 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

• 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. Dec 8, 2017 at 19:55

# 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?

# 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)

# 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(⍵)

• {⍵=f⍵:⍵⋄∇(f⍵)} would be ok for separate anonymous function from its name (n)
– user58988
Dec 9, 2017 at 10:22
• This assumes that f is preassigned, which I think is prohibited by PPCG consensus. {⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} would be a valid operator solution.
Dec 10, 2017 at 21:18

# 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.

# Kotlin, 50 bytes

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


Try it online!

# 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


# Ruby, 31 28 bytes

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


Try it online!

• 25 bytes - ->x,f{1while x!=x=f[x];x}
– G B
Dec 14, 2017 at 7:39

# 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.

# APL NARS 65 chars

r←(f v)n;c
c←0⋄→B
E: r←∞⋄→0
A: n←r
B: r←f n⋄c+←1⋄→E×⍳c>1e3⋄→A×⍳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=2∣⍵:⍵÷2⋄1+3×⍵}
f2←c1∘c1∘c1
f2 v 1
1
f2 v 2
2
f2 v 7
2
f2 v 82
4


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


# 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!

# 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. • It would certainly help if you make the answer more readable. Dec 14, 2017 at 7:04 • more edit to make it correct – l4m2 Dec 14, 2017 at 7:33 # 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 . # 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. # Perl 5, 18 + 1 (-p) $_=f$_ while$_^f\$_


try it online

# Vyxal, 1 byte

Ẋ


Try it Online!

Builtin lol

# J-uby, 3 bytes

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

:!~


Attempt This Online!

# 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.

• 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 Dec 2, 2022 at 11:52