Win a copy of Kotlin in Action this week in the Kotlin forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# all solutions for f(n) = n

Jerry Young
Ranch Hand
Posts: 77
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

Jim Yingst
Wanderer
Sheriff
Posts: 18671
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.

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

Jerry Young
Ranch Hand
Posts: 77
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 :-).

Jerry Young
Ranch Hand
Posts: 77
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.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
[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.

 It is sorta covered in the JavaRanch Style Guide.