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

%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