Prime Factors Bounds in a Recurrence

In summary, the problem asks to show that for the recursion $$i(n)=i(n-1)+\frac{1}{i(n-1)}$$ with $$i(0)=1$$, where $$g(n)$$ is the numerators of the elements expressed in simplest form, and $$p$$ is the smallest prime factor of $$g(m)$$, it follows that $$p>4m-4$$. Some observations have been made, but a proof has not yet been found.
  • #1
Matt Rolo
2
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
  • #2
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 WWGD

1. What is the definition of prime factors?

Prime factors are the set of prime numbers that, when multiplied together, result in a given number.

2. How do prime factors play a role in recurrence relations?

In recurrence relations, prime factors are used to determine the upper and lower bounds of the time complexity. This is because the number of prime factors in a given number can have a significant impact on the number of recursive calls required in the recurrence relation.

3. What is the importance of finding the bounds of prime factors in a recurrence relation?

Finding the bounds of prime factors in a recurrence relation is important because it helps to determine the time complexity of the algorithm. This information is crucial in understanding the efficiency and performance of the algorithm and can aid in making improvements or optimizations.

4. How can the bounds of prime factors be calculated?

The bounds of prime factors in a recurrence relation can be calculated using techniques such as the Master Theorem, which provides a general formula for solving recurrence relations, or through mathematical analysis and manipulation of the recurrence relation itself.

5. Are there any limitations to using prime factors to determine the bounds in a recurrence relation?

Yes, there are limitations to using prime factors to determine the bounds in a recurrence relation. In some cases, the recurrence relation may have non-constant coefficients or may not have a clear pattern, making it difficult to accurately calculate the bounds using prime factors alone. In these cases, other techniques such as asymptotic analysis may be used.

Similar threads

  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
553
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
506
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
988
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
Back
Top