|
Problems & Puzzles:
Puzzles
Puzzle 1248
Pairs (p, 2^k) such that their sum is prime.
On Nov. 3, Giorgos Kalogeropoulos sent the following
nice puzzle:
|
|
Take the first n odd primes p {3,5,7,11,13,17...}.
Take the first n powers of two 2^k {2,4,8,16,32,64...} with
1<=k<=n.
Construct pairs (p, 2^k) such that their
sum is prime.
Your goal is to determine whether a perfect matching exists.
That is, a one-to-one pairing where every odd prime is matched
with a distinct power of two, and each sum p+2^k is prime.
Here is an example for n=5 wich has
eight perfect-matchings
The 8 perfect matchings for n=5 are
{{3, 2}, {7, 4}, {5, 8}, {13, 16}, {11, 32}},
{{3, 2}, {7, 4}, {11, 8}, {13, 16}, {5, 32}},
{{3, 2}, {13, 4}, {5, 8}, {7, 16}, {11, 32}},
{{3, 2}, {13, 4}, {11, 8}, {7, 16}, {5, 32}},
{{5, 2}, {7, 4}, {3, 8}, {13, 16}, {11, 32}},
{{5, 2}, {13, 4}, {3, 8}, {7, 16}, {11, 32}},
{{11, 2}, {7, 4}, {3, 8}, {13, 16}, {5, 32}},
{{11, 2}, {13, 4}, {3, 8}, {7,
16}, {5, 32}}
Q1. Find one perfect matching for the cases
n=6,7,8... and write it in the form of pairs.
Q2. Find the smallest value of n for which a
perfect matching does not exist.
Q3. Count the number of perfect matchings for
each n. First values for 1<=n<=6 are 1, 1, 2, 4, 8, 8...
Extend the sequence.
|
|
From Nov 29 to Dec 5, 2025 contributions came from Adam Stinchcombe,
Emmanuel Vantieghem, Michael Branicky, Gennady Gusev, Oscar Volpatti, Simon
Cavegn
***
Adam wrote:
p+2^42 is not prime until the 59th prime (58th odd prime), so there are no
perfect matchings for 42 through 57. I haven't verified that all counts
below 42 do have perfect matchings.
***
Emmanuel wrote:
Q1 :
n = 6
{{17, 2}, {3, 4}, {5, 8}, {13, 16}, {11, 32}, {7, 64}}
n = 7
{{17, 2}, {7, 4}, {3, 8}, {13, 16}, {5, 32}, {19, 64}, {11, 128}}
n = 8
{{17, 2}, {3, 4}, {5, 8}, {7, 16}, {11, 32}, {19, 64}, {23, 128}, {13, 256}}
n = 9
{{17, 2}, {3, 4}, {5, 8}, {7, 16}, {11, 32}, {19, 64}, {23, 128}, {13, 256},
{29, 512}}
n = 10
{17, 2}, {3, 4}, {5, 8}, {31, 16}, {11, 32}, {19, 64}, {23, 128}, {13, 256},
{29, 512}, {7, 1024}
n = 11
{{17, 2}, {7, 4}, {3, 8}, {31, 16}, {11, 32}, {19, 64}, {23, 128}, {13,
256}, {29, 512}, {37, 1024}, {5, 2048}
n = 12
{17, 2}, {37, 4}, {29, 8}, {31, 16}, {41, 32}, {19, 64}, {23, 128}, {13,
256}, {11, 512}, {7, 1024}, {5, 2048}, {3, 4096}
n = 13
{{41, 2}, {37, 4}, {23, 8}, {43, 16}, {29, 32}, {19, 64}, {3, 128}, {13,
256}, {11, 512}, {7, 1024}, {5, 2048}, {31, 4096}, {17, 8192}}
n = 14
{{41, 2}, {43, 4}, {29, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {11, 512}, {7, 1024}, {5, 2048}, {3, 4096}, {17, 8192}, {37, 16384}}
n = 15
{{41, 2}, {43, 4}, {53, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {29, 512}, {7, 1024}, {5, 2048}, {3, 4096}, {17, 8192}, {37, 16384},
{11, 32768}}
n = 16 : definitely no solution
n = 17
{{41, 2}, {43, 4}, {53, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {59, 512}, {7, 1024}, {5, 2048}, {61, 4096}, {17, 8192}, {37, 16384},
{11, 32768}, {3, 65536}, {29, 131072}}
n = 18
{{5, 2}, {3, 4}, {23, 8}, {31, 16}, {47, 32}, {19, 64}, {53, 128}, {13,
256}, {59, 512}, {37, 1024}, {41, 2048}, {61, 4096}, {17, 8192}, {67,
16384}, {11, 32768}, {7, 65536}, {29, 131072}, {43, 262144}}
n = 19
{{41, 2}, {67, 4}, {59, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {11, 512}, {7, 1024}, {5, 2048}, {61, 4096}, {17, 8192}, {37, 16384},
{71, 32768}, {3, 65536}, {29, 131072}, {43, 262144}, {53, 524288}}
n = 20
{{41, 2}, {19, 4}, {71, 8}, {31, 16}, {47, 32}, {73, 64}, {23, 128}, {13,
256}, {59, 512}, {67, 1024}, {5, 2048}, {61, 4096}, {17, 8192}, {37, 16384},
{11, 32768}, {3, 65536}, {29, 131072}, {43, 262144}, {53, 524288}, {7,
1048576}}
n = 21
{{59, 2}, {79, 4}, {71, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {11, 512}, {67, 1024}, {5, 2048}, {61, 4096}, {41, 8192}, {37, 16384},
{3, 32768}, {43, 65536}, {29, 131072}, {73, 262144}, {53, 524288}, {7,
1048576}, {17, 2097152}}
n = 22
{{71, 2}, {7, 4}, {23, 8}, {31, 16}, {47, 32}, {19, 64}, {3, 128}, {13,
256}, {11, 512}, {79, 1024}, {5, 2048}, {61, 4096}, {17, 8192}, {67, 16384},
{29, 32768}, {43, 65536}, {41, 131072}, {73, 262144}, {53, 524288}, {37,
1048576}, {59, 2097152}}
n = 23
{{71,2},{79,4},{89,8},{31,16},{47,32},{19,64},{23,128},{13,256},{59,512},{73,1024},{5,2048},{61,4096},{41,8192},{37,16384},{11,32768},{3,65536},{29,131072},{43,262144},{53,524288},{7,1048576},{17,2097152},{67,4194304},{83,8388608}}
n = 24
{{71,2},{79,4},{89,8},{31,16},{47,32},{19,64},{23,128},{13,256},{59,512},{73,1024},{5,2048},{61,4096},{41,8192},{37,16384},{11,32768},{97,65536},{29,131072},{3,262144},{53,524288},{7,1048576},{17,2097152},{67,4194304},{83,8388608},{43,16777216}}
n = 25
{{59,2},{79,4},{23,8},{31,16},{47,32},{19,64},{83,128},{13,256},{89,512},{73,1024},{5,2048},{61,4096},{71,8192},{37,16384},{101,32768},{97,65536},{29,131072},{3,262144},{53,524288},{7,1048576},{17,2097152},{67,4194304},{11,8388608},{43,16777216},{41,33554432}}
n = 26
{{59,2},{79,4},{23,8},{13,16},{47,32},{19,64},{83,128},{61,256},{89,512},{37,1024},{5,2048},{31,4096},{71,8192},{103,16384},{101,32768},{73,65536},{29,131072},{3,262144},{53,524288},{7,1048576},{17,2097152},{67,4194304},{11,8388608},{43,16777216},{41,33554432},{97,67108864}}
n = 27
{{107,2},{79,4},{23,8},{13,16},{47,32},{19,64},{83,128},{61,256},{89,512},{37,1024},{5,2048},{31,4096},{17,8192},{103,16384},{101,32768},{73,65536},{29,131072},{3,262144},{53,524288},{7,1048576},{59,2097152},{67,4194304},{11,8388608},{43,16777216},{41,33554432},{97,67108864},{71,134217728}}
n = 28
{{5, 2}, {3, 4}, {11, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {7, 256},
{59, 512}, {79, 1024}, {83, 2048}, {61, 4096}, {17, 8192}, {103, 16384},
{29, 32768}, {43, 65536}, {41, 131072}, {109, 262144}, {101, 524288}, {13,
1048576}, {107, 2097152}, {67, 4194304}, {89, 8388608}, {73, 16777216}, {71,
33554432}, {97, 67108864}, {53, 134217728}, {37, 268435456}}
n = 29
{{5, 2}, {3, 4}, {11, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {7, 256},
{59, 512}, {79, 1024}, {113, 2048}, {61, 4096}, {17, 8192}, {103, 16384},
{29, 32768}, {43, 65536}, {41, 131072}, {109, 262144}, {101, 524288}, {13,
1048576}, {107, 2097152}, {67, 4194304}, {83, 8388608}, {73, 16777216}, {71,
33554432}, {97, 67108864}, {53, 134217728}, {37, 268435456}, {89,
536870912}}
n = 30
{{5, 2}, {3, 4}, {11, 8}, {31, 16}, {47, 32}, {7, 64}, {23, 128}, {13, 256},
{59, 512}, {79, 1024}, {113, 2048}, {61, 4096}, {17, 8192}, {103, 16384},
{29, 32768}, {43, 65536}, {41, 131072}, {109, 262144}, {101, 524288}, {127,
1048576}, {107, 2097152}, {67, 4194304}, {83, 8388608}, {73, 16777216}, {71,
33554432}, {97, 67108864}, {53, 134217728}, {37, 268435456}, {89,
536870912}, {19, 1073741824}}
n = 31, 32, 33, 34, 35 : the method I used (for the results of n > 17) gave
no solution.
Q2 : The smallest n for which there is definitely no solution is 16.
Q3 : The list of the number s of solutions definitely continues as follows
:
n 7 8 9 10 11 12 13 14 15 16
17
s 9 21 29 12 24 220 748 450 360 0 290
For n >= 18 my method was no longer exhaustive.
***
Michael wrote:
Q1: Here is one perfect
match
for each of n =
1, ...,
15
and n =
17.
1: ((3,
2),)
2: ((5,
2), (3,
4))
3: ((3,
2), (7,
4), (5,
8))
4: ((11,
2), (3,
4), (5,
8), (7,
16))
5: ((11,
2), (13,
4), (3,
8), (7,
16), (5,
32))
6: ((17,
2), (3,
4), (11,
8), (13,
16), (5,
32), (7,
64))
7: ((17,
2), (19,
4), (11,
8), (13,
16), (5,
32), (7,
64), (3,
128))
8: ((17,
2), (19,
4), (11,
8), (3,
16), (5,
32), (7,
64), (23,
128), (13,
256))
9: ((17,
2), (19,
4), (5,
8), (3,
16), (29,
32), (7,
64), (23,
128), (13,
256), (11,
512))
10: ((17,
2), (19,
4), (5,
8), (31,
16), (29,
32), (3,
64), (23,
128), (13,
256), (11,
512), (7,
1024))
11: ((17,
2), (37,
4), (3,
8), (31,
16), (29,
32), (19,
64), (23,
128), (13,
256), (11,
512), (7,
1024), (5,
2048))
12: ((17,
2), (3,
4), (5,
8), (37,
16), (29,
32), (19,
64), (23,
128), (13,
256), (11,
512), (7,
1024), (41,
2048), (31,
4096))
13: ((3,
2), (37,
4), (5,
8), (43,
16), (29,
32), (19,
64), (23,
128), (13,
256), (11,
512), (7,
1024), (41,
2048), (31,
4096), (17,
8192))
14: ((5,
2), (3,
4), (11,
8), (37,
16), (47,
32), (19,
64), (23,
128), (13,
256), (29,
512), (7,
1024), (41,
2048), (31,
4096), (17,
8192), (43,
16384))
15: ((5,
2), (3,
4), (53,
8), (37,
16), (47,
32), (19,
64), (23,
128), (13,
256), (11,
512), (7,
1024), (41,
2048), (31,
4096), (17,
8192), (43,
16384), (29,
32768))
16: [ no perfect matching found ]
17: ((5,
2), (3,
4), (53,
8), (13,
16), (47,
32), (19,
64), (23,
128), (61,
256), (59,
512), (37,
1024), (41,
2048), (31,
4096), (17,
8192), (43,
16384), (11,
32768), (7,
65536), (29,
131072))
Q2: n = 16
is the smallest value
with no perfect matching.
Also, for
42 <= n <=
1000, there are no perfect
matchings. For example, n = 42
has no perfect matching since p+2^42
is
not prime
for any prime
3 <= p <= prime(43).
Q3: Sequence of perfect matching counts
is
1,
1,
2,
4,
8,
8,
9,
21,
42,
12,
24,
220,
748,
450,
360,
0, ...
***
Gennady wrote:
Q1. (k - perfect-matchings).
n=6
{{17,2},{3,4},{5,8},{13,16},{11,32},{7,64}}
k=8
n=7
{{17,2},{7,4},{3,8},{13,16},{5,32},{19,64},{11,128}}
k=9
n=8
{{17,2},{3,4},{5,8},{7,16},{11,32},{19,64},{23,128},{13,256}}
k=21
n=9
{{17,2},{3,4},{5,8},{7,16},{11,32},{19,64},{23,128},{13,256},{29,512}}
k=42
n=10
{{17,2},{3,4},{5,8},{31,16},{11,32},{19,64},{23,128},{13,256},{29,512},{7,1024}}
k=12
n=11
{{17,2},{7,4},{3,8},{31,16},{11,32},{19,64},{23,128},{13,256},{29,512},{37,1024},{5,2048}}
k=24
n=12
{{17,2},{3,4},{5,8},{7,16},{11,32},{19,64},{23,128},{13,256},{29,512},{37,1024},{41,2048},{31,4096}}
k=220
n=13
{{3,2},{7,4},{5,8},{31,16},{11,32},{19,64},{23,128},{13,256},{29,512},{37,1024},{41,2048},{43,4096},{17,8192}}
k=748
n=14
{{5,2},{3,4},{11,8},{7,16},{47,32},{19,64},{23,128},{13,256},{29,512},{37,1024},{41,2048},{31,4096},{17,8192},{43,16384}}
k=450
n=15
{{5,2},{3,4},{23,8},{7,16},{47,32},{19,64},{53,128},{13,256},{11,512},{37,1024},{41,2048},{31,4096},{17,8192},{43,16384},{29,32768}}
k=360
n=16
k=0
n=17
{{5,2},{3,4},{23,8},{13,16},{47,32},{19,64},{53,128},{61,256},{59,512},{7,1024},{41,2048},{31,4096},{17,8192},{37,16384},{11,32768},{43,65536},{29,131072}}
k=496
n=18
{{5,2},{3,4},{23,8},{13,16},{47,32},{19,64},{53,128},{61,256},{59,512},{37,1024},{41,2048},{31,4096},{17,8192},{67,16384},{11,32768},{7,65536},{29,131072},{43,262144}}
k=1920
n=19
{{5,2},{3,4},{11,8},{13,16},{47,32},{19,64},{23,128},{61,256},{59,512},{37,1024},{41,2048},{31,4096},{17,8192},{67,16384},{29,32768},{7,65536},{71,131072},{43,262144},{53,524288}}
k=13080
n=20
{{5,2},{3,4},{11,8},{7,16},{47,32},{19,64},{23,128},{61,256},{59,512},{37,1024},{41,2048},{31,4096},{17,8192},{67,16384},{29,32768},{43,65536},{71,131072},{73,262144},{53,524288},{13,1048576}}
k=71504
n=21
{{3,2},{7,4},{5,8},{13,16},{47,32},{19,64},{23,128},{61,256},{11,512},{79,1024},{41,2048},{31,4096},{17,8192},{67,16384},{29,32768},{43,65536},{71,131072},{73,262144},{53,524288},{37,1048576},{59,2097152}}
k=63840
n=22
{{5,2},{3,4},{11,8},{7,16},{47,32},{19,64},{23,128},{61,256},{29,512},{79,1024},{83,2048},{31,4096},{17,8192},{37,16384},{71,32768},{43,65536},{41,131072},{73,262144},{53,524288},{13,1048576},{59,2097152},{67,4194304}}
k=33280
n=23
{{5,2},{3,4},{11,8},{7,16},{47,32},{19,64},{23,128},{61,256},{29,512},{79,1024},{83,2048},{31,4096},{17,8192},{37,16384},{71,32768},{43,65536},{41,131072},{73,262144},{53,524288},{13,1048576},{59,2097152},{67,4194304},{89,8388608}}
k=123904
n=24
{{5,2},{3,4},{11,8},{7,16},{47,32},{19,64},{23,128},{61,256},{29,512},{79,1024},{83,2048},{31,4096},{17,8192},{37,16384},{71,32768},{97,65536},{41,131072},{43,262144},{53,524288},{13,1048576},{59,2097152},{67,4194304},{89,8388608},{73,16777216}}
k=245872
n=25
{{101,2},{3,4},{5,8},{7,16},{47,32},{19,64},{23,128},{61,256},{11,512},{79,1024},{83,2048},{31,4096},{17,8192},{37,16384},{29,32768},{97,65536},{41,131072},{43,262144},{53,524288},{13,1048576},{59,2097152},{67,4194304},{89,8388608},{73,16777216},{71,33554432}}
k=39624
n=26
{{5,2},{3,4},{11,8},{13,16},{47,32},{19,64},{23,128},{61,256},{29,512},{79,1024},{83,2048},{31,4096},{17,8192},{103,16384},{101,32768},{7,65536},{41,131072},{43,262144},{53,524288},{37,1048576},{59,2097152},{67,4194304},{89,8388608},{73,16777216},{71,33554432},{97,67108864}}
k=337152
n=27
{{5,2},{3,4},{11,8},{13,16},{47,32},{19,64},{23,128},{61,256},{29,512},{79,1024},{83,2048},{31,4096},{17,8192},{103,16384},{101,32768},{7,65536},{41,131072},{43,262144},{59,524288},{37,1048576},{107,2097152},{67,4194304},{89,8388608},{73,16777216},{71,33554432},{97,67108864},{53,134217728}}
k=506880
n=28
{{5,2},{3,4},{11,8},{7,16},{47,32},{19,64},{23,128},{61,256},{29,512},{79,1024},{83,2048},{31,4096},{17,8192},{103,16384},{101,32768},{43,65536},{41,131072},{109,262144},{59,524288},{13,1048576},{107,2097152},{67,4194304},{89,8388608},{73,16777216},{71,33554432},
{97,67108864},{53,134217728},{37,268435456}}
k=929280
n=29
{{107,2},{103,4},{23,8},{13,16},{47,32},{19,64},{113,128},{61,256},{89,512},{79,1024},{5,2048},{31,4096},{17,8192},{37,16384},{101,32768},{73,65536},{71,131072},{109,262144},{53,524288},{7,1048576},{59,2097152},{67,4194304},{83,8388608},{43,16777216},{41,33554432},{97,67108864},{29,134217728},
{3,268435456},{11,536870912}}
k=745536
n=30
{{107,2},{127,4},{23,8},{31,16},{47,32},{19,64},{113,128},{103,256},{89,512},{79,1024},{5,2048},{61,4096},{17,8192},{37,16384},{101,32768},{73,65536},{71,131072},{109,262144},{53,524288},{13,1048576},{59,2097152},{67,4194304},{83,8388608},{43,16777216},{41,33554432},
{97,67108864},{29,134217728},{7,268435456},{11,536870912},{3,1073741824}}
k=3295608
n=31
{{107,2},{127,4},{23,8},{31,16},{47,32},{19,64},{113,128},{103,256},{59,512},{79,1024},{5,2048},{61,4096},{101,8192},{37,16384},{71,32768},{73,65536},{131,131072},{109,262144},{53,524288},{13,1048576},{17,2097152},{67,4194304},{83,8388608},{43,16777216},{41,33554432},{97,67108864},
{29,134217728},{7,268435456},{89,536870912},{3,1073741824},{11,2147483648}}
k=2666984
n=32
k=0
n=33
{{107,2},{79,4},{23,8},{37,16},{47,32},{19,64},{113,128},{127,256},{131,512},{139,1024},{5,2048},{31,4096},{137,8192},{103,16384},{101,32768},{73,65536},{71,131072},{109,262144},{53,524288},{13,1048576},{59,2097152},{67,4194304},{83,8388608},{43,16777216},{41,33554432},{97,67108864},
{29,134217728},{7,268435456},{89,536870912},{3,1073741824},{11,2147483648},{61,4294967296},{17,8589934592}}
k=1631350
n=34
k=0
n=35
{{107,2},{109,4},{23,8},{37,16},{47,32},{19,64},{113,128},{127,256},{131,512},{139,1024},{5,2048},{31,4096},{137,8192},{103,16384},{149,32768},{151,65536},{71,131072},{73,262144},{101,524288},{13,1048576},{59,2097152},{67,4194304},{83,8388608},{43,16777216},{41,33554432},{97,67108864},
{29,134217728},{7,268435456},{89,536870912},{3,1073741824},{11,2147483648},{61,4294967296},{17,8589934592},{79,17179869184},{53,34359738368}}
k=69286350
n=36
{{107,2},{109,4},{23,8},{157,16},{47,32},{19,64},{113,128},{127,256},{131,512},{139,1024},{5,2048},{37,4096},{137,8192},{103,16384},{149,32768},{151,65536},{71,131072},{73,262144},{101,524288},{13,1048576},{59,2097152},{67,4194304},{83,8388608},{43,16777216},{41,33554432},{97,67108864},
{29,134217728},{7,268435456},{89,536870912},{3,1073741824},{11,2147483648},{61,4294967296},{17,8589934592},{79,17179869184},{53,34359738368},
{31,68719476736}}
k=69286350
n=37
{{149,2},{109,4},{23,8},{163,16},{47,32},{19,64},{113,128},{127,256},{107,512},{139,1024},{5,2048},{157,4096},{137,8192},{103,16384},{3,32768},{151,65536},{131,131072},{73,262144},{101,524288},{13,1048576},{59,2097152},{67,4194304},{83,8388608},{43,16777216},{41,33554432},{97,67108864},
{71,134217728},{37,268435456,{89,536870912},{7,1073741824},{11,2147483648},{61,4294967296},{17,8589934592},{79,17179869184},{53,34359738368},
{31,68719476736},{29,137438953472}}
k=43896356
n=38-41
k=0
Q2. n=16
Q3. The sequence will be like this:
1,1,2,4,8,8,9,21,42,12,24,220,748,450,360,0,496,1920,13080,71504,63840,33280,123904,245872,39624,337152,506880,929280,745536,3295608,2666984,0,1631350,0,
69286350,69286350,43896356,0,0,0,...
For 2^42, there is no prime with a 'n' less than 42. The first power,
giving a prime sum with 2^42 is 59.
But for 2^58, again, there is no such prime with a 'n' less than 59. The
next one will be with the 'n'= 106. etc.
We have:
42 -> 59
58-> 106
66 -> 127
76-> 117
85 -> 107
90 -> 151
102 -> 180 ...
By the time we get
to the right power, there will be a power that doesn't have the matching
prime number.
I think there won't be any more solutions after 37, but I don't have a
proof.
***
Oscar wrote:
Puzzle 1248 was very interesting, I had as much fun in finding
non-existence arguments as in searching for permitted matchings.
Perfect matchings
DON'T exist for n=16, n=32, n=34, and for every n>=38.
Perfect
matchings DO exist for the remaining values of n.
Attached file
Pu1248OV.txt contains one such matching
for each permitted value of n, properly formatted and with n distinct
sums whenever possible (only exceptions are n=2 and n=4).
I counted the number a(n) of distinct perfect matchings for every n<=37:
n a(n)
1 1
2 1
3 2
4 4
5 8
6 8
7 9
8
21
9 42
10 12
11 24
12 220
13 748
14 450
15
360
16 0
17 496
18 1920
19 13080
20 71504
21
63840
22 33280
23 123904
24 245872
25 446024
26
337152
27 506880
28 929280
29 745536
30 3295608
31
2666984
32 0
33 1631350
34 0
35 69286350
36
69286350
37 43896356
I hope that my search program had no
bugs and that such numbers will be confirmed by other puzzlers.
Then I claimed that equality a(n)=0 holds for every n>=38. I'll
prove it.
It shouldn't surprise that perfect matchings do
exist only for finitely many values of n, because there are
"dual-Sierpinski" primes p such that the sum p+2^k is composite for
every positive exponent k; if the set of the first n odd primes includes
one such prime p, then no perfect matching is possible because p can't
be matched with any positive power of two.
The smallest known
dual-Sierpinski prime is 271129=prime(23738): each sum of the form
271129+2^k admits at least one proper factor from the covering set
{3,5,7,13,17,241}.
Therefore, there is no perfect matching for
n>=23737.
Conversely, if an odd prime p=prime(j) isn't of
dual-Sierpinski type, let k be the least positive exponent such that the
sum p+2^k is prime (at least one such exponent must exist); in other
words, 2^k is the least power of two which can be matched with prime p.
OEIS page for sequence A067760 provides such k for every prime
p<=39251=prime(4135).
If inequality j<=k holds, then there is no
perfect matching for every n with j-1<=n<=k-1, because such "critical"
prime p belongs to the set of the first n odd primes but it can't be
matched with any of the first n positive powers of two.
The first two
critical odd primes are:
773=prime(137), with k=955;
2131=prime(321), with k=4583176!!
Hence there is no perfect matching
for 136<=n<=954 and for 320<=n<=4583175.
Finally, consider the
following "conflicting" odd primes:
47=prime(15) can be matched with
2^5, 2^209, 2^1049, 2^8501...
167=prime(39) can be matched with 2^5,
2^509, 2^5513...
For 38<=n<=208, both primes must be used and both
primes can be matched only with power 2^5, but no power of two can be
used more than once, so there is no perfect matching.
The four
non-existence intervals found so far are overlapping and their union
covers every n>=38. QED.
A parity argument allows to justify
non-existence results also for n=16, n=32, n=34.
Even powers of two
are congruent to 1 modulo 3, while odd powers of two are congruent to 2
modulo 3.
In order to avoid composite sums divisible by 3, every odd
prime congruent to 1 modulo 3 must be matched with an even power of two,
while every odd prime congruent to 2 modulo 3 must be matched with an
odd power of two.
Sometimes, this can't be done:
for n=16, there
are 9 odd primes congruent to 2 mod 3 but only 8 odd powers of 2;
for
n=32, there are 17 odd primes congruent to 2 mod 3 but only 16 odd
powers of 2;
for n=34, there are 18 odd primes congruent to 2 mod 3
but only 17 odd powers of 2
...
What do you mean by "only
exceptions are n=2 and n=4" (CR)
"I meant that, when several matchings are
permitted, I searched for matchings with the additional constraint that
the n involved sums are all distinct too, buy no such matching was found
for n=2 and for n=4.
For n=2 there is only one possibile matching, involving two sums 5+2
and 3+4 which produce the same value 7.
for n=4 I checked each of the four
possibile matchings; in each case, two of the four involved sums happen
to produce the same value, so there are only three distinct sums"
(OV)
***
Simon wrote:
Q1:
n=6: {17, 2}, {3, 4}, {5, 8}, {13, 16}, {11, 32}, {7, 64}
n=7: {17, 2}, {13, 4}, {3, 8}, {7, 16}, {5, 32}, {19, 64}, {11, 128}
n=8: {17, 2}, {3, 4}, {5, 8}, {7, 16}, {11, 32}, {19, 64}, {23, 128}, {13,
256}
n=9: {17, 2}, {3, 4}, {5, 8}, {7, 16}, {11, 32}, {19, 64}, {23, 128}, {13,
256}, {29, 512}
n=10: {17, 2}, {3, 4}, {5, 8}, {31, 16}, {11, 32}, {19, 64}, {23, 128}, {13,
256}, {29, 512}, {7, 1024}
n=11: {17, 2}, {19, 4}, {3, 8}, {31, 16}, {11, 32}, {7, 64}, {23, 128}, {13,
256}, {29, 512}, {37, 1024}, {5, 2048}
n=12: {17, 2}, {3, 4}, {5, 8}, {7, 16}, {11, 32}, {19, 64}, {23, 128}, {13,
256}, {29, 512}, {37, 1024}, {41, 2048}, {31, 4096}
n=13: {3, 2}, {7, 4}, {5, 8}, {43, 16}, {11, 32}, {19, 64}, {23, 128}, {13,
256}, {29, 512}, {37, 1024}, {41, 2048}, {31, 4096}, {17, 8192}
n=14: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {29, 512}, {37, 1024}, {41, 2048}, {31, 4096}, {17, 8192}, {43, 16384}
n=15: {5, 2}, {3, 4}, {23, 8}, {7, 16}, {47, 32}, {19, 64}, {53, 128}, {13,
256}, {11, 512}, {37, 1024}, {41, 2048}, {31, 4096}, {17, 8192}, {43,
16384}, {29, 32768}
n=17: {5, 2}, {3, 4}, {23, 8}, {31, 16}, {47, 32}, {19, 64}, {53, 128}, {13,
256}, {59, 512}, {7, 1024}, {41, 2048}, {61, 4096}, {17, 8192}, {37, 16384},
{11, 32768}, {43, 65536}, {29, 131072}
n=18: {5, 2}, {3, 4}, {53, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {59, 512}, {67, 1024}, {41, 2048}, {61, 4096}, {17, 8192}, {37,
16384}, {11, 32768}, {7, 65536}, {29, 131072}, {43, 262144}
n=19: {5, 2}, {3, 4}, {23, 8}, {13, 16}, {47, 32}, {19, 64}, {11, 128}, {61,
256}, {59, 512}, {37, 1024}, {41, 2048}, {31, 4096}, {17, 8192}, {67,
16384}, {29, 32768}, {7, 65536}, {71, 131072}, {43, 262144}, {53, 524288}
n=20: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {19, 64}, {23, 128}, {61,
256}, {59, 512}, {37, 1024}, {41, 2048}, {31, 4096}, {17, 8192}, {67,
16384}, {29, 32768}, {43, 65536}, {71, 131072}, {73, 262144}, {53, 524288},
{13, 1048576}
n=21: {3, 2}, {7, 4}, {5, 8}, {31, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {11, 512}, {79, 1024}, {41, 2048}, {61, 4096}, {17, 8192}, {67,
16384}, {29, 32768}, {43, 65536}, {71, 131072}, {73, 262144}, {53, 524288},
{37, 1048576}, {59, 2097152}
n=22: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {19, 64}, {23, 128}, {61,
256}, {29, 512}, {79, 1024}, {83, 2048}, {31, 4096}, {17, 8192}, {37,
16384}, {71, 32768}, {43, 65536}, {41, 131072}, {73, 262144}, {53, 524288},
{13, 1048576}, {59, 2097152}, {67, 4194304}
n=23: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {19, 64}, {23, 128}, {61,
256}, {29, 512}, {79, 1024}, {83, 2048}, {31, 4096}, {17, 8192}, {37,
16384}, {71, 32768}, {43, 65536}, {41, 131072}, {73, 262144}, {53, 524288},
{13, 1048576}, {59, 2097152}, {67, 4194304}, {89, 8388608}
n=24: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {19, 64}, {23, 128}, {61,
256}, {29, 512}, {79, 1024}, {89, 2048}, {31, 4096}, {17, 8192}, {37,
16384}, {71, 32768}, {97, 65536}, {41, 131072}, {43, 262144}, {53, 524288},
{13, 1048576}, {59, 2097152}, {67, 4194304}, {83, 8388608}, {73, 16777216}
n=25: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {19, 64}, {23, 128}, {61,
256}, {29, 512}, {79, 1024}, {89, 2048}, {31, 4096}, {17, 8192}, {37,
16384}, {101, 32768}, {97, 65536}, {41, 131072}, {43, 262144}, {53, 524288},
{13, 1048576}, {59, 2097152}, {67, 4194304}, {83, 8388608}, {73, 16777216},
{71, 33554432}
n=26: {5, 2}, {3, 4}, {23, 8}, {13, 16}, {47, 32}, {19, 64}, {11, 128}, {61,
256}, {29, 512}, {79, 1024}, {89, 2048}, {31, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {7, 65536}, {41, 131072}, {43, 262144}, {53, 524288},
{37, 1048576}, {59, 2097152}, {67, 4194304}, {83, 8388608}, {73, 16777216},
{71, 33554432}, {97, 67108864}
n=27: {5, 2}, {3, 4}, {23, 8}, {13, 16}, {47, 32}, {19, 64}, {11, 128}, {61,
256}, {29, 512}, {79, 1024}, {89, 2048}, {31, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {7, 65536}, {41, 131072}, {43, 262144}, {59, 524288},
{37, 1048576}, {107, 2097152}, {67, 4194304}, {83, 8388608}, {73, 16777216},
{71, 33554432}, {97, 67108864}, {53, 134217728}
n=28: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {19, 64}, {23, 128}, {61,
256}, {29, 512}, {79, 1024}, {89, 2048}, {31, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {43, 65536}, {41, 131072}, {109, 262144}, {59,
524288}, {13, 1048576}, {107, 2097152}, {67, 4194304}, {83, 8388608}, {73,
16777216}, {71, 33554432}, {97, 67108864}, {53, 134217728}, {37, 268435456}
n=29: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {19, 64}, {23, 128}, {61,
256}, {29, 512}, {79, 1024}, {113, 2048}, {31, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {43, 65536}, {41, 131072}, {109, 262144}, {59,
524288}, {13, 1048576}, {107, 2097152}, {67, 4194304}, {83, 8388608}, {73,
16777216}, {71, 33554432}, {97, 67108864}, {53, 134217728}, {37, 268435456},
{89, 536870912}
n=30: {5, 2}, {3, 4}, {11, 8}, {7, 16}, {47, 32}, {127, 64}, {23, 128}, {61,
256}, {29, 512}, {79, 1024}, {113, 2048}, {31, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {43, 65536}, {41, 131072}, {109, 262144}, {59,
524288}, {13, 1048576}, {107, 2097152}, {67, 4194304}, {83, 8388608}, {73,
16777216}, {71, 33554432}, {97, 67108864}, {53, 134217728}, {37, 268435456},
{89, 536870912}, {19, 1073741824}
n=31: {5, 2}, {3, 4}, {131, 8}, {7, 16}, {47, 32}, {127, 64}, {23, 128},
{61, 256}, {29, 512}, {79, 1024}, {113, 2048}, {31, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {43, 65536}, {41, 131072}, {109, 262144}, {59,
524288}, {13, 1048576}, {107, 2097152}, {67, 4194304}, {83, 8388608}, {73,
16777216}, {71, 33554432}, {97, 67108864}, {53, 134217728}, {37, 268435456},
{89, 536870912}, {19, 1073741824}, {11, 2147483648}
n=33: {107, 2}, {79, 4}, {5, 8}, {3, 16}, {47, 32}, {7, 64}, {23, 128}, {13,
256}, {29, 512}, {139, 1024}, {113, 2048}, {31, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {43, 65536}, {131, 131072}, {109, 262144}, {53,
524288}, {127, 1048576}, {137, 2097152}, {67, 4194304}, {83, 8388608}, {73,
16777216}, {41, 33554432}, {97, 67108864}, {71, 134217728}, {37, 268435456},
{89, 536870912}, {19, 1073741824}, {11, 2147483648}, {61, 4294967296}, {59,
8589934592}
n=35: {5, 2}, {3, 4}, {131, 8}, {7, 16}, {47, 32}, {43, 64}, {23, 128}, {13,
256}, {29, 512}, {139, 1024}, {113, 2048}, {31, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {151, 65536}, {41, 131072}, {109, 262144}, {53,
524288}, {127, 1048576}, {137, 2097152}, {67, 4194304}, {89, 8388608}, {73,
16777216}, {71, 33554432}, {97, 67108864}, {149, 134217728}, {37,
268435456}, {107, 536870912}, {19, 1073741824}, {11, 2147483648}, {61,
4294967296}, {59, 8589934592}, {79, 17179869184}, {83, 34359738368}
n=36: {107, 2}, {7, 4}, {5, 8}, {3, 16}, {47, 32}, {43, 64}, {23, 128}, {13,
256}, {29, 512}, {139, 1024}, {113, 2048}, {157, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {151, 65536}, {41, 131072}, {109, 262144}, {53,
524288}, {127, 1048576}, {137, 2097152}, {67, 4194304}, {131, 8388608}, {73,
16777216}, {71, 33554432}, {97, 67108864}, {149, 134217728}, {37,
268435456}, {89, 536870912}, {19, 1073741824}, {11, 2147483648}, {61,
4294967296}, {59, 8589934592}, {79, 17179869184}, {83, 34359738368}, {31,
68719476736}
n=37: {3, 2}, {7, 4}, {5, 8}, {151, 16}, {47, 32}, {19, 64}, {23, 128}, {13,
256}, {29, 512}, {139, 1024}, {113, 2048}, {157, 4096}, {17, 8192}, {103,
16384}, {101, 32768}, {43, 65536}, {131, 131072}, {109, 262144}, {53,
524288}, {127, 1048576}, {137, 2097152}, {67, 4194304}, {89, 8388608}, {73,
16777216}, {71, 33554432}, {97, 67108864}, {149, 134217728}, {37,
268435456}, {107, 536870912}, {163, 1073741824}, {11, 2147483648}, {61,
4294967296}, {59, 8589934592}, {79, 17179869184}, {83, 34359738368}, {31,
68719476736}, {41, 137438953472}
Q2:
A perfect matching does not exist for n=16 and n=32.
Q3:
1,1,2,4,8,8,9,21,42,12,24,220,748,450,360,0,496,1920,13080,71504,63840,33280,123904,245872,446024,337152,506880,929280,745536,3295608,2666984,0
***
|
