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.

  • 5
    $\begingroup$ It seems that you are trying to determine the primality of these numbers. It might be good to state that at the beginning. $\endgroup$ – marty cohen Feb 11 '16 at 6:08
  • 1
    $\begingroup$ 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). $\endgroup$ – Gerry Myerson Feb 11 '16 at 6:21
  • $\begingroup$ I edited the title - thanks - and maybe I should have elaborated further, this is not the case after $k=52$ $\endgroup$ – Alex Lieberman Feb 11 '16 at 6:31
  • 1
    $\begingroup$ 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]. $\endgroup$ – Galc127 Feb 11 '16 at 7:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Feb 11 '16 at 11:49

to test big number, is better to use a more specialized algorithm than trial division like: Miller-Rabin (deterministic version) or Baille-PSW

here you can find implementations to the Miller test: http://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test and adjusting it with the pseudo primes find in prove2_3.html and StrongPseudoprime you can make this test exact until 1543267864443420616877677640751301 (1.543 x 1033)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.