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.

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