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

Loops in a largest-prime-factor function

Expand Messages
  • mad37wriggle
    I m looking at the function lf(n) = largest prime factor of (n^2+1). Specifically I m looking at loops in the iteration of this function. Loops of length 1,
    Message 1 of 4 , May 8 3:07 PM
    • 0 Attachment
      I'm looking at the function lf(n) = largest prime factor of (n^2+1). Specifically I'm looking
      at loops in the iteration of this function.

      Loops of length 1, i.e. lf(n) = n: obviously impossible.

      Loops of length 2, i.e. lf(lf(n)) = n: 89 and 233 are the only members of a length-2 loop
      below 10^8.

      Loops of length 3: none below 1.5*10^7

      Loops of length 4: none below 3.2*10^5

      Is it possible to ascertain whether loops of length >2 actually exist? Has anyone found
      one? Or any further loops of length 2?

      Thanks,

      Richard
    • jbrennen
      ... Can t help you with looking for loops in the function, but this is interesting in other ways... Another interesting computational exercise is to look for
      Message 2 of 4 , May 9 2:07 PM
      • 0 Attachment
        --- mad37wriggle wrote:
        >
        >
        > I'm looking at the function lf(n) = largest prime factor of
        > (n^2+1). Specifically I'm looking at loops in the iteration
        > of this function.
        >

        Can't help you with looking for loops in the function, but
        this is interesting in other ways...

        Another interesting computational exercise is to look for prime
        values of n which minimize log(lf(n))/log(n) -- those values
        of n which have sharp "drops" to their successor. Obviously,
        these are those values of n such that n^2+1 is exceptionally
        "smooth", with no large prime factors.

        Here are all of the records for sharpest drops, for n < 10^9:

        n lf(n) log(lf(n))/log(n)

        7 5 0.827087
        47 17 0.735871
        157 29 0.665968
        239 13 0.468359
        17923 97 0.467101
        34367 113 0.452605
        43633 113 0.442491
        44179 53 0.371194
        1413443 157 0.357041
        2041537 137 0.338627
        4773557 157 0.328784
        7691443 113 0.298152
        18975991 101 0.275387
        211823957 181 0.271161
        584159743 193 0.260714
        851387893 157 0.245898


        If you permit composite values of n, the record for n < 10^9 is:

        599832943 113 0.233888

        And then, later, the very impressive:

        2189376182 101 0.214588

        Yes, 2189376182^2+1 = 5^3 * 17^2 * 29^2 * 53 * 61^2 * 89^2 * 101


        How far would we have to search to find lf(n) less than the
        fifth root of n? The sixth root?

        Can log(lf(n))/log(n) be made arbitrarily small?


        It seems that approximately 25% of primes p have lf(p)<p.
      • jbrennen
        ... Extending the table with some new results: 5271470807 181 0.232225 72227609747 317 0.230328 Exhaustively searched to 10^11... Among composite n, 2189376182
        Message 3 of 4 , May 9 6:06 PM
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "jbrennen" <jb@...> wrote:
          >
          > Here are all of the records for sharpest drops, for n < 10^9:
          >
          > n lf(n) log(lf(n))/log(n)
          >
          > 7 5 0.827087
          > 47 17 0.735871
          > 157 29 0.665968
          > 239 13 0.468359
          > 17923 97 0.467101
          > 34367 113 0.452605
          > 43633 113 0.442491
          > 44179 53 0.371194
          > 1413443 157 0.357041
          > 2041537 137 0.338627
          > 4773557 157 0.328784
          > 7691443 113 0.298152
          > 18975991 101 0.275387
          > 211823957 181 0.271161
          > 584159743 193 0.260714
          > 851387893 157 0.245898
          >

          Extending the table with some new results:

          5271470807 181 0.232225
          72227609747 317 0.230328

          Exhaustively searched to 10^11...

          Among composite n, 2189376182 remains the champion.
        • Robert
          ... It appears that: All n^2+1 prime factors are either 2 or pythagorean primes (primes of the form 4x+1) Each pythagorean prime P appears as factors in n^2+1
          Message 4 of 4 , May 13 6:05 AM
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "jbrennen" <jb@...> wrote:

            >
            > And then, later, the very impressive:
            >
            > 2189376182 101 0.214588
            >
            > Yes, 2189376182^2+1 = 5^3 * 17^2 * 29^2 * 53 * 61^2 * 89^2 * 101
            >
            >
            > How far would we have to search to find lf(n) less than the
            > fifth root of n? The sixth root?
            >
            > Can log(lf(n))/log(n) be made arbitrarily small?
            >
            >
            > It seems that approximately 25% of primes p have lf(p)<p.
            >

            It appears that:
            All n^2+1 prime factors are either 2 or pythagorean primes (primes of
            the form 4x+1)
            Each pythagorean prime P appears as factors in n^2+1 where n=a or
            bmodP, a and b given by a^2+1==0modP, b^2+1==0modP

            The chance that a given value of n^2+1 has no factors between any
            given lf(n) and n is given approximately by

            Product(from P[1] to P[2]) (P-2)/P

            P[1] = next pythagorean prime after lf(n)
            P[2] = last pythagorean prime before n

            For n=188437, the chance that n^2+1 has no factors between 101 and
            188437 is about 0.36%.

            I am sure something this simple can be evaluated over very large P.
            Trouble is, I don't know how to do this.

            I don't know how to evaluate the chance that there are prime factors
            of n^2+1 greater than n. It looks a complex proposition.

            Maybe others can help.

            Regards

            Robert Smith
          Your message has been successfully submitted and would be delivered to recipients shortly.