Maximum Sized Sets With Sums That Avoid Squares (A363069)
Description
Given a natural number n, what is the largest subset of the natural numbers up to n such that no sums of two elements from this subset are squares?
For example: What is the largest square sumless subset of [1,3]?
We can pick either {1} or {3}, but not both because 1+3=22. We also can not pick {2} because 2+2=22.
Theoretic Results
Simple 1 / 3 Lower Bound
Take all of the numbers x ≡ 1 mod 3 because 2 is quadratic nonresidue modulo 3.
This produces the following sequence: 1, 4, 7, 10, 13, 16, 19, 22, ...
Alternative 1 / 3 Lower Bound
Take all of the numbers x ≡ 3×4y-1 mod 4y for all y > 0.
This produces the following sequence: 3, 7, 11, 12, 15, 19, 23, 24, ...
Consider the following short proof that this sequence has no square sums:
Let 4a + 3×4a-1 and 4b + 3×4b-1 be two numbers with a ≥ b > 0.
Adding them together we get 4a + 4b + 3×(4a-1+4b-1).
We can divide through by 4b-1, which is a square, to get 4a-b+1 + 4 + 3×4a-b + 3.
When a = b we have 4 + 4 + 3 + 3 ≡ 2 mod 4.
When a > b we have 4(4a-b + 1 + 3×4a-b-1) + 3 ≡ 3 mod 4.
2 and 3 are quadratic nonresidue modulo 4, so the sums of elements in our subset will never be squares.
1 / 2 Upper Bound
Consider the square which is closest to n and partition the natural numbers at n / 2, so for all 0 < a < n / 2, we can either take (n / 2) - a or (n / 2) + a but never both.
Computational Results
I calculated the largest subsets and the number of unique largest subsets from [1,1] to [1,100].
All of the subsets are only slightly better than (or equal to) my best lower bound of 1 / 3.
| [1,n] | Largest Subset Size | Number of Largest Subsets | Lexically First Largest Subset (including n) of equal or greater size to the Largest n-1 case |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | - |
| 3 | 1 | 2 | 3 |
| 4 | 2 | 2 | 1 4 |
| 5 | 2 | 4 | 1 5 |
| 6 | 3 | 2 | 1 4 6 |
| 7 | 4 | 2 | 1 4 6 7 |
| 8 | 4 | 2 | - |
| 9 | 4 | 4 | 1 4 6 9 |
| 10 | 4 | 12 | 1 4 7 10 |
| 11 | 5 | 6 | 1 4 6 7 11 |
| 12 | 5 | 18 | 1 5 6 7 12 |
| 13 | 6 | 4 | 1 4 6 7 11 13 |
| 14 | 6 | 18 | 1 4 6 7 13 14 |
| 15 | 6 | 28 | 3 5 7 12 14 15 |
| 16 | 7 | 14 | 1 4 6 7 11 13 16 |
| 17 | 8 | 14 | 1 4 6 7 11 13 16 17 |
| 18 | 8 | 14 | - |
| 19 | 8 | 20 | 1 4 7 10 11 13 16 19 |
| 20 | 8 | 36 | 1 4 6 7 11 13 17 20 |
| 21 | 9 | 8 | 1 5 6 7 12 14 16 17 21 |
| 22 | 9 | 44 | 1 4 6 7 11 13 16 17 22 |
| 23 | 10 | 17 | 1 5 6 7 12 14 16 17 21 23 |
| 24 | 10 | 25 | 3 5 7 10 14 16 17 21 23 24 |
| 25 | 11 | 8 | 1 5 6 7 12 14 16 17 21 23 25 |
| 26 | 11 | 15 | 1 5 6 7 12 14 16 17 21 25 26 |
| 27 | 12 | 7 | 1 5 6 7 12 14 16 17 21 23 25 27 |
| 28 | 12 | 33 | 1 4 6 7 13 14 16 17 25 26 27 28 |
| 29 | 12 | 61 | 1 4 6 13 14 16 17 25 26 27 28 29 |
| 30 | 13 | 12 | 1 5 7 10 12 14 16 17 21 23 25 27 30 |
| 31 | 13 | 97 | 1 4 6 7 13 14 16 17 25 26 27 28 31 |
| 32 | 13 | 97 | - |
| 33 | 13 | 123 | 1 4 6 7 13 14 17 20 25 26 27 28 33 |
| 34 | 14 | 4 | 1 4 6 7 13 14 16 17 25 26 27 28 31 34 |
| 35 | 14 | 38 | 3 4 7 10 11 16 17 23 24 27 28 30 31 35 |
| 36 | 14 | 134 | 1 5 6 7 12 14 16 17 21 23 25 27 34 36 |
| 37 | 15 | 15 | 4 6 7 11 13 15 16 17 22 24 26 28 31 35 37 |
| 38 | 15 | 87 | 1 5 6 7 12 14 16 17 21 23 25 27 34 36 38 |
| 39 | 16 | 15 | 4 6 7 11 13 15 16 17 22 24 26 28 31 35 37 39 |
| 40 | 16 | 92 | 1 4 6 7 11 13 16 17 22 26 28 31 34 37 39 40 |
| 41 | 17 | 15 | 4 6 7 11 13 15 16 17 22 24 26 28 31 35 37 39 41 |
| 42 | 17 | 33 | 1 5 6 12 14 16 17 21 23 25 27 29 34 36 38 40 42 |
| 43 | 18 | 5 | 4 7 11 13 15 16 17 22 24 26 28 30 31 35 37 39 41 43 |
| 44 | 18 | 16 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 |
| 45 | 18 | 45 | 1 6 12 14 16 17 21 23 25 27 29 31 34 38 40 42 44 45 |
| 46 | 19 | 12 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 |
| 47 | 19 | 17 | 1 10 12 14 16 19 21 23 25 27 29 31 36 38 40 42 44 46 47 |
| 48 | 19 | 47 | 4 7 11 13 15 17 20 22 24 26 28 30 31 35 37 39 41 43 48 |
| 49 | 20 | 17 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 |
| 50 | 20 | 17 | - |
| 51 | 20 | 26 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 51 |
| 52 | 20 | 28 | 3 4 7 11 15 16 19 24 26 27 28 31 35 39 41 43 44 47 51 52 |
| 53 | 21 | 12 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 |
| 54 | 21 | 12 | - |
| 55 | 22 | 7 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 |
| 56 | 22 | 7 | - |
| 57 | 23 | 7 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 57 |
| 58 | 23 | 7 | - |
| 59 | 24 | 7 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 57 59 |
| 60 | 24 | 7 | - |
| 61 | 25 | 7 | 1 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 57 59 61 |
| 62 | 25 | 7 | - |
| 63 | 25 | 21 | 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 57 59 61 63 |
| 64 | 25 | 35 | 7 11 13 15 16 22 24 26 28 30 31 35 37 39 41 43 45 47 52 54 56 58 60 62 64 |
| 65 | 26 | 7 | 6 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 |
| 66 | 26 | 16 | 7 11 13 16 22 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 |
| 67 | 26 | 48 | 1 7 11 13 16 22 26 28 30 31 37 39 41 43 45 46 47 49 52 56 58 60 62 64 66 67 |
| 68 | 26 | 148 | 1 7 11 16 22 26 28 30 31 37 39 41 43 45 46 47 49 52 56 58 60 62 64 66 67 68 |
| 69 | 26 | 188 | 3 5 9 14 24 26 28 29 30 37 39 41 43 45 47 48 49 54 56 58 60 62 64 66 68 69 |
| 70 | 27 | 16 | 6 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 |
| 71 | 27 | 118 | 1 7 11 13 16 22 26 28 30 31 37 39 41 43 45 46 47 49 52 56 58 60 62 64 66 67 71 |
| 72 | 27 | 118 | - |
| 73 | 27 | 169 | 1 5 6 9 13 14 17 21 25 26 29 33 34 37 41 42 45 46 49 53 57 61 62 65 69 70 73 |
| 74 | 27 | 223 | 1 5 9 10 13 14 17 21 25 29 30 33 37 38 41 42 45 46 49 53 57 61 65 66 69 73 74 |
| 75 | 28 | 66 | 3 7 11 12 20 26 27 28 30 31 35 39 41 43 45 47 48 49 56 58 60 62 64 66 67 68 71 75 |
| 76 | 28 | 94 | 6 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 76 |
| 77 | 29 | 32 | 3 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 |
| 78 | 29 | 60 | 1 5 6 9 13 14 17 21 25 26 29 33 34 37 41 42 45 46 49 53 57 61 62 65 69 70 73 77 78 |
| 79 | 30 | 32 | 3 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 |
| 80 | 30 | 58 | 6 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 76 78 80 |
| 81 | 31 | 32 | 3 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 |
| 82 | 31 | 58 | 6 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 76 78 80 82 |
| 83 | 32 | 32 | 3 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 83 |
| 84 | 32 | 58 | 6 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 76 78 80 82 84 |
| 85 | 33 | 32 | 3 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 83 85 |
| 86 | 33 | 45 | 6 12 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 67 70 76 78 80 82 84 86 |
| 87 | 34 | 20 | 3 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 83 85 87 |
| 88 | 34 | 20 | - |
| 89 | 34 | 96 | 3 5 7 14 16 24 26 28 30 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 83 85 87 89 |
| 90 | 34 | 110 | 4 6 15 17 23 25 27 29 36 38 40 42 44 46 48 51 53 55 57 59 61 63 65 67 69 74 76 78 80 82 84 86 88 90 |
| 91 | 35 | 25 | 3 5 7 14 16 24 26 28 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 70 71 75 77 79 81 83 85 87 89 91 |
| 92 | 35 | 39 | 3 7 12 20 26 27 28 31 35 39 41 43 45 47 48 49 56 58 60 62 64 66 67 68 70 71 75 79 81 83 85 87 89 91 92 |
| 93 | 35 | 51 | 4 6 17 23 25 27 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 67 69 70 71 78 80 82 84 86 88 90 92 93 |
| 94 | 35 | 148 | 1 5 7 16 22 26 28 37 39 41 43 45 46 47 49 56 58 60 62 64 66 67 68 69 70 71 79 81 83 85 87 89 91 92 94 |
| 95 | 35 | 169 | 4 6 15 17 23 25 27 36 38 40 42 44 46 48 51 53 55 57 59 61 63 65 67 69 71 76 78 80 82 84 86 88 90 92 95 |
| 96 | 36 | 40 | 1 5 7 16 22 26 28 37 39 41 43 45 46 47 49 56 58 60 62 64 66 67 68 69 70 71 79 81 83 85 87 89 91 92 94 96 |
| 97 | 36 | 76 | 1 5 7 16 22 26 28 37 39 41 43 45 46 49 56 58 60 62 64 66 67 68 69 70 71 79 81 83 85 87 89 91 92 94 96 97 |
| 98 | 36 | 76 | - |
| 99 | 36 | 90 | 4 6 15 17 23 25 27 36 38 40 42 44 46 48 51 53 55 57 59 61 63 65 67 69 71 74 76 78 80 82 84 86 88 90 92 99 |
| 100 | 36 | 162 | 3 4 7 11 15 19 20 23 24 27 28 31 35 39 43 47 48 51 55 56 59 63 64 67 68 71 75 79 83 84 87 91 92 95 99 100 |
zachdestefano (at) gmail (dot) com