A277564 -id:A277564 - cp's OEIS frontend

A277615 a(1)=1; thereafter, if n = c(x_1)^...^c(x_k) (where c(k) = A007916(k) and with parentheses nested from the right, as in the definition of A277564), a(n) = 1 + a(x_1) + ... + a(x_k).

1, 2, 3, 3, 4, 4, 5, 4, 4, 5, 6, 5, 5, 6, 7, 4, 6, 6, 7, 8, 5, 7, 7, 8, 5, 9, 5, 6, 8, 8, 9, 5, 6, 10, 6, 5, 7, 9, 9, 10, 6, 7, 11, 7, 6, 8, 10, 10, 6, 11, 7, 8, 12, 8, 7, 9, 11, 11, 7, 12, 8, 9, 13, 5, 9, 8, 10, 12, 12, 8, 13, 9, 10, 14, 6, 10, 9, 11, 13, 13, 5, 9, 14, 10, 11, 15, 7, 11, 10, 12, 14, 14, 6, 10, 15, 11, 12

Offset: 1

Gus Wiseman, Oct 23 2016

A007916 lists the numbers whose prime multiplicities are relatively prime. For each n we can construct a plane tree by repeatedly factoring all positive integers at any level into their corresponding power towers of non-perfect-powers (see A277564). a(n) is the number of nodes in this plane tree.

			a(1)=1, a(2)=1+a(1)=2, a(3)=1+a(2)=3, a(4)=1+a(1)+a(1)=3 because 4=c(1)^c(1), a(8)=1+a(1)+a(2)=4 because 8=c(1)^c(2), a(9)=1+a(2)+a(1)=4 because 9=c(2)^c(1), a(10)=1+a(6)=5 because 10=c(6).

Gus Wiseman, Table of n, a(n) for n = 1..10000

Cf. A000108, A007916, A014221, A277564, A277576.

