A052409 -id:A052409 - cp's OEIS frontend

A317765 Number of distinct subexpressions of the free pure symmetric multifunction (with empty expressions allowed) with e-number n.

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

Offset: 1

Gus Wiseman, Aug 18 2018

nonn

If n = 1 let e(n) be the leaf symbol "o". Given a positive integer n > 1 we construct a unique free pure symmetric multifunction (with empty expressions allowed) e(n) with one atom by expressing n as a power of a number that is not a perfect power to a product of prime numbers: n = rad(x)^(prime(y_1) * ... * prime(y_k)) where rad = A007916. Then e(n) = e(x)[e(y_1), ..., e(y_k)]. For example, e(21025) = o[o[o]][o] because 21025 = rad(rad(1)^prime(rad(1)^prime(1)))^prime(1).

			The a(12) = 4 subexpressions of o[o[]][] are {o, o[], o[o[]], o[o[]][]}.

Cf. A007916, A052409, A052410, A277576, A277996, A300626, A316112, A317056, A317658, A317713, A317994.

nn=1000;
radQ[n_]:=If[n===1,False,GCD@@FactorInteger[n][[All,2]]===1];
rad[n_]:=rad[n]=If[n===0,1,NestWhile[#+1&,rad[n-1]+1,Not[radQ[#]]&]];
Clear[radPi];Set@@@Array[radPi[rad[#]]==#&,nn];
exp[n_]:=If[n===1,"o",With[{g=GCD@@FactorInteger[n][[All,2]]},Apply[exp[radPi[Power[n,1/g]]],exp/@Flatten[Cases[FactorInteger[g],{p_?PrimeQ,k_}:>ConstantArray[PrimePi[p],k]]]]]];
Table[Length[Union[Cases[exp[n],_,{0,Infinity},Heads->True]]],{n,100}]

A322900 Number of integer partitions of n whose parts are all proper powers of the same number.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 5, 2, 5, 3, 7, 2, 11, 2, 9, 5, 11, 2, 16, 2, 18, 6, 17, 2, 27, 3, 23, 6, 30, 2, 38, 2, 37, 8, 39, 5, 58, 2, 49, 10, 66, 2, 74, 2, 78, 14, 77, 2, 109, 3, 100, 12, 118, 2, 131, 6, 146, 15, 143, 2, 190, 2, 169, 20, 203, 6, 224, 2, 242, 18, 248

Offset: 0

Gus Wiseman, Dec 30 2018

nonn

Such a partition contains either no 1's or only 1's.
A proper power of n is a number n^k for some positive integer k.
Also integer partitions whose parts all have the same radical base (A052410).

			The a(1) = 1 through a(14) = 9 integer partitions (A = 10, B = 11, C = 12, D = 13, E = 14):
  (1) (2)  (3)   (4)    (5)     (6)      (7)       (8)        (9)
      (11) (111) (22)   (11111) (33)     (1111111) (44)       (333)
                 (1111)         (42)               (422)      (111111111)
                                (222)              (2222)
                                (111111)           (11111111)
.
  (A)          (B)           (C)            (D)             (E)
  (55)         (11111111111) (66)           (1111111111111) (77)
  (82)                       (84)                           (842)
  (442)                      (93)                           (4442)
  (4222)                     (444)                          (8222)
  (22222)                    (822)                          (44222)
  (1111111111)               (3333)                         (422222)
                             (4422)                         (2222222)
                             (42222)                        (11111111111111)
                             (222222)
                             (111111111111)

a(n) = A072721(n) + 1.

Cf. A000961, A001597, A018819, A023893, A023894, A052409, A052410, A072720, A102430, A302593, A322901, A322902, A322903.

radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
Table[Length[Select[IntegerPartitions[n],SameQ@@radbase/@#&]],{n,30}]

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

A295923 Number of twice-factorizations of n where the first factorization is constant, i.e., type (P,R,P).

Original entry on oeis.org

1, 1, 1, 3, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 2, 10, 1, 4, 1, 4, 2, 2, 1, 7, 3, 2, 4, 4, 1, 5, 1, 8, 2, 2, 2, 13, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 3, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11, 1, 2, 4, 29, 2, 5, 1, 4, 2, 5, 1, 16, 1, 2, 4, 4, 2, 5, 1, 12, 10, 2, 1, 11

Offset: 1

Gus Wiseman, Nov 30 2017

nonn

a(n) is also the number of ways to choose a perfect divisor d|n and then a sequence of log_d(n) factorizations of d.

			The a(16) = 10 twice-factorizations are (2*2*2*2), (2*2*4), (2*8), (4*4), (16), (2*2)*(2*2), (2*2)*(4), (4)*(2*2), (4)*(4), (2)*(2)*(2)*(2).

Cf. A000005, A001055, A052409, A052410, A279787, A281113, A284639, A295920, A295924, A295931, A295935.

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
a[n_]:=Sum[Length[postfacs[n^(1/g)]]^g,{g,Divisors[GCD@@FactorInteger[n][[All,2]]]}];
Array[a,50]

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&]

A319269 Number of uniform factorizations of n into factors > 1, where a factorization is uniform if all factors appear with the same multiplicity.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 5, 2, 2, 3, 3, 1, 5, 1, 4, 2, 2, 2, 7, 1, 2, 2, 5, 1, 5, 1, 3, 3, 2, 1, 7, 2, 3, 2, 3, 1, 5, 2, 5, 2, 2, 1, 9, 1, 2, 3, 8, 2, 5, 1, 3, 2, 5, 1, 9, 1, 2, 3, 3, 2, 5, 1, 7, 4, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Sep 16 2018

nonn

			The a(144) = 17 factorizations:
  (144),
  (2*72), (3*48), (4*36), (6*24), (8*18), (9*16), (12*12),
  (2*3*24), (2*4*18), (2*6*12), (2*8*9), (3*4*12), (3*6*8),
  (2*2*6*6), (2*3*4*6), (3*3*4*4).

Cf. A001055, A045778, A047966, A052409, A072774, A296132, A303386, A317710, A317712, A317717, A317718.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],SameQ@@Length/@Split[#]&]],{n,100}]

a(n) = Sum_{d|A052409(n)} A045778(n^(1/d)).

A072776 Exponents of powers of squarefree numbers.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 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, 3, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Reinhard Zumkeller, Jul 10 2002

nonn

A072774(n) = A072775(n)^a(n);

A072774(n) is squarefree iff a(n)=1.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A052409.

a072776 n = a072776_list !! (n-1)  -- a072776_list defined in A072774.
-- Reinhard Zumkeller, Apr 06 2014

from math import isqrt
from sympy import mobius, integer_nthroot, perfect_power
def A072776(n):
    def g(x): return int(sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1)))-1
    def f(x): return n-2+x-sum(g(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length()))
    kmin, kmax = 1,2
    while f(kmax) >= kmax:
        kmax <<= 1
    while True:
        kmid = kmax+kmin>>1
        if f(kmid) < kmid:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return 1 if not (p:=perfect_power(kmax)) else p[1] # Chai Wah Wu, Aug 19 2024

A175432 a(n) = the greatest number k such that sigma(n) = m^k for any m >= 1 (sigma = A000203).

Original entry on oeis.org

1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 2, 1, 1, 1, 1, 1, 1

Offset: 1

Jaroslav Krizek, May 10 2010

nonn

a(A175431(n)) = 1 for n >= 1.
a(A065496(n)) > 1 for n >= 1.
It appears that the record values in this sequence, 1, 2, 3, 5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, ..., is A180221 with a 1 prepended, at least through term #469. Is this a theorem? - Ray Chandler, Aug 20 2010

			For n = 7, a(7) = 3 because sigma(7) = 8 = 2^3.

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

For locations of records see A169981.

Cf. A000203, A052409, A175433.

Array[Apply[GCD, FactorInteger[DivisorSigma[1, #]][[All, -1]]] &, 105] (* Michael De Vlieger, Nov 05 2017 *)

a(n)=max(ispower(sigma(n)),1) \\ Charles R Greathouse IV, Feb 14 2013

a(n) = A052409(A000203(n)). - N. J. A. Sloane, Aug 19 2010

a(n) = log_A175433(n) [A000203(n)].

A294338 Number of ways to write n as a finite power-tower of positive integers greater than one, allowing both left and right nesting of parentheses.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 5, 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, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, Oct 28 2017

nonn

			The a(16) = 5 ways are: 16, 4^2, (2^2)^2, 2^4, 2^(2^2).

R. J. Mathar, Table of n, a(n) for n = 1..10000

Cf. A001597, A007916, A052409, A052410, A089723, A164336, A277562, A284639, A288636, A294336, A294337, A294339.

A294338 := proc(n)
    local expo,g,a,d ;
    if n =1 then
        return 1;
    end if;
    # compute gcd of the set of prime power exponents (A052409)
    ifactors(n)[2] ;
    [ seq(op(2,ep),ep=%)] ;
    igcd(op(%)) ;
    # set of divisors of A052409 (without the 1)
    g := numtheory[divisors](%) minus {1} ;
    a := 0 ;
    for d in g do
        # recursive (sort of convolution) call
        a := a+ procname(d)*procname(root[d](n)) ;
    end do:
    1+a ;
end proc:
seq(A294338(n),n=1..120) ; # R. J. Mathar, Nov 27 2017

a[n_]:=1+Sum[a[n^(1/g)]*a[g],{g,Rest[Divisors[GCD@@FactorInteger[n][[All,2]]]]}];
Array[a,100]

A296132 Number of twice-factorizations of n where the first factorization is constant and the latter factorizations are strict, i.e., type (P,R,Q).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 5, 2, 2, 3, 3, 1, 5, 1, 4, 2, 2, 2, 9, 1, 2, 2, 5, 1, 5, 1, 3, 3, 2, 1, 7, 2, 3, 2, 3, 1, 5, 2, 5, 2, 2, 1, 9, 1, 2, 3, 10, 2, 5, 1, 3, 2, 5, 1, 9, 1, 2, 3, 3, 2, 5, 1, 7, 4, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Dec 05 2017

nonn

a(n) is also the number of ways to choose a perfect divisor d|n and then a sequence of log_d(n) strict factorizations of d.

			The a(36) = 9 twice-factorizations are (2*3)*(2*3), (2*3)*(6), (6)*(2*3), (6)*(6), (2*3*6), (2*18), (3*12), (4*9), (36).

Cf. A000005, A001055, A005117, A045778, A052409, A052410, A089723, A279788, A281113, A284639, A295920, A295931.

sfs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sfs[n/d],Min@@#>d&]],{d,Rest[Divisors[n]]}]];
Table[Sum[Length[sfs[n^(1/g)]]^g,{g,Divisors[GCD@@FactorInteger[n][[All,2]]]}],{n,100}]

cp's OEIS Frontend

A317765 Number of distinct subexpressions of the free pure symmetric multifunction (with empty expressions allowed) with e-number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A322900 Number of integer partitions of n whose parts are all proper powers of the same number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A295923 Number of twice-factorizations of n where the first factorization is constant, i.e., type (P,R,P).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A319269 Number of uniform factorizations of n into factors > 1, where a factorization is uniform if all factors appear with the same multiplicity.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A072776 Exponents of powers of squarefree numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Python

A175432 a(n) = the greatest number k such that sigma(n) = m^k for any m >= 1 (sigma = A000203).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A294338 Number of ways to write n as a finite power-tower of positive integers greater than one, allowing both left and right nesting of parentheses.

Views

Author