Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> writes:
quote:

>   I am preparing for a student programming competition and from
>   the previous year experience I know that there are 2 'simply
>   programming' problems and a single one which involves strong
>   mathematics.
>
>   One of the problems I don't know answer is:
>   A sequence of number powers of 2 starting from 1 is given,
>   find the Nth digit of the sequence.
>
>   Example:
>   1 2 4 9 16 25 36 49 64 81 100 121 144 ...
>
>   7th digit is 2, 14th is 4, etc.


What has that got to do with programming?  Those who invent those
problems don't seem to know much about reality.

--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

mru@kth.se (Måns Rullgård) writes:
quote:

> Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> writes:
> 

BTW, did you mean a sequence of squares, rather than powers of two?
That's what that sequence most resembles.
[QUOTE]
> What has that got to do with programming?  Those who invent those
> problems don't seem to know much about reality.


Of course, if we look at it as a programming problem, we can just
count the digits.  This little program should do it.  There's probably
some clever method, but it would take me longer to figure it out than
to run this program hundreds of times.

#include <stdio.h>
#include <stdlib.h>

extern int
main(int argc, char **argv)
{
int i, d, l, n;
char buf[256];

if(argc > 1)
n = strtol(argv[1], NULL, 0);
else
exit(1);

for(i = 1, d = 0; d < n; i++){
l = sprintf(buf, "%i", i*i);
d += l;
}

printf("%c\n", buf[l-d+n-1]);

return 0;
}


--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

mru@kth.se (Måns Rullgård) writes:
quote:

> Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> writes:
> 

BTW, did you mean a sequence of squares, rather than powers of two?
That's what that sequence most resembles.
[QUOTE]
> What has that got to do with programming?  Those who invent those
> problems don't seem to know much about reality.


Of course, if we look at it as a programming problem, we can just
count the digits.  This little program should do it.  There's probably
some clever method, but it would take me longer to figure it out than
to run this program hundreds of times.

#include <stdio.h>
#include <stdlib.h>

extern int
main(int argc, char **argv)
{
int i, d, l, n;
char buf[256];

if(argc > 1)
n = strtol(argv[1], NULL, 0);
else
exit(1);

for(i = 1, d = 0; d < n; i++){
l = sprintf(buf, "%i", i*i);
d += l;
}

printf("%c\n", buf[l-d+n-1]);

return 0;
}


--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> writes:
quote:

> mru@kth.se (Måns Rullgård) wrote in news:yw1xy8s77ek1.fsf@kth.se:
> 
>
> Of course, such program would do it but:
> I forgot to note that the Nth digit to find can be as enormous as 10^9.
> And I forgot to mention that any problem in the competition must be
> solved in less than or queal to 1 second.


I should have guessed.
quote:

> This simple program would take too long to calculate the answer.


Right.  It took 39 seconds for 10^9.  That's still much less time than
it takes to figure out the clever solution.
quote:

> Also I have a solution in Pascal from the organisators of
> competition (as this problem was presented the previous year) but a
> plain algorithm provides no background of the problem which is
> exactly what I am looking to hear.


Sorry, I'm not feeling mathematical today.

--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> writes:
quote:

> mru@kth.se (Måns Rullgård) wrote in news:yw1xy8s77ek1.fsf@kth.se:
> 
>
> Of course, such program would do it but:
> I forgot to note that the Nth digit to find can be as enormous as 10^9.
> And I forgot to mention that any problem in the competition must be
> solved in less than or queal to 1 second.


I should have guessed.
quote:

> This simple program would take too long to calculate the answer.


Right.  It took 39 seconds for 10^9.  That's still much less time than
it takes to figure out the clever solution.
quote:

> Also I have a solution in Pascal from the organisators of
> competition (as this problem was presented the previous year) but a
> plain algorithm provides no background of the problem which is
> exactly what I am looking to hear.


Sorry, I'm not feeling mathematical today.

--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

Dmitry Karasik <dmitry@karasik.eu.org> writes:
quote:

> 	Hi Måns!
>
> On 16 Jan 04 at 22:45, "Måns" (Måns Rullgård) wrote: 
>
>  Måns> BTW, did you mean a sequence of squares, rather than powers of two?
>
> Aren't these the same? 


No, squares are n^2, powers of two are 2^n.
quote:

> Anyway, 2 is not a square of an integer.


It's not, but hardly any of the rest of the numbers are powers of two.

--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

Dmitry Karasik <dmitry@karasik.eu.org> writes:
quote:

> 	Hi Måns!
>
> On 16 Jan 04 at 22:45, "Måns" (Måns Rullgård) wrote: 
>
>  Måns> BTW, did you mean a sequence of squares, rather than powers of two?
>
> Aren't these the same? 


No, squares are n^2, powers of two are 2^n.
quote:

> Anyway, 2 is not a square of an integer.


It's not, but hardly any of the rest of the numbers are powers of two.

--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> writes:
quote:

>   I am preparing for a student programming competition and from
>   the previous year experience I know that there are 2 'simply
>   programming' problems and a single one which involves strong
>   mathematics.
>
>   One of the problems I don't know answer is:
>   A sequence of number powers of 2 starting from 1 is given,
>   find the Nth digit of the sequence.
>
>   Example:
>   1 2 4 9 16 25 36 49 64 81 100 121 144 ...
>
>   7th digit is 2, 14th is 4, etc.


What has that got to do with programming?  Those who invent those
problems don't seem to know much about reality.

--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

mru@kth.se (Måns Rullgård) writes:
quote:

> Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> writes:
> 

BTW, did you mean a sequence of squares, rather than powers of two?
That's what that sequence most resembles.
[QUOTE]
> What has that got to do with programming?  Those who invent those
> problems don't seem to know much about reality.


Of course, if we look at it as a programming problem, we can just
count the digits.  This little program should do it.  There's probably
some clever method, but it would take me longer to figure it out than
to run this program hundreds of times.

#include <stdio.h>
#include <stdlib.h>

extern int
main(int argc, char **argv)
{
int i, d, l, n;
char buf[256];

if(argc > 1)
n = strtol(argv[1], NULL, 0);
else
exit(1);

for(i = 1, d = 0; d < n; i++){
l = sprintf(buf, "%i", i*i);
d += l;
}

printf("%c\n", buf[l-d+n-1]);

return 0;
}


--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]

Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> writes:
quote:

> mru@kth.se (Måns Rullgård) wrote in news:yw1xy8s77ek1.fsf@kth.se:
> 
>
> Of course, such program would do it but:
> I forgot to note that the Nth digit to find can be as enormous as 10^9.
> And I forgot to mention that any problem in the competition must be
> solved in less than or queal to 1 second.


I should have guessed.
quote:

> This simple program would take too long to calculate the answer.


Right.  It took 39 seconds for 10^9.  That's still much less time than
it takes to figure out the clever solution.
quote:

> Also I have a solution in Pascal from the organisators of
> competition (as this problem was presented the previous year) but a
> plain algorithm provides no background of the problem which is
> exactly what I am looking to hear.


Sorry, I'm not feeling mathematical today.

--
Måns Rullgård
mru@kth.se

[ Post a follow-up to this message ]