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!)...

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 ]

Jerry Young
Ranch Hand

Joined: Jun 15, 2004
Posts: 77

posted

0

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

Joined: Jun 15, 2004
Posts: 77

posted

0

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

Joined: Jan 30, 2000
Posts: 18671

posted

0

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