Prime Factors Bounds in a Recurrence

Click For Summary
SUMMARY

The discussion centers on the recursion defined by $$i(n)=i(n-1)+\frac{1}{i(n-1)}$$ with initial condition $$i(0)=1$$, leading to the numerators $$g(n)$$. It is established that the smallest prime factor $$p$$ of $$g(m)$$ satisfies the inequality $$p>4m-4$$. The sequence $$g(n)$$ exhibits properties such as being congruent to 1 modulo 4 for all $$n>2$$ and being relatively prime. Notably, the first few terms of $$g(n)$$ include 1, 2, 5, 29, 941, and 969581, with connections to Pythagorean triples.

PREREQUISITES
  • Understanding of recursion and sequences in mathematics
  • Familiarity with prime factorization and properties of primes
  • Knowledge of modular arithmetic, specifically congruences
  • Basic concepts of number theory, including Pythagorean triples
NEXT STEPS
  • Explore Euler's Theorem and its implications in number theory
  • Investigate the properties of the sequence defined by $$g(n)$$ in more depth
  • Learn about the relationship between prime factors and Pythagorean triples
  • Study the OEIS sequence related to $$g(n)$$ for further insights
USEFUL FOR

Mathematicians, number theorists, and students interested in advanced recursion, prime factorization, and the properties of integer sequences.

Matt Rolo
Messages
2
Reaction score
1
Let $$g(n)$$ be the numerators of the elements of the recursion $$i(n)=i(n-1)+\frac{1}{i(n-1)}$$ when they are expressed in simplest form, with $$i(0)=1$$. Let $$p$$ be the smallest prime factor of $$g(m)$$. Show that $$p>4m-4$$.

Homework Equations


Euler's Theorem?

The Attempt at a Solution


OEIS yielded the following recursion for $$g(n)$$:
$$0 = g(n)^2(g(n+1) - g(n)^2) - (g(n+2) - g(n+1)^2)$$, which I found to be equivalent to $$g(n)=g^2(n-1)+(\prod_{i=0}^{n-2} g(i))^2$$. This seems suggestive of Euler's contradiction proof of infinitely many primes, but I'm not sure how to proceed.
 
Last edited:
Physics news on Phys.org
A few observations: It’s quite clear that all ##g## for ##n>2## are congruent to 1 modulo 4. In addition I’ve found that all ##g## are relatively prime. It’s also not quite true that the ##p## increase as ##m## increases; for instance, 941 has ##p## of 941, while 969581 has ##p## of 521. Further the first few elements are part of Pythagorean triples:
$$5^2=3^2+4^2$$
$$29^2=20^2+21^2$$

$$941^2=580^2+741^2$$
$$969581^2=492100^2+835419^2=545780^2+801381^2$$
Each of which is primitive. This is of course necessary by Euclid’s formula, since each ##g(n)## is the sum of two squares, but the fact might be useful.
Still, I can’t put together a proof for the original problem

Here’s the first few ##g(n)##:
1,2,5,29,941, 969581.
OEIS link:
https://oeis.org/search?q=1,2,5,29,941&sort=&language=english&go=Search
 
  • Like
Likes   Reactions: WWGD

Similar threads

  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
1K
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 10 ·
Replies
10
Views
2K
  • · Replies 5 ·
Replies
5
Views
1K
  • · Replies 4 ·
Replies
4
Views
2K