cp's OEIS Frontend

A368824 a(n) is the smallest degree of (0,1)-polynomial with exactly n real distinct roots.

%I A368824 #44 Mar 30 2024 06:34:35
%S A368824 1,2,7,10,19,28
%N A368824 a(n) is the smallest degree of (0,1)-polynomial with exactly n real distinct roots.
%C A368824 (0,1) (or Newman) polynomials have coefficients from {0,1}.
%H A368824 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 A368824 MathOverflow, <a href="https://mathoverflow.net/questions/461631/number-of-real-roots-of-0-1-polynomial">Number of real roots of 0,1 polynomial</a>.
%H A368824 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.
%F A368824 a(n) ~ C*n^2 (see Odlyzko and Poonen) with numerical estimate 0.7 < C < 0.9.
%t A368824 (* Suitable only for 1 <= n <= 4;
%t A368824 for larger n, special Julia and Python packages are needed *)
%t A368824 Table[Exponent[Monitor[Catch[Do[
%t A368824    poly = FromDigits[IntegerDigits[k, 2], x];
%t A368824    res = Length@{ToRules@Reduce[poly == 0, x, Reals]};
%t A368824    If[res == n, Throw@{res, Expand@poly}]
%t A368824    , {k, 2000}]], k][[2]], x], {n, 1, 4}]
%o A368824 (Python)
%o A368824 from itertools import count
%o A368824 from sympy.abc import x
%o A368824 from sympy import sturm, oo, sign, nan, LT
%o A368824 def A368824(n):
%o A368824     for m in count(2):
%o A368824         l = len(s:=bin(m)[2:])
%o A368824         q = sturm(sum(int(s[i])*x**(l-i-1) for i in range(l)))
%o A368824         a = [1 if (k:=LT(p).subs(x,-oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]
%o A368824         b = [1 if (k:=LT(p).subs(x,oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]
%o A368824         if n==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 A368824             return l-1 # _Chai Wah Wu_, Feb 15 2024
%Y A368824 Cf. A368774, A362344.
%K A368824 nonn,hard,more
%O A368824 1,2
%A A368824 _Denis Ivanov_, Jan 07 2024