# Easy way to figure out primes? (Powers of 2, not Mersenne)

1. May 27, 2014

### Z.L.

I have figured out a seemingly revolutionary way to calculate primes. It is very simple. Let o be the number of odd digits in p, where p is a power of 2. If o is an odd number, then the sum of digits in p will be a prime number. Please, PLEASE do not hold back with commenting. I really want somebody to try to prove this wrong :P By the way, I would appreciate HUGELY if somebody with programming knowledge would make a program that calculates using this formula. Also, I need to make a proof! If anybody can help with either of these things, tell me so.

Also, in some cases if you make 0 -2 while adding instead of adding 0 it gives you a twin prime to the original.

Examples:
2^12 (4096) = p
o for p is equal to 1. One is an odd number, so the sum of 4+0+9+6 is a prime number (19). This example works also if you follow my 0 = -2 rule (it gives you 17).
2^4 (32) = p
o for p is equal to 1, so because one is an odd number the sum of 3+2 is a prime number.

I have had to figure out numbers up to 2^149 by hand, so a program that does this would help!

Thanks!
Z.L.

2. May 27, 2014

### gopher_p

Your hypothesis fails for $2^{16}=65,536$.

3. May 27, 2014

### micromass

Your hypothesis fails for several $2^n$. Here is a list of all the $n$ below $1000$ for which it fails:

