4
$\begingroup$

If we write down the digits of the $33$ rd Fermat number $$F_{33}=2^{2^{33}}+1$$ in base $10$ in reverse order , the resulting number should , considering its magnitude , be composite.

But can we search for a prime factor WITHOUT actually calculating $F_{33}$ ? $F_{33}$ begins with a $9$ , so there is no obvious prime factor of the reversed number. Can I , for example , determine whether the reverse of $F_{33}$ is divisible by $7$ ?

$\endgroup$
5
  • $\begingroup$ Why do you wish to avoid using a computer to programmatically compute the reverse digits of $~F_{33}?~$ Assuming that the reversal is composite, it is almost certainly divisible by some prime less that $~100,000.~$ Java has the BigInteger class, and (presumably) programming languages like C or Python have similar facilities, so confining all calculations to integers (i.e. avoiding floating point calculations) is straightforward. $\endgroup$
    – user2661923
    Commented Aug 31, 2023 at 0:22
  • $\begingroup$ @user2661923 I am not aware of a program with that I can handle such monster numbers with the memory of my computer. If you know such a program and have such a computer , you can do the calculations. Note that we need not only the number itself , we must also actively create the reverse. My memory limit does not even allow to make this with numbers of around $100$ million digits. $\endgroup$
    – Peter
    Commented Aug 31, 2023 at 5:59
  • $\begingroup$ The probability that there is no prime factor below $10^5$ is about $18$% (We already know that $2,3,5$ cannot be a prime factor) , so the "risk" that the smallest prime factor exceeds $10^5$ is not so small. $\endgroup$
    – Peter
    Commented Aug 31, 2023 at 6:04
  • $\begingroup$ Very interesting points, in both of your comments. Re your first comment, it was my carelessness for not examining $~F_{33}~$ closely enough. I assumed that $~F_{33} < 10^{10000},~$ but now I see that $\displaystyle ~F_{33} > 10^{\left(2^{31}\right)} > 10^{\left(10^9\right)}.~$ So, $~F_{33}~$ has more than 1 billion digits, which no standard home PC can handle. $\endgroup$
    – user2661923
    Commented Aug 31, 2023 at 8:51
  • $\begingroup$ @user2661923 Exactly. $\endgroup$
    – Peter
    Commented Aug 31, 2023 at 8:52

1 Answer 1

Reset to default
4
$\begingroup$

The Fermat number $F_{33}$ can be calculated in around 3 seconds on my machine. Reversing its decimal representation - we can trial divide by around 1 prime per second. With this, we have that:

$$ (7 \cdot 17 \cdot 37 \cdot 101 \cdot 101 \cdot 191 \cdot 257) \; | \; \text{rev}(F_{33}) = \underbrace{ 7986106331 \cdots 3310530369}_{\text{2,585,827,973 digits}} $$

Here is the code that I used to generate the factors - let me know if you have any questions.

$\endgroup$
2
  • $\begingroup$ My main question is how you were able not only to store this number , but also to invert it. I am not aware of any tool that can do this. Also, the computation time for this monster number is very surprising to me. You must have a powerful tool together with a machine offering much working space. Surprising also that we have so many small factors. $\endgroup$
    – Peter
    Commented Jun 9 at 9:08
  • $\begingroup$ The number only takes up 2.5 GB when expressed as a string and so can be easily stored in RAM - my machine has 32 GB of RAM so this was very much doable. $\endgroup$
    – Husnain Raza
    Commented Jun 9 at 21:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .