Solution
This collates information from three sources: Witold Jarnicki (Krakow), Stephen Morris (Newbury, Eng.), and a group from Oakland Univ. in Michigan, consisting of Jerry Grossman, Eddie Cheng, and Laszlo Liptak. The original problem was solved by these, and also by Alberto Monteiro, Joseph DeVincentis, Bud Brown, and Seth Kleinerman.
First, an elegant approach is to solve the given problem directly using the negabinary representation of −2. Observe that −1 is in the set from 2014 x + 2014. Then use −1 to get this polynomial for −2:
−x^12 − x^11 − x^5 − x + 2014 = 0.
This makes use of the represenation of 2014 in terms of powers of −2, called the negabinary representation. This Mathematica code from Mathworld gives the represenation of any number:
Negabinary[n_] := Module[ {t = (2/3)(4^Floor[Log[4, Abs[n] + 1] + 2] - 1)},
IntegerDigits[BitXor[n + t, t], 2] ]
Negabinaryp[2014]
{1,1,0,0,0,0,0,1,0,0,0,1,0}
We may as well generalize. Let S(n) (just S when n is understood) be the set obtained by starting with {0, n}, and then repeatedly adding to the set all integer roots of (nontrivial) polynomials with coefficients in the set, until there is no change. That is, S is the closure of {0, n} under the taking of integer roots.
Start with some easy rules.
Observe first that S can consist only of divisors of n (by the rational root
theorem). Also, S(n) always contains:
|
-1
|
|
from n x + n
|
|
0
|
|
from n x
|
|
1
|
|
from (−1) xn + (−1) x(n − 1) + ... + (−1) x + n
|
|
−n
|
|
from x + n
|
So S always contains {0, 1, −1, n, −n}.
Call n "maximal" if S(n) consists of all divisors of n.
Call n "minimal" if S(n) consists only of {0, 1, −1, n, −n}.
A prime is both minimal and maximal, and we can ignore primes in what follows since S(p) is determined.
If k is in the set, then so is −k, from x + k.
If n is even, 2 is in S(n). Use the base-two expansion of n. For example, for the given problem, 2 is a root of
x10 + x9 + x8 + x7 + x6 + x4 + x3 + x2 + x − 2014.
So this solves the problem posed in a different way than the negabinary approach.
If n is divisible by 3, then the same argument as for 2 works, using coefficients 0, 1, and −1 in a base-3 expansion. Similarly if n is even and 5 divides n, then a base-5 expansion can be used to get 5 in the set.
If d divides n and d is in S(n) then n/d is also, as it is a root of d x − n. Also, under the same hypothesis, if dk is the largest power of d that divides n, then any smaller di is in S(n) as is n/di. Consider i = 2, 3, ..., in order, and use the polynomial d x − n/d(i − 1) and (n/di)x − n.
Conversely, if am is in S(n) then so is a, because a is a root of xm − am, and so in this case S(n) contains all divisors that are powers of a.
The discussion so far shows that all n ≤ 34 are maximal.
35 is minimal, and so 35 is the smallest composite minimal number: We need
show that neither 5 nor 7 can be the first to enter the set.
Suppose 5 is the first. Then 5 or −5 is the root of a polynomial having coefficients (in abs value) 0, 1, or 35. And, by dividing out powers of 5, we can assume the constant term is nonzero. Since it must be a multiple of 5, the constant term can be assume to be 35. But then 25 divides each monomial except the last two, which has the form a x + 35. If a is 35 or −35, this is not divisible by 25 when x = 5. And if a is 1 or −1, this is not divisible by 25 when x = 5. Contradiction. A similar argument works for 7.
The Michigan group proved this: Similar arguments to 35 show that if n = p q, where p and q are distinct primes, then n is minimal so long as neither prime is congruent to 1 or −1 modulo the other. This takes care of 65, 77, and 85. On the other hand, 95 is maximal, since 5 is a root of x3 −x2 − x − 95. The preceding observations take care of all numbers under 100 except for 55 and 91, but arguments in the same spirit show that both of these are minimal.
Returning to 2014, we have
S(2014) = {0, 1, −1, 2, −2, 1007, −1007, 2014, −2014}
The divisors 19, 38, 53, 106 are not in the set, so 2014 is neither minimal nor maximal. But I will omit the details of this because of an algorithmic approach to be presented shortly.
The Michigan group, and Stephen Morris, showed that 154 = 2 × 7 × 11 is the smallest number that is neither minimal nor maximal. The divisors are {1, 2, 7, 11, 14, 22, 77, 154}. We know that 2 is in S. But 7 is not. Again, I will omit the proof because of the next algorithm.
Now, Witold Jarnicki came up with a fantastic algorithm that can fairly quickly compute S(n) given n. I coded it in Mathematica (code is below). Investigating the results led to no clear patterns or conjectures, except the one mentioned above that the Oakland Univ. group had found: If n = p q, with p < q, and both prime, then if n is maximal, it must be that q is congruent to either +1 or −1 mod p. Note that the converse is not true, since 55 is not maximal and 11 is 1 mod 5. From the work above note that any n of this type is either minimal or maximal.
Theorem (Grossman, Liptak, Cheng).
If n = p q is maximal (p, q, prime, p < q), then q is +1 or −1 mod p.
Witold Jarnicki has the following proof of this.
Proof (Jarnicki).
Let A = {−pq, −1, 0, 1, pq}.
Suppose p is visible from A via f. Without loss of generality, we can assume that f(p) > 0.
Now f(0) is congruent to f(p) mod p. So f(0) === 0 (mod p).
So f(0) = p q, since that is the only member of A that is divisible by p and is such that f(0) gt; 0. So the polynomial f(X) = X g(X) + p q, where g is another nonzero polynomial with coefficients in A.
Observe that
0 = f(p) = p q + p g(p) === p q + p g(0) mod p^2
Hence 0 === q + g(0) mod p. As q is not divisible by p, neither is g(0). This only leaves g(0) = +1 or −1, as those are the only possibilities in A. But then q is +1 or −1 mod p, which completes the proof in this case.
Now, suppose instead that q is the first to become visible. The same argument shows that p is 1 or −1 mod q, which is not possible since p < q. So the proof is complete.
Here is Mathematica code for the Jarnicki algorithm, which produces the set S(n) (with negatives omitted in the output).
Options[visible] ={TraceQ->False}; (* so I can easily debug by setting to True *)
visible[n_, opts___]:=Module[{print, trQ,A,i},
A = {0,1, -1, n, -n}; done=False;
trQ = TraceQ /. {opts} /. Options[visible]; If[trQ, print=Print];
candidates=Complement[Union [Divisors[n],-Divisors[n]],A];
count = 0; maxCount = Infinity; (* for debugging *)
(* next is a functional way of recording who has appeared *)
Clear[appeared];appeared[_] := False;
Do[appeared[j] = True, {j, A}];
(* the maxCount is just to abort in case of bugs *)
While[count++; count <= maxCount && !done,
(* make a linear pass through the divisors, and repeat, stopping when there
is no further change *)
addedThisPass = {};
Do[If[!appeared[d], print["trying ", d];
(*check to see if d can appear from the current A *)
Clear[CC]; $RecursionLimit=5000; (* maybe not necessary; and the CC loop
could be programmed iteratively not recursively *)
CC[0] = Select[ Table[a/d, {a,Select[A, #>0&]}], IntegerQ[#]&];
CC[m_] := CC[m] = Union[Flatten[ Table[(a+b)/d, {a, CC[m-1]}, {b,Select[A,
Divisible[ a+#,d]&]}]]];
dAppears = False;i = 0;old = CC[0]; new = {};
(* iterate until no change to get C *)
While[new =!= old, i++; print[{i, Length[old]}]; old = new;
new = Union[CC[i],old]; If[MemberQ[new,0], dAppears =True;Break[]]];
If[dAppears, print["appears", d];A = Union[A,{d, n/d,-d, -n/d}]; (* update A
*)
addedThisPass = Union[addedThisPass,{d, n/d,-d, -n/d}]; Do[appeared[dd]
= True, {dd,{d,n/d,-d, -n/d}}]]],
{d, candidates}];
print[addedThisPass];
done = ( addedThisPass=={}) (*nothing added in a full pass, so we are
finished *)
]; (* end While *)
print["max count = ", count];
Union[Abs[Select[Append[Divisors@n,0], appeared]]]];
MinimalQ[n_] := visible[n] == {0,1,n}
MaximalQ[n_] := visible[n] == Prepend[Divisors[n],0]
EXAMPLES
visible[123456]
{0,1,2,3,4,6,8,12,16,24,32,48,64,96,192,643,1286,1929,
2572,3858,5144,7716,10288,15432,20576,30864,41152,61728,123456}
visible[2014]
{0,1,2,1007,2014}
All the maximals below 200:
max = Select[Range[200], MaximalQ]
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,
19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,
37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,
56,57,58,59,60,61,62,63,64,66,67,68,69,70,71,72,73,74,
75,76,78,79,80,81,82,83,84,86,87,88,89,90,92,93,94,95,
96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,
114,116,117,118,120,121,122,123,124,125,126,127,128,129,130,131,132,
134,135,136,137,138,139,140,141,142,144,145,146,147,148,149,150,151,
152,153,155,156,157,158,159,160,162,163,164,165,166,167,168,169,170,
171,172,173,174,176,177,178,179,180,181,182,183,184,186,188,189,190,
191,192,193,194,195,196,197,198,199,200}
All the minimals below 200:
min = Select[Range[200], MinimalQ]
{2,3,5,7,11,13,17,19,23,29,31,35,
37,41,43,47,53,55,59,61,65,67,71,73,77,79,83,
85,89,91,97,101,103,107,109,113,115,119,127,131,133,137,
139,143,149,151,157,161,163,167,173,175,179,181,185,187,
191,193,197,199}
Numbers below 2000 that are neither maximal nor minimal:
neither = Select[Range[2020], ( !MaximalQ[#] && !MinimalQ[#]) &]
{154,231,266,322,357,374,418,429,442,494,
561,598,627,638,663,682,741,748,754,759,
777,782,806,814,826,874,897,902,938,962,
969,986,988,994,1023,1034,1054,1066,1102,1106,1118,
1131,1166,1173,1178,1196,1209,1222,1258,1276,1281,1298,
1311,1334,1353,1364,1394,1414,1426,1443,1462,1463,1479,
1526,1534,1551,1558,1564,1581,1586,1598,1599,1606,1612,
1628,1634,1653,1659,1702,1738,1742,1743,1749,1767,1786,
1802,1826,1833,1834,1869,1886,1887,1898,1918,1924,1947,
1958,1972,1978,2001,2006,2013,2014}
The preceding list has numbers that are divisible by 2 or 3, and those don't
really count. If we exclude those, only one number remains!
1463 is the first that is coprime to 6 and neither minimal nor maximal.
Select[neither, GCD[#, 6] ==1 &]
{1463}
visible[1463]
{0,1,11,133,1463}
Divisors[1463]
{1,7,11,19,77,133,209,1463}
There are more numbers like 1463:
{1463, 2255, 2405, 2737, 2755, 3145, 3245, 3655, 3745, 3895....}