login
Exponents of powers of squarefree numbers.
5

%I #11 Aug 19 2024 11:38:42

%S 1,1,1,2,1,1,1,3,2,1,1,1,1,1,4,1,1,1,1,1,2,1,3,1,1,1,5,1,1,1,2,1,1,1,

%T 1,1,1,1,1,2,1,1,1,1,1,1,1,1,6,1,1,1,1,1,1,1,1,1,1,1,4,1,1,1,1,1,1,1,

%U 1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,3,1,7,1,1,1,1,1,1,1,1,1,1,1,1

%N Exponents of powers of squarefree numbers.

%C A072774(n) = A072775(n)^a(n);

%C A072774(n) is squarefree iff a(n)=1.

%H Reinhard Zumkeller, <a href="/A072776/b072776.txt">Table of n, a(n) for n = 1..10000</a>

%o (Haskell)

%o a072776 n = a072776_list !! (n-1) -- a072776_list defined in A072774.

%o -- _Reinhard Zumkeller_, Apr 06 2014

%o (Python)

%o from math import isqrt

%o from sympy import mobius, integer_nthroot, perfect_power

%o def A072776(n):

%o def g(x): return int(sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1)))-1

%o def f(x): return n-2+x-sum(g(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length()))

%o kmin, kmax = 1,2

%o while f(kmax) >= kmax:

%o kmax <<= 1

%o while True:

%o kmid = kmax+kmin>>1

%o if f(kmid) < kmid:

%o kmax = kmid

%o else:

%o kmin = kmid

%o if kmax-kmin <= 1:

%o break

%o return 1 if not (p:=perfect_power(kmax)) else p[1] # _Chai Wah Wu_, Aug 19 2024

%Y Cf. A052409.

%K nonn

%O 1,4

%A _Reinhard Zumkeller_, Jul 10 2002