cp's OEIS Frontend

A007916 Numbers that are not perfect powers.

%I A007916 #84 Nov 23 2024 12:38:29
%S A007916 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 A007916 33,34,35,37,38,39,40,41,42,43,44,45,46,47,48,50,51,52,53,54,55,56,57,
%U A007916 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 A007916 Numbers that are not perfect powers.
%C A007916 From _Gus Wiseman_, Oct 23 2016: (Start)
%C A007916 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 A007916 N = a(x_1)^a(x_2)^a(x_3)^...^a(x_k),
%C A007916 where the exponents are to be nested from the right.
%C A007916 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 A007916 Of course, prime numbers also have distinct power towers (see A164336). (End)
%C A007916 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 A007916 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 A007916 N. J. A. Sloane, <a href="/A007916/b007916.txt">Table of n, a(n) for n = 1..9875</a>
%H A007916 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 A007916 N. J. A. Sloane, <a href="/A278028/a278028.txt">Maple programs for A007916, A278028, A278029, A052409, A089723, A277564</a>
%H A007916 F. Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/OPNS.pdf">Only Problems, Not Solutions!</a>, Xiquan Publ., Phoenix-Chicago, 1993
%H A007916 <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>
%F A007916 A075802(a(n)) = 0. - _Reinhard Zumkeller_, Mar 19 2009
%F A007916 Gcd(exponents in prime factorization of a(n)) = 1, cf. A124010. - _Reinhard Zumkeller_, Apr 13 2012
%F A007916 a(n) ~ n. - _Charles R Greathouse IV_, Jul 01 2013
%F A007916 A052409(a(n)) = 1. - _Ridouane Oudra_, Nov 23 2024
%e A007916 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 A007916 See link.
%t A007916 a = {}; Do[If[Apply[GCD, Transpose[FactorInteger[n]][[2]]] == 1, a = Append[a, n]], {n, 2, 200}];
%t A007916 Select[Range[2,200],GCD@@FactorInteger[#][[All,-1]]===1&] (* _Michael De Vlieger_, Oct 21 2016. Corrected by _Gus Wiseman_, Jan 14 2017 *)
%o A007916 (Magma) [n : n in [2..1000] | not IsPower(n) ];
%o A007916 (Haskell)
%o A007916 a007916 n = a007916_list !! (n-1)
%o A007916 a007916_list = filter ((== 1) . foldl1 gcd . a124010_row) [2..]
%o A007916 -- _Reinhard Zumkeller_, Apr 13 2012
%o A007916 (PARI) is(n)=!ispower(n)&&n>1 \\ _Charles R Greathouse IV_, Jul 01 2013
%o A007916 (Python)
%o A007916 from sympy import mobius, integer_nthroot
%o A007916 def A007916(n):
%o A007916     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 A007916     m, k = n, f(n)
%o A007916     while m != k:
%o A007916         m, k = k, f(k)
%o A007916     return m # _Chai Wah Wu_, Aug 13 2024
%Y A007916 Complement of A001597. Union of A052485 and A052486.
%Y A007916 Cf. A144338, A277562, A277564, A075802.
%Y A007916 Cf. A153158 (squares of these numbers).
%Y A007916 See A277562, A277564, A277576, A277615 for more about the power towers.
%Y A007916 A278029 is a left inverse.
%Y A007916 Cf. A052409.
%K A007916 nonn,easy
%O A007916 1,1
%A A007916 R. Muller
%E A007916 More terms from _Henry Bottomley_, Sep 12 2000
%E A007916 Edited by _Charles R Greathouse IV_, Mar 18 2010
%E A007916 Further edited by _N. J. A. Sloane_, Nov 09 2016