[Easy] Solving a Small Equation

[u/07734willy]

This problem is a codegolf problem. That means the objective isn't to just solve the problem, but to do so with the smallest program size. Everything from comments, spaces, tabs, and newlines counts against you.

Background

While there certainly are some complex mathematical equations that are too difficult to solve, most of the ones using the basic mathematical operations (addition, multiplication, exponentiation...) are usually fairly easy. Especially when they they only have one variable, and one operator. However, one particularly difficult equation stands out:

x^x = k

Where ^ denotes exponentiation, and k is some constant we choose. This may look trivial to solve, and its worth taking a stab at it to convince yourself there isn't a simple way to approach this, apart from approximation.

Your task is to write a program to solve for x, to 5 decimal digits of precision, for a provided constant k.

Input

A single number- the k in x^x = k. Example:

743

Output

A number, for which the x in x^x = k is accurate to 5 decimal places. For the above input, we would have:

4.43686

Testcases

=========
743

4.43686
=========
97

3.58392
=========
256

4.0
=========
947

4.53387
=========
15

2.71316
=========
78974

6.18749
=========
11592.347

5.49334
=========

Character Count

Use the following command to measure the size of the program, in bytes and characters:

wc -mc filename.txt

[u/engiwengi]

Rust: 62

First codegolf ever, almost certain this could be shortened using recursion somehow to remove the for loop.

|k:f64|{let mut x=1.;for _ in 0..9{x=(x+k.ln())/(1.+x.ln())}x}

[u/07734willy → u/engiwengi]

I like this approach. I thought the only practical way (for code golf) would be to brute force it. Figured a smarter approach would require too much math to be compact, but looks like I was wrong.

At first I didn't realize how you got your approximation formula, but then I realized its newtons method of approximation. For anyone else who might be curious:

x^x=k  =>  xln(x) = ln(k) => xln(x) - ln(k) = 0

Using newtons root finding algorithm-
x_(n+1) = x_n - f(x_n)/(d/dx(f(x_n)))
and
d/dx (xln(x) - ln(k)) =  1 + ln(x)

x_(n+1) = x_n - (x_n*ln(x_n) - ln(k)) / (1 + ln(x_n)) 
= (x_n + x_n * ln(x_n) - x_n * ln(x_n) + ln(k))/(1+ ln(x_n))
= (x_n + ln(k)) / (1 + ln(x_n))

[u/engiwengi → u/07734willy]

A little prettier.

Pretty sweet visualisation of how this method works from wikipedia. I start with an arbitrary guess of 1 and assume that it will converge fast enough in 10 iterations. I think for really huge numbers it might not get to 5 decimal places quick enough but not certain.

[u/NemPlayer → u/07734willy]

Thanks! That's a really nice solution, didn't know about Newtons root finding algorithm. I like it.

[u/engiwengi → u/engiwengi]

Runnable code for those interested:

fn main() {
    let f = 

    |k:f64|{let mut x=1.;for _ in 0..9{x=(x+k.ln())/(1.+x.ln())}x}
    
    ;
    println!("{:.5}", f(78974.))
}

[u/engiwengi]

I've never tried a code golf before. I'm learning rust at the moment so would like to use that (even though I imagine it's an awful language for golfing). Does the input/output need to be through stdin/stdout or can i just write a function that takes and returns it? eg. fn f(k:f64)->f64{}

[u/07734willy → u/engiwengi]

Most problems I have solved personally have required stdin/stdout usage, but I've never actually considered otherwise. I'm going to look around to see what the general consensus in on other sites, and see if allowing function arguments+return value would be appropriate.

Two reasons I appose it as of right now:

1. To run it, one must know the language well enough to write the rest of the program to execute tests, instead of calling it from terminal as is.

2. I plan to add validation scripts to all these challenges, so that you guys can just call python validator <your program> and have it spit out [PASS]'s [FAIL]'s

---

I'll update this comment once I've reviewed those other sites (probably about 10 minutes).

Edit: they are all allowed- functions, full programs, code blocks, etc. The only argument against it is automatic execution, which really isn't as big of a deal here, since we aren't hosting leaderboards.

[u/engiwengi → u/07734willy]

Fair enough. Looking on Programming Puzzles & Code Golf on stackexchange I've found examples where it seems to me the code is just a function or closure that takes the input as an argument and returns the output, even removing essential parts of code such as fn main() { and println!() noting it as header and footer, not counted. This subreddit doesn't need to use the same rules.

[u/NemPlayer]

Python 3.7.0

62 61

  k=input();x=0
  while x**x<float(k):x+=9**-7
  print(round(x,5))

There are two incorrect testcases:

97

3.58292 (it should be 3.58392)
=========
245

4.0 (it should be 3.98158)

[u/07734willy → u/NemPlayer]

Both typos- thank you for pointing that out.

I verified each solution through wolframalpha in case my solver was rounding incorrectly, but WA was giving me issues with copy/pasting so I just typed them by hand.

[u/07734willy]

Python 3: 81 81

I feel like there might be a way to shorten this, using

exec("statements"*largeNumber)

however, I can't get it to work because of the loop within. So for now, this is my solution:

n=float(input())
v=0
for i in 1,1e-6:
 while v**v<n:v+=i
 v-=i
print(round(v,5))

[u/NemPlayer → u/07734willy]

That's not a correct solution. If k (in your case n) is a decimal number, it wouldn't work.

There is also no need for v-=i and the for-loop. It will work without it you'll just need a smaller increment like 9**-7. It will be a bit slower, but I feel like 1-2 second faster solution isn't better than a ~20 character less solution for CodeGolf.

[u/07734willy → u/NemPlayer]

You're right- I just now updated it to support floats.

When I remove the loop and use 1e-7 increments, it takes about 13 seconds to compute the answer. I'm feel like this is pushing into a grey area- how long is too long for a solution. I might check against the code golf stackexchange, and see what their policy is- and adopt that. Also, for completeness, 60 bytes:

n=float(input())
v=0
while v**v<n:v+=1e-7
print(round(v,5))

[u/07734willy → u/NemPlayer]

So I've done some research, and the automated scoring systems tend to allow anywhere from a few seconds to 10 seconds. The stackexchange doesn't have any limits as far as I can see. So- I'll again side with the stackexchange. As long as the program terminates in some finite amount of time, and has done so for the testcases previously, it is valid.

[u/Bubbler-4]

J: 5 5

^~inv

x^y calculates the thing you'd expect, ^~ x calculates x^x, and inv converts the function into its inverse. Somewhat feels like cheating, but J just works like that.

Run example

It's insanely fast, and it even automatically maps over an array.

^~inv 743 97 256 947 15 78974 11592.347
4.43686 3.58392 4 4.53387 2.71316 6.18749 5.49334

[u/[deleted]]

C

I'd love to get rid of math.h but have no idea how to

#include<stdio.h>
#include<math.h>
void main(){float k,x=0;scanf("%a",&k);while(pow(x,x)<k)x+=0.000001;printf("%.5f",x);}