$$\begin{array}{|l|l|l|} \hline n & \text{Sum of Digits} & \text{Prime Decomposition}\\ \hline 998 & 1417 & 13\cdot 109\\ 995 & 1391 & 13\cdot 107\\ 993 & 1313 & 13\cdot 101\\ 992 & 1363 & 29\cdot 47\\ 985 & 1343 & 17\cdot 79\\ 978 & 1315 & 5\cdot 263\\ 977 & 1337 & 7\cdot 191\\ 975 & 1331 & 11^{3} \\ 974 & 1345 & 5\cdot 269\\ 972 & 1369 & 37^{2} \\ 968 & 1345 & 5\cdot 269\\ 967 & 1325 & 5^{2} \cdot 53\\ 961 & 1343 & 17\cdot 79\\ 958 & 1393 & 7\cdot 199\\ 957 & 1331 & 11^{3} \\ 952 & 1285 & 5\cdot 257\\ 951 & 1241 & 17\cdot 73\\ 946 & 1285 & 5\cdot 257\\ 945 & 1295 & 5\cdot 7\cdot 37\\ 944 & 1309 & 7\cdot 11\cdot 17\\ 939 & 1313 & 13\cdot 101\\ 936 & 1261 & 13\cdot 97\\ 935 & 1247 & 29\cdot 43\\ 934 & 1177 & 11\cdot 107\\ 933 & 1169 & 7\cdot 167\\ 930 & 1333 & 31\cdot 43\\ 923 & 1265 & 5\cdot 11\cdot 23\\ 920 & 1309 & 7\cdot 11\cdot 17\\ 918 & 1225 & 5^{2} \cdot 7^{2} \\ 917 & 1175 & 5^{2} \cdot 47\\ 907 & 1199 & 11\cdot 109\\ 905 & 1211 & 7\cdot 173\\ 903 & 1205 & 5\cdot 241\\ 901 & 1235 & 5\cdot 13\cdot 19\\ 899 & 1157 & 13\cdot 89\\ 894 & 1225 & 5^{2} \cdot 7^{2} \\ 892 & 1339 & 13\cdot 103\\ 890 & 1273 & 19\cdot 67\\ 889 & 1235 & 5\cdot 13\cdot 19\\ 888 & 1207 & 17\cdot 71\\ 887 & 1175 & 5^{2} \cdot 47\\ 885 & 1169 & 7\cdot 167\\ 881 & 1175 & 5^{2} \cdot 47\\ 880 & 1195 & 5\cdot 239\\ 878 & 1183 & 7\cdot 13^{2} \\ 870 & 1081 & 23\cdot 47\\ 868 & 1141 & 7\cdot 163\\ 866 & 1183 & 7\cdot 13^{2} \\ 864 & 1189 & 29\cdot 41\\ 861 & 1241 & 17\cdot 73\\ 856 & 1141 & 7\cdot 163\\ 855 & 1115 & 5\cdot 223\\ 854 & 1147 & 31\cdot 37\\ 851 & 1139 & 17\cdot 67\\ 850 & 1177 & 11\cdot 107\\ 846 & 1189 & 29\cdot 41\\ 841 & 1127 & 7^{2} \cdot 23\\ 839 & 1121 & 19\cdot 59\\ 837 & 1133 & 11\cdot 103\\ 836 & 1147 & 31\cdot 37\\ 830 & 1111 & 11\cdot 101\\ 829 & 1127 & 7^{2} \cdot 23\\ 826 & 1141 & 7\cdot 163\\ 825 & 1133 & 11\cdot 103\\ 824 & 1147 & 31\cdot 37\\ 821 & 1139 & 17\cdot 67\\ 820 & 1177 & 11\cdot 107\\ 815 & 1157 & 13\cdot 89\\ 801 & 1043 & 7\cdot 149\\ 799 & 1073 & 29\cdot 37\\ 791 & 1139 & 17\cdot 67\\ 790 & 1105 & 5\cdot 13\cdot 17\\ 789 & 1043 & 7\cdot 149\\ 788 & 1003 & 17\cdot 59\\ 785 & 995 & 5\cdot 199\\ 783 & 1115 & 5\cdot 223\\ 781 & 1055 & 5\cdot 211\\ 777 & 1115 & 5\cdot 223\\ 776 & 1057 & 7\cdot 151\\ 775 & 1055 & 5\cdot 211\\ 769 & 1001 & 7\cdot 11\cdot 13\\ 768 & 1045 & 5\cdot 11\cdot 19\\ 767 & 995 & 5\cdot 199\\ 764 & 1075 & 5^{2} \cdot 43\\ 754 & 1015 & 5\cdot 7\cdot 29\\ 753 & 1043 & 7\cdot 149\\ 751 & 965 & 5\cdot 193\\ 750 & 1027 & 13\cdot 79\\ 743 & 995 & 5\cdot 199\\ 739 & 1037 & 17\cdot 61\\ 737 & 1067 & 11\cdot 97\\ 734 & 1075 & 5^{2} \cdot 43\\ 733 & 1037 & 17\cdot 61\\ 732 & 1099 & 7\cdot 157\\ 727 & 1037 & 17\cdot 61\\ 720 & 955 & 5\cdot 191\\ 719 & 995 & 5\cdot 199\\ 706 & 925 & 5^{2} \cdot 37\\ 705 & 917 & 7\cdot 131\\ 702 & 901 & 17\cdot 53\\ 700 & 961 & 31^{2} \\ 697 & 965 & 5\cdot 193\\ 694 & 943 & 23\cdot 41\\ 693 & 935 & 5\cdot 11\cdot 17\\ 691 & 875 & 5^{3} \cdot 7\\ 689 & 959 & 7\cdot 137\\ 682 & 889 & 7\cdot 127\\ 674 & 913 & 11\cdot 83\\ 672 & 901 & 17\cdot 53\\ 671 & 905 & 5\cdot 181\\ 662 & 913 & 11\cdot 83\\ 658 & 835 & 5\cdot 167\\ 653 & 869 & 11\cdot 79\\ 649 & 875 & 5^{3} \cdot 7\\ 647 & 869 & 11\cdot 79\\ 641 & 869 & 11\cdot 79\\ 640 & 871 & 13\cdot 67\\ 629 & 725 & 5^{2} \cdot 29\\ 628 & 781 & 11\cdot 71\\ 623 & 833 & 7^{2} \cdot 17\\ 622 & 799 & 17\cdot 47\\ 621 & 791 & 7\cdot 113\\ 620 & 841 & 29^{2} \\ 619 & 875 & 5^{3} \cdot 7\\ 617 & 851 & 23\cdot 37\\ 614 & 841 & 29^{2} \\ 613 & 767 & 13\cdot 59\\ 608 & 841 & 29^{2} \\ 605 & 851 & 23\cdot 37\\ 603 & 845 & 5\cdot 13^{2} \\ 602 & 841 & 29^{2} \\ 596 & 805 & 5\cdot 7\cdot 23\\ 589 & 731 & 17\cdot 43\\ 574 & 799 & 17\cdot 47\\ 571 & 803 & 11\cdot 73\\ 563 & 707 & 7\cdot 101\\ 562 & 781 & 11\cdot 71\\ 561 & 791 & 7\cdot 113\\ 557 & 689 & 13\cdot 53\\ 555 & 791 & 7\cdot 113\\ 554 & 805 & 5\cdot 7\cdot 23\\ 551 & 707 & 7\cdot 101\\ 541 & 713 & 23\cdot 31\\ 535 & 785 & 5\cdot 157\\ 534 & 775 & 5^{2} \cdot 31\\ 532 & 781 & 11\cdot 71\\ 531 & 737 & 11\cdot 67\\ 528 & 721 & 7\cdot 103\\ 522 & 703 & 19\cdot 37\\ 520 & 745 & 5\cdot 149\\ 513 & 737 & 11\cdot 67\\ 511 & 695 & 5\cdot 139\\ 510 & 667 & 23\cdot 29\\ 509 & 635 & 5\cdot 127\\ 505 & 713 & 23\cdot 31\\ 504 & 649 & 11\cdot 59\\ 501 & 665 & 5\cdot 7\cdot 19\\ 500 & 679 & 7\cdot 97\\ 496 & 655 & 5\cdot 131\\ 495 & 665 & 5\cdot 7\cdot 19\\ 492 & 667 & 23\cdot 29\\ 488 & 679 & 7\cdot 97\\ 486 & 649 & 11\cdot 59\\ 476 & 715 & 5\cdot 11\cdot 13\\ 475 & 731 & 17\cdot 43\\ 474 & 703 & 19\cdot 37\\ 473 & 707 & 7\cdot 101\\ 466 & 583 & 11\cdot 53\\ 461 & 635 & 5\cdot 127\\ 457 & 623 & 7\cdot 89\\ 450 & 559 & 13\cdot 43\\ 440 & 625 & 5^{4} \\ 435 & 629 & 17\cdot 37\\ 433 & 605 & 5\cdot 11^{2} \\ 431 & 581 & 7\cdot 83\\ 428 & 589 & 19\cdot 31\\ 427 & 605 & 5\cdot 11^{2} \\ 423 & 611 & 13\cdot 47\\ 421 & 551 & 19\cdot 29\\ 417 & 575 & 5^{2} \cdot 23\\ 416 & 589 & 19\cdot 31\\ 414 & 559 & 13\cdot 43\\ 398 & 553 & 7\cdot 79\\ 397 & 551 & 19\cdot 29\\ 394 & 511 & 7\cdot 73\\ 392 & 517 & 11\cdot 47\\ 391 & 515 & 5\cdot 103\\ 389 & 545 & 5\cdot 109\\ 387 & 485 & 5\cdot 97\\ 379 & 497 & 7\cdot 71\\ 374 & 535 & 5\cdot 107\\ 373 & 515 & 5\cdot 103\\ 371 & 473 & 11\cdot 43\\ 366 & 505 & 5\cdot 101\\ 361 & 551 & 19\cdot 29\\ 358 & 529 & 23^{2} \\ 354 & 505 & 5\cdot 101\\ 352 & 475 & 5^{2} \cdot 19\\ 346 & 493 & 17\cdot 29\\ 344 & 535 & 5\cdot 107\\ 343 & 515 & 5\cdot 103\\ 340 & 475 & 5^{2} \cdot 19\\ 338 & 445 & 5\cdot 89\\ 336 & 469 & 7\cdot 67\\ 335 & 473 & 11\cdot 43\\ 334 & 475 & 5^{2} \cdot 19\\ 329 & 455 & 5\cdot 7\cdot 13\\ 326 & 445 & 5\cdot 89\\ 317 & 437 & 19\cdot 23\\ 314 & 391 & 17\cdot 23\\ 308 & 427 & 7\cdot 61\\ 296 & 391 & 17\cdot 23\\ 284 & 355 & 5\cdot 71\\ 282 & 415 & 5\cdot 83\\ 277 & 335 & 5\cdot 67\\ 276 & 361 & 19^{2} \\ 270 & 361 & 19^{2} \\ 268 & 385 & 5\cdot 7\cdot 11\\ 261 & 323 & 17\cdot 19\\ 255 & 377 & 13\cdot 29\\ 254 & 355 & 5\cdot 71\\ 249 & 305 & 5\cdot 61\\ 243 & 323 & 17\cdot 19\\ 241 & 335 & 5\cdot 67\\ 240 & 361 & 19^{2} \\ 237 & 341 & 11\cdot 31\\ 234 & 325 & 5^{2} \cdot 13\\ 231 & 323 & 17\cdot 19\\ 230 & 355 & 5\cdot 71\\ 227 & 329 & 7\cdot 47\\ 225 & 287 & 7\cdot 41\\ 216 & 289 & 17^{2} \\ 213 & 323 & 17\cdot 19\\ 204 & 253 & 11\cdot 23\\ 192 & 253 & 11\cdot 23\\ 190 & 259 & 7\cdot 37\\ 188 & 265 & 5\cdot 53\\ 186 & 289 & 17^{2} \\ 182 & 247 & 13\cdot 19\\ 172 & 259 & 7\cdot 37\\ 169 & 209 & 11\cdot 19\\ 163 & 209 & 11\cdot 19\\ 160 & 205 & 5\cdot 41\\ 159 & 215 & 5\cdot 43\\ 157 & 245 & 5\cdot 7^{2} \\ 156 & 217 & 7\cdot 31\\ 155 & 221 & 13\cdot 17\\ 150 & 235 & 5\cdot 47\\ 147 & 215 & 5\cdot 43\\ 143 & 185 & 5\cdot 37\\ 141 & 215 & 5\cdot 43\\ 139 & 209 & 11\cdot 19\\ 131 & 203 & 7\cdot 29\\ 127 & 155 & 5\cdot 31\\ 118 & 169 & 13^{2} \\ 114 & 145 & 5\cdot 29\\ 111 & 143 & 11\cdot 13\\ 110 & 121 & 11^{2} \\ 109 & 119 & 7\cdot 17\\ 108 & 145 & 5\cdot 29\\ 105 & 125 & 5^{3} \\ 104 & 121 & 11^{2} \\ 100 & 115 & 5\cdot 23\\ 93 & 125 & 5^{3} \\ 88 & 115 & 5\cdot 23\\ 75 & 125 & 5^{3} \\ 62 & 85 & 5\cdot 17\\ 59 & 77 & 7\cdot 11\\ 56 & 85 & 5\cdot 17\\ 53 & 77 & 7\cdot 11\\ 49 & 65 & 5\cdot 13\\ 27 & 35 & 5\cdot 7\\ 22 & 25 & 5^{2} \\ 16 & 25 & 5^{2} \\ \hline \end{array}$$

