It Must Be A Prime Number!

Computer Science Level 4

In mathematics, a Fermat Number is a positive integer of the form $F_n = 2^{\left (2^n \right)} + 1$

Given that $F_7 = 340282366920938463463374607431768211457,$
what are the last three digits of the smallest prime factor of $F_7$ ?

The answer is 217.

3 solutions

Agnishom Chattopadhyay
Mar 8, 2014

$59649589127497217 \times 5704689200685129054721=340282366920938463463374607431768211457$

Thats all I can say.

Here is the maxima code:

(%i35) factor(2^(2^7) + 1);
(%o35)             59649589127497217 5704689200685129054721

I wrote a program in Ruby to produce the lowest prime factor of a number, but it fails if you input a number of more than around 15 digits. Does anybody have any suggestions for how to get around this problem without using a different program? Here is the code:

user_num = Float(gets.chomp)
counter = 0
for num in 2...user_num
  new_num = user_num/num
  until counter == 1
    if new_num == Integer(new_num)
      puts num
      counter = counter + 1
    end
  end
end

Alex Pacheco - 7 years, 2 months ago

wikipedia FTW!!!!!

math man - 6 years, 9 months ago

Tan Ang
Mar 28, 2014

Using MuPAD: factor((2^(2^7))+1)

> 59649589127497217*5704689200685129054721

I've cheated, haven't I?

Khanh Le
Mar 17, 2014

Can you explain to me the code. I don't understand and how long it takes to find the prime factor? I used linear algorithm to do this and it takes a lot of time to see the result

I can't say too much, as I've only given this a few minutes thought. But clearly it is of the form $a^2+1$ , so perhaps the best approach is to find another $b^2+c^2$ representation.

Peter Byers - 7 years, 2 months ago

It Must Be A Prime Number!

The answer is 217.

3 solutions

0 pending reports