A007916 -id:A007916 - cp's OEIS frontend

A303709 Number of periodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

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

Offset: 1

Gus Wiseman, Apr 29 2018

nonn

A periodic factorization of n is a finite multiset of positive integers greater than 1 whose product is n and whose multiplicities have a common divisor greater than 1. Note that a factorization of a number that is not a perfect power (A007916) is always aperiodic (A303386), so the indices of nonzero entries of this sequence all lie at perfect powers (A001597).

			The a(900) = 5 periodic factorizations are (2*2*3*3*5*5), (2*2*15*15), (3*3*10*10), (5*5*6*6), (30*30).

Antti Karttunen, Table of n, a(n) for n = 1..100000

Cf. A000740, A000837, A001055, A001597, A007716, A007916, A052409, A052410, A281116, A303547, A303552, A303553, A303386, A303707, A303708, A303710.

radQ[n_]:=Or[n===1,GCD@@FactorInteger[n][[All,2]]===1];
facsr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facsr[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],radQ]}]];
Table[Length[Select[facsr[n],GCD@@Length/@Split[#]!=1&]],{n,200}]

gcd_of_multiplicities(lista) = { my(u=length(lista)); if(u<2, u, my(g=0, pe = lista[1], j=1); for(i=2,u,if(lista[i]==pe, j++, g = gcd(j,g); j=1; pe = lista[i])); gcd(g,j)); }; \\ the supplied lista (newfacs) should be monotonic
A303709(n, m=n, facs=List([])) = if(1==n, (1!=gcd_of_multiplicities(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m)&&!ispower(d), newfacs = List(facs); listput(newfacs,d); s += A303709(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Dec 06 2018

a(n) <= A303553(n) <= A001055(n). - Antti Karttunen, Dec 06 2018

Changed a(1) to 1 by Gus Wiseman, Dec 06 2018

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

A303945 Triangle whose n-th row lists the multiset of prime indices of the n-th number that is not a perfect power A007916(n).

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, May 03 2018

A number is not a perfect power if its prime multiplicities are relatively prime. This triangle is an enumeration of all finite aperiodic multisets of positive integers, where a multiset is aperiodic if its multiplicities are relatively prime.

			Sequence of numbers that are not perfect powers together with their multisets of prime indices begins:
2:  {1}
3:  {2}
5:  {3}
6:  {1,2}
7:  {4}
10: {1,3}
11: {5}
12: {1,1,2}
13: {6}
14: {1,4}
15: {2,3}
17: {7}
18: {1,2,2}
19: {8}
20: {1,1,3}
21: {2,4}
22: {1,5}
23: {9}
24: {1,1,1,2}
26: {1,6}
28: {1,1,4}
29: {10}
30: {1,2,3}

Cf. A000041, A000720, A000837, A001222, A005117, A007916, A052409, A052410, A056239, A112798, A296150.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
primeMS/@Select[Range[2,100],GCD@@FactorInteger[#][[All,2]]===1&]

A376588 Inflection and undulation points in the sequence of non-perfect-powers (A007916).

Original entry on oeis.org

3, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 19, 21, 22, 25, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84

Offset: 1

Gus Wiseman, Oct 03 2024

nonn

These are points at which the second differences (A376562) are zero.

Non-perfect-powers (A007916) are numbers without a proper integer root.

			The non-perfect powers (A007916) are:
  2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, ...
with first differences (A375706):
  1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, ...
with first differences (A376562):
  1, -1, 0, 2, -2, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 1, -1, 0, ...
with zeros at (A376588):
  3, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 19, 21, 22, 25, 28, 29, 30, 31, 32, 33, ...

Gus Wiseman, Inflection and undulation points in the non-perfect-powers.

The version for A000002 is empty.
For first differences we had A375706, ones A375740, complement A375714.
Positions of zeros in A376562, complement A376589.
Runs of non-perfect-powers:
- length: A375702 = A053289(n+1) - 1
- first: A375703 (same as A216765 with 2 exceptions)
- last: A375704 (same as A045542 with 8 removed)
- sum: A375705
A000961 lists prime-powers inclusive, exclusive A246655.
A007916 lists non-perfect-powers, complement A001597.
A305631 counts integer partitions into non-perfect-powers, factorizations A322452.
A333254 gives run-lengths of differences between consecutive primes.
For non-perfect-powers: A375706 (first differences), A376562 (second differences), A376589 (nonzero curvature).
For second differences: A064113 (prime), A376602 (composite), {} (perfect-power), A376591 (squarefree), A376594 (nonsquarefree), A376597 (prime-power inclusive), A376600 (non-prime-power inclusive).
Cf. A025475, A052410, A053707, A069623, A073445, A093555, A174965, A294068, A336416, A361102, A376599, A376590.

radQ[n_]:=n>1&&GCD@@Last/@FactorInteger[n]==1;
Join@@Position[Differences[Select[Range[100],radQ],2],0]

A376589 Points of nonzero curvature in the sequence of non-perfect-powers (A007916).

Original entry on oeis.org

1, 2, 4, 5, 10, 11, 18, 20, 23, 24, 26, 27, 38, 39, 52, 53, 68, 69, 86, 87, 106, 107, 109, 110, 111, 112, 126, 127, 150, 151, 176, 177, 195, 196, 203, 204, 220, 221, 232, 233, 264, 265, 298, 299, 316, 317, 333, 334, 371, 372, 411, 412, 453, 454, 480, 481, 496

Offset: 1

Gus Wiseman, Oct 03 2024

nonn

These are points at which the second differences (A376562) are nonzero.

Non-perfect-powers (A007916) are numbers without a proper integer root.

			The non-perfect powers (A007916) are:
  2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, ...
with first differences (A375706):
  1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, ...
with first differences (A376562):
  1, -1, 0, 2, -2, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 1, -1, 0, ...
with nonzeros at (A376589):
  1, 2, 4, 5, 10, 11, 18, 20, 23, 24, 26, 27, 38, 39, 52, 53, 68, 69, 86, 87, ...

Gus Wiseman, Points of nonzero curvature in the non-perfect-powers.

For first differences we had A375706, ones A375740, complement A375714.
These are the positions of nonzeros in A376562, complement A376588.
Runs of non-perfect-powers:
- length: A375702 = A053289(n+1) - 1
- first: A375703 (same as A216765 with 2 exceptions)
- last: A375704 (same as A045542 with 8 removed)
- sum: A375705
A000961 lists prime-powers inclusive, exclusive A246655.
A007916 lists non-perfect-powers, complement A001597.
A305631 counts integer partitions into non-perfect-powers, factorizations A322452.
For non-perfect-powers: A375706 (first differences), A376562 (second differences), A376588 (inflection and undulation points).
For second differences: A064113 (prime), A376602 (composite), A376591 (squarefree), A376594 (nonsquarefree), A376597 (prime-power), A376600 (non-prime-power).
Cf. A025475, A052410, A053707, A069623, A073445, A093555, A174965, A182853, A294068, A333254, A336416, A376599.

radQ[n_]:=n>1&&GCD@@Last/@FactorInteger[n]==1;
Join@@Position[Sign[Differences[Select[Range[1000],radQ],2]],1|-1]

A153147 a(n) = A007916(n)^3.

Original entry on oeis.org

8, 27, 125, 216, 343, 1000, 1331, 1728, 2197, 2744, 3375, 4913, 5832, 6859, 8000, 9261, 10648, 12167, 13824, 17576, 21952, 24389, 27000, 29791, 35937, 39304, 42875, 50653, 54872, 59319, 64000, 68921, 74088, 79507, 85184, 91125, 97336, 103823

Offset: 1

Vladimir Joseph Stephan Orlovsky, Dec 19 2008

nonn

2^3=8, 3^3=27, 4^3=64=2^6 is not in the sequence, 5^3=125, 6^3=216, ...

Cf. A000578, A007916, A153157, A153158, A153159, A153160, A062838.

Select[Range[2,100],GCD@@Last/@FactorInteger@#==1&]^3

from sympy import mobius, integer_nthroot
def A153147(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**3

Edited by Ray Chandler, Dec 22 2008

A153157 a(n) = A007916(n)^4.

Original entry on oeis.org

16, 81, 625, 1296, 2401, 10000, 14641, 20736, 28561, 38416, 50625, 83521, 104976, 130321, 160000, 194481, 234256, 279841, 331776, 456976, 614656, 707281, 810000, 923521, 1185921, 1336336, 1500625, 1874161, 2085136, 2313441, 2560000, 2825761

Offset: 1

Vladimir Joseph Stephan Orlovsky, Dec 19 2008

nonn

2^4=16,3^4=81,4^4=256=2^8 is not in the sequence,5^4=625,6^4=1296,...

Cf. A007916, A153147, A153158, A153159, A153160, A113849.

Select[Range[2,100],GCD@@Last/@FactorInteger@#==1&]^4

from sympy import mobius, integer_nthroot
def A153157(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**4 # Chai Wah Wu, Nov 21 2024

Edited by Ray Chandler, Dec 22 2008

A153159 a(n) = A007916(n)^5.

Original entry on oeis.org

32, 243, 3125, 7776, 16807, 100000, 161051, 248832, 371293, 537824, 759375, 1419857, 1889568, 2476099, 3200000, 4084101, 5153632, 6436343, 7962624, 11881376, 17210368, 20511149, 24300000, 28629151, 39135393, 45435424

Offset: 1

Vladimir Joseph Stephan Orlovsky, Dec 19 2008

nonn

Cf. A007916, A153147, A153157, A153158, A153160, A113850.

Select[Range[2,100],GCD@@Last/@FactorInteger@#==1&]^5

from sympy import mobius, integer_nthroot
def A153159(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**5 # Chai Wah Wu, Nov 21 2024

Edited and extended by Ray Chandler, Dec 22 2008

A153160 a(n) = A007916(n)^6.

Original entry on oeis.org

64, 729, 15625, 46656, 117649, 1000000, 1771561, 2985984, 4826809, 7529536, 11390625, 24137569, 34012224, 47045881, 64000000, 85766121, 113379904, 148035889, 191102976, 308915776, 481890304, 594823321, 729000000, 887503681

Offset: 1

Vladimir Joseph Stephan Orlovsky, Dec 19 2008

nonn

Cf. A007916, A153147, A153157, A153158, A153159, A113851.

Select[Range[2,100],GCD@@Last/@FactorInteger@#==1&]^6

from sympy import mobius, integer_nthroot
def A153160(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**6 # Chai Wah Wu, Nov 21 2024

Edited and extended by Ray Chandler, Dec 22 2008

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

Original entry on oeis.org

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

cp's OEIS Frontend

A303709 Number of periodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A303945 Triangle whose n-th row lists the multiset of prime indices of the n-th number that is not a perfect power A007916(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A376588 Inflection and undulation points in the sequence of non-perfect-powers (A007916).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A376589 Points of nonzero curvature in the sequence of non-perfect-powers (A007916).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A153147 a(n) = A007916(n)^3.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

Extensions

A153157 a(n) = A007916(n)^4.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

Extensions

A153159 a(n) = A007916(n)^5.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Python