Is $21300113901613$ prime? And is there any easy way to check? I'm just checking properties of primes from the sequence $a(1) = 3$ and $$a(n) = \frac{a(n - 1)^2 + 1}{2}.$$
Asked
Active
Viewed 116 times
3
-
233 divides it, so it's not prime. – dromastyx Jul 05 '17 at 20:43
-
1https://oeis.org/A053630 – Andrés E. Caicedo Jul 05 '17 at 20:50
-
1It looks like $a(n)$ is divisible by $5$ if $n$ if $n$ is even, and divisible by some slightly larger primer otherwise... – Mr. Brooks Jul 05 '17 at 20:57
-
@Andrés Did you already think what I'm thinking? Zak Seidov's 2013 comment suggests that $a(n)$ is always composite for $n > 3$. And, as Mr. Brooks pointed out, every other term is a multiple of 5. – Robert Soupe Jul 06 '17 at 02:46
3 Answers
3
21300113901613 is not prime because it's divisible by 233.
There's no "easy" way to determine if a number is prime by hand.
Here are some quick hints:
If the number ends with a 0, 2, 4, 5, 6 or 8 then it's not prime (except for the numbers 2 and 5). If the sum of the digits is a multiple of 3, then the number is not prime (except for the number 3). $$\\$$ This link may help: https://brilliant.org/wiki/prime-testing/
BBot
- 927
2
The answers so far don't go into detail on how to algorithmically find out primality, so adding my take here.
If we're checking to see if $n$ is prime, it suffices to check all primes up to $\sqrt{n}$. So for this example, it's 4615204.
For each prime $p$ less than or equal to 4615204, if $p$ divides 21300113901613, then 21300113901613 is composite. If no prime divides 21300113901613, then 21300113901613 is prime.
But as we've seen so far, we quickly find out that 233 divides it.
Paul Raff
- 757
