A277576 - OEIS

%I #21 Nov 22 2024 01:49:57

%S 1,2,3,5,7,11,15,20,26,34,43,53,63,74,86,98,111,126,142,159,177,195,

%T 214,235,258,281,305,330,356,383,411,439,468,498,530,562,595,629,663,

%U 698,734,770,807,845,883,922,962,1003,1045,1087,1130,1174,1218,1263,1309,1356,1404,1453,1502,1552,1603,1654,1706,1759

%N a(1)=1; thereafter a(n) = A007916(a(n-1)).

%C Non-perfect-powers (A007916) are numbers such that the exponents in their prime factorizations have GCD equal to 1. For each n we can construct a plane tree by replacing all positive integers at any level with their corresponding planar factorization sequences (A277564), and repeating this replacement until no numbers are left. The result will be a unique "pure" sequence or plane tree. Under this correspondence a(n) is the path tree ((((((...)))))) = string of n consecutive open brackets followed by the same number of closed brackets.

%H Chai Wah Wu, <a href="/A277576/b277576.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..2480 from Gus Wiseman)

%e The first forty plane trees:

%e ()         11(((((())))))      ((()()()))         (((((((()())))))))

%e 2(())         ((()(())))        ((((()(())))))     (()((())))

%e 3((()))       (((())()))        (((((())()))))     ((((()))()))

%e (()())       ((((()()))))      ((((((()())))))) 34(((((((((())))))))))

%e 5(((())))   15((((((()))))))    (((()))())         (((())(())))

%e ((()()))     (()()())        26((((((((())))))))) ((()())())

%e 7((((()))))   (((()(()))))      ((())(()))         ((((()()()))))

%e (()(()))     ((((())())))      (((()()())))       ((((((()(())))))))

%e ((())())     (((((()())))))    (((((()(()))))))   (((((((())()))))))

%e (((()()))) 20(((((((())))))))  ((((((())())))))   ((((((((()()))))))))

%t radicalQ[1]:=False;radicalQ[n_]:=SameQ[GCD@@FactorInteger[n][[All,2]],1];

%t rad[0]:=1;rad[n_?Positive]:=rad[n]=NestWhile[#+1&,rad[n-1]+1,Not[radicalQ[#]]&];

%t nn=2000;Scan[rad,Range[nn]];NestWhileList[rad,1,#<nn&]

%o (Python)

%o from itertools import islice

%o from sympy import mobius, integer_nthroot

%o def A277576_gen(): # generator of terms

%o     def iterfun(f,n=0):

%o         m, k = n, f(n)

%o         while m != k: m, k = k, f(k)

%o         return m

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

%o     a = 1

%o     while True:

%o         yield a

%o         a = iterfun(lambda x:f(x)+a,a)

%o A277576_list = list(islice(A277576_gen(),40)) # _Chai Wah Wu_, Nov 21 2024

%Y Cf. A007916, A277564, A276625, A004111 (rooted trees), A007097 (rooted paths).

%K nonn

%O 1,2

%A _Gus Wiseman_, Oct 20 2016

%E Edited by _N. J. A. Sloane_, Nov 09 2016