6
$\begingroup$

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

  • 3
    Are you sure such an $n$ exists?2012-08-20
  • 0
    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?2012-08-20
  • 0
    Does this mean the digit $2$ in the decimal expansion? Or maybe how many times $2$ occurs as a prime factor? Or what?2012-08-20
  • 0
    @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?2012-08-20
  • 0
    @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.2012-08-20
  • 0
    @Sidd Ah, I misinterpreted the question. Apologies.2012-08-20
  • 0
    See http://oeis.org/A1016392012-08-20
  • 0
    Also https://oeis.org/A0947982012-08-21

2 Answers 2

4

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++;
        }
    }
}
  • 0
    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 :)2012-08-20
  • 0
    @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.2012-08-20
  • 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.2012-08-20
  • 0
    Hm I think I agree with you now. Point taken!2012-08-20
  • 0
    @Prayera Please let me know if the formula I have provided is sufficient, or if you want a more compact formula.2012-08-20
  • 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$.2012-08-20
  • 0
    There are some errors in your calculations with my formulas, but nevertheless you are still right. I will try to fix that2012-08-21
  • 0
    @celtschk do you have any ideas on how to fix that?2012-08-21
  • 0
    Thanks, Sidd, this is a starting point. I will try to work from there too, see where it takes me. I get your logic, we just need to get to the final correct formula2012-08-21
  • 0
    Where's the error in my use of your formulas? $f(n)$ is defined not by you, but by the original poster, to be the number of $2$s in the numbers up to $n$. That's how I determined the values of $f(27)$, $f(20)$ and $f(7)$. The only formula from you I've used is the "sum rule". Now, formally you've only claimed it for the number $6387$ but from context it is clear that you meant it to apply to all numbers, as you didn't claim a restriction, and having a rule for just one number would be meaningless. Therefore I used the rule to get $f(27)=f(20)+f(7)$ which I disproved with the values above.2012-08-21
  • 0
    About how to fix it: The sum rule for $f(a\cdot10^b+c)$ with $0\le a\le 9$ and $c\le 10^b$ needs to be adjusted for $a>1$. Especially you need to special case $a=2$. I think the following change of your rule should work: First, do the decomposition stepwise (i.e. in each step, only split up the leftmost digit). Second, if $a=2$, then add $c*f(10^b)$ to your formula. If $a>2$, add $f(10^b)$ to your formula. So for example, $f(23) = f(20) + f(3) + 3\cdot f(10) = 3+1+3 = 7$. However I didn't check the modified rule very much.2012-08-21
  • 0
    @celtschk Sorry I meant that f(20) + f(7) with my formulas would be instead 12 + 1 = 13 rather than 3 + 1 = 4. It's not a big deal, but it was just a side comment.2012-08-21
  • 0
    @celtschk In addition, that method seems to me like it would work. But I don't want to introduce c, so I have thought of an iffy way to make it work with a and b.2012-08-21
  • 0
    You are now using an $x$ which, as far as I can see, you define nowhere.2012-08-21
  • 0
    @celtschk The comment right below should have implied that.2012-08-21
  • 0
    But I got it changed anyways..You don't need the f(10) part of it though2012-08-21
1

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.