A277576 a(1)=1; thereafter a(n) = A007916(a(n-1)).

1, 2, 3, 5, 7, 11, 15, 20, 26, 34, 43, 53, 63, 74, 86, 98, 111, 126, 142, 159, 177, 195, 214, 235, 258, 281, 305, 330, 356, 383, 411, 439, 468, 498, 530, 562, 595, 629, 663, 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

Offset: 1

Author

Gus Wiseman, Oct 20 2016

Keywords

• nonn

Comments

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.

Examples

			The first forty plane trees:
()         11(((((())))))      ((()()()))         (((((((()())))))))
2(())         ((()(())))        ((((()(())))))     (()((())))
3((()))       (((())()))        (((((())()))))     ((((()))()))
(()())       ((((()()))))      ((((((()())))))) 34(((((((((())))))))))
5(((())))   15((((((()))))))    (((()))())         (((())(())))
((()()))     (()()())        26((((((((())))))))) ((()())())
7((((()))))   (((()(()))))      ((())(()))         ((((()()()))))
(()(()))     ((((())())))      (((()()())))       ((((((()(())))))))
((())())     (((((()())))))    (((((()(()))))))   (((((((())()))))))
(((()()))) 20(((((((())))))))  ((((((())())))))   ((((((((()()))))))))
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms 1..2480 from Gus Wiseman)

Crossrefs

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

Programs

Mathematica

radicalQ[1]:=False;radicalQ[n_]:=SameQ[GCD@@FactorInteger[n][[All,2]],1];
rad[0]:=1;rad[n_?Positive]:=rad[n]=NestWhile[#+1&,rad[n-1]+1,Not[radicalQ[#]]&];
nn=2000;Scan[rad,Range[nn]];NestWhileList[rad,1,#
				

Python

from itertools import islice
from sympy import mobius, integer_nthroot
def A277576_gen(): # generator of terms
    def iterfun(f,n=0):
        m, k = n, f(n)
        while m != k: m, k = k, f(k)
        return m
    def f(x): return int(1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    a = 1
    while True:
        yield a
        a = iterfun(lambda x:f(x)+a,a)
A277576_list = list(islice(A277576_gen(),40)) # Chai Wah Wu, Nov 21 2024

Extensions

Edited by N. J. A. Sloane, Nov 09 2016