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
KEYWORD
nonn,base
AUTHOR
Denis Ivanov, Jan 05 2024
STATUS
approved