|
|
A195854
|
|
Smallest possible largest number in a set of n integers such that sum of two elements is always a perfect square.
|
|
3
|
|
|
|
OFFSET
|
2,2
|
|
COMMENTS
|
Note that in the examples, first term is negative (since we are asking the smallest) and the remaining terms are positive (since perfect squares cannot be negative). Solution for n=7 is not found.
Let g(N) denote the greatest integer g such that there is a set Q such that there is a set A that is a subset of {1, 2, 3, 4, 5 ...} such that the cardinality equals g. Then, there is an efficiently computable real number K such that if N exceeds K, then g(N) < 37 * log(N). The proof of this is based on a sieve result called Gallagher's larger sieve.
In any n-tuplet having the property that sum of any two numbers is a perfect square, at least one of the number must be even. It should also not have odd numbers of the form 4k + 1 or 4k + 3, since perfect squares are only 0 or 1 (mod 4).
|
|
REFERENCES
|
Richard K. Guy, Unsolved Problems in Number Theory, Springer, Third Edition, 2004, p. 268-270.
|
|
LINKS
|
|
|
FORMULA
|
Jean Lagrange gave a parametric representric representation to produce 6-tuples (a, b, c, d, e and f) such that sum of any two of the numbers is a square. It depends on two parameters x and y where he specializes the case where y = 1.
a = (80y^6 + 320y^2)x^2 + (64y^4 + 128y^2)x + 32y^2 ==> 1
b = (80y^6 + 320y^2)x^2 - (64y^4 + 128y^2)x + 32y^2 ==> 2
c = (16y^8 - 16y^6 + 32y^4 - 64y^2 - 128)x^2 - 32y^2 + 64 ==> 3
d = -(48y^6 + 192y^2)x^2 - (64y^4 - 128y^2)x + 32y^2 ==> 4
e = -(48y^6 + 192y^2)x^2 + (64y^4 - 128y^2)x + 32y^2 ==> 5
f = -(8y^8 + 16y^6 - 32y^4 + 64y^2 - 256)x^2 + 16m^4 - 32m^2 ==> 6
But, for any rational number y there are only finite values of x such that a, b, c, d, e and f in 1, 2, 3, 4, 5 and 6 are distinct integers which form a set with the property that sum of any two numbers in the set is a perfect square.
The formula used to generate triples (k, l, m) such that sum of any two numbers is a square where a, b and c are any parameters are
k = (b^2 + c^2 - a^2)/2
l = (c^2 + a^2 - b^2)/2
m = (a^2 + b^2 - c^2)/2
The formula used to generate quadruplets (k, l, m, n) such that sum of any two numbers is a square is where s is any number that is the sum of two distinct squares in three ways and a, b and c are any three parameters is
k = (b^2 + c^2 - a^2)/2
l = (c^2 + a^2 - b^2)/2
m = (a^2 + b^2 - c^2)/2
n = s - (a^2 + b^2 - c^2)/2
The formula to generate 5-tuplets such that sum of any two numbers is a perfect square uses complex trigonometric formulas.
|
|
EXAMPLE
|
In the set of numbers {-15863902, 17798783, 21126338, 49064546, 82221218, 447422978}, if we add any two numbers, all the 15 combinations give a perfect square and 447422978 is the largest number. For example, 21126338 + -15863902 and 49064546 + 82221218 = 11458^2 = 2294^2. Hence a(6) = 447422978. Similarly
{-4878, 4978, 6903, 12978, 31122} is the set of 5 elements, with the smallest lesser element, such that all the 10 combinations of adding any two numbers gives a perfect square. 31122 is the largest number in this set. Hence a(5) = 31122.
{-94, 95, 130, 194} is the set of 4 elements, with the smallest lesser element, such that all six combinations of adding any two numbers is a perfect square. 194 is the largest number in this set. Hence a(4) = 194.
{-4, 4, 5} is the smallest set of 3 elements such that all three combinations of adding any two numbers gives a perfect square.
{-1, 1} is the trivial set since -1 + 1 = 0^2.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|