A368824 -id:A368824 - cp's OEIS frontend

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, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6

Offset: 1

Keyang Li, May 05 2023

			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.

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.

Cf. A368774, A368824.

% 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

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

For[n=1,n<=8,n++,Print[Max[Length@DeleteDuplicates@NSolve[Total[x^#]+x^n==0,x,Reals]&/@Subsets[Range[0,n-1]]]]]

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

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

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

A368774 a(n) is the number of distinct real roots of the polynomial whose coefficients are the digits of the binary expansion of n.

Original entry on oeis.org

0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0, 2, 0, 1, 0, 2, 0, 2, 0, 2, 1, 1, 0, 2, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0, 2, 0, 1, 0, 2, 0, 2, 0, 2, 2, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 2, 0, 2, 0, 2, 0, 1, 0, 2, 0, 2, 0, 2, 1, 1

Offset: 1

Denis Ivanov, Jan 05 2024

In the full-form binary representation of n = c_m*2^m + c_{m-1}*2^(m-1) + ... + c_0*2^0 we replace 2 with x and count the distinct real roots of the polynomial f_n(x) = c_m*x^m + c_{m-1}*x^(m-1) + ... + c_0.
Multiple roots count only once.
The first occurrences a(n) = 3, 4, 5, 6 are at n = 150, 1686, 854646 and 437545878, respectively.
a(n) >= 1 if n is even or has an even number of binary digits. - Robert Israel, Jan 08 2024

			n = 1 = 1*2^0 -> f_n(x) = 1*x^0 = 1 -> no roots, a(1) = 0.
n = 6 = 1*2^2 + 1*2^1 + 0*2^0 -> f_n(x) = x^2 + x = x*(x + 1) -> roots {0,-1}, a(6) = 2.
n = 150 = 1*2^7 + 0*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 0*2^0 -> f_n(x) = x^7 + x^4 + x^2 + x -> roots {-1, -0.755..., 0}, a(150) = 3.

Robin Visser, Table of n, a(n) for n = 1..10000
M. Filaseta, C. Finch and C. Nicol, On three questions concerning 0,1-polynomials, Journal de théorie des nombres de Bordeaux, Tome 18 (2006) no. 2, pp. 357-370.
D. Ivanov et al., Number of real roots of 0,1 polynomial, MathOverflow.

Cf. A362344, A368824.

f:= proc(n) local L,p,i,z;
  L:= convert(n,base,2);
  p:= add(L[i]*z^(i-1),i=1..nops(L));
  sturm(sturmseq(p,z),z,-infinity,infinity);
end proc:
map(f, [$1..100]); # Robert Israel, Jan 08 2024

a[n_]:=Length@{ToRules@Reduce[FromDigits[IntegerDigits[n, 2], x] == 0, x, Reals]};

a(n) = #Set(polrootsreal(Pol(binary(n)))); \\ Michel Marcus, Jan 05 2024

from sympy.abc import x
from sympy import sturm, oo, sign, nan, LT
def A368774(n):
    if n == 1: return 0
    l = len(s:=bin(n)[2:])
    q = sturm(sum(int(s[i])*x**(l-i-1) for i in range(l)))
    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])]
    return 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]) # Chai Wah Wu, Feb 15 2024

def a(n):
    R. = PolynomialRing(ZZ); poly = R(list(bin(n)[:1:-1]))
    return poly.number_of_real_roots()  # Robin Visser, Aug 03 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

MATLAB

Maple

Mathematica

PARI

Python

Extensions