%I #50 Sep 03 2024 00:59:29
%S 1,2,2,2,2,2,3,3,3,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,6,6,6,6,6
%N Maximum number of distinct real roots of degree-n polynomial with coefficients 0,1.
%H Enrico Bertolazzi, <a href="https://github.com/ebertolazzi/Sturm">Sturm</a>.
%H P. Borwein, T. Erdélyi, and G. Kós, <a href="https://doi.org/10.1112/S0024611599011831">Littlewood-type problems on [0,1]</a>, Proc. London Math. Soc. 79 (1999), 22-46.
%H D. Ivanov et al., <a href="https://mathoverflow.net/questions/461631/number-of-real-roots-of-0-1-polynomial">Number of real roots of 0,1 polynomial</a>, MathOverflow.
%H A. Odlyzko and B. Poonen, <a href="https://doi.org/10.5169/seals-60430">Zeros of polynomials with 0,1 coefficients</a>, L’Enseignement Mathématique 39 (1993), 317-348.
%e 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.
%p f:= proc(n) local i,j,L,p,v,m;
%p m:= 0:
%p for i from 2^n to 2^(n+1)-1 do
%p L:= convert(i,base,2);
%p p:= add(L[j]*x^(j-1),j=1..n+1);
%p v:= sturm(sturmseq(p,x),x,-infinity,infinity);
%p if v > m then m:= v fi;
%p od;
%p m
%p end proc:
%p map(f, [$1..19]); # _Robert Israel_, May 07 2023
%t For[n=1,n<=8,n++,Print[Max[Length@DeleteDuplicates@NSolve[Total[x^#]+x^n==0,x,Reals]&/@Subsets[Range[0,n-1]]]]]
%o (MATLAB)
%o % uses the Sturm toolbox; see links
%o for i=2:13
%o display([i-1 maxroots(i)]);
%o end
%o function max_len=maxroots(n)
%o max_len = 0;
%o combinations = dec2bin(1:2:2^n-1) - '0';
%o for i = 1:2^(n-1)
%o c = combinations(i,:);
%o if sum(c, 2) == 1
%o continue;
%o end
%o len = distinct_real_roots(c);
%o if len > max_len
%o max_len = len;
%o end
%o end
%o end
%o function sign_var=distinct_real_roots(a)
%o S=Sturm();
%o S.build(Poly(a));
%o sign_var=0;
%o last_sign=0;
%o last_sign_parity=0;
%o parity=1;
%o for i=1:length(S.m_sturm)
%o v=S.m_sturm{i}.m_coeffs(end);
%o if v>0
%o if last_sign<0
%o sign_var = sign_var - 1;
%o end
%o if last_sign_parity == -parity
%o sign_var = sign_var + 1;
%o end
%o last_sign = 1;
%o last_sign_parity = parity;
%o elseif v<0
%o if last_sign>0
%o sign_var = sign_var - 1;
%o end
%o if last_sign_parity == parity
%o sign_var = sign_var + 1;
%o end
%o last_sign = -1;
%o last_sign_parity = -parity;
%o end
%o parity = -parity;
%o end
%o end
%o (Python)
%o from itertools import product
%o from sympy.abc import x
%o from sympy import sturm, oo, sign, nan, LT
%o def A362344(n):
%o c = 0
%o for s in product([0,1],repeat=n):
%o q = sturm(x**n+sum(int(s[i])*x**i for i in range(n)))
%o a = [1 if (k:=LT(p).subs(x,-oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]
%o b = [1 if (k:=LT(p).subs(x,oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]
%o 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]))
%o return c # _Chai Wah Wu_, Feb 15 2024
%o (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
%Y Cf. A368774, A368824.
%K nonn,more
%O 1,2
%A _Keyang Li_, May 05 2023
%E a(14) on corrected by _Robert Israel_, May 07 2023
%E a(20)-a(22) from _Michel Marcus_, Feb 15 2024
%E a(23)-a(32) from _Robin Visser_, Aug 30 2024