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.
Programming Praxis 
A Haskell solution: https://gist.github.com/2935580
def count_ones(number): return str(number).count('1') def f(n): return sum(map(count_ones, xrange(n+1)))The answer is 199981.
Common Lisp solution
Bah, forgot to paste half of my solution. Common Lisp solution [updated]
My solutions written in Go lang: https://gist.github.com/2941907
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;
}
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
For a challenge where this is used see Project Euler Problem 156 [http://projecteuler.net/problem=156].
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;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);
}
}
}
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);
}
}
}
#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;
}
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.
In Python:
def cnt(n):
return 0 if n<1 else str(n).count('1') + cnt(n-1)
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#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
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
That didn’t format correctly at all… I’ll figure that out later!
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