nn=10000;
radicalQ[1]:=False;radicalQ[n_]:=SameQ[GCD@@FactorInteger[n][[All,2]],1];
hyperfactor[1]:={};hyperfactor[n_?radicalQ]:={n};
hyperfactor[n_]:=With[{g=GCD@@FactorInteger[n][[All,2]]},Prepend[hyperfactor[g],Product[Apply[Power[#1,#2/g]&,r],{r,FactorInteger[n]}]]];
rad[0]:=1;rad[n_?Positive]:=rad[n]=NestWhile[#+1&,rad[n-1]+1,Not[radicalQ[#]]&];Set@@@Array[radPi[rad[#]]==#&,nn];
rnk[n_]:=rnk[n]=1+Total[rnk/@radPi/@hyperfactor[n]];
Array[rnk,nn]

First appearance of n is a(A277576(n)). Last appearance of n is a(2^^{n-1}) where ^^ denotes iterated exponentiation (or tetration).

Number of appearances of n is the Catalan number |{k:a(k)=n}| = C_{n-1}.

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

A007916 Numbers that are not perfect powers.

Original entry on oeis.org

2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 82, 83

Offset: 1

R. Muller

From Gus Wiseman, Oct 23 2016: (Start)
There is a 1-to-1 correspondence between integers N >= 2 and sequences a(x_1),a(x_2),...,a(x_k) of terms from this sequence. Every N >= 2 can be written uniquely as a "power tower"
N = a(x_1)^a(x_2)^a(x_3)^...^a(x_k),
where the exponents are to be nested from the right.
Proof: If N is not a perfect power then N = a(x) for some x, and we are done. Otherwise, write N = a(x_1)^M for some M >=2, and repeat the process. QED
Of course, prime numbers also have distinct power towers (see A164336). (End)
These numbers can be computed with a modified Sieve of Eratosthenes: (1) start at n=2; (2) if n is not crossed out, then append n to the sequence and cross out all powers of n; (3) set n = n+1 and go to step 2. - Sam Alexander, Dec 15 2003
These are all numbers such that the multiplicities of the prime factors have no common divisor. The first number in the sequence whose prime multiplicities are not coprime is 180 = 2 * 2 * 3 * 3 * 5. Mathematica: CoprimeQ[2,2,1]->False. - Gus Wiseman, Jan 14 2017

			Example of the power tower factorizations for the first nine positive integers: 1=1, 2=a(1), 3=a(2), 4=a(1)^a(1), 5=a(3), 6=a(4), 7=a(5), 8=a(1)^a(2), 9=a(2)^a(1). - _Gus Wiseman_, Oct 20 2016

N. J. A. Sloane, Table of n, a(n) for n = 1..9875
Joakim Munkhammar, The Riemann zeta function as a sum of geometric series, The Mathematical Gazette (2020) Vol. 104, Issue 561, 527-530.
N. J. A. Sloane, Maple programs for A007916, A278028, A278029, A052409, A089723, A277564
F. Smarandache, Only Problems, Not Solutions!, Xiquan Publ., Phoenix-Chicago, 1993
Index entries for sequences generated by sieves

Complement of A001597. Union of A052485 and A052486.
Cf. A144338, A277562, A277564, A075802.
Cf. A153158 (squares of these numbers).
See A277562, A277564, A277576, A277615 for more about the power towers.
A278029 is a left inverse.
Cf. A052409.

a007916 n = a007916_list !! (n-1)
a007916_list = filter ((== 1) . foldl1 gcd . a124010_row) [2..]
-- Reinhard Zumkeller, Apr 13 2012

[n : n in [2..1000] | not IsPower(n) ];

Maple
```
See link.
```

a = {}; Do[If[Apply[GCD, Transpose[FactorInteger[n]][[2]]] == 1, a = Append[a, n]], {n, 2, 200}];
Select[Range[2,200],GCD@@FactorInteger[#][[All,-1]]===1&] (* Michael De Vlieger, Oct 21 2016. Corrected by Gus Wiseman, Jan 14 2017 *)

is(n)=!ispower(n)&&n>1 \\ Charles R Greathouse IV, Jul 01 2013

from sympy import mobius, integer_nthroot
def A007916(n):
    def f(x): return int(n+1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return m # Chai Wah Wu, Aug 13 2024

A075802(a(n)) = 0. - Reinhard Zumkeller, Mar 19 2009
Gcd(exponents in prime factorization of a(n)) = 1, cf. A124010. - Reinhard Zumkeller, Apr 13 2012
a(n) ~ n. - Charles R Greathouse IV, Jul 01 2013
A052409(a(n)) = 1. - Ridouane Oudra, Nov 23 2024

More terms from Henry Bottomley, Sep 12 2000
Edited by Charles R Greathouse IV, Mar 18 2010
Further edited by N. J. A. Sloane, Nov 09 2016

A052409 a(n) = largest integer power m for which a representation of the form n = k^m exists (for some k).

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1

Offset: 1

Eric W. Weisstein

nonn

Greatest common divisor of all prime-exponents in canonical factorization of n for n>1: a(n)>1 iff n is a perfect power; a(A001597(k))=A025479(k). - Reinhard Zumkeller, Oct 13 2002
a(1) set to 0 since there is no largest finite integer power m for which a representation of the form 1 = 1^m exists (infinite largest m). - Daniel Forgues, Mar 06 2009
A052410(n)^a(n) = n. - Reinhard Zumkeller, Apr 06 2014
Positions of 1's are A007916. Smallest base is given by A052410. - Gus Wiseman, Jun 09 2020

			n = 72 = 2*2*2*3*3: GCD[exponents] = GCD[3,2] = 1. This is the least n for which a(n) <> A051904(n), the minimum of exponents.
For n = 10800 = 2^4 * 3^3 * 5^2, GCD[4,3,2] = 1, thus a(10800) = 1.

Daniel Forgues, Table of n, a(n) for n = 1..100000
N. J. A. Sloane, Maple programs for A007916, A278028, A278029, A052409, A089723, A277564
Eric Weisstein's World of Mathematics, Power
Eric Weisstein's World of Mathematics, Perfect Power
Index entries for sequences computed from exponents in factorization of n

Cf. A052410, A005361, A051903, A072411-A072414, A124010, A075802, A072776, A270492.
Apart from the initial term essentially the same as A253641.
Differs from A051904 for the first time at n=72, where a(72) = 1, while A051904(72) = 2.
Differs from A158378 for the first time at n=10800, where a(10800) = 1, while A158378(10800) = 2.
Cf. A000005, A000961, A001597, A052410, A303386, A327501.

a052409 1 = 0
a052409 n = foldr1 gcd $ a124010_row n
-- Reinhard Zumkeller, May 26 2012

# See link.
#
a:= n-> igcd(map(i-> i[2], ifactors(n)[2])[]):
seq(a(n), n=1..120);  # Alois P. Heinz, Oct 20 2019

Table[GCD @@ Last /@ FactorInteger[n], {n, 100}] (* Ray Chandler, Jan 24 2006 *)

a(n)=my(k=ispower(n)); if(k, k, n>1) \\ Charles R Greathouse IV, Oct 30 2012

from math import gcd
from sympy import factorint
def A052409(n): return gcd(*factorint(n).values()) # Chai Wah Wu, Aug 31 2022

(define (A052409 n) (if (= 1 n) 0 (gcd (A067029 n) (A052409 (A028234 n))))) ;; Antti Karttunen, Aug 07 2017

a(1) = 0; for n > 1, a(n) = gcd(A067029(n), a(A028234(n))). - Antti Karttunen, Aug 07 2017

More terms from Labos Elemer, Jun 17 2002

A089723 a(1)=1; for n>1, a(n) gives number of ways to write n as n = x^y, 2 <= x, 1 <= y.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1

Offset: 1

Naohiro Nomoto, Jan 07 2004

This function depends only on the prime signature of n. - Franklin T. Adams-Watters, Mar 10 2006
a(n) is the number of perfect divisors of n. Perfect divisor of n is divisor d such that d^k = n for some k >= 1. a(n) > 1 for perfect powers n = A001597(m) for m > 2. - Jaroslav Krizek, Jan 23 2010
Also the number of uniform perfect integer partitions of n - 1. An integer partition of n is uniform if all parts appear with the same multiplicity, and perfect if every nonnegative integer up to n is the sum of a unique submultiset. The Heinz numbers of these partitions are given by A326037. The a(16) = 3 partitions are: (8,4,2,1), (4,4,4,1,1,1), (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1). - Gus Wiseman, Jun 07 2019
The record values occur at 1 and at 2^A002182(n) for n > 1. - Amiram Eldar, Nov 06 2020

			144 = 2^4 * 3^2, gcd(4,2) = 2, d(2) = 2, so a(144) = 2. The representations are 144^1 and 12^2.
From _Friedjof Tellkamp_, Jun 14 2025: (Start)
n:          1, 2, 3, 4, 5, 6, 7, 8, 9, ...
----------------------------------------------------
1st powers: 1, 1, 1, 1, 1, 1, 1, 1, 1, ... (A000012)
Squares:    1, 0, 0, 1, 0, 0, 0, 0, 1, ... (A010052)
Cubes:      1, 0, 0, 0, 0, 0, 0, 1, 0, ... (A010057)
Quartics:   1, 0, 0, 0, 0, 0, 0, 0, 0, ... (A374016)
...
Sum:       oo, 1, 1, 2, 1, 1, 1, 2, 2, ...
a(1)=1:     1, 1, 1, 2, 1, 1, 1, 2, 2, ... (= this sequence). (End)

N. J. A. Sloane, Table of n, a(n) for n = 1..20000
Solomon W. Golomb, A new arithmetic function of combinatorial significance, J. Number Theory, Vol. 5, No. 3 (1973), pp. 218-223. 1973JNT.....5..218G
Jan Mycielski, Sur les représentations des nombres naturels par des puissances à base et exposant naturels, Colloquium Mathematicum, Vol. 2 (1951), pp. 254-260. See gamma(n).
N. J. A. Sloane, Maple programs for A007916, A278028, A278029, A052409, A089723, A277564

Cf. A000005, A277564, A278028.
Cf. A000961, A002033, A002182, A007916, A047966, A070941, A108917, A126796, A276024, A326035, A326036, A326037.
Cf. A010052, A010057, A374016, A259362.

with(numtheory):
A089723 := proc(n) local t1,t2,g,j;
if n=1 then 1 else
t1:=ifactors(n)[2]; t2:=nops(t1); g := t1[1][2];
for j from 2 to t2 do g:=gcd(g,t1[j][2]); od:
tau(g); fi; end;
[seq(A089723(n),n=1..100)]; # N. J. A. Sloane, Nov 10 2016

Table[DivisorSigma[0, GCD @@ FactorInteger[n][[All, 2]]], {n, 100}] (* Gus Wiseman, Jun 12 2017 *)

a(n) = if (n==1, 1, numdiv(gcd(factor(n)[,2]))); \\ Michel Marcus, Jun 13 2017

from math import gcd
from sympy import factorint, divisor_sigma
def a(n):
    if n == 1: return 1
    e = list(factorint(n).values())
    g = e[0]
    for ei in e[1:]: g = gcd(g, ei)
    return divisor_sigma(g, 0)
print([a(n) for n in range(1, 105)]) # Michael S. Branicky, Jul 15 2021

If n = Product p_i^e_i, a(n) = d(gcd()). - Franklin T. Adams-Watters, Mar 10 2006
Sum_{n=1..m} a(n) = A255165(m) + 1. - Richard R. Forberg, Feb 16 2015
Sum_{n>=2} a(n)/n^s = Sum_{n>=2} 1/(n^s-1) = Sum_{k>=1} (zeta(s*k)-1) for all real s with Re(s) > 1 (Golomb, 1973). - Amiram Eldar, Nov 06 2020
For n > 1, a(n) = Sum_{i=1..floor(n/2)} floor(n^(1/i))-floor((n-1)^(1/i)). - Wesley Ivan Hurt, Dec 08 2020
Sum_{n>=1} (a(n)-1)/n = 1 (Mycielski, 1951). - Amiram Eldar, Jul 15 2021
From Friedjof Tellkamp, Jun 14 2025: (Start)
a(n) = 1 + A259362(n) = 1 + A010052(n) + A010057(n) + A374016(n) + (...), for n > 1.
G.f.: x + Sum_{j>=2, k>=1} x^(j^k). (End)

A288636 Height of power-tower factorization of n. Row lengths of A278028.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, Jun 12 2017

nonn

After a(1)=0 this sequence has many terms equal to A089723. It first differs at a(64)=2, A089723(64)=4.

First positions of a(n) = {0, 1, 2, 3, 4} are n = {1, 2, 4, 16, 65536}. - Michael De Vlieger, Nov 24 2017

Michael De Vlieger, Table of n, a(n) for n = 1..65536

Cf. A007916, A089723, A164337, A277562, A277564, A278028.

a[n_] := If[n == 1, 0, 1+a[GCD @@ FactorInteger[n][[All, 2]]]];
Array[a,100]

A278028 Let {c(i)} = A007916 denote the sequence of numbers > 1 which are not perfect powers. Every positive integer n has a unique representation as a tower n = c(x_1)^c(x_2)^c(x_3)^...^c(x_k), where the exponents are nested from the right. The sequence is an irregular triangle read by rows, where the n-th row lists x_1, ..., x_k.

Original entry on oeis.org

1, 2, 1, 1, 3, 4, 5, 1, 2, 2, 1, 6, 7, 8, 9, 10, 11, 1, 1, 1, 12, 13, 14, 15, 16, 17, 18, 19, 3, 1, 20, 2, 2, 21, 22, 23, 24, 1, 3, 25, 26, 27, 4, 1, 28, 29, 30, 31

Offset: 1

N. J. A. Sloane, Nov 09 2016

Row lengths are A288636(n). - Gus Wiseman, Jun 12 2017

			Rows 2 through 32 are:
1,
2,
1, 1,
3,
4,
5,
1, 2,
2, 1,
6,
7,
8,
9,
10,
11,
1, 1, 1,
12,
13,
14,
15,
16,
17,
18,
19,
3, 1,
20,
2, 2,
21,
22,
23,
24,
1, 3,
...

N. J. A. Sloane, Table of n, a(n) for n = 1..20181
N. J. A. Sloane, Maple programs for A007916, A278028, A278029, A052409, A089723, A277564

See A277564 for another version.

Cf. A007916, A089723, A277562, A288636.

A279944 Number of positions in the free pure symmetric multifunction in one symbol with j-number n.

Original entry on oeis.org

1, 3, 5, 5, 7, 7, 9, 4, 7, 9, 11, 6, 9, 11, 13, 7, 8, 11, 13, 15, 9, 10, 13, 15, 9, 17, 6, 11, 12, 15, 17, 6, 11, 19, 8, 9, 13, 14, 17, 19, 8, 13, 21, 10, 11, 15, 16, 19, 11, 21, 10, 15, 23, 12, 13, 17, 18, 21, 13, 23, 12, 17, 25, 7, 14, 15, 19, 20, 23, 15, 25, 14, 19, 27, 9, 16, 17, 21, 22, 25, 9, 17, 27, 16, 21, 29, 11, 18, 19, 23, 24, 27, 11, 19, 29, 18, 23, 31, 13, 11

Offset: 1

Gus Wiseman, Dec 24 2016

nonn

A free pure symmetric multifunction in one symbol f in PSM(x) is either (case 1) f = the symbol x, or (case 2) f = an expression of the form h[g_1,...,g_k] where h is in PSM(x), each of the g_i for i=1..(k>0) is in PSM(x), and for i < j we have g_i <= g_j under a canonical total ordering of PSM(x), such as the Mathematica ordering of expressions. For a positive integer n we define a free pure symmetric multifunction j(n) by: j(1)=x; j(n>1) = j(h)[j(g_1),...,j(g_k)] where n = r(h)^(p(g_1)*...*p(g_k)-1). Here r(n) is the n-th number that is not a perfect power (A007916) and p(n) is the n-th prime number (A000040). See example. Then a(n) is the number of brackets [...] plus the number of x's in j(n).

			The first 20 free pure symmetric multifunctions in x are:
j(1)  = j(1)            = x
j(2)  = j(1)[j(1)]      = x[x]
j(3)  = j(2)[j(1)]      = x[x][x]
j(4)  = j(1)[j(2)]      = x[x[x]]
j(5)  = j(3)[j(1)]      = x[x][x][x]
j(6)  = j(4)[j(1)]      = x[x[x]][x]
j(7)  = j(5)[j(1)]      = x[x][x][x][x]
j(8)  = j(1)[j(1),j(1)] = x[x,x]
j(9)  = j(2)[j(2)]      = x[x][x[x]]
j(10) = j(6)[j(1)]      = x[x[x]][x][x]
j(11) = j(7)[j(1)]      = x[x][x][x][x][x]
j(12) = j(8)[j(1)]      = x[x,x][x]
j(13) = j(9)[j(1)]      = x[x][x[x]][x]
j(14) = j(10)[j(1)]     = x[x[x]][x][x][x]
j(15) = j(11)[j(1)]     = x[x][x][x][x][x][x]
j(16) = j(1)[j(3)]      = x[x[x][x]]
j(17) = j(12)[j(1)]     = x[x,x][x][x]
j(18) = j(13)[j(1)]     = x[x][x[x]][x][x]
j(19) = j(14)[j(1)]     = x[x[x]][x][x][x][x]
j(20) = j(15)[j(1)]     = x[x][x][x][x][x][x][x].

Cf. A005043, A007916, A106490, A277564, A277615, A277996, A278028, A280000.

Cf. A279984 (numbers j(n)[x]=j(prime(n))), A277576 (numbers j(n)=x[x][x][x]...), A058891 (numbers j(n)=x[x,...,x]), A279969 (numbers j(n)=x[x[...[x]]]).

nn=100;
radQ[n_]:=If[n===1,False,SameQ[GCD@@FactorInteger[n][[All,2]],1]];
rad[n_]:=rad[n]=If[n===0,1,NestWhile[#+1&,rad[n-1]+1,Not[radQ[#]]&]];
Set@@@Array[radPi[rad[#]]==#&,nn];
jfac[n_]:=With[{g=GCD@@FactorInteger[n+1][[All,2]]},JIX[radPi[Power[n+1,1/g]],Flatten[Cases[FactorInteger[g+1],{p_,k_}:>ConstantArray[PrimePi[p],k]]]]];
diwt[n_]:=If[n===1,1,Apply[1+diwt[#1]+Total[diwt/@#2]&,jfac[n-1]]];
Array[diwt,nn]

a(A007916(h)^(A000040(g_1)*...*A000040(g_k)-1)) = 1 + a(h) + a(g_1) + ... + a(g_k).

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

Original entry on oeis.org

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

Gus Wiseman, Oct 20 2016

nonn

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.

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

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

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

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,#

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

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

A278029 a(1) = 0; for n > 1, a(n) = k if n is a non-perfect-power, A007916(k); or 0 if n is a perfect power.

Original entry on oeis.org

0, 1, 2, 0, 3, 4, 5, 0, 0, 6, 7, 8, 9, 10, 11, 0, 12, 13, 14, 15, 16, 17, 18, 19, 0, 20, 0, 21, 22, 23, 24, 0, 25, 26, 27, 0, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 0, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 0, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 0

Offset: 1

N. J. A. Sloane, Nov 10 2016

Rémy Sigrist, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Maple programs for A007916, A278028, A278029, A052409, A089723, A277564

Cf. A007916, A072813, A289023.

FoldList[Boole[#2 != #1] #2 &, #] &@ Accumulate@ Array[Boole[And[# > 1, CoprimeQ @@ FactorInteger[#][[All, -1]]]] &, 81] (* Michael De Vlieger, Dec 18 2016 *)

Name corrected by Peter Munn, Feb 28 2024

A304481 Turn the power-tower for n upside-down.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 32, 26, 27, 28, 29, 30, 31, 25, 33, 34, 35, 64, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 128, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 36, 65, 66, 67

Offset: 1

Gus Wiseman, May 13 2018

This is an involution of the positive integers.

The power-tower for n is defined as follows. Let {c(i)} = A007916 denote the sequence of numbers > 1 which are not perfect powers. Every positive integer n has a unique representation as a tower n = c(x_1)^c(x_2)^c(x_3)^...^c(x_k), where the exponents are nested from the right. Then a(n) = c(x_k)^...^c(x_3)^c(x_2)^c(x_1).

			The power tower of 81 is 3^2^2, which turned upside-down is 2^2^3 = 256, so a(81) = 256.

Robert Israel, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Maple programs for A007916, A278028, A278029, A052409, A089723, A277564

Cf. A052409, A052410, A007916, A089723, A164337, A277562, A277564, A278028, A288636, A289023, A294336, A294337, A304491, A304492, A304495.

f:= proc(n,r) local F,a,y;
     if n = 1 then return 1 fi;
     F:= ifactors(n)[2];
     y:= igcd(seq(t[2],t=F));
     if y = 1 then return n^r fi;
     a:= mul(t[1]^(t[2]/y),t=F);
     procname(y,a^r)
end proc:
seq(f(n,1),n=1..100); # Robert Israel, May 13 2018

tow[n_]:=If[n==1,{},With[{g=GCD@@FactorInteger[n][[All,2]]},If[g===1,{n},Prepend[tow[g],n^(1/g)]]]];
Table[Power@@Reverse[tow[n]],{n,100}]

cp's OEIS Frontend

A277615 a(1)=1; thereafter, if n = c(x_1)^...^c(x_k) (where c(k) = A007916(k) and with parentheses nested from the right, as in the definition of A277564), a(n) = 1 + a(x_1) + ... + a(x_k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A007916 Numbers that are not perfect powers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A052409 a(n) = largest integer power m for which a representation of the form n = k^m exists (for some k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Scheme

Formula

Extensions

A089723 a(1)=1; for n>1, a(n) gives number of ways to write n as n = x^y, 2 <= x, 1 <= y.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A288636 Height of power-tower factorization of n. Row lengths of A278028.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A279944 Number of positions in the free pure symmetric multifunction in one symbol with j-number n.

Views

Author