cp's OEIS Frontend

A072776 Exponents of powers of squarefree numbers.

%I A072776 #11 Aug 19 2024 11:38:42
%S A072776 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 A072776 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 A072776 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 A072776 Exponents of powers of squarefree numbers.
%C A072776 A072774(n) = A072775(n)^a(n);
%C A072776 A072774(n) is squarefree iff a(n)=1.
%H A072776 Reinhard Zumkeller, <a href="/A072776/b072776.txt">Table of n, a(n) for n = 1..10000</a>
%o A072776 (Haskell)
%o A072776 a072776 n = a072776_list !! (n-1)  -- a072776_list defined in A072774.
%o A072776 -- _Reinhard Zumkeller_, Apr 06 2014
%o A072776 (Python)
%o A072776 from math import isqrt
%o A072776 from sympy import mobius, integer_nthroot, perfect_power
%o A072776 def A072776(n):
%o A072776     def g(x): return int(sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1)))-1
%o A072776     def f(x): return n-2+x-sum(g(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length()))
%o A072776     kmin, kmax = 1,2
%o A072776     while f(kmax) >= kmax:
%o A072776         kmax <<= 1
%o A072776     while True:
%o A072776         kmid = kmax+kmin>>1
%o A072776         if f(kmid) < kmid:
%o A072776             kmax = kmid
%o A072776         else:
%o A072776             kmin = kmid
%o A072776         if kmax-kmin <= 1:
%o A072776             break
%o A072776     return 1 if not (p:=perfect_power(kmax)) else p[1] # _Chai Wah Wu_, Aug 19 2024
%Y A072776 Cf. A052409.
%K A072776 nonn
%O A072776 1,4
%A A072776 _Reinhard Zumkeller_, Jul 10 2002