I generated this list with Scheme. Here is the code

Code (Text):

#lang racket
(require math)

(define (sum-of-digits x)
(if (= x 0) 0
(+ (modulo x 10)
(sum-of-digits (/ (- x (modulo x 10)) 10)))))

(define (sum-of-odd-digits x)
(if (= x 0) 0
(if (odd? (modulo x 10))
(+ (modulo x 10)
(sum-of-odd-digits (/ (- x (modulo x 10)) 10)))
(sum-of-odd-digits (/ (- x (modulo x 10)) 10)))))

(define (Print-Prime-Decomp n)
(define (Print-Prime-Decomp-iter Div Exp)
(cond [(not (empty? Div)) (fprintf (current-output-port) "~a" (car Div))
(cond [(not (= (car Exp) 1)) (fprintf (current-output-port) "^")
(fprintf (current-output-port) "{~a} " (car Exp))])
(cond [(not (empty? (cdr Div))) (fprintf (current-output-port) "\\cdot ")])
(Print-Prime-Decomp-iter (cdr Div) (cdr Exp))]))
(cond [(= n 1) (fprintf (current-output-port) "1 ")])
(Print-Prime-Decomp-iter (prime-divisors n) (prime-exponents n)))

(define (Counterex n)
(define x (sum-of-digits (expt 2 n)))
(cond [(and (odd? x) (not (prime? x)))
(fprintf (current-output-port) "~a & ~a & " n x)
(Print-Prime-Decomp x)
(fprintf (current-output-port) "\\\\ \n")])
(if (> n 1)
(Counterex (- n 1))
(print "end"))
)

