Ok, last one:
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13) = 6. Notice that f(1) = 1. What is the next largest n such that f(n) = n?Again I failed to solve it with no help from my old good Pentium :( I came up with some sort of formula, which I believe is right, but the number seemed to be quite big, so... 5-lines of code solved it. Can anybody show how it can be deducted in mind?
PS. Oh, forgot to mention - the puzzles were taken from the GLAT.
Mr. Faron Michael Tkachenko's son is searching for him. I believe he's approximately 50 years old. He was living in Long Beach, CA and was married to Michelle Miller. If you have any information. Please contact me.
This might be easier for some to do this mentally to follow:
f(9) = 1
f(20) = 2*f(9) + 10 = 12 [(1 thru 9) x 2 + 10 (10 thru 19 on the 2nd digit)]
f(99) = 10*f(9) + 10 (counting first digit in 10 thru 19) = 20
f(200) = 2*f(99) + 100 = 140
f(999) = 10*f(99) + 100 = 300
f(2000) = 2*f(999) + 1000 = 1600
f(9999) = 10*f(999) + 1000 = 4000
f(20000) = 2*f(9999)+ 10000 = 18000
f(99999) = 10*f(9999) + 100000 = 50000
f(200000) = 2*f(99999) + 100000 = 200000
And more results. With the last result you have:
f(200000) = 200000
then f(199999) = 200000
If you down the value you have:
if 199991 f(n) = n + 1
the next lower number is:
f(199990) = 199990 (the number of ones is reduced in 2)
if 199981 f(n) = n (great)
and the next lower number is:
f(199980) = 199979 (the number of ones is reduced in 2)
AND THE SOLUTION IS..... 199981
Check the next solution:
f(200) -> 120 + 20
f(2000) -> 1300 + 300
f(20000) -> 14000 + 4000
f(200000) -> 150000 + 50000 (OK Solution)