Jerry Young

Ranch Hand

Posts: 77

posted 12 years ago

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

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

Sheriff

Posts: 18671

posted 12 years ago

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.

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.

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.

"I'm not back." - Bill Harding, *Twister*

Jerry Young

Ranch Hand

Posts: 77

Jerry Young

Ranch Hand

Posts: 77

posted 12 years ago

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.

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

Sheriff

Posts: 18671

posted 12 years ago

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.

**[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 :-).

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.

"I'm not back." - Bill Harding, *Twister*

It is sorta covered in the JavaRanch Style Guide. |