Counting Ones
June 15, 2012
This is simple:
> (let loop ((n 0) (sum 0))
(when (= n sum) (display sum) (newline))
(loop (+ n 1) (+ sum (length (filter one? (digits (+ n 1)))))))
0
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
...
The program uses filter
and digits
function from the Standard Prelude, as well as a helper function that recognizes the digit 1. You can run the program at http://programmingpraxis.codepad.org/urm4Ud0S.
There are exactly 84 numbers n for which f(n) = n; there is a list at A014778, where you will also find references to a proof that the list of 84 numbers is complete. It’s fascinating little tidbits like this that make me love math so much.
A Haskell solution: https://gist.github.com/2935580
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:
And another solution in perl using string operations:
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:
I also came up with this function that calculates the number of ones directly, without enumerating all the values from 1 to n.
#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