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

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

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.

Example

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.

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]};

Prog

(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.<x> = PolynomialRing(ZZ); poly = R(list(bin(n)[:1:-1]))
    return poly.number_of_real_roots()  # Robin Visser, Aug 03 2024

Crossrefs

Cf. A362344, A368824.

Sequence in context: A284203 A375106 A341594 * A005087 A050332 A369258

Adjacent sequences: A368771 A368772 A368773 * A368775 A368776 A368777

Keyword

nonn,base

Author

Denis Ivanov, Jan 05 2024

Status

approved