Sorry, an error occurred while loading the content.

## Loops in a largest-prime-factor function

Expand Messages
• 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, 2006
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
• ... 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, 2006
>
>
> 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.
• ... 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, 2006
--- 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.
• ... 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, 2006
--- 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.