A373549 - OEIS

A373549

a(n) is the parity of the n-th powerful number.

%I #13 Sep 11 2024 00:34:43

%S 1,0,0,1,0,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,0,1,1,0,0,1,0,1,1,0,0,0,

%T 1,0,0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,

%U 0,0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,1,0,1

%N a(n) is the parity of the n-th powerful number.

%H Amiram Eldar, <a href="/A373549/b373549.txt">Table of n, a(n) for n = 1..10000</a>

%H Teerapat Srichan, <a href="http://www.math.nthu.edu.tw/~amen/2020/AMEN-200219.pdf">The odd/even dichotomy for the set of square-full numbers</a>, Applied Mathematics E-Notes, Vol. 20 (2020), pp. 528-531.

%H Wikipedia, <a href="https://oeis.org/A363176/b363176.txt">Powerful number</a>.

%F a(n) = A001694(n) mod 2 = A000035(A001694(n)).

%F Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = (2 - sqrt(2))/(3 - sqrt(2)) = 0.3693980625... .

%t Mod[Select[Range[5000], # == 1 || Min[FactorInteger[#][[;;, 2]]] > 1 &], 2]

%o (PARI) lista(kmax) = for(k = 1, kmax, if(ispowerful(k), print1(k % 2, ", ")));

%o (Python)

%o from math import isqrt

%o from sympy import mobius, integer_nthroot

%o def A373549(n):

%o def squarefreepi(n):

%o return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))

%o def bisection(f, kmin=0, kmax=1):

%o while f(kmax) > kmax: kmax <<= 1

%o while kmax-kmin > 1:

%o kmid = kmax+kmin>>1

%o if f(kmid) <= kmid:

%o kmax = kmid

%o else:

%o kmin = kmid

%o return kmax

%o def f(x):

%o c, l = n+x, 0

%o j = isqrt(x)

%o while j>1:

%o k2 = integer_nthroot(x//j**2, 3)[0]+1

%o w = squarefreepi(k2-1)

%o c -= j*(w-l)

%o l, j = w, isqrt(x//k2**3)

%o c -= squarefreepi(integer_nthroot(x, 3)[0])-l

%o return c

%o return bisection(f,n,n)&1 # _Chai Wah Wu_, Sep 10 2024

%Y Characteristic function of A363189.

%Y Cf. A000035, A001694, A062739, A335851, A363191, A363192, A373550.

%K nonn,easy

%O 1

%A _Amiram Eldar_, Jun 09 2024