3
$\begingroup$

Gerry Myerson examined the sequence $$a_n=\gcd(2^{2^n}-1,3^{2^n}-1)$$

I am interested in the factors of $a_n$.

Since $2^{2^n}-1$ is the product of first $n-1$ Fermat numbers, and $3^{2^n}-1=2 \prod\limits_{k=0}^{n-1}{3^{2^k}+1}$, factors of $a_n$ will be in the intersection.

What is currently known to me about the factors:

For $n<20$, the factors are Fermat Primes.

For $20 \le n \le 36$, $a_n=5 \cdot 17 \cdot 257 \cdot 65537 \cdot 13631489$. $a_{39}$ is divisible by $ 2^{41} \cdot 3+1$.

Search in the intersection of known Fermat factors and known factors of generalized fermat numbers GFN'(3)=$\frac{3^{2^m}+1}{2}$ showed 19 factors of $a_n$. The format is pair $(k,n)$ with $p=k\cdot2^n+1$:

[(3, 41), (21, 41), (9, 67), (5, 127), (3, 209), (7, 320), (29, 4727), (9, 9431), (81, 12189), (81, 28285), (7, 95330), (3, 157169), (3, 213321), (3, 303093), (3, 382449), (9, 461081), (243, 495732), (3, 2145353), (3, 2478785)]

To verify the above, work modulo the factor.

Computing the actual gcd for $n=33$ will require about 12G of RAM and will take about 7 hours in a C++ ntl implementation.

Would it be possible some clever trick to reduce the memory requirement, hopefully finding unknown Fermat factor?

Another question are infinitely many primes expected to divide $a_n$?

$\endgroup$
11
  • $\begingroup$ You won't find all factors in this way, but you could simply calculate modulo some power of two times a small odd factor plus 1, as these are anyway the most likely prime factors to show up. $\endgroup$
    – j.p.
    Jul 17, 2011 at 16:41
  • $\begingroup$ @jp I suppose they already did what you propose for Fermat factors, so for know I resort to searching in the subset of Fermat factors - it is not very fast for me assuming I am doing it right (just testing the pseudo primality of the largest Fermat factors might take more than 10 hours IMHO...) $\endgroup$
    – joro
    Jul 17, 2011 at 17:31
  • $\begingroup$ @jp How do you formally define small odd? $\endgroup$
    – joro
    Jul 17, 2011 at 17:49
  • $\begingroup$ @joro: I don't define small formally. I would just start with $3$ and increase it at will. Is your goal to find Fermat factors or to find the gcd? $\endgroup$
    – j.p.
    Jul 18, 2011 at 9:30
  • $\begingroup$ @jp Thank you! I am interested in both the gcd and the fermat factors. I completely agree with your method. AFAICT the gcd is divisible by only fermat factors. A lot of people spent a lot of time searching for fermat factors (mainly by your method) so I just reuse their computations checking the found factors, which is not as fast as it may seem. $\endgroup$
    – joro
    Jul 18, 2011 at 10:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.