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