Weird prime analyzing

Projects General Guidance
1

I'm working on this sketch that goes around and proves the Goldbach's conjecture (Goldbach's conjecture - Wikipedia). I want it to find the prime numbers (which are loaded in a list) that can add up to the number. But the Serial monitor display's:

GoldBach's Conjunction Analyzer Booting...
Bootup Complete
Analyzing:
1
Less Than 2! NO GO!
Analyzing:
2
Less Than 2! NO GO!
Analyzing:
3
More Than 2! GO!
Not Even! NO GO!
Analyzing:
4
More Than 2! GO!
Even! GO!
Finding Prime Addends...
Found Prime Addends!
2 + 1

1 is not even in the list of primes! What is wrong with This???
Any Ideas and tips will be well appreciated!

GoldBach_s_Conjunction.ino (1.41 KB)

2

Did you write the sketch or did you find it published somewhere ?

I guess it is just filtering out candidate numbers to be used in the search for the 2 prime numbers which, when added together, equal that number. But you must say what you are expecting. The 1 which you mentioned is not in the prime table, it is a integer candidate which is not going to be submitted for the prime number addition test.

The Arduino is not a renowned number cruncher so is an unusual choice to test out such mathematical theorems.

3

It is possible to make it work, but you have to be careful how to write code. If your code is a big mess, so will the result be ::slight_smile: I mean the text layout of the code. Use the same style of writing the code and set every indent, every space, every comma, every '{' and '}' at the right place. Or you can press Ctrl+T, that is the auto-text-format function.

You have declared 'PP' twice.
You forgot that '=' means 'assign' and '==' means compare 'if equal'. Find the single '=' in a if-statement.
Using the "return" in the Arduino loop() function indicates lack of programming skills :smiley_cat: Can you try to write a sketch without it ?

Fix the bug in the if-statement and perhaps you can make a few small adjustments for printing the output.
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
...
238 = 5 + 233

Is using the table perhaps some kind of cheating ? Can you make it without using the table ? If you remove all the delay(), and use unsigned long for the numbers, you can run it for a while at full speed.

4

I have something running, but I don't know if it is correct:

2000 = 3 + 1997
2000 = 7 + 1993
2000 = 13 + 1987
2000 = 67 + 1933
2000 = 127 + 1873
2000 = 139 + 1861
2000 = 199 + 1801
2000 = 211 + 1789
2000 = 223 + 1777
2000 = 241 + 1759
2000 = 277 + 1723
2000 = 307 + 1693
2000 = 331 + 1669
2000 = 337 + 1663
2000 = 373 + 1627
2000 = 379 + 1621
2000 = 421 + 1579
2000 = 433 + 1567
2000 = 457 + 1543
2000 = 541 + 1459
2000 = 547 + 1453
2000 = 571 + 1429
2000 = 577 + 1423
2000 = 601 + 1399
2000 = 619 + 1381
2000 = 673 + 1327
2000 = 709 + 1291
2000 = 751 + 1249
2000 = 769 + 1231
2000 = 787 + 1213
2000 = 829 + 1171
2000 = 877 + 1123
2000 = 883 + 1117
2000 = 907 + 1093
2000 = 937 + 1063
2000 = 967 + 1033
2000 = 991 + 1009
5

Koepel:
I have something running, but I don't know if it is correct:

2000 = 3 + 1997

2000 = 7 + 1993
2000 = 13 + 1987
2000 = 67 + 1933
2000 = 127 + 1873
2000 = 139 + 1861
2000 = 199 + 1801
2000 = 211 + 1789
2000 = 223 + 1777
2000 = 241 + 1759
2000 = 277 + 1723
2000 = 307 + 1693
2000 = 331 + 1669
2000 = 337 + 1663
2000 = 373 + 1627
2000 = 379 + 1621
2000 = 421 + 1579
2000 = 433 + 1567
2000 = 457 + 1543
2000 = 541 + 1459
2000 = 547 + 1453
2000 = 571 + 1429
2000 = 577 + 1423
2000 = 601 + 1399
2000 = 619 + 1381
2000 = 673 + 1327
2000 = 709 + 1291
2000 = 751 + 1249
2000 = 769 + 1231
2000 = 787 + 1213
2000 = 829 + 1171
2000 = 877 + 1123
2000 = 883 + 1117
2000 = 907 + 1093
2000 = 937 + 1063
2000 = 967 + 1033
2000 = 991 + 1009

I think that may be the master stroke which will change Goldbach's conjecture into Goldbach's theorem. And all done with power of an Arduino :slight_smile:

6

Fun!
as one prime goes up the other goes down, can be used to make searching quite fast

This is approx. what fits in an UNO.

//    FILE: goldbach02.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.0.2
// PURPOSE: fun

uint32_t start, stop;

uint16_t primes[] =
{
  2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
  31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
  73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
  127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
  179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
  233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
  283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
  353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
  419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
  467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
  547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
  607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
  661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
  739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
  811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
  877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
  947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
  1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
  1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
  1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
  1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
  1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
  1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
  1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
  1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
  1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
  1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
  1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
  1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
  1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
  1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
  2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
  2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
  2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
  2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
  2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
  2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
  2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
  2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
  2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
  2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,
  2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
  2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
  3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
  3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,
  3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
  3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
  3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
  3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,
  3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571,
  3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
  3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
  3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,
  3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
  3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
  4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
  4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139,
  4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,
  4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
  4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
  4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493,
  4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583,
  4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
  4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
  4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831,
  4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
  4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003,
  5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
  5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179,
  5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279,
  5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387,
  5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
  5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521,
  5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639,
  5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693,
  5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
  5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857,
  5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939,
  5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053,
  6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
  6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221,
  6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301,
  6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367,
  6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
  6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571,
  6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673,
  6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761,
  // 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
  //  6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917,
  //  6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997,
};

void setup()
{
  Serial.begin(500000);
  // Serial.println(__FILE__);

  start = millis();
  for (uint16_t i = 2; i <= (6761 * 2); i = i + 2)
  {
    Serial.print(i);
    int n = 0;
    int a = 0, b = sizeof(primes) / sizeof(primes[0]);

    while ( b >= a)
    {
      uint16_t sum = primes[a] + primes[b];
      if (i < sum) b--;
      else if (i > sum) a++;
      else if (i == sum)
      {
        Serial.print(" = ");
        Serial.print(primes[a]);
        Serial.print('+');
        Serial.print(primes[b]);
        n++;
        a++;
        b--;
      }
    }
    Serial.print("\t(");
    Serial.print(n);
    Serial.println(")");
  }
  stop = millis();
  Serial.print("TIME: ");
  Serial.println(stop - start);
}

void loop()
{
}
7

I tried to get rid of the table, but that is slow.

8

I had two ideas:

  1. creating a prime table based upon the difference between two successive primes = primeGaps. As this is allways a multiple of two, storing half the distance would be sufficient. Of course we can skip 0 in the distance coding. In a nibble 16 distances could be encoded, so 2..32. However a primeGap of 33 allready occurs around 1327, so a whole byte should be used. One byte per prime means that for ~1900 primes a primeGap table upto 16273, can be made. The coding scheme could be made "more clever" to hold more but that will be more complex too. So I had another idea

  2. generating a prime table and store them in a bitArray. Given ~1900 bytes for a table means it can hold 3800 * 8 odd numbers starting at 3 so upto 30401. That maximizes the storages of the primes. One can test the conjecture at least up to 30401. This is pretty straightforward coding.

So maybe when time permits I'll chase idea 2.

9

I think that when I let my Uno run for a week, it might be further than 30401.

Kev1n8088 started this thread, he has not replied yet, and we are having fun with this mathematical challenge :stuck_out_tongue: