- 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 - --- mad37wriggle wrote:
>

Can't help you with looking for loops in the function, but

>

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

>

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. - --- In primenumbers@yahoogroups.com, "jbrennen" <jb@...> wrote:
>

Extending the table with some new results:

> 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

>

5271470807 181 0.232225

72227609747 317 0.230328

Exhaustively searched to 10^11...

Among composite n, 2189376182 remains the champion. - --- In primenumbers@yahoogroups.com, "jbrennen" <jb@...> wrote:

>

It appears that:

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

>

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