A051613 -id:A051613 - cp's OEIS frontend

A008475 If n = Product (p_j^k_j) then a(n) = Sum (p_j^k_j) (a(1) = 0 by convention).

0, 2, 3, 4, 5, 5, 7, 8, 9, 7, 11, 7, 13, 9, 8, 16, 17, 11, 19, 9, 10, 13, 23, 11, 25, 15, 27, 11, 29, 10, 31, 32, 14, 19, 12, 13, 37, 21, 16, 13, 41, 12, 43, 15, 14, 25, 47, 19, 49, 27, 20, 17, 53, 29, 16, 15, 22, 31, 59, 12, 61, 33, 16, 64, 18, 16, 67, 21, 26, 14, 71, 17, 73

Offset: 1

Olivier Gérard

For n>1, a(n) is the minimal number m such that the symmetric group S_m has an element of order n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 26 2001

If gcd(u,w) = 1, then a(u*w) = a(u) + a(w); behaves like logarithm; compare A001414 or A056239. - Labos Elemer, Mar 31 2003

			a(180) = a(2^2 * 3^2 * 5) = 2^2 + 3^2 + 5 = 18.

F. J. Budden, The Fascination of Groups, Cambridge, 1972; pp. 322, 573.
József Sándor, Dragoslav S. Mitrinovic and Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Chapter IV, p. 147.
T. Z. Xuan, On some sums of large additive number theoretic functions (in Chinese), Journal of Beijing normal university, No. 2 (1984), pp. 11-18.

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from T. D. Noe)
John Bamberg, Grant Cairns and Devin Kilminster, The crystallographic restriction, permutations and Goldbach's conjecture, Amer. Math. Monthly, Vol. 110, No. 3 (March 2003), pp. 202-209.
Roger B. Eggleton and William P. Galvin, Upper Bounds on the Sum of Principal Divisors of an Integer, Mathematics Magazine, Vol. 77, No. 3 (Jun., 2004), pp. 190-200.

Cf. A001414, A000961, A005117, A051613, A072691, A081402, A081403, A081404, A027748, A124010, A001221, A028233, A034684, A053585, A159077, A023888, A078771, A092509, A286875.

See A222416 for the variant with a(1)=1.

a008475 1 = 0
a008475 n = sum $ a141809_row n
-- Reinhard Zumkeller, Jan 29 2013, Oct 10 2011

A008475 := proc(n) local e,j; e := ifactors(n)[2]:
add(e[j][1]^e[j][2], j=1..nops(e)) end:
seq(A008475(n), n=1..60); # Peter Luschny, Jan 17 2010

f[n_] := Plus @@ Power @@@ FactorInteger@ n; f[1] = 0; Array[f, 73]

for(n=1,100,print1(sum(i=1,omega(n), component(component(factor(n),1),i)^component(component(factor(n),2),i)),","))

a(n)=local(t);if(n<1,0,t=factor(n);sum(k=1,matsize(t)[1],t[k,1]^t[k,2])) /* Michael Somos, Oct 20 2004 */

