A362344 Maximum number of distinct real roots of degree-n polynomial with coefficients 0,1.

1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5

Offset

1,2

Links

Table of n, a(n) for n=1..22.

Enrico Bertolazzi, Sturm

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

Possible duplicate of A090735 or A090736.

Sequence in context: A279220 A114575 A131849 * A244479 A090735 A090736

Adjacent sequences: A362341 A362342 A362343 * A362345 A362346 A362347

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

Status

approved