Velocity Reviews > limits reached

# limits reached

O.R.Senthil Kumaran
Guest
Posts: n/a

 10-24-2004
Hi all,
I am trying with the following Question:
Q: 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
eg: f(13)=6. Notice that f(1)=1.

What is the next largest n such that f(n) =n.

To solve this, I wrote the following program:

#include<limits.h>
#include<stdio.h>
int main(void)
{
unsigned long long int i,n,count;
for(i=1;i<=ULLONG_MAX;i++)
{
count=0;
while((n=(i%10))>10)
{
if(n==1)
count++;
i/=10;
}
if (n == 1)
count++;
if( i == count)
printf("%llu",i);
}
}

But, the program (a.out) is running for more than 45 minutes! now without
any output.
Is it feasible to try out such a program? How should I approach this
otherwise?

Regards,
Senthil

http://sarovar.org/projects/uthcode/

Artie Gold
Guest
Posts: n/a

 10-24-2004
O.R.Senthil Kumaran wrote:
> Hi all,
> I am trying with the following Question:
> Q: 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
> eg: f(13)=6. Notice that f(1)=1.
>
> What is the next largest n such that f(n) =n.
>
> To solve this, I wrote the following program:
>
> #include<limits.h>
> #include<stdio.h>
> int main(void)
> {
> unsigned long long int i,n,count;
> for(i=1;i<=ULLONG_MAX;i++)
> {
> count=0;
> while((n=(i%10))>10)
> {
> if(n==1)
> count++;
> i/=10;
> }
> if (n == 1)
> count++;
> if( i == count)
> printf("%llu",i);
> }
> }
>
> But, the program (a.out) is running for more than 45 minutes! now without
> any output.
> Is it feasible to try out such a program? How should I approach this
> otherwise?
>

Hint: What is the value of ULLONG_MAX on your implementation?

HTH,
--ag

--
Artie Gold -- Austin, Texas

"If you don't think it matters, you're not paying attention."

O.R.Senthil Kumaran
Guest
Posts: n/a

 10-24-2004
On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
> Hint: What is the value of ULLONG_MAX on your implementation?

Maximum value - Unsigned long long int : 18446744073709551615

Well, the program I posted initially was a wrong one. For the above
problem, here is the correct program:

/*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
eg: f(13)=6. Notice that f(1)=1.
What is the next largest n such that f(n) =n */

#include<limits.h>
#include<stdio.h>
unsigned long long int countones(unsigned long long int); int main(void)
{
unsigned long long int i,cn;

for(i = 1; i<= ULLONG_MAX; ++i)
{
cn = countones(i);
if( i == cn)
printf("%d",i);
}

return 0;
}

unsigned long long int countones(unsigned long long int i) {
static unsigned long long int count = 0; int digit;

while((i/10) >= 1)
{
digit = i % 10;

if(digit == 1)
count++;
i /= 10;
}
if( i == 1)
count++;

return count;
}
The problem still remains,I understand unsigned long long integer is a
HUGE number, but I would like to try out till the limits to get the
solution to this problem. It is taking a long time and I have not
reached the end of execution yet!(leave alone the results). Do you have
any alternative to try out this?

Senthil

http://sarovar.org/projects/uthcode/

Artie Gold
Guest
Posts: n/a

 10-24-2004
O.R.Senthil Kumaran wrote:
> On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
>
>>Hint: What is the value of ULLONG_MAX on your implementation?

>
>
> Maximum value - Unsigned long long int : 18446744073709551615

