Loading ...
Sorry, an error occurred while loading the content.
 

sigma-related sequence

Expand Messages
  • jbrennen
    In my brainstorming over sigma-related problems, I came up with a neat sequence. Let S[n] be the smallest number x 2 such that: x divides: Sum {i=1..x}
    Message 1 of 3 , Jul 2, 2002
      In my brainstorming over sigma-related problems, I came up with
      a neat sequence.

      Let S[n] be the smallest number x>2 such that:

      x divides: Sum {i=1..x} (sigma_n(i))

      Here sigma_n(i) denotes the sum of the nth powers of the positive
      integer divisors of i.

      So for any particular n, we are looking for the smallest x>2 such
      that sigma_n(1), sigma_n(2), ... sigma_n(x) have an integer average.

      The sequence can be generated in PARI/GP:


      for(n=0,10000,x=0;t=0;while(1,x=x+1;t=t+sigma(x,n);if(x>2&&t%x==0,prin
      t1(x,", ");break)))

      The sequence starts out:

      4, 8, 8, 7, 7, 36, 9, 9, 31, 7, 7, 11, 9, 9, 38, 7, 7, 17, 9, 9 ...

      Interesting things I noted about the sequence:

      - The values 4 and 8 only occur in the first three terms
      - If n == 0 (mod 6) or n == 1 (mod 6), and n>1, then S[n] = 9
      - If n == 3 (mod 6) or n == 4 (mod 6), then S[n] = 7
      - If n == 5 (mod 6), then S[n] <= 36
      - If n == 14 (mod 18), then S[n] <= 38
      - If n == 2 (mod 36), then S[n] <= 74

      This leaves the "interesting" subsets where
      n == 8, 20, or 26 (mod 36) -- these appear more chaotic at
      first glance, although it seems reasonable to believe they
      too are periodic and that a "covering set" exists.

      Note that I have not found any value of S[n] exceeding 200,
      searching through about n==5000. The value 200 occurs for
      the first time at S[632].


      So the question is... is the sequence periodic (after the
      first three terms of course)? If so, what is its period?
      Are there any members exceeding 200? Note that if a covering
      set exists, the period of the sequence will certainly be much
      larger than the period of the covering set, due to the
      presence of sequence members not in the covering set, but
      smaller than the covering member of the covering set.

      If it is periodic, it has period >= 1607760, since this
      is the period of the subset where n == 2 (mod 36).


      Anyway, I thought this might be of interest....



      Jack
    • Phil Carmody
      ... for(n=0,10000,x=0;t=0;while(1,x=x+1;t=t+sigma(x,n);if(x 2&&t%x==0,prin ... I used subsampling via a swift change to nn=0,10000,n=36*nn+8 inter alia. ...
      Message 2 of 3 , Jul 2, 2002
        --- jbrennen <jack@...> wrote:
        for(n=0,10000,x=0;t=0;while(1,x=x+1;t=t+sigma(x,n);if(x>2&&t%x==0,prin
        > t1(x,", ");break)))

        I used subsampling via a swift change to
        nn=0,10000,n=36*nn+8
        inter alia.

        > Interesting things I noted about the sequence:
        >
        > - The values 4 and 8 only occur in the first three terms
        > - If n == 0 (mod 6) or n == 1 (mod 6), and n>1, then S[n] = 9
        > - If n == 3 (mod 6) or n == 4 (mod 6), then S[n] = 7
        > - If n == 5 (mod 6), then S[n] <= 36
        > - If n == 14 (mod 18), then S[n] <= 38
        > - If n == 2 (mod 36), then S[n] <= 74
        >
        > This leaves the "interesting" subsets where
        > n == 8, 20, or 26 (mod 36) -- these appear more chaotic at
        > first glance, although it seems reasonable to believe they
        > too are periodic and that a "covering set" exists.

        Note - when I say "repeats", I mean ther seems to be a period, but
        occasionally a smaller value also satisfies the relation, i.e. "<="
        as above.

        Looking at 8(mod 36)
        31 repeats every 5 terms from 8
        186 repeats every 5 terms from 44
        62 repeats every 5 terms from 80
        50 repeats every 5 terms from 116
        xx is a gap every 5 terms from 152

        So looking at 152(mod 180)
        xx is a gap every 2 terms from 152
        123 repeats every 2 terms from 332

        So looking at 152(mod 360)
        200 repeats every 2 terms from 152
        17 repeats every 2 terms from 512

        Done.

        20(mod 36) gives a similar pattern, obviously for the
        62, 50, xx, 31, 186
        92(mod 180) gives
        123, xx,
        272(mod 180) gives
        17, 200

        Actualy it's clear that 123, 17, 200 provide a covering set, so it
        will never exceed 200.

        > Note that I have not found any value of S[n] exceeding 200,
        > searching through about n==5000. The value 200 occurs for
        > the first time at S[632].
        >
        >
        > So the question is... is the sequence periodic (after the
        > first three terms of course)? If so, what is its period?
        > Are there any members exceeding 200? Note that if a covering
        > set exists, the period of the sequence will certainly be much
        > larger than the period of the covering set, due to the
        > presence of sequence members not in the covering set, but
        > smaller than the covering member of the covering set.

        It must be periodic as each value that can occur at all will cause a
        periodic pattern of residues when summed.

        > If it is periodic, it has period >= 1607760, since this
        > is the period of the subset where n == 2 (mod 36).

        Only 200 numbers to check, shouldn't be too hard to find all their
        periods, and then munge them together in a big LCM.

        However that required more than 5-character edits to your script, and
        so were deemed 'hard' :-)

        Phil

        =====
        --
        "One cannot delete the Web browser from KDE without
        losing the ability to manage files on the user's own
        hard disk." - Prof. Stuart E Madnick, MIT.
        So called "expert" witness for Microsoft. 2002/05/02

        __________________________________________________
        Do You Yahoo!?
        Yahoo! - Official partner of 2002 FIFA World Cup
        http://fifaworldcup.yahoo.com
      • jbrennen
        ... I explored this sequence further, and have essentially fully characterized it... It is periodic, as Phil already figured out. The period is 14802818350320
        Message 3 of 3 , Jul 3, 2002
          --- In primenumbers@y..., "jbrennen" <jack@b...> wrote:
          >
          > Let S[n] be the smallest number x>2 such that:
          >
          > x divides: Sum {i=1..x} (sigma_n(i))
          >
          > Here sigma_n(i) denotes the sum of the nth powers of the positive
          > integer divisors of i.
          >
          > So for any particular n, we are looking for the smallest x>2 such
          > that sigma_n(1), sigma_n(2), ... sigma_n(x) have an integer average.

          I explored this sequence further, and have essentially fully
          characterized it...

          It is periodic, as Phil already figured out. The period is
          14802818350320 == 2^4*3^2*5*7^2*11*13*23*29*53*83.
          That is, for n>=3, S[n+14802818350320] = S[n].

          There are 32 numbers which appear in the sequence. The numbers
          4 and 8 only appear within the initial (non-periodic) subsequence
          of length 3. So 30 numbers appear in the periodic portion of
          the sequence. The numbers are: 7, 9, 11, 17, 23, 29, 31,
          36, 38, 46, 50, 51, 59, 61, 62, 69, 71, 74, 89, 107, 113, 123,
          150, 158, 167, 169, 186, 188, 197, 200.

          The last number to show up as the sequence is enumerated is the
          number 197, which doesn't appear until S[19592].
        Your message has been successfully submitted and would be delivered to recipients shortly.