cp's OEIS Frontend

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

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