login
Numbers that are not perfect powers.
240

%I #78 Aug 13 2024 11:20:52

%S 2,3,5,6,7,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,28,29,30,31,

%T 33,34,35,37,38,39,40,41,42,43,44,45,46,47,48,50,51,52,53,54,55,56,57,

%U 58,59,60,61,62,63,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,82,83

%N Numbers that are not perfect powers.

%C From _Gus Wiseman_, Oct 23 2016: (Start)

%C 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"

%C N = a(x_1)^a(x_2)^a(x_3)^...^a(x_k),

%C where the exponents are to be nested from the right.

%C 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

%C Of course, prime numbers also have distinct power towers (see A164336). (End)

%C 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

%C A075802(a(n)) = 0. - _Reinhard Zumkeller_, Mar 19 2009

%C 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

%H N. J. A. Sloane, <a href="/A007916/b007916.txt">Table of n, a(n) for n = 1..9875</a>

%H Joakim Munkhammar, <a href="https://doi.org/10.1017/mag.2020.110">The Riemann zeta function as a sum of geometric series</a>, The Mathematical Gazette (2020) Vol. 104, Issue 561, 527-530.

%H N. J. A. Sloane, <a href="/A278028/a278028.txt">Maple programs for A007916, A278028, A278029, A052409, A089723, A277564</a>

%H F. Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/OPNS.pdf">Only Problems, Not Solutions!</a>, Xiquan Publ., Phoenix-Chicago, 1993

%H <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>

%F Gcd(exponents in prime factorization of a(n)) = 1, cf. A124010. - _Reinhard Zumkeller_, Apr 13 2012

%F a(n) ~ n. - _Charles R Greathouse IV_, Jul 01 2013

%e 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

%p See link.

%t a = {}; Do[If[Apply[GCD, Transpose[FactorInteger[n]][[2]]] == 1, a = Append[a, n]], {n, 2, 200}];

%t Select[Range[2,200],GCD@@FactorInteger[#][[All,-1]]===1&] (* _Michael De Vlieger_, Oct 21 2016. Corrected by _Gus Wiseman_, Jan 14 2017 *)

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

%o (Haskell)

%o a007916 n = a007916_list !! (n-1)

%o a007916_list = filter ((== 1) . foldl1 gcd . a124010_row) [2..]

%o -- _Reinhard Zumkeller_, Apr 13 2012

%o (PARI) is(n)=!ispower(n)&&n>1 \\ _Charles R Greathouse IV_, Jul 01 2013

%o (Python)

%o from sympy import mobius, integer_nthroot

%o def A007916(n):

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

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

%o while m != k:

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

%o return m # _Chai Wah Wu_, Aug 13 2024

%Y Complement of A001597. Union of A052485 and A052486.

%Y Cf. A144338, A277562, A277564, A075802.

%Y Cf. A153158 (squares of these numbers).

%Y See A277562, A277564, A277576, A277615 for more about the power towers.

%Y A278029 is a left inverse.

%K nonn,easy

%O 1,1

%A R. Muller

%E More terms from _Henry Bottomley_, Sep 12 2000

%E Edited by _Charles R Greathouse IV_, Mar 18 2010

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