A008475(n) = { my(f=factor(n)); vecsum(vector(#f~,i,f[i,1]^f[i,2])); }; \\ Antti Karttunen, Nov 17 2017

from sympy import factorint
def a(n):
    f=factorint(n)
    return 0 if n==1 else sum([i**f[i] for i in f]) # Indranil Ghosh, May 20 2017

Additive with a(p^e) = p^e.
a(A000961(n)) = A000961(n); a(A005117(n)) = A001414(A005117(n)).
a(n) = Sum_{k=1..A001221(n)} A027748(n,k) ^ A124010(n,k) for n>1. - Reinhard Zumkeller, Oct 10 2011
a(n) = Sum_{k=1..A001221(n)} A141809(n,k) for n > 1. - Reinhard Zumkeller, Jan 29 2013
Sum_{k=1..n} a(k) ~ (Pi^2/12)* n^2/log(n) + O(n^2/log(n)^2) (Xuan, 1984). - Amiram Eldar, Mar 04 2021

A106244 Number of partitions into distinct prime powers.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 17, 19, 21, 24, 27, 30, 33, 37, 41, 46, 50, 56, 62, 68, 75, 82, 91, 99, 108, 118, 129, 141, 152, 166, 180, 196, 211, 229, 248, 267, 288, 310, 335, 360, 387, 415, 447, 479, 513, 549, 589, 630, 672, 719, 768, 820, 873, 930

Offset: 0

Reinhard Zumkeller, Apr 26 2005

nonn

A054685(n) < a(n) < A023893(n) for n>2.

			a(10) = #{3^2+1,2^3+2,7+3,7+2+1,5+2^2+1,5+3+2,2^2+3+2+1} = 7.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)

Cf. A000586, A000607, A000961.
Cf. A062051, A105420, A131996.
Cf. A023893, A051613, A054685.

import Data.MemoCombinators (memo2, integral)
a106244 n = a106244_list !! n
a106244_list = map (p' 1) [0..] where
   p' = memo2 integral integral p
   p _ 0 = 1
   p k m = if m < pp then 0 else p' (k + 1) (m - pp) + p' (k + 1) m
           where pp = a000961 k
-- Reinhard Zumkeller, Nov 24 2015

g:=(1+x)*(product(product(1+x^(ithprime(k)^j),j=1..5),k=1..20)): gser:=series(g,x=0,68): seq(coeff(gser,x,n),n=1..63); # Emeric Deutsch, Aug 27 2007

m = 64; gf = (1+x)*Product[1+x^(Prime[k]^j), {j, 1, 5}, {k, 1, 18}] + O[x]^m; CoefficientList[gf, x] (* Jean-François Alcover, Mar 02 2019, from Maple *)

lista(m) = {x = t + t*O(t^m); gf = (1+x)*prod(k=1, m, if (isprimepower(k),(1+x^k), 1)); for (n=0, m, print1(polcoeff(gf, n, t), ", "));} \\ Michel Marcus, Mar 02 2019

a(n) = A054685(n-1)+A054685(n). - Vladeta Jovovic, Apr 28 2005

G.f.: (1+x)*Product(Product(1+x^(p(k)^j), j=1..infinity),k=1..infinity), where p(k) is the k-th prime (offset 0). - Emeric Deutsch, Aug 27 2007

Offset corrected and a(0)=1 added by Reinhard Zumkeller, Nov 24 2015

A054685 Number of partitions of n into distinct prime powers (1 not considered a power).

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 1, 3, 2, 4, 3, 5, 5, 6, 7, 7, 10, 9, 12, 12, 15, 15, 18, 19, 22, 24, 26, 30, 32, 36, 39, 43, 48, 51, 57, 61, 68, 73, 79, 87, 93, 103, 108, 121, 127, 140, 148, 162, 173, 187, 200, 215, 232, 247, 266, 283, 306, 324, 348, 371, 397, 423, 450, 480, 512, 543, 579, 614

Offset: 0

David W. Wilson, Apr 19 2000

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)

Cf. A051613.
Cf. A106244.
Cf. A000961.

import Data.MemoCombinators (memo2, integral)
a054685 n = a054685_list !! n
a054685_list = map (p' 2) [0..] where
   p' = memo2 integral integral p
   p _ 0 = 1
   p k m = if m < pp then 0 else p' (k + 1) (m - pp) + p' (k + 1) m
           where pp = a000961 k
-- Reinhard Zumkeller, Nov 23 2015

CoefficientList[Series[Product[Product[1 +x^(Prime[n]^k), {k, 1, 9}], {n, 1, 25}], {x, 0, 100}], x] (* G. C. Greubel, May 09 2019 *)

G.f.: Product_{p prime} Product_{k >= 1} (1 + x^(p^k)).

A009490 Number of distinct orders of permutations of n objects; number of nonisomorphic cyclic subgroups of symmetric group S_n.

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 6, 9, 11, 14, 16, 20, 23, 27, 31, 35, 43, 47, 55, 61, 70, 78, 88, 98, 111, 123, 136, 152, 168, 187, 204, 225, 248, 271, 296, 325, 356, 387, 418, 455, 495, 537, 581, 629, 678, 732, 787, 851, 918, 986, 1056, 1133, 1217, 1307, 1399, 1498, 1600, 1708, 1823

Offset: 0

David W. Wilson

Also number of different LCM's of partitions of n.

a(n) <= A023893(n), which counts the nonisomorphic Abelian subgroups of S_n. - M. F. Hasler, May 24 2013

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
L. Elliott, A. Levine, and J. D. Mitchell, Counting monogenic monoids and inverse monoids, arXiv:2303.12387 [math.GR], 2023.
Index entries for sequences related to lcm's

Cf. A051613 (first differences), A000792, A000793, A034891, A051625 (all cyclic subgroups), A256067.

b:= proc(n,i) option remember; local p;
      p:= `if`(i<1, 1, ithprime(i));
      `if`(n=0 or i<1, 1, b(n, i-1)+
      add(b(n-p^j, i-1), j=1..ilog[p](n)))
    end:
a:= n-> b(n, numtheory[pi](n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 15 2013

Table[ Length[ Union[ Apply[ LCM, Partitions[ n ], 1 ] ] ], {n, 30} ]
f[n_] := Length@ Union[LCM @@@ IntegerPartitions@ n]; Array[f, 60, 0]
(* Caution, the following is Extremely Slow and Resource Intensive *) CoefficientList[ Series[ Expand[ Product[1 + Sum[x^(Prime@ i^k), {k, 4}], {i, 10}]/(1 - x)], {x, 0, 30}], x]
b[n_, i_] := b[n, i] = Module[{p}, p = If[i<1, 1, Prime[i]]; If[n == 0 || i<1, 1, b[n, i-1]+Sum[b[n-p^j, i-1], {j, 1, Log[p, n]}]]]; a[n_] := b[n, PrimePi[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 03 2014, after Alois P. Heinz *)

/* compute David W. Wilson's g.f., needs <1 sec for 1000 terms */
N=1000;  x='x+O('x^N); /* N terms */
gf=1; /* generating function */
{ forprime(p=2,N,
    sm = 1;  pp=p;  /* sum;  prime power */
    while ( ppJoerg Arndt, Jan 19 2011 */

a(n) = Sum_{k=0..n} b(k), where b(k) is the number of partitions of k into distinct prime power parts (1 excluded) (A051613). - Vladeta Jovovic

G.f.: (Product_{p prime} (1 + Sum_{k >= 1} x^(p^k))) / (1-x). - David W. Wilson, Apr 19 2000

A051703 Maximal value of products of partitions of n into powers of distinct primes (1 not considered a power).

Original entry on oeis.org

1, 0, 2, 3, 4, 6, 0, 12, 15, 20, 30, 28, 60, 40, 84, 105, 140, 210, 180, 420, 280, 330, 360, 840, 504, 1260, 1155, 1540, 2310, 2520, 4620, 3080, 5460, 3960, 9240, 5544, 13860, 6552, 16380, 15015, 27720, 30030, 32760, 60060, 40040, 45045, 51480, 120120

Offset: 0

Vladeta Jovovic

nonn

			a(11) = 28 because max{11, 2*3^2, 2^3*3, 2^2*7} = 28.

Robert Gerbicz, Table of n, a(n) for n = 0..1000
J. Bamberg, G. Cairns and D. Kilminster, The crystallographic restriction, permutations and Goldbach's conjecture, Amer. Math. Monthly, 110 (March 2003), 202-209.

Largest element of n-th row of A080743.
A000793(n)=max{A000793(n-1), a(n)}, A000793(0)=1.
Cf. A008475, A051613, A080743, A080744, A051704.

b:= proc(n, i) option remember; local p;
      p:= `if`(i<1, 1, ithprime(i));
      `if`(n=0, 1, `if`(i<1 or n<0, 0, max(b(n, i-1),
      seq(p^j*b(n-p^j, i-1), j=1..ilog[p](n))) ))
    end:
a:= n-> b(n, numtheory[pi](n)):
seq(a(n), n=0..60);  # Alois P. Heinz, Feb 16 2013

nmax = 48; Do[a[n]=0, {n, 1, nmax}]; km = PrimePi[nmax]; For[k=1, k <= km, k++, q = 1; p = Prime[k]; For[i=nmax, i >= 1, i--, q=1; While[q*p <= i, q *= p; If[i == q, m = q, If[a[i - q] != 0, m = q*a[i - q], m = 0]]; a[i] = Max[a[i], m]]]]; a[0] = 1; Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Aug 02 2012, translated from Robert Gerbicz's Pari program *)

{N=1000;v=vector(N,i,0);forprime(p=2,N,q=1;forstep(i=N,1,-1,
q=1;while(q*p<=i,q*=p;if(i==q,M=q,if(v[i-q],M=q*v[i-q],M=0));
v[i]=max(v[i],M))));print(0" "1);for(i=1,N,print(i" "v[i]))} \\ Robert Gerbicz, Jul 31 2012

Corrected and extended by Robert Gerbicz, Jul 31 2012

A080743 Array read by rows in which n-th row lists orders of elements of Symm(n) that are not orders of elements of Symm(n-1) (6th row is empty, written as 0 by convention).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 0, 7, 10, 12, 8, 15, 9, 14, 20, 21, 30, 11, 18, 24, 28, 35, 42, 60, 13, 22, 36, 40, 33, 45, 70, 84, 26, 44, 56, 105, 16, 39, 55, 63, 66, 90, 120, 140, 17, 52, 72, 210, 65, 77, 78, 110, 126, 132, 168, 180, 19, 34, 48, 88, 165, 420, 51, 91, 99, 130, 154, 156, 220

Offset: 1

N. J. A. Sloane, Mar 08 2003

A051613 gives number of elements in n-th row.

			1;
2;
3;
4;
5, 6;
0;
7, 10, 12;
8, 15;
...

Alois P. Heinz, Rows n = 1..100, flattened
J. Bamberg, G. Cairns and D. Kilminster, The crystallographic restriction, permutations and Goldbach's conjecture, Amer. Math. Monthly, 110 (March 2003), 202-209.

Cf. A008475, A051613, A080744, A051703.

b:= proc(n) option remember; `if`(n<3, {n},
      {n, seq(map(x-> ilcm(x, i), b(n-i))[], i=2..n-1)}
       minus {seq(b(i)[], i=1..n-1)})
    end:
T:= proc(n) local l; l:= [b(n, n)[]];
      `if`(nops(l)=0, 0, sort(l)[])
    end:
seq(T(n), n=1..20);  # Alois P. Heinz, Feb 15 2013

b[n_, i_] := b[n, i] = Module[{p}, p = If[i<1, 1, Prime[i]]; If[n == 0, 1, If[i<1 || n<0, 0, Max[Join[{b[n, i-1]}, Table[p^j*b[n-p^j, i-1], {j, 1, Log[p, n]}]]]]] ]; T[1] = {1}; T[6] = {0}; T[n_] := Reap[For[m = n, m <= b[n, PrimePi[n]], m++,  If[n == Total[Power @@@ FactorInteger[m]], Sow[m]]]][[2, 1]]; Table[T[n], {n, 1, 20}] // Flatten (* Jean-François Alcover, Feb 26 2015, after Alois P. Heinz *)

n-th row = set of m such that A008475(m) = n, or 0 if no such m exists.

More terms from Vladeta Jovovic, Mar 12 2003

A035942 Number of partitions of n into distinct prime power parts (1 and 2 excluded).

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 6, 5, 5, 3, 6, 8, 7, 8, 7, 7, 8, 10, 12, 11, 10, 10, 12, 15, 18, 15, 15, 15, 17, 20, 24, 24, 20, 20, 25, 29, 32, 32, 28, 28, 32, 40, 44, 44, 39, 39, 43, 56, 58, 55, 54, 53, 58, 71, 80, 77, 69, 69, 79, 92

Offset: 0

Vladeta Jovovic

nonn

			a(16) = 3 because we can write 16=3+13=5+11=3^2+7

Cf. A051613.

A080744 Smallest element of n-th row of A080743.

Original entry on oeis.org

1, 2, 3, 4, 5, 0, 7, 8, 9, 21, 11, 35, 13, 33, 26, 16, 17, 65, 19, 51, 38, 57, 23, 95, 25, 69, 27, 75, 29, 150, 31, 32, 62, 93, 96, 155, 37, 217, 74, 111, 41, 185, 43, 123, 86, 129, 47, 215, 49, 141, 98, 147, 53, 245, 106, 159, 212, 265, 59, 371, 61, 177, 122, 64, 244, 305

Offset: 1

N. J. A. Sloane, Mar 08 2003

J. Bamberg, G. Cairns and D. Kilminster, The crystallographic restriction, permutations and Goldbach's conjecture, Amer. Math. Monthly, 110 (March 2003), 202-209.

Cf. A008475, A051613, A080743, A051703.

More terms from Vladeta Jovovic, Mar 09 2003

A079412 Number of ways to write n as sum of prime powers p^e such that e>0 and p does not divide n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 3, 1, 3, 1, 11, 1, 18, 3, 7, 5, 43, 2, 65, 5, 24, 10, 137, 4, 115, 17, 84, 16, 379, 3, 519, 42, 152, 47, 317, 12, 1267, 73, 334, 41, 2213, 9, 2897, 107, 344, 174, 4871, 32, 3733, 100, 1369, 245, 10218, 51, 4037, 235, 2607, 554, 20586, 23, 25792, 795

Offset: 1

Reinhard Zumkeller, Jan 07 2003

nonn

a(p) = A023894(p) - 1 for p prime.

			13 = 11+2 = 3^2+2^2 = 3^2+2+2 = 2^3+5 = 2^3+3+2 = 7+2^2+2 = 7+3+3 = 7+2+2+2 = 5+5+3 = 5+2^2+2^2 = 5+2^2+2+2 = 5+3+3+2 = 5+2+2+2+2 = 2^2+2^2+3+2 = 2^2+3+3+3 = 2^2+3+2+2+2 = 3+3+3+2+2 = 3+2+2+2+2+2, therefore a(13)=18, (A023894(13)=19, A079413(13)=3);
14 = 11+3 = 3^2+5 = 5+3+3+3, therefore a(14)=3, (A023894(14)=23, A079413(14)=2).

Cf. A079413, A023894, A051613, A000961.

A079413 Number of ways to write n as sum of powers p^e of distinct primes p such that e>0 and p does not divide n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 2, 1, 2, 1, 3, 1, 3, 2, 3, 3, 3, 2, 5, 3, 4, 3, 9, 3, 5, 4, 6, 4, 18, 3, 20, 8, 7, 8, 10, 6, 30, 9, 11, 8, 41, 5, 47, 11, 12, 13, 63, 10, 42, 13, 23, 16, 89, 13, 35, 20, 34, 28, 126, 11, 134, 35, 36, 44, 57, 15, 185, 40, 64, 19, 236, 31, 251, 64, 55, 54, 117, 24, 341

Offset: 1

Reinhard Zumkeller, Jan 07 2003

nonn

a(p) = A051613(p) - 1 for p prime.

			13 = 11+2 = 3^3+2^2 = 2^3+5, therefore a(13)=3, (A051613(13)=4, A054685(13)=6, A079412(13)=18);
14 = 11+3 = 3^2+5, therefore a(14)=2, (A051613(14)=4, A054685(14)=7, A079412(14)=3).

Cf. A079412, A054685, A051613, A023894, A000961.

cp's OEIS Frontend

A008475 If n = Product (p_j^k_j) then a(n) = Sum (p_j^k_j) (a(1) = 0 by convention).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A106244 Number of partitions into distinct prime powers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A054685 Number of partitions of n into distinct prime powers (1 not considered a power).

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A009490 Number of distinct orders of permutations of n objects; number of nonisomorphic cyclic subgroups of symmetric group S_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A051703 Maximal value of products of partitions of n into powers of distinct primes (1 not considered a power).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A080743 Array read by rows in which n-th row lists orders of elements of Symm(n) that are not orders of elements of Symm(n-1) (6th row is empty, written as 0 by convention).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula