# $2^k+3$ : Primality Brute Forcing Theory Below The Square Root

I'm testing a theory of brute forcing $2^k+3$.

I've tried to test $(2^k)+3$ where $k=84$ but my computer just takes too long... Java takes too long too..

It's pretty stupid to assume 83 tests makes a perfect case, but I'll take it as a halfway decent case.

My Brute Force -vs- Square Root Brute Force

• $(2^k)+3$ where $k=55$ as prime in 4.7 seconds vs 7.1 seconds.
• $(2^k)+3$ where $k=64$ as NOT PRIME in 19 seconds vs 29 seconds
• $(2^k)+3$ where $k=67$ as prime in 63 seconds vs 899 seconds.

I'm no expert and I'm sure there are much better ways than brute forcing...

I just found it weird (despite being useless?) and I am not capable of mathematically proving/testing why it works so far as I am not a mathematician - and I am curious if it will continue to work.

For numbers of the form $2^k+3$:

1. Find $2^k+3$.
2. Take the square root of step 1.
3. Take the square root of step 2.
4. Times the result of step 3 by the square of k.
5. Times the result of step 4 by 3.
6. Mod by all numbers underneath step 5.
7. If no result of step 6 equals 0, the number is prime.

Further optimization can include testing step 6 by numbers of form 6k+-1.

• It seems that you are trying to determine the primality of these numbers. It might be good to state that at the beginning. – marty cohen Feb 11 '16 at 6:08
• The number you have after Step 5 is bigger than $\sqrt{2^k+3}$, so of course if no number below that number divides $2^k+3$, then $2^k+3$ is prime. This would work with any starting number (Step 4 is superfluous). – Gerry Myerson Feb 11 '16 at 6:21
• I edited the title - thanks - and maybe I should have elaborated further, this is not the case after $k=52$ – Alex Lieberman Feb 11 '16 at 6:31
• If you are trying to show that $2^n+3$ is prime, than $n=5$ is the minimum case which doesn't work. By the way, using Fermat little theorem, you can reduce times significantly. My python code gives an answer for k between 1 and 2000 in about 15 seconds [the only k's that return a prime number are 1,2,3,4,6,7,12,15,16,18,28,30,55,67,84,228,390,784,1110,1704]. – Galc127 Feb 11 '16 at 7:27
• OK, so you're asking whether $2^k+3$ always has a factor much much smaller than its square root, unless it's prime. Seems unlikely. – Gerry Myerson Feb 11 '16 at 11:49