|
Home > Archive > Unix Programming > January 2004 > Number sequences, programming, preparing for Programming Competition
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Number sequences, programming, preparing for Programming Competition
|
|
| Peteris Krumins 2004-01-23, 5:13 pm |
|
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-analysis 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 Krumins 2004-01-23, 5:14 pm |
| Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> wrote in
news:Xns9472E774A68A4whitesuneapollolv@1
30.133.1.4:
quote:
>
> Hello,
>
Excuse me for posting to comp.unix.programmer. I wanted to
post to more general group - comp.programming.
P.Krumins
| |
| Peteris Krumins 2004-01-23, 5:14 pm |
| Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> wrote in
news:Xns9472E774A68A4whitesuneapollolv@1
30.133.1.4:
quote:
>
> Hello,
>
Excuse me for posting to comp.unix.programmer. I wanted to
post to more general group - comp.programming.
P.Krumins
| |
| Peteris Krumins 2004-01-23, 5:14 pm |
| mru@kth.se (Måns Rullgård) wrote in news:yw1xptdj1us6.fsf@kth.se:
quote:
>
> What has that got to do with programming? Those who invent those
> problems don't seem to know much about reality.
>
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 Krumins 2004-01-23, 5:14 pm |
| mru@kth.se (Måns Rullgård) wrote in news:yw1xptdj1us6.fsf@kth.se:
quote:
>
> What has that got to do with programming? Those who invent those
> problems don't seem to know much about reality.
>
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 Krumins 2004-01-23, 5:14 pm |
| mru@kth.se (Måns Rullgård) wrote in news:yw1xy8s77ek1.fsf@kth.se:
quote:
>
> 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.
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 Krumins 2004-01-23, 5:14 pm |
| mru@kth.se (Måns Rullgård) wrote in news:yw1xy8s77ek1.fsf@kth.se:
quote:
>
> 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.
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
| |
| Larry Doolittle 2004-01-23, 5:14 pm |
| In article <yw1xy8s77ek1.fsf@kth.se>, Måns Rullgård wrote:quote:
>
> 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.
>
> [chop C implementation, which is useless for
input integers >65535 on my machine]
#!/bin/sh
echo "$1^2" | bc | tr -cd '0-9' | wc -c
has no such limitiation.
- Larry
| |
| Larry Doolittle 2004-01-23, 5:14 pm |
| In article <yw1xy8s77ek1.fsf@kth.se>, Måns Rullgård wrote:quote:
>
> 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.
>
> [chop C implementation, which is useless for
input integers >65535 on my machine]
#!/bin/sh
echo "$1^2" | bc | tr -cd '0-9' | wc -c
has no such limitiation.
- Larry
| |
| Chris F.A. Johnson 2004-01-23, 5:14 pm |
| On Fri, 16 Jan 2004 at 20:45 GMT, Peteris Krumins wrote:quote:
>
> 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.
#!/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 F.A. Johnson 2004-01-23, 5:14 pm |
| On Fri, 16 Jan 2004 at 20:45 GMT, Peteris Krumins wrote:quote:
>
> 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.
#!/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
| |
| David Schwartz 2004-01-23, 5:14 pm |
|
""Måns Rullgård"" <mru@kth.se> wrote in message
news:yw1xllo77b39.fsf@kth.se...
quote:
[QUOTE][color=darkred]
> Right. It took 39 seconds for 10^9. That's still much less time than
> it takes to figure out the clever solution.
Agreed.
quote:
>
> Sorry, I'm not feeling mathematical today.
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 Schwartz 2004-01-23, 5:14 pm |
|
""Måns Rullgård"" <mru@kth.se> wrote in message
news:yw1xllo77b39.fsf@kth.se...
quote:
[QUOTE][color=darkred]
> Right. It took 39 seconds for 10^9. That's still much less time than
> it takes to figure out the clever solution.
Agreed.
quote:
>
> Sorry, I'm not feeling mathematical today.
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
| |
| Bjorn Reese 2004-01-23, 5:14 pm |
| On Fri, 16 Jan 2004 20:45:27 +0000, Peteris Krumins wrote:
quote:
> 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.
Assuming that 2 is not a part of the sequence, I would approach
the task as follows:
First, I would create a function to calculate the number of digits
in one digit. Logarithm (base 10) will help you here.
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 Reese 2004-01-23, 5:14 pm |
| On Fri, 16 Jan 2004 20:45:27 +0000, Peteris Krumins wrote:
quote:
> 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.
Assuming that 2 is not a part of the sequence, I would approach
the task as follows:
First, I would create a function to calculate the number of digits
in one digit. Logarithm (base 10) will help you here.
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
| |
| phil hunt 2004-01-23, 5:14 pm |
| On 16 Jan 2004 22:13:34 GMT, Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> wrote: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.
>This simple program would take too long to calculate the answer.
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 hunt 2004-01-23, 5:14 pm |
| On 16 Jan 2004 22:13:34 GMT, Peteris Krumins <pkruminsREMOVETHIS@inbox.lv> wrote: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.
>This simple program would take too long to calculate the answer.
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)
|
|
|
|
|