A007916 Numbers that are not perfect powers.

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

Author

R. Muller

Keywords

• nonn
• easy

Comments

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

Examples

			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
		

Links

• 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

Crossrefs

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.

Programs

Haskell

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

Magma

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

Maple

See link.

Mathematica

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 *)

PARI

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

Python

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

Formula

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

Extensions

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