OFFSET
1,2
LINKS
Enrico Bertolazzi, Sturm.
P. Borwein, T. Erdélyi, and G. Kós, Littlewood-type problems on [0,1], Proc. London Math. Soc. 79 (1999), 22-46.
D. Ivanov et al., Number of real roots of 0,1 polynomial, MathOverflow.
A. Odlyzko and B. Poonen, Zeros of polynomials with 0,1 coefficients, L’Enseignement Mathématique 39 (1993), 317-348.
EXAMPLE
For n = 7, the maximum number of distinct real roots of a degree-7 polynomial with coefficients 0,1 is 3; e.g., the polynomial x^7 + x^4 + x^2 + x has 3 distinct real roots.
MAPLE
f:= proc(n) local i, j, L, p, v, m;
m:= 0:
for i from 2^n to 2^(n+1)-1 do
L:= convert(i, base, 2);
p:= add(L[j]*x^(j-1), j=1..n+1);
v:= sturm(sturmseq(p, x), x, -infinity, infinity);
if v > m then m:= v fi;
od;
m
end proc:
map(f, [$1..19]); # Robert Israel, May 07 2023
MATHEMATICA
For[n=1, n<=8, n++, Print[Max[Length@DeleteDuplicates@NSolve[Total[x^#]+x^n==0, x, Reals]&/@Subsets[Range[0, n-1]]]]]
PROG
(MATLAB)
% uses the Sturm toolbox; see links
for i=2:13
display([i-1 maxroots(i)]);
end
function max_len=maxroots(n)
max_len = 0;
combinations = dec2bin(1:2:2^n-1) - '0';
for i = 1:2^(n-1)
c = combinations(i, :);
if sum(c, 2) == 1
continue;
end
len = distinct_real_roots(c);
if len > max_len
max_len = len;
end
end
end
function sign_var=distinct_real_roots(a)
S=Sturm();
S.build(Poly(a));
sign_var=0;
last_sign=0;
last_sign_parity=0;
parity=1;
for i=1:length(S.m_sturm)
v=S.m_sturm{i}.m_coeffs(end);
if v>0
if last_sign<0
sign_var = sign_var - 1;
end
if last_sign_parity == -parity
sign_var = sign_var + 1;
end
last_sign = 1;
last_sign_parity = parity;
elseif v<0
if last_sign>0
sign_var = sign_var - 1;
end
if last_sign_parity == parity
sign_var = sign_var + 1;
end
last_sign = -1;
last_sign_parity = -parity;
end
parity = -parity;
end
end
(Python)
from itertools import product
from sympy.abc import x
from sympy import sturm, oo, sign, nan, LT
def A362344(n):
c = 0
for s in product([0, 1], repeat=n):
q = sturm(x**n+sum(int(s[i])*x**i for i in range(n)))
a = [1 if (k:=LT(p).subs(x, -oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]
b = [1 if (k:=LT(p).subs(x, oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]
c = max(c, sum(1 for i in range(len(a)-1) if a[i]!=a[i+1])-sum(1 for i in range(len(b)-1) if b[i]!=b[i+1]))
return c # Chai Wah Wu, Feb 15 2024
(PARI) a(n) = my(nb=0, k); for (i=2^n, 2^(n+1)-1, k = #Set(polrootsreal(Pol(binary(i)))); if (k>nb, nb=k)); nb; \\ Michel Marcus, Feb 15 2024
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Keyang Li, May 05 2023
EXTENSIONS
a(14) on corrected by Robert Israel, May 07 2023
a(20)-a(22) from Michel Marcus, Feb 15 2024
a(23)-a(32) from Robin Visser, Aug 30 2024
STATUS
approved