Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$f(n)$ calculates how many times $2$ appears in numbers from $1$ to $n$. For example, $f(1)=0$, $f(2)=1$ and $f(12)=2$.

What is the first $n$ for which $f(n)=n$?

I would need first of all to figure out the function itself, if you can help me. And also the result, so I can compare after I solve the function myself.

Please help me with this one, I am stuck. I tried to do it through MS Excel, but the number is too large for what Excel can handle. Any help is highly appreciated.

Thanks!

p.s: thanks to Sidd, I now have an answer. However, if someone can also figure out the mathematical function for this, it would be very helpful.

share|improve this question
3  
Are you sure such an $n$ exists? –  enzotib Aug 20 '12 at 18:13
    
You said you used excel to try to do this...does this mean you only want the answer in the end? and the function won't matter? –  mathguy Aug 20 '12 at 18:26
    
Does this mean the digit $2$ in the decimal expansion? Or maybe how many times $2$ occurs as a prime factor? Or what? –  Michael Hardy Aug 20 '12 at 18:29
    
@Sidd: I used excel just to have an idea of the algorithm behind it. The function does matter, I just didn't know how to get to it. Tell me, how did you obtain the answer? –  Prayera Aug 20 '12 at 18:36
    
@Prayera look at my answer below. I know this isn't what you want, but I will try to see if I can find a function for it. –  mathguy Aug 20 '12 at 18:37
show 3 more comments

2 Answers

If you have a number like $6387$, then instead of doing $f(6387)$ you can do $f(6000) + f(300) + f(80) + f(7)$. For any $n$ in the form of $a*10^b$ where $a,b \in \mathbb{Z}$ ,

$f(n) = \begin{cases} ab*10^{b-1} + 10^b & \text{:$b\ge1, a\gt2$} \\ ab*10^{b-1} + (n \bmod 10^b) + 1 & \text{:$b\ge1, a=2$} \\ ab*10^{b-1} & \text{:$b\ge1, a=1$} \\ 1 & \text{:$b=0, a\ge2$} \\ 0 & \text{:$b=0, a\lt2$} \\ \end{cases}$

For an explanation on how that equation works, take the number $6000$. If you put a $2$ in the units place (_ _ _ 2), then for all $4$ digit numbers, $6$ numbers can occupy the first spot, $10$ the second, and $10$ the third. $6*10*10 = 600$. The $2$ can also be placed in the tens and hundreds place, so make that $600*3$. Now a $2$ can also be placed in the thousands place since 2 <= 6, but there can be 10 other digits everywhere else, so it would be $10*10*10$, leaving you with $1800+1000=2800$. (That is the basic logic behind what I did).

I do not know if you are looking for a function, or just an answer. But I know the answer is $28263827$.

import java.io.File;

import java.io.PrintWriter;

public class test {
    public static long count = 0;

    public static void main(String[] args) {
        long i = 1;
        find(i);
        while (i != count) {
            if(i%100000==0){
                System.out.println(i + ":" + count);
            }

            i++;
            find(i);
        }

        System.out.println(i);
    }

    public static void find(long s) {
        String s2 = Long.toString(s);
        char[] chars = s2.toCharArray();

        for (char c : chars) {
            if (c == '2')
                count++;
        }
    }
}
share|improve this answer
    
Thanks a lot, Sidd. I knew that this would be easy to do in a programming language. Too bad I don't know any anymore :) –  Prayera Aug 20 '12 at 18:41
    
@Prayera Just as a side note, I think there will be an infinite amount of answers. I realized another answer is 35000000 (exactly oddly enough) for instance. –  mathguy Aug 20 '12 at 19:03
2  
I think there will be a finite number of answers, because (see my answer below) we will eventually have the function greater than $kn$ for any $k$ and the proportion of numbers without a '2' in becomes as small as we like as $n$ increases. –  Mark Bennet Aug 20 '12 at 19:14
    
Hm I think I agree with you now. Point taken! –  mathguy Aug 20 '12 at 19:30
1  
However if any digit of the argument is a $2$, your decomposition will not work. For example, $f(23)=7$ (2, 12, 20, 21, 22, 23), but $f(20)+f(3)=3+1=4$. –  celtschk Aug 20 '12 at 20:33
show 11 more comments

In each block of 10 numbers there is one '2' in the units place. So counting the twos in the units place gives approx $\frac n {10}$.

In each block of 100 numbers, there are 10 '2's in the 10s place. So for sufficiently large $n$ there are approximately $\frac n {10}$ '2's in the tens place.

By the time you get to 10 places the value of the function is about $n$, and grows higher than this.

The '2's in each place come in blocks, and specifying the function accurately enough to get the precise answer for the first equality will take some care. But from here the process for doing so ought to be clear.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.