Even numbers which cannot be expressed as the sum of two twin primes
Even numbers which cannot be expressed as the sum of two twin primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
In 1742, Goldbach and Euler corresponded about what is now known as the Goldbach Conjecture: that all even integers greater than 2 can be written as the sum of two primes.
In 2000, Henry Dubner proposed a stronger conjecture: that every even integer greater than 4208 can be written as the sum of two twin primes.
At the time the Goldbach conjecture was made, 1 was considered a prime number - this is not so now. So, the Goldbach conjecture was originally that all even natural numbers could be written as the sum of two primes.
- Task
- Find and display the positive even integers that cannot be expressed as the sum of two twin primes, up to a limit of 5,000.
- E.g.: The first 3 twin primes are 3, 5 and 7, so 6 (3+3), 8 (5+3) and 10 (5+5 or 7+3) can be formed but 2 and 4 cannot.
- Show the numbers that cannot be formed by summing two twin primes when 1 is treated as a prime (and so a twin prime).
- Note
- For the purposes of this task, twin prime refers to a prime that is 2 more or less than another prime, not the pair of primes.
- Stretch
- Verify that there no more such numbers up to 10,000 or more, as you like (note it has been verified up to at least 10^9).
- See also
ALGOL 68
BEGIN # find even numbers that are not the sum of two twin primes #
INT max number = 100 000; # maximum number we will consider #
[ 0 : max number ]BOOL prime; # sieve the primes to max number #
prime[ 0 ] := prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
prime[ 2 ] := FALSE; # restrict the sieve to twin primes only #
FOR i FROM 3 BY 2 TO max number - 2 DO
IF prime[ i ] AND NOT prime[ i - 2 ] AND NOT prime[ i + 2 ] THEN
prime[ i ] := FALSE
FI
OD;
# construct a table of the even numbers that can be formed by summing #
# two twin primes #
[ 1 : max number ]BOOL p2sum; FOR i TO UPB p2sum DO p2sum[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO max number DO
IF prime[ i ] THEN
FOR j FROM i TO ( max number + 1 ) - i DO
IF prime[ j ] THEN p2sum[ i + j ] := TRUE FI
OD
FI
OD;
# print the even numbers which aren't the sum of 2 twin primes #
print( ( "Non twin prime sums:", newline ) );
INT count := 0;
INT per line = 10;
FOR i FROM 2 BY 2 TO max number DO
IF NOT p2sum[ i ] THEN
print( ( whole( i, - 6 ) ) );
IF ( count +:= 1 ) MOD per line = 0 THEN print( ( newline ) ) FI
FI
OD;
IF count MOD per line /= 0 THEN print( ( newline ) ) FI;
print( ( "Found ", whole( count, 0 ), newline, newline ) );
# adjust the table as if 1 was a twin prime #
p2sum[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO max number DO
IF prime[ i ] THEN p2sum[ i + 1 ] := TRUE FI
OD;
# print the revised even numbers which aren't the sum of 2 twin primes #
print( ( "Non twin prime sums (including 1):", newline ) );
count := 0;
FOR i FROM 2 BY 2 TO max number DO
IF NOT p2sum[ i ] THEN
print( ( whole( i, - 6 ) ) );
IF ( count +:= 1 ) MOD per line = 0 THEN print( ( newline ) ) FI
FI
OD;
IF count MOD per line /= 0 THEN print( ( newline ) ) FI;
print( ( "Found ", whole( count, 0 ), newline ) )
END- Output:
Non twin prime sums:
2 4 94 96 98 400 402 404 514 516
518 784 786 788 904 906 908 1114 1116 1118
1144 1146 1148 1264 1266 1268 1354 1356 1358 3244
3246 3248 4204 4206 4208
Found 35
Non twin prime sums (including 1):
94 96 98 400 402 404 514 516 518 784
786 788 904 906 908 1114 1116 1118 1144 1146
1148 1264 1266 1268 1354 1356 1358 3244 3246 3248
4204 4206 4208
Found 33
Julia
using Primes
""" Even numbers which cannot be expressed as the sum of two twin primes """
function nonpairsums(;include1=false, limit=20_000)
tpri = primesmask(limit + 2)
for i in 1:limit
tpri[i] && (i > 2 && !tpri[i - 2]) && !tpri[i + 2] && (tpri[i] = false)
end
include1 && (tpri[1] = true)
twinsums = falses(limit * 2)
for i in 1:limit-2, j in 1:limit-2
if tpri[i] && tpri[j]
twinsums[i + j] = true
end
end
return [i for i in 2:2:limit if twinsums[i] == false]
end
println("Non twin prime sums:")
foreach(p -> print(lpad(p[2], 6), p[1] % 10 == 0 ? "\n" : ""), pairs(nonpairsums()))
println("\nNon twin prime sums (including 1):")
foreach(p -> print(lpad(p[2], 6), p[1] % 10 == 0 ? "\n" : ""), pairs(nonpairsums(include1 = true)))
- Output:
Non twin prime sums:
2 4 94 96 98 400 402 404 514 516
518 784 786 788 904 906 908 1114 1116 1118
1144 1146 1148 1264 1266 1268 1354 1356 1358 3244
3246 3248 4204 4206 4208
Non twin prime sums (including 1):
94 96 98 400 402 404 514 516 518 784
786 788 904 906 908 1114 1116 1118 1144 1146
1148 1264 1266 1268 1354 1356 1358 3244 3246 3248
4204 4206 4208
Raku
my $threshold = 10000;
my @twins = unique flat (3..$threshold).grep(&is-prime).map: { $_, $_+2 if ($_+2).is-prime };
my @sums;
map {@sums[$_]++}, (@twins X+ @twins);
display 'Non twin prime sums:',
@sums[^$threshold].kv.map: -> $k, $v { $k if ($k %% 2) && !$v };
@sums = Empty;
@twins.push: 1;
map {@sums[$_]++}, (@twins X+ @twins);
display "\nNon twin prime sums (including 1):",
@sums[^$threshold].kv.map: -> $k, $v { $k if ($k %% 2) && !$v };
sub display ($msg, @p) { put "$msg\n" ~ @p.skip(1).batch(10)».fmt("%4d").join: "\n" }
- Output:
Non twin prime sums: 2 4 94 96 98 400 402 404 514 516 518 784 786 788 904 906 908 1114 1116 1118 1144 1146 1148 1264 1266 1268 1354 1356 1358 3244 3246 3248 4204 4206 4208 Non twin prime sums (including 1): 94 96 98 400 402 404 514 516 518 784 786 788 904 906 908 1114 1116 1118 1144 1146 1148 1264 1266 1268 1354 1356 1358 3244 3246 3248 4204 4206 4208