(Counterex 1000)

You can try this yourself by downloading the following program and pasting the above code in it: http://racket-lang.org/

Last edited: May 28, 2014
4. May 27, 2014

### willem2

The reason this worked for small powers of 2 is that the number produced can't be divisible by 2 or 3.

If you have an odd number of odd digits, the sum of the digits must be odd as well.
Powers of two aren't divisible by 3, so the sum of their digits can't be divisible by 3.

The lowest digit sum that can be produced that isn't a prime is 25, and indeed 2^16 = 65536, and 6+5+5+3+6 = 25.

5. May 27, 2014

### Z.L.

Thanks for the criticism! I didn't really have my hopes too high, but I appreciate the time taken to figure out the fails.

6. May 28, 2014

### Staff: Mentor

Also note that your original post failed to state you tried it for numbers in decimal representation (as opposed to octal, hexadecimal, whatever base numbers). That's always a sure sign someone have not taken everything into account.

7. May 28, 2014

### PeroK

What if you take the sum only of the odd digits?

8. May 28, 2014

### PeroK

What if you take the sum only of the odd digits?

... doesn't work. Interesting idea, though!

9. May 28, 2014

### micromass

Counterexamples for this:

$$\begin{array}{|l|l|l|l|} \hline n & 2^n & \text{Sum of digits} & \text{Prime Decomposition}\\ \hline 100 & 1267650600228229401496703205376 & 57 & 3\cdot 19\\ 96 & 79228162514264337593543950336 & 81 & 3^{4} \\ 94 & 19807040628566084398385987584 & 63 & 3^{2} \cdot 7\\ 93 & 9903520314283042199192993792 & 99 & 3^{2} \cdot 11\\ 92 & 4951760157141521099596496896 & 93 & 3\cdot 31\\ 89 & 618970019642690137449562112 & 63 & 3^{2} \cdot 7\\ 88 & 309485009821345068724781056 & 55 & 5\cdot 11\\ 87 & 154742504910672534362390528 & 63 & 3^{2} \cdot 7\\ 75 & 37778931862957161709568 & 81 & 3^{4} \\ 69 & 590295810358705651712 & 63 & 3^{2} \cdot 7\\ 66 & 73786976294838206464 & 45 & 3^{2} \cdot 5\\ 63 & 9223372036854775808 & 49 & 7^{2} \\ 59 & 576460752303423488 & 33 & 3\cdot 11\\ 53 & 9007199254740992 & 65 & 5\cdot 13\\ 52 & 4503599627370496 & 57 & 3\cdot 19\\ 49 & 562949953421312 & 45 & 3^{2} \cdot 5\\ 39 & 549755813888 & 35 & 5\cdot 7\\ 38 & 274877906944 & 39 & 3\cdot 13\\ 35 & 34359738368 & 33 & 3\cdot 11\\ 34 & 17179869184 & 35 & 5\cdot 7\\ 29 & 536870912 & 25 & 5^{2} \\ 18 & 262144 & 1 & 1 \\ 12 & 4096 & 9 & 3^{2} \\ 10 & 1024 & 1 & 1 \\ 7 & 128 & 1 & 1 \\ 4 & 16 & 1 & 1 \\ \hline \end{array}$$

