login
Powers of squarefree numbers.
124

%I #38 Aug 19 2024 02:20:45

%S 1,2,3,4,5,6,7,8,9,10,11,13,14,15,16,17,19,21,22,23,25,26,27,29,30,31,

%T 32,33,34,35,36,37,38,39,41,42,43,46,47,49,51,53,55,57,58,59,61,62,64,

%U 65,66,67,69,70,71,73,74,77,78,79,81,82,83,85,86,87,89,91,93,94,95,97

%N Powers of squarefree numbers.

%C a(n) = A072775(n)^A072776(n); complement of A059404.

%C Essentially the same as A062770. - _R. J. Mathar_, Sep 25 2008

%C Numbers m such that in canonical prime factorization all prime exponents are identical: A124010(m,k) = A124010(m,1) for k = 2..A000005(m). - _Reinhard Zumkeller_, Apr 06 2014

%C Heinz numbers of uniform partitions. An integer partition is uniform if all parts appear with the same multiplicity. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). - _Gus Wiseman_, Apr 16 2018

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

%t Select[Range[100], Length[Union[FactorInteger[#][[All, 2]]]] == 1 &] (* _Geoffrey Critzer_, Mar 30 2015 *)

%o (Haskell)

%o import Data.Map (empty, findMin, deleteMin, insert)

%o import qualified Data.Map.Lazy as Map (null)

%o a072774 n = a072774_list !! (n-1)

%o (a072774_list, a072775_list, a072776_list) = unzip3 $

%o (1, 1, 1) : f (tail a005117_list) empty where

%o f vs'@(v:vs) m

%o | Map.null m || xx > v = (v, v, 1) :

%o f vs (insert (v^2) (v, 2) m)

%o | otherwise = (xx, bx, ex) :

%o f vs' (insert (bx*xx) (bx, ex+1) $ deleteMin m)

%o where (xx, (bx, ex)) = findMin m

%o -- _Reinhard Zumkeller_, Apr 06 2014

%o (PARI) is(n)=ispower(n,,&n); issquarefree(n) \\ _Charles R Greathouse IV_, Oct 16 2015

%o (Python)

%o from math import isqrt

%o from sympy import mobius, integer_nthroot

%o def A072774(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 kmax # _Chai Wah Wu_, Aug 19 2024

%Y Cf. A072777 (subsequence), A005117, A072778, A329332 (tabular arrangement).

%Y A subsequence of A242414.

%Y Cf. A000009, A000837, A007916, A047966, A052409, A052410, A072774, A078374, A289023, A289509, A300486, A302491, A302796, A302979.

%K nonn

%O 1,2

%A _Reinhard Zumkeller_, Jul 10 2002