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

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

Author

Denis Ivanov, Jan 05 2024

Keywords

• nonn
• base

Comments

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

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A362344, A368824.

Programs

Maple

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

Mathematica

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

PARI

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

Python

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

Sage

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