2
$\begingroup$

I encountered an intriguing problem and I think I have a solution, but I want to run it by some of the smarter people around here:

Find the smallest integer $n, n>1$ such that $C(n)=n, C(n)$ is the total number of 1s that appear as you count from 1. For example, $C(9) = 1$, counting from $n=1$ to $n=9$, there is one 1. $C(99) =20, C(100)=21$, etc. I was able to get, as I stated, that from 1 to 99, there are 20 1s. From 1 to 199, $100 + 20*2$, up to 999 there are these $140 + 8*20 = 300$. Keeping with this algorithm I get $C(9,999)=4,000, C(99,999)=50,000$, and $C(199,999)=C(200,000)=200,000$

What I seem to be having trouble with is, is this the smallest integer for which $C(n)=n$?

$\endgroup$
3
  • 3
    $\begingroup$ It's $n=1$, maybe? $\endgroup$ Commented Jul 22, 2015 at 5:24
  • $\begingroup$ I'm sorry, that's n>1, not n>0. Let me fix that. Thanks! $\endgroup$ Commented Jul 22, 2015 at 5:37
  • $\begingroup$ $n = 199981$ seems to work. Project Euler Problem 156 seems to agree that this is the smallest such integer larger than $1$. $\endgroup$ Commented Jul 22, 2015 at 5:50

1 Answer 1

Reset to default
2
$\begingroup$

Through a simple brute-force program I see that the smallest such value is $n=199,981$ which makes sense.

Similarly you could backtrack from $200,000$ to see that at 10 less, $199,990$ also works, as well as every number below it down to $199,981$.

This is an interesting function, after $200,001$ there are no more results until $1,599,981$ at which point it does a few and jumps again to $2,600,000$ and continues to jump higher and higher, giving some strange values like $117,463,825$; I would initially assume that there would but I am now wondering if there's a maximum such $n$.

Edit:

OEIS never ceases to amaze me: http://oeis.org/A014778

It appears that it has been shown that there are only 84 such numbers (including 0 and 1) ending at $1,111,111,110$

$\endgroup$
1
  • $\begingroup$ Very interesting, indeed. $\endgroup$ Commented Jul 22, 2015 at 6:00

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.