%I #56 Aug 03 2024 15:02:01
%S 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,
%T 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,
%U 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
%N a(n) is the number of distinct real roots of the polynomial whose coefficients are the digits of the binary expansion of n.
%C 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.
%C Multiple roots count only once.
%C The first occurrences a(n) = 3, 4, 5, 6 are at n = 150, 1686, 854646 and 437545878, respectively.
%C a(n) >= 1 if n is even or has an even number of binary digits. - _Robert Israel_, Jan 08 2024
%H Robin Visser, <a href="/A368774/b368774.txt">Table of n, a(n) for n = 1..10000</a>
%H M. Filaseta, C. Finch and C. Nicol, <a href="https://doi.org/10.5802/jtnb.549">On three questions concerning 0,1-polynomials</a>, Journal de théorie des nombres de Bordeaux, Tome 18 (2006) no. 2, pp. 357-370.
%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.
%e n = 1 = 1*2^0 -> f_n(x) = 1*x^0 = 1 -> no roots, a(1) = 0.
%e 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.
%e 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.
%p f:= proc(n) local L,p,i,z;
%p L:= convert(n,base,2);
%p p:= add(L[i]*z^(i-1),i=1..nops(L));
%p sturm(sturmseq(p,z),z,-infinity,infinity);
%p end proc:
%p map(f, [$1..100]); # _Robert Israel_, Jan 08 2024
%t a[n_]:=Length@{ToRules@Reduce[FromDigits[IntegerDigits[n, 2], x] == 0, x, Reals]};
%o (PARI) a(n) = #Set(polrootsreal(Pol(binary(n)))); \\ _Michel Marcus_, Jan 05 2024
%o (Python)
%o from sympy.abc import x
%o from sympy import sturm, oo, sign, nan, LT
%o def A368774(n):
%o if n == 1: return 0
%o l = len(s:=bin(n)[2:])
%o q = sturm(sum(int(s[i])*x**(l-i-1) for i in range(l)))
%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 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
%o (Sage)
%o def a(n):
%o R.<x> = PolynomialRing(ZZ); poly = R(list(bin(n)[:1:-1]))
%o return poly.number_of_real_roots() # _Robin Visser_, Aug 03 2024
%Y Cf. A362344, A368824.
%K nonn,base
%O 1,6
%A _Denis Ivanov_, Jan 05 2024