all solutions for f(n) = n

We can develop this function f to be of time log(n). Notice
that f(10^k - 1) = k * 10^(k-1). And starting from this we can develop a general log(n)-algorithm to get f(n) for any n.

For instance, we can get
f(99990001110003334) = 169987001107012079
in 0.01 second.

Using brutal force, it will take forever.

Here are all the n's such that f(n)=n (prove it!)...

f(0) = 0
f(1) = 1
f(199981) = 199981
f(199982) = 199982
f(199983) = 199983
f(199984) = 199984
f(199985) = 199985
f(199986) = 199986
f(199987) = 199987
f(199988) = 199988
f(199989) = 199989
f(199990) = 199990
f(200000) = 200000
f(200001) = 200001
f(1599981) = 1599981
f(1599982) = 1599982
f(1599983) = 1599983
f(1599984) = 1599984
f(1599985) = 1599985
f(1599986) = 1599986
f(1599987) = 1599987
f(1599988) = 1599988
f(1599989) = 1599989
f(1599990) = 1599990
f(2600000) = 2600000
f(2600001) = 2600001
f(13199998) = 13199998
f(35000000) = 35000000
f(35000001) = 35000001
f(35199981) = 35199981
f(35199982) = 35199982
f(35199983) = 35199983
f(35199984) = 35199984
f(35199985) = 35199985
f(35199986) = 35199986
f(35199987) = 35199987
f(35199988) = 35199988
f(35199989) = 35199989
f(35199990) = 35199990
f(35200000) = 35200000
f(35200001) = 35200001
f(117463825) = 117463825
f(500000000) = 500000000
f(500000001) = 500000001
f(500199981) = 500199981
f(500199982) = 500199982
f(500199983) = 500199983
f(500199984) = 500199984
f(500199985) = 500199985
f(500199986) = 500199986
f(500199987) = 500199987
f(500199988) = 500199988
f(500199989) = 500199989
f(500199990) = 500199990
f(500200000) = 500200000
f(500200001) = 500200001
f(501599981) = 501599981
f(501599982) = 501599982
f(501599983) = 501599983
f(501599984) = 501599984
f(501599985) = 501599985
f(501599986) = 501599986
f(501599987) = 501599987
f(501599988) = 501599988
f(501599989) = 501599989
f(501599990) = 501599990
f(502600000) = 502600000
f(502600001) = 502600001
f(513199998) = 513199998
f(535000000) = 535000000
f(535000001) = 535000001
f(535199981) = 535199981
f(535199982) = 535199982
f(535199983) = 535199983
f(535199984) = 535199984
f(535199985) = 535199985
f(535199986) = 535199986
f(535199987) = 535199987
f(535199988) = 535199988
f(535199989) = 535199989
f(535199990) = 535199990
f(535200000) = 535200000
f(535200001) = 535200001
f(1111111110) = 1111111110

Um, for anyone wondering what the heck this is about, it's evidently a continuation from this thread.

I got the same results as you.

[JC]: Using brutal force, it will take forever.

Not really. Calculating n values for f(n) by "brute force" takes n*log(n) (if done correctly). Which is basically the same as you get, right? I ran it in a few hours, and successfully checked all the f(n) values up to n=10000000000. Proof of why that's sufficient is omitted as an excercise for the reader.

It does pay to be the 2nd mouse.
[ November 15, 2004: Message edited by: Glen Tanner ]

Jim,

What I meant is, to calculate:

f(99990001110003334) = 169987001107012079

using brutal force, it will take virtually forever. Try it if you have any doubt :-).

Jim,

I was discussing f(n) itself... a log(n) algorithm for f(n), of course, should not be a recursive one (which has to calculate f(n-1) to get f(n)).

So in this case, the trick is to get f(n) without knowing f(n-1).

This algorithm itself does not by its own tell anything about f(n)=n.
A careful search is needed to get all the n's such that f(n)=n.

First, determine the upper bound. This is easy...

Second, deterimine the seed numbers... those n's between 10*k and 2*10^k, k = 0,1,2,3,4,5,6,7,8,10 (10 is good enough, if we have done first step correctly)... such than f(n) = n. This is easy as well if we notice that f(n) is non-descreasing in these periods and so we can do binary search instead of brutal search...

Then, based on the seeds, perform some other searchs based on f(a+b)=f(a)+f(b) for certain types of a and b.

In 3 or 4 rounds of such search we can pick up all the n's very quickly, namely, in a few seconds.

[Jimmy]: What I meant is, to calculate:

f(99990001110003334) = 169987001107012079

using brutal force, it will take virtually forever. Try it if you have any doubt :-).

No, I agree. I had overlooked that you meant that this particular calculation would take forever. I agree with your other statements. I didn't bother developing f(n) itself (i.e. without knowing f(n-1)) because I developed the cumulative solution early on, hit "run", and went to a party. When I came back a few hours later it was done, and I'd already proven to myself that there would be no other solutions above the near miss at f(9999999999) = 10000000000. So the problem as I saw it was solved. If you also want an optimal strategy for finding f(n) for arbitrary n (not just where f(n) = n), then yes, the approach you outline is the way to go. Good job.