## Counting Ones

### June 15, 2012

Today’s exercise is a fun math problem:

Consider a function f that takes a positive integer n and returns the number of 1s in the decimal representation of all the integers from 0 to n, inclusive. For example, f(13) = 6, for the numbers 1, 10, 11 (twice, for two 1s), 12 and 13. Notice that f(1) = 1. After 1, what is the next largest n for which f(n) = n?

Your task is to write a program that finds the solution. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 20 Responses to “Counting Ones”

1. Lautaro Pecile said
```def count_ones(number):
return str(number).count('1')

def f(n):
return sum(map(count_ones, xrange(n+1)))
```
2. The answer is 199981.

```
cl-user> (loop for n from 1 for f = 1 then (+ f (count #\1 (format nil "~A" n))) when (= n f) do (print n))

1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001 ; Evaluation aborted.
cl-user>

```
3. PBC said

Bah, forgot to paste half of my solution. Common Lisp solution [updated]

4. Christian Siegert said

My solutions written in Go lang: https://gist.github.com/2941907

5. In Javascript

``` function countOnes(num) { num = "" + num; return (num.match(/1/g)||[]).length; }```

``` //console.log(countOnes(enumRange(0,13))) console.log(countOnes(111)); function largest() { var i = 1; var sum = 1; do { i++; sum += countOnes(i); ```

``` } while (i !== sum) ; return i; } ```

6. Python solution:

def n_equals_f():
n = 2
f = 1
while True:
f += str(n).count(‘1’)
if f == n:
return n
else:
n += 1

7. Juergen said

For a challenge where this is used see Project Euler Problem 156 [http://projecteuler.net/problem=156].

8. ardnew said

I can’t seem to figure out an efficient way to compute f, so here’s a brute-force C implementation using integer divisions:

```#include <stdio.h>
#include <stdint.h>

uint32_t f(uint32_t n)
{
uint32_t       c = 0;
uint_fast32_t  m = 0;

while (n)
{
m = n--;
while (m)
{
c += m % 10 == 1;
m /= 10;
}
}
return c;
}

int main(void)
{
uint32_t n = 2; // skip 1
for (; n != f(n); ++n);
printf("%u\n", n);
return 0;
}
```

And another solution in perl using string operations:

```use strict;
use warnings;

sub f
{
my \$n = shift;
my \$c = 0;
\$c += tr/1// for 1 .. \$n;
return \$c;
}

my \$n = 2; # skip 1
++\$n while \$n != f(\$n);
print \$n;
```
9. Miracle said

public static void Function(int n)
{
int result = 0;

String str = “”;

for (int i = 0; i <= n; i++)
{
str = String.valueOf(i);

char[] ch = new char[str.length()];

ch = str.toCharArray();

for (int j = 0; j < ch.length; j++)
{
if (ch[j] == '1')
{
result++;
}
}

if (i == result)
{
System.out.println(i);
}
}
}

10. Miracle said

The following is a C# code
public static void Function(int n)
{
int result = 0;
string str = “”;

for (int i = 0; i <= n; i++)
{
str = Convert.ToString(i);

char[] ch = new char[str.Length];

ch = str.ToCharArray();

for (int j = 0; j < ch.Length; j++)
{
if (ch[j] == '1')
{
result++;
}
}

if (i == result)
{
Console.WriteLine(i);
}
}
}

11. paul christodoulou said

#include
using namespace std;

int main(){
int n=2;
int count=0;
cout<<"welcome \n";
while(count!=n){
count=0;
for(int i=0; i0){
if(j%10==1)
count++;
j=j/10;
}
}
cout<<n<<": "<<count<<endl;
n+=1;
}
cout<<"The number in which f(n) = n is "<< count;
}

12. The solution is:
import java.util.*;

class CountingOne
{
int num;
CountingOne(int a)
{
num = a;
}

int Count(int m)
{
int i, rem, count=0;
while(m>0)
{
rem = m%10;
m = m/10;
if(rem==1)
count++;
}
}
return count;
}

void display(int k)
{
if(k == num)
System.out.println(“f(“+num+”) = “+k);
}
}

class CountingOnes
{
public static void main(String args[])
{
int k=0, m=1;
CountingOne cone = null;
while(true)
{
cone = new CountingOne(m);
k += cone.Count(m);
cone.display(k);
cone = null;
m++;
}
}
}

This is giving correct outputs that too not pussillanimus.

13. Quaspam said

In Python:

def cnt(n):
return 0 if n<1 else str(n).count('1') + cnt(n-1)

14. Mike said

In Python 3:

```from itertools import accumulate, islice

number_of_ones = accumulate(str(i).count('1') for i in count(1))
matches = (n for n,v in enumerate(number_of_ones, 1) if n == v)
list( islice(matches, 2) )

```

I also came up with this function that calculates the number of ones directly, without enumerating all the values from 1 to n.

```def number_of_ones(n):
d = 1
s = 0

while d <= n:
lt, rt = divmod(n,d)

if lt % 10 == 1:
s += rt + 1
s += lt // 10 * d

else:
s += (lt + 9)//10 * d

d *= 10

return s
```
15. ryan said

#include <iostream>
#include <iomanip>

int main(int argc, char *argv[]) {
unsigned long gCount(0);
for(unsigned long idx(1); idx <= ULONG_MAX; ++idx) {
unsigned long tmp(idx);
while(tmp) {
gCount += (unsigned long)(1 == tmp % 10);
tmp /= 10;
}

if(gCount == idx) {
if(idx != 1) {
std::cout << "f(" << idx << ") == " << idx << std::endl;
break;
}
}
}

return 0;
}

f(199981) == 199981

16. Tom Blanchet said

This generates solutions in Python :D
``` def findCOfisN(): ret = 0 j = 0 while(True): i = j while(i!=0): tmp = i%10 i/=10 if tmp==1: ret+=1 if ret == j: yield j j+=1 ```

17. Tom Blanchet said

That didn’t format correctly at all… I’ll figure that out later!

18. Tom Blanchet said

but for now, here are a bunch of solutions: 0 1 199981 199982 199983 199984 199985 199986 199987 199988 199989 199990 200000 200001 1599981 1599982 1599983 1599984 1599985 1599986 1599987 1599988 1599989 1599990 2600000 2600001 13199998 35000000 35000001 35199981 35199982 35199983 35199984 35199985 35199986 35199987 35199988 35199989 35199990 35200000 35200001 117463825 500000000 500000001 500199981 500199982 500199983 500199984 500199985 500199986 500199987 500199988 500199989 500199990 500200000 500200001 501599981 501599982 501599983 501599984 501599985 501599986 501599987 501599988 501599989 501599990 502600000 502600001 513199998 535000000 535000001 535199981 535199982 535199983 535199984 535199985 535199986 535199987 535199988 535199989 535199990 535200000 535200001 1111111110