This is (as you state below) a HUGE number.
>
> Well, the program I posted initially was a wrong one. For the above
> problem, here is the correct program:
>
> /*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
> eg: f(13)=6. Notice that f(1)=1.
> What is the next largest n such that f(n) =n */
>
> #include<limits.h>
> #include<stdio.h>
> unsigned long long int countones(unsigned long long int); int main(void)
> {
> unsigned long long int i,cn;
>
> for(i = 1; i<= ULLONG_MAX; ++i)
> {
> cn = countones(i);
> if( i == cn)
> printf("%d",i);

Try:
{
printf("%d ", i);
fflush(stdout);
}
otherwise you will see no output -- and Bad Things are likely to happen
first.

> }
>
> return 0;
> }
>
> unsigned long long int countones(unsigned long long int i) {
> static unsigned long long int count = 0; int digit;
>
> while((i/10) >= 1)
> {
> digit = i % 10;
>
> if(digit == 1)
> count++;
> i /= 10;
> }
> if( i == 1)
> count++;
>
> return count;
> }
> The problem still remains,I understand unsigned long long integer is a
> HUGE number, but I would like to try out till the limits to get the
> solution to this problem. It is taking a long time and I have not
> reached the end of execution yet!(leave alone the results). Do you have
> any alternative to try out this?

Right.

You are executing the loop approximately (4 billion x 4 billion) times.
4 billion seconds is approxiamtely 120 *years*.

Do you see the problem?

HTH,
--ag

--
Artie Gold -- Austin, Texas

"If you don't think it matters, you're not paying attention."

Jack Klein
Guest
Posts: n/a

 10-24-2004
On Mon, 25 Oct 2004 02:45:00 +0500, "O.R.Senthil Kumaran"
<(E-Mail Removed)> wrote in comp.lang.c:

> On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
> > Hint: What is the value of ULLONG_MAX on your implementation?

