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.

About these ads

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: