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

Puzzle - Law of small numbers

Expand Messages
  • jbrennen
    This is an interesting example of how small numbers don t always behave the same as big numbers, and it s somewhat related to prime numbers (well,
    Message 1 of 5 , Jan 9, 2007
    • 0 Attachment
      This is an interesting example of how small numbers don't always
      behave the same as big numbers, and it's somewhat related to prime
      numbers (well, factorization anyway)...


      Start enumerating those values of sigma(N) which are divisible by 17
      (sigma function here being the sum of positive integer divisors).

      The first few are of course:

      sigma(67) == 68
      sigma(101) == 102
      sigma(128) == 255
      sigma(134) == 204

      There seems to be no scarcity of such numbers -- for N < 10^6, we
      have sigma(N) divisible by 17 a grand total of 80608 times,
      a hit rate of just over 8%.


      Now also enumerate those values of sigma(N) which are congruent
      to 5 (modulo 6):

      sigma(2401) == 2801
      sigma(9604) == 19607
      sigma(21609) == 36413
      sigma(28561) == 30941

      Okay, these are a little bit scarce, but still, there are 24
      of them for N < 10^6, and 1644 of them for N < 10^10. There
      are clearly an infinite number of them -- for instance, given
      any prime p of the form 6*a+1, N = p^4 will work.


      The big question is, how far do you have to go to find a number
      which is in both lists?

      Or for those who like their problem stated succinctly:
      What is the smallest N such that sigma(N) is congruent to
      17 (modulo 102)?


      Jack
    • Phil Carmody
      ... Well, an upper bound is 160470643909878751793805444097921 Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail
      Message 2 of 5 , Jan 10, 2007
      • 0 Attachment
        --- jbrennen <jb@...> wrote:
        > What is the smallest N such that sigma(N) is congruent to
        > 17 (modulo 102)?

        Well, an upper bound is 160470643909878751793805444097921

        Phil



        () ASCII ribbon campaign () Hopeless ribbon campaign
        /\ against HTML mail /\ against gratuitous bloodshed

        [stolen with permission from Daniel B. Cristofani]

        __________________________________________________
        Do You Yahoo!?
        Tired of spam? Yahoo! Mail has the best spam protection around
        http://mail.yahoo.com
      • thefatphil
        Apologies if people get 2 copies - yahoo seems flakey, so I m trying again. ... An upper bound is 160470643909878751793805444097921 Phil
        Message 3 of 5 , Jan 10, 2007
        • 0 Attachment
          Apologies if people get 2 copies - yahoo seems flakey, so I'm trying
          again.

          --- In primenumbers@yahoogroups.com, "jbrennen" <jb@...> wrote:
          > What is the smallest N such that sigma(N) is congruent to
          > 17 (modulo 102)?

          An upper bound is 160470643909878751793805444097921

          Phil
        • Adam
          I think you can prove that Phil s example 103^16 is the smallest such number. Sigma(n) has factors (1+p+p^2+...+p^k) for p^k||n (
          Message 4 of 5 , Jan 10, 2007
          • 0 Attachment
            I think you can prove that Phil's example 103^16 is the smallest
            such number. Sigma(n) has factors (1+p+p^2+...+p^k) for p^k||n (<-
            largest power of p that divides n). For sigma(n) to be 5 mod 6, all
            the factors have to be either 1 or 5 mod 6 (i.e., no factors that
            are 2,3,4,0 mod 6). By examination, for p=2 and p=3,
            (1+p+p^2+...+p^k) is never 0 mod 17 and 1 or 5 mod 6.

            For p=3, we get 1+3+3^2+...+3^k odd when k is even but then
            1+3+3^2+...+3^k=(3^(k+1)-1)/2 while the order of 3 mod 17 is 16 so 3^
            (k+1)-1 is divisible by 17 only when 16 divides k+1. It can not be
            true that k is even and 16 divides k+1.

            For p=2, we get 1+2+2^2+...+2^k is 1 mod 3 when k is even. But the
            order of 2 mod 17 is 8, so 2^(k+1)-1 == 0 mod 17 means (k+1) is even.

            The only other available primes are either 1 or 5 mod 6. If p is 5
            mod 6 and 1+p+...+p^k is either 1 or 5 mod 6, then k is even. If p
            is 1 mod 6 and 1+p+...+p^k is either 1 or 5 mod 6, then k is either
            4 or 6 mod 6.

            For k even, solve 1+x+...+x^k==0 mod 17 and find the first solution
            happens when k=16 and x==1 mod 17. The first prime that is 1 mod 17
            is 103. 103^16 is the first number that solve sigma(n)==17 mod 102.
          • jbrennen
            ... Yes, and you seemed to give a convincing argument. :) Did anyone notice that I basically gave away the key to finding Phil s example? I stated that
            Message 5 of 5 , Jan 10, 2007
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "Adam" <a_math_guy@...> wrote:
              >
              > I think you can prove that Phil's example 103^16 is the smallest
              > such number.

              Yes, and you seemed to give a convincing argument. :)


              Did anyone notice that I basically gave away the key to finding
              Phil's example? I stated that solving sigma(N) == 5 (mod 6)
              was easily done by picking a prime p of the form 6*x+1 and
              then taking p^4, or p^(5-1).

              This is of course easily generalized...

              So to solve sigma(N) == 17 (mod 102), find a prime of the
              form 102*x+1. The first such is of course 103. And then
              set N = 103^(17-1) = 103^16.



              The tricky part is proving that 103^16 is in fact the minimal
              solution.

              My method for doing so:

              Note that N must be divisible by a prime power p^a which
              has sigma(p^a) divisible by 17 but not divisible by 2 or 3.

              Note also that sigma(p^a) = (p^(a+1)-1)/(p-1).

              In order for sigma(p^a) to be an odd number (not divisible
              by 2), we need to have either p or a be even.

              If p is even, it must be 2, and we would have:
              p^(a+1) == 1 (mod 17). It turns out that this is true
              when a == 7 (mod 8); however, when a == 7 (mod 8), we
              also have sigma(2^a) divisible by 3. So that doesn't
              work.

              So p must be odd and a must be even. In order for
              p^(a+1)-1 (the numerator of the expression above) to
              be divisible by 17, (a+1) must be divisible by the
              order of p modulo 17. Note that the order of p
              modulo 17 must divide evenly into 16 (a consequence
              of Fermat's Little Theorem). So we have an
              odd number (a+1) which must be divisible by a
              divisor of 16. Clearly the divisor (the order of
              p modulo 17) must be 1. This implies that the
              prime p is in fact of the form 17*x+1.

              And once we know that p == 1 (mod 17), we can see
              easily that a must be of the form 17*y-1.

              The smallest prime p of the form 17*x+1 is 103,
              and the smallest exponent a of the form 17*y-1 is 16.

              So the smallest prime power which has sigma(p^a)
              divisible by 17, but not by 2 or 3, is 103^16.

              So any solution N to the original puzzle must be
              divisible by a prime power >= 103^16.



              There are not a lot of ordered pairs (A,B) such
              that A > 2 and such that N = (B+1)^(A-1) is the
              smallest solution to sigma(N) == A (modulo B).

              I know of these three: (5,6), (5,30), and (17,102).

              There could be others, if anyone wants to try
              to find them. It's interesting that for those
              three I know of, A is always a Fermat prime.
            Your message has been successfully submitted and would be delivered to recipients shortly.