10. May 31, 2014

### brjense

Might have a few more ways for you to find prime. The first one I just thought of the other day when hearing something about pi. If pi is infinite then every possible number sequence must be in the number line to infinity so therefore every prime must be in a sequential order somewhere in the line. The trick here is finding where it starts and well theoretically it should go on to infinity. The second idea I have would be to use even numbers to make an equation with dividing the numbers by two since all primes can be doubled and I think it would be easier to make an equation that can find primes that have been halved from their x2, still toying with the idea of some even prime numbers(numbers that can only be divided by 1, 2, their half and the number itself. Like 22, only 1, 2, 11 and itself can go into it). Another thought is to have a number line and use a wave going through the number line. 1 would be going through every number, 2 through every even, taking away every even from the prime line. Then with 3 and 7(sorta mirrors of each other three away from the nearest zero and three(4,5,6) away from each other). Anyway the off numbers missed by 3 and 7 would be a new starting point for a new wave to go through the numbers, like 11, 13 well you probably know the primes. Anyways hope this helps with your search.

11. May 31, 2014

### Staff: Mentor

Every possible finite sequence is in there. There will be "235711", but not "235711...." going on forever.

All those approaches have been tried centuries ago, without success.

12. May 31, 2014

### micromass

Sure, $\pi$ is infinite in the sense that is has an infinite number of nonrepeating decimals. But that does not mean that every possible number sequence must occur in $\pi$!

