Number sequences, programming, preparing for Programming Competition - UNIX Programming

Hello, As programmers are very smart and mostly well educated with a strong mathematical background, I ask this question here as well as sci.math and sci.math.num-ysis by posting a this message to each of those groups. 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. I am very experienced programmer (6years +) so those 2 'simply programming' are not problems for me. But to win the competition I have to solve all three problems. So I post to ...

1. Number sequences, programming, preparing for Programming Competition

Hello,

As programmers are very smart and mostly well educated
with a strong mathematical background, I ask this question
here as well as sci.math and sci.math.num-ysis by posting
a this message to each of those groups.

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.
I am very experienced programmer (6years +) so
those 2 'simply programming'
are not problems for me. But to win the competition I have
to solve all three problems.

So I post to ask the math questions I would like get explanation
for and an advice on resources for further reading. (Yes, I know
google but I dont know what to search for, suggest me after looking
at the problem. At least I was not able to found suiting
papers(docs)).

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.

Thanks,
P.Krumins
Peteris Guest

2. Re: Number sequences, programming, preparing for ProgrammingCompetition

Peteris Krumins <lv> writes:

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
se
Måns Guest

3. Re: Number sequences, programming, preparing for Programming Competition

Peteris Krumins <lv> wrote in
news:133.1.4:

Excuse me for posting to comp.unix.programmer. I wanted to
post to more general group - comp.programming.

P.Krumins
Peteris Guest

4. Re: Number sequences, programming, preparing for Programming Competition

se (Måns Rullgård) wrote in news:se:

I agree they do not know.

As I wrote programmers are smart, so I thought someone could possibly
know the details of this math problem.

P.Krumins
Peteris Guest

5. Re: Number sequences, programming, preparing for ProgrammingCompetition

se (Måns Rullgård) writes:
[/ref]

BTW, did you mean a sequence of squares, rather than powers of two?
That's what that sequence most resembles.

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
se
Måns Guest

6. Re: Number sequences, programming, preparing for Programming Competition

se (Måns Rullgård) wrote in news: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.
This simple program would take too long to calculate the answer.

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.

P.Krumins
Peteris Guest

7. Re: Number sequences, programming, preparing for Programming Competition

In article <se>, Måns Rullgård wrote:
input integers >65535 on my machine]

#!/bin/sh
echo "\$1^2" | bc | tr -cd '0-9' | wc -c

has no such limitiation.

- Larry
Larry Guest

8. Re: Number sequences, programming, preparing for ProgrammingCompetition

Peteris Krumins <lv> writes:

>
> 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.[/ref]

I should have guessed.

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

Sorry, I'm not feeling mathematical today.

--
Måns Rullgård
se
Måns Guest

9. Re: Number sequences, programming, preparing for Programming Competition

On Fri, 16 Jan 2004 at 20:45 GMT, Peteris Krumins wrote:

#!/bin/sh
num=\${1:-3}
sequence="1 2 4 9 16 25 36 49 64 81 100 121 144 ..."
echo "\$sequence" | tr -dc '0-9' | cut -c 14

#!/bin/bash
num=\${1:-3}
sequence=\$(
n=0
while [ \$n -lt 64 ] ## bash 2.05[?]; older versions use 32
do
printf "\$(( 1 << n++ ))"
done
)
echo \${sequence:num-1:1}

--
Chris F.A. Johnson http://cfaj.freeshell.org
================================================== =================
My code (if any) in this post is copyright 2004, Chris F.A. Johnson
and may be copied under the terms of the GNU General Public License
Chris Guest

10. Re: Number sequences, programming, preparing for Programming Competition

""Måns Rullgård"" <se> wrote in message
news:se...

[/ref]

Agreed.

>
> Sorry, I'm not feeling mathematical today.[/ref]

Just build a table of starting points. Space them 1/2 second of CPU time
apart. It appears that to support numbers up to 10^9, only 80 preconfigured
starting points are needed. Then find the largest starting point not past
the number you're looking for.

DS

David Guest

11. Re: Number sequences, programming, preparing for Programming Competition

On Fri, 16 Jan 2004 20:45:27 +0000, Peteris Krumins wrote:

Assuming that 2 is not a part of the sequence, I would approach

First, I would create a function to calculate the number of digits

Second, I would iteratively call this above function until I have
found the number in the sequence that contains the Nth digit.

Third, I would determine which of the digits in the number
corresponds to the Nth digit.

--
mail1dotstofanetdotdk

Bjorn Guest

12. Re: Number sequences, programming, preparing for Programming Competition

On 16 Jan 2004 22:13:34 GMT, Peteris Krumins <lv> wrote:
>
>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.
>This simple program would take too long to calculate the answer.[/ref]

Ah, that's different.

What you need is a program that quickly calculates the sum of
the number of digits in the decimal expansions of all the squares up
to a number.

One way to calculat this is to consider (where X is a number of
decimal digits)

1x --> has 2*x+1 digits
2x --> has 2*x+1 digits

4x to 9x --> has 2*x+2 digits

3x ---> has either 2*x+1 or 2*x+2 digits,

All you need to do is calculate which number is on the dividing line
between 2*x+1 and 2*x+2, (Hint: consider sqrt(10)) then you can
quickly calculate the number of digits used up to a number, without
having to calculat all the digits themselves.

This is Ord(log(N)) rather than Ord(N).

--
"It's easier to find people online who openly support the KKK than
people who openly support the RIAA" -- comment on Wikipedia
(Email: zen19725 at zen dot co dot uk)

phil Guest

13. Re: Number sequences, programming, preparing for Programming Competition

Hi Måns!

On 16 Jan 04 at 22:45, "Måns" (Måns Rullgård) wrote: [/ref][/ref]

Måns> BTW, did you mean a sequence of squares, rather than powers of two?

Aren't these the same? :) Anyway, 2 is not a square of an integer.

perl -le '1 while ( \$ARGV[0] -= length ( \$_ = ++\$x * \$x)) > 0; print substr
\$_, length(\$_)+\$ARGV[0]-1, 1;'

--
Sincerely,
Dmitry

--- www.karasik.eu.org ---

He who dies with most the toys wins
Dmitry Guest

14. Re: Number sequences, programming, preparing for ProgrammingCompetition

Dmitry Karasik <eu.org> writes:
[/ref]
>
> Måns> BTW, did you mean a sequence of squares, rather than powers of two?
>
> Aren't these the same? :)[/ref]

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

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

--
Måns Rullgård
se
Måns Guest

15. Re: Number sequences, programming, preparing for Programming Competition

Hi Måns!

On 18 Jan 04 at 23:41, "Måns" (Måns Rullgård) wrote: [/ref]
Måns> No, squares are n^2, powers of two are 2^n.

Hmm.. always thought that n in a power of 2 is n^2, not vice versa.

--
Sincerely,
Dmitry

--- www.karasik.eu.org ---

He who dies with most the toys wins
Dmitry Guest

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•