>
> Maximum value - Unsigned long long int : 18446744073709551615
>
> Well, the program I posted initially was a wrong one. For the above
> problem, here is the correct program:
>
> /*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
> eg: f(13)=6. Notice that f(1)=1.
> What is the next largest n such that f(n) =n */
>
> #include<limits.h>
> #include<stdio.h>
> unsigned long long int countones(unsigned long long int); int main(void)
> {
> unsigned long long int i,cn;
>
> for(i = 1; i<= ULLONG_MAX; ++i)

Since the subtle hint did not work, let's try the not-so-subtle hint.

Your loop will end when 'long long int i' holds a value GREATER than
ULLONG_MAX.

If you still don't get it, reread the sentence above slowly.

Hint:

long long int i = ULLONG_MAX;

++i;

What is the value of 'i'? It is GREATER than ULLONG_MAX?

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

Chris Torek
Guest
Posts: n/a

 10-24-2004
>On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
>> Hint: What is the value of ULLONG_MAX on your implementation?

In article <(E-Mail Removed)>
O.R.Senthil Kumaran <(E-Mail Removed)> wrote:
>Maximum value - Unsigned long long int : 18446744073709551615

OK, now, what happens when i (a variable of type "unsigned long
long") is equal to 18446744073709551615, and the loop executes the
"i++" instruction? What is the new value in i? (Remember that
unsigned arithmetic is modular or "clock" arithmetic, much as on
a 12-hour clock, the hours count 1,2,3,...,9,10,11,12,1,2,3,... so
that 12+1 = 1.)

>... here is the correct program:

The program still has a bug: your function countones() returns the
number of '1' digits in the decial expansion of its argument. The
the problem specifies:

_n_
\
f(n) = > countones(i)
/__
i = 1

but you call countones() only for one number; you need to compute
the sum of countones() for n numbers (for a brute-force solution,
which is clearly not the best possible solution).

A hint for a "better" solution: consider any expansion of some
number i, expressed in base b, as a series of terms:

k k-1 1
d b + d b + ... + d b + d
k k-1 1 0

For instance, i=175 in base 10 is 1(100) + 7(10) + 5. Here
countones(i) is 1 (because there is one "1" digit, for ten squared,
in the hundreds place). We can immediately see that countones(i-1)
through countones(i-75) all have a 1 in the hundreds place -- so
we need only consider the tens and ones places in all the smaller
numbers. Once i exceeds 199 (up through 999 inclusive), however,
it will have a 2 or 3 or ... or 9 in the hundreds place. The only
contributions you can get to "1" digits will come from the tens and
ones places.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
Reading email is like searching for food in the garbage, thanks to spammers.

Artie Gold
Guest
Posts: n/a

 10-24-2004
Jack Klein wrote:
> On Mon, 25 Oct 2004 02:45:00 +0500, "O.R.Senthil Kumaran"
> <(E-Mail Removed)> wrote in comp.lang.c:
>
>
>>On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
>>
>>>Hint: What is the value of ULLONG_MAX on your implementation?

>>
>>Maximum value - Unsigned long long int : 18446744073709551615
>>
>>Well, the program I posted initially was a wrong one. For the above
>>problem, here is the correct program:
>>
>>/*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
>>eg: f(13)=6. Notice that f(1)=1.
>>What is the next largest n such that f(n) =n */
>>
>>#include<limits.h>
>>#include<stdio.h>
>>unsigned long long int countones(unsigned long long int); int main(void)
>>{
>> unsigned long long int i,cn;
>>
>> for(i = 1; i<= ULLONG_MAX; ++i)

>
>
> Since the subtle hint did not work, let's try the not-so-subtle hint.
>
> Your loop will end when 'long long int i' holds a value GREATER than
> ULLONG_MAX.
>
> If you still don't get it, reread the sentence above slowly.
>
> Hint:
>
> long long int i = ULLONG_MAX;
>
> ++i;
>
> What is the value of 'i'? It is GREATER than ULLONG_MAX?
>

Jack, the test in the code is `<='.

The question is, when will it even get that far?

Cheers,
--ag

--
Artie Gold -- Austin, Texas

"If you don't think it matters, you're not paying attention."

Brett Frankenberger
Guest
Posts: n/a

 10-24-2004
In article <(E-Mail Removed)>,
Chris Torek <(E-Mail Removed)> wrote:
>
>but you call countones() only for one number; you need to compute
>the sum of countones() for n numbers (for a brute-force solution,
>which is clearly not the best possible solution).

"count" is declared static in countones(). As long as he calls
countones in order (countones(1), countones(2), ...), which he does, it

-- Brett

Guest
Posts: n/a

 10-25-2004
In article <(E-Mail Removed)>,
"O.R.Senthil Kumaran" <(E-Mail Removed)> wrote:

> Well, the program I posted initially was a wrong one. For the above
> problem, here is the correct program:

(put main on its own line, removed excess blank lines, added one or two
blank lines)

> /*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
> eg: f(13)=6. Notice that f(1)=1.
> What is the next largest n such that f(n) =n */
>
> #include<limits.h>
> #include<stdio.h>
> unsigned long long int countones(unsigned long long int);
>
> int main(void)
> {
> unsigned long long int i,cn;
>
> for(i = 1; i<= ULLONG_MAX; ++i)
> {
> cn = countones(i);
> if( i == cn)
> printf("%d",i);
> }
> return 0;
> }
>
> unsigned long long int countones(unsigned long long int i) {
> static unsigned long long int count = 0; int digit;
>
> while((i/10) >= 1)
> {
> digit = i % 10;
>
> if(digit == 1)
> count++;
> i /= 10;
> }
> if( i == 1)
> count++;
>
> return count;
> }

For what it's worth, it shouldn't take that long to get an answer.
Unless I did something wrong, I get an answer which easily fits in a
32-bit integer.

I'd recommend you clean up your code some; the use of "static" in
countones() is just asking for trouble -- main() should be doing the
summation. You loop is also more complex than it needs to be.
Something like:

while (i > 0) {
if ((i % 10) == 1)
count++;
i /= 10;
}
return (count);

is equivalent, easier to understand, and avoids the fix-up afterwards.
buffered -- you should do something like:

if (i == cn)
printf("%d\n", i);

Since stdout is line-buffered, this will guarantee a flush. Note that
you should get the output "1" immediately -- if you don't, investigate

Cheers,
- jonathan

Chris Torek
Guest
Posts: n/a

 10-25-2004
>In article <(E-Mail Removed)>,
>Chris Torek <(E-Mail Removed)> wrote:
>>but you call countones() only for one number ...

In article <news:clhd8i\$54r\$(E-Mail Removed)>
Brett Frankenberger <(E-Mail Removed)> wrote:
>"count" is declared static in countones(). As long as he calls
>countones in order (countones(1), countones(2), ...), which he does, it

Oops, quite right. I missed the "static" completely!
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
Reading email is like searching for food in the garbage, thanks to spammers.