I’ll Tell You What…

March 19, 2005

Fun with Numbers

Filed under: Technology, Programming — Larry @ 11:17 am

An interesting question is on the Google Labs Aptitude Test. Question 17 asks the following:

17. Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

I thought about it for a while but since I couldn't figure out a way in my head to get the answer I thought, "I could program that." I initially wrote it in PHP because I've used it quite a bit here lately. I chose to count up to 2,000,000 so I could time the execution.


#!/usr/bin/php

$ones_count = 0;
		
for ( $i = 1; $i <= 2000000; $i++ ) {
    $ones_count = $ones_count + substr_count( $i, "1" );
	
    if ( $ones_count == $i ) 
        echo "$ones_count == $i \n";
}

And then I thought, "How fast would this be if it were written in Perl?" This is what I came up with.


#!/usr/bin/perl

my $ones_count = 0;

for ( $i = 1; $i <= 2000000; $i++ ) {
    my $pos = 0;

    while ( ( $pos = index( $i, "1", $pos )) != -1 ) {
        $ones_count++;
        $pos++;
    }

    if ( $ones_count == $i ) {
        print "$i == $ones_count\n";
    }
}

The computer I tested this on is a PowerMac G5 Dual 2.0 GHz with 2 GB RAM. Here are my benchmarks: PHP on average took about 6.3 seconds. Perl, on the other hand, on average took about 5.1 seconds. I didn't even think my Perl code was very efficient either. Of course, I'm not a programming guru at all so if you know of a way to optimize the code let me know.

3 Comments »

The answer to the question is 199,981 but I put the program in an infinite loop to find as many as it could (until I got bored). This is the result after almost 4.5 hours:

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

Comment by Larry — March 19, 2005 @ 11:22 am
Before you ask, I don’t know why the code doesn’t show up correctly in IE Mac.

Comment by Larry — March 20, 2005 @ 12:45 pm
[…] end at work whom I regard as one fo the best Perl programmers around. The Perl code in my previous post was crude but it was a whole lot faster than using the regular expression engine. I asked my buddy a […]

Pingback by I’ll Tell You What… » Blog Archive » Opimized! — March 22, 2005 @ 12:46 pm