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) [allowsmilie] => 1 [showsignature] => 0 [ipaddress] => [iconid] => 0 [visible] => 1 [attach] => 0 [infraction] => 0 [reportthreadid] => 0 [isusenetpost] => 1 [msgid] => [ref] => [htmlstate] => on_nl2br [postusername] => phil [ip] => philh@invalid.e [isdeleted] => 0 [usergroupid] => [membergroupids] => [displaygroupid] => [password] => [passworddate] => [email] => [styleid] => [parentemail] => [homepage] => [icq] => [aim] => [yahoo] => [msn] => [skype] => [showvbcode] => [showbirthday] => [usertitle] => [customtitle] => [joindate] => [daysprune] => [lastvisit] => [lastactivity] => [lastpost] => [lastpostid] => [posts] => [reputation] => [reputationlevelid] => [timezoneoffset] => [pmpopup] => [avatarid] => [avatarrevision] => [profilepicrevision] => [sigpicrevision] => [options] => [akvbghsfs_optionsfield] => [birthday] => [birthday_search] => [maxposts] => [startofweek] => [referrerid] => [languageid] => [emailstamp] => [threadedmode] => [autosubscribe] => [pmtotal] => [pmunread] => [salt] => [ipoints] => [infractions] => [warnings] => [infractiongroupids] => [infractiongroupid] => [adminoptions] => [profilevisits] => [friendcount] => [friendreqcount] => [vmunreadcount] => [vmmoderatedcount] => [socgroupinvitecount] => [socgroupreqcount] => [pcunreadcount] => [pcmoderatedcount] => [gmmoderatedcount] => [assetposthash] => [fbuserid] => [fbjoindate] => [fbname] => [logintype] => [fbaccesstoken] => [newrepcount] => [vbseo_likes_in] => [vbseo_likes_out] => [vbseo_likes_unread] => [temp] => [field1] => [field2] => [field3] => [field4] => [field5] => [subfolders] => [pmfolders] => [buddylist] => [ignorelist] => [signature] => [searchprefs] => [rank] => [icontitle] => [iconpath] => [avatarpath] => [hascustomavatar] => 0 [avatardateline] => [avwidth] => [avheight] => [edit_userid] => [edit_username] => [edit_dateline] => [edit_reason] => [hashistory] => [pagetext_html] => [hasimages] => [signatureparsed] => [sighasimages] => [sigpic] => [sigpicdateline] => [sigpicwidth] => [sigpicheight] => [postcount] => 12 [islastshown] => [isfirstshown] => [attachments] => [allattachments] => ) --> Number sequences, programming, preparing for Programming Competition - UNIX Programming

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. #1

    Default 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. #2

    Default 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. #3

    Default 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. #4

    Default 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. #5

    Default 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. #6

    Default 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. #7

    Default 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. #8

    Default 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. #9

    Default 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. #10

    Default 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. #11

    Default 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
    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 Guest

  12. #12

    Default 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. #13

    Default 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. #14

    Default 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. #15

    Default 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

Similar Threads

  1. Replies: 0
    Last Post: May 5th, 06:41 PM
  2. Need help with programming
    By Sofia in forum PHP Development
    Replies: 0
    Last Post: September 14th, 02:10 PM
  3. Programming ASP.net
    By Steve S in forum ASP.NET General
    Replies: 1
    Last Post: July 31st, 04:29 PM
  4. RPC Programming
    By Ramesh Nair in forum UNIX Programming
    Replies: 0
    Last Post: July 22nd, 11:29 AM

Bookmarks

Posting Permissions

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