13. May 31, 2014

### Nick O

We don't actually know this, do we?

In any case, even if it did have every infinite sequence (which I think is impossible for a countably infinite decimal expansion), there would be no way of knowing whether you had found that sequence or something close to it.

The set of all primes can be made into a sequence, but so can the union of the set of the first N primes and the set of odd integers greater than the Nth prime.

14. May 31, 2014

### micromass

Normality of $\pi$ would certainly imply it, but we don't know normality. The weaker fact if any finite sequence appears in $\pi$ is saying that $\pi$ is a rich or disjunctive number http://oeis.org/wiki/Disjunctive_numbers It is not known whether $\pi$ is disjunctive.

15. May 31, 2014

### Nick O

Thanks!

Here's an nice proof that pi cannot contain all infinite sequences, without going into cardinality:

Suppose the decimal expansion of pi contains every infinite sequence of digits. Then the decimal expansion of pi must contain the sequence 000... Then pi must be rational.

This contradicts the fact that pi is irrational, therefore the decimal expansion of pi does not contain every infinite sequence of digits.

16. May 31, 2014

### brjense

So would it be safe then to say that infinite's have a limit if the prime number infinite cannot be found within it? A limit of one infinite is another infinite

17. May 31, 2014

### Nick O

I'm not sure what you mean. Pi does contain an infinite number of distinct infinite sequences (e.g., 314159..., 14159..., 4159..., 159..., 59..., 9...), but that doesn't mean it contains every infinite sequence.

There are at least two kinds of infinity, called countable and uncountable. I would post links if I weren't posting from my phone, but I recommend looking into it. It's a fascinating a mind-boggling concept.

There is a countably infinite number of digits in pi, but there is an uncountably infinite number of infinite sets (of either kind). Countable sets cannot contain every uncountable set.

18. May 31, 2014

### brjense

I will look into those books thanks for posting them. I guess what I am trying to say is that an infinite cannot be defined with another infinite so that would bring a limit to what an infinite may define so infinite's do have a limit and with that infinite's are not infinite?. Still sorta lost in thought on my description sorry for the confusion

19. May 31, 2014

### Nick O

I suppose the problem here is that I'm not sure what you mean by "define" and "limit" in this case. Certainly there are rules that govern infinite sequences, though.

Let's look at a really simple and easy-to-understand infinite sequence. 10/9 = 1.1111111...

There is exactly one infinite sequence of digits in 1.111111..., which is 1,1,1,1,1,1... It can begin on the first 1, the second 1, or whatever 1 you like, but in the sequence will be identical no matter where it begins.

Now, let's look at (10/9) + 1 = 2.1111111..... Now we have two infinite sequences of digits. If you start at the 2, you have 2,1,1,1,1.... If you start at any of the 1s, you have 1,1,1,1,1....

You could then look at (10/9) + 2.1, which gives you 3.2111111, which contains three infinite sequences. If fact, you can go on forever and obtain an arbitrary number of infinite sequences. But, each of these sequences follows certain rules, and we cannot produce every sequence in this manner.

Now, back to pi. Pi does not repeat like 10/9 does, so it contains a truly infinite number of sequences. But, just like (10/9), the sequences are restricted to a certain class of sequences. We already know that 0,0,0,0.... is not in that class. So, in this sense, you can say that there are restrictions as to what sort of sequences you can get from this infinite set of sequences.

I'm sorry, I'm rambling a bit.

EDIT:

I guess what I'm trying to say is that the sequences are infinite in number, but not boundless in terms of form.

20. May 31, 2014

### Staff: Mentor

You are right, sorry. Yes, there is no proof yet so we cannot be sure, but I would be extremely surprised if it would be different.

There is no "prime number infinite". And what do you mean with "infinite's have a limit"? What is "an infinite", and a limit of what?
Whatever "an infinite" is supposed to mean, it is wrong: let a be "an infinite" and define b=a.

21. May 31, 2014

### Nick O

I was just surprised because I had never heard or thought about that possibility before. It makes sense, though.