4 ms·
One thing that has got me thinking in the past was another kind of formula,`f(f(x)) = g(x)`, where `g` is given. It bothered me that far from a general algorith
by ludamad 7y ago
One thing that has got me thinking in the past was another kind of formula,`f(f(x)) = g(x)`, where `g` is given. It bothered me that far from a general algorithm being known, individual cases were stumping (e.g., `f(f(x)) = e^x`). Any insights/references from HN folks about this?
- dan-robertson 7y agoProblems like these (typically restricted to integers/natural numbers) come up in competitions from time to time. Sometimes there are some tricks required that are very hard to find on the spot. Here is a related problem you may enjoy: Find all increasing functions f : N -> N such that f(f(x)) = 3x
- fyp 7y agoIs this problem correctly stated? Substituting in x=f(y) you get f(f(f(y))) = 3f(y) so f(3y) = 3f(y) This suggests a linear solution but then you get f(x)=sqrt(3)x which doesn't work since it's N -> N.
- Chinjut 7y agoSuggests is not demands. If we discard the requirement to be an increasing function, one recursively defined solution takes f(3x + 1) = 3x + 2, f(3x + 2) = 3 * (3x + 1), and f(3x) = 3f(x), with f(0) = 0. Or analogously for any way of splitting the positive integers not divisible by 3 into ordered pairs (a, b). Then define f(3^n a) = 3^n b and f(3^n b) = 3^(n + 1) a. This is the general form of the solutions.
- a1369209993 7y ago∅ assume f exists increasing requires that x < f(x) < f(f(x)) f(f(0)) = 3*0 = 0 ≮ 0 therefore f does not exist, qed
- AnimalMuppet 7y agof(x) = sqrt(3) * x. Then f(f(x)) = sqrt(3) * sqrt(3) * x = 3x. So there is at least one solution.
- a1369209993 7y agoThat's not increasing (√3 * 0 = 0 ≮ 0) and it's not on natural numbers (√3 * 1 = √3 (≈ 1.732) ∉ ℕ).
- JoshuaDavid 7y agoI think in this context "increasing" means f(x+ε)>f(x) for all x, not f(x) > x for all x.
- a1369209993 7y agoWhat is ε? The original problem is about natural numbers (ie nonnegative/unsigned integers).
- AnimalMuppet 7y agoWell then, f(x + 1) > f(x). I don't know where you're getting this x < f(x) as "increasing". The point about sqrt(3) not working for the naturals is a valid point, however.
- a1369209993 7y ago> Well then, f(x + 1) > f(x). I don't know where you're getting this x < f(x) as "increasing". Headdesk Yes, that's correct; I misparsed "increasing functions f" as "functions f that increase [the value passed through them]" and then got distracted by the discrete vs continuous confusion.
- AnimalMuppet 7y ago
- sgdpk 7y agoInteresting! The form of the solution can be written conveniently in base 3.
- sgdpk 7y agoI really like this answer on Quora [1], about the precise example you mention. The author is worth following for his insights, and the clear way he talks about math. [1] https://qr.ae/TaQ8y2 https://qr.ae/TaQ8y2
- BoppreH 7y agoI think you are looking for the functional square root operation: https://en.wikipedia.org/wiki/Functional_square_root https://en.wikipedia.org/wiki/Functional_square_root In mathematics, a functional square root (sometimes called a half iterate) is a square root of a function with respect to the operation of function composition. In other words, a functional square root of a function g is a function f satisfying f(f(x)) = g(x) for all x. For your example of f(f(x)) = e^x, that would be the https://en.wikipedia.org/wiki/Half-exponential_function https://en.wikipedia.org/wiki/Half-exponential_function with a=1 and b=e. Unfortunately there's no simple arithmetic representation of f(x).
- ludamad 7y agoThanks so much!
- paulddraper 7y agoOh wow, thanks!