A008480 -id:A008480 - cp's OEIS frontend

A050382 Number of ordered factorizations of n into primes by prime signature: A008480(A025487).

1, 1, 1, 2, 1, 3, 1, 4, 6, 1, 6, 5, 12, 1, 10, 6, 20, 1, 15, 30, 7, 24, 20, 30, 1, 21, 60, 8, 60, 35, 42, 1, 28, 105, 9, 120, 56, 90, 56, 1, 140, 36, 180, 70, 168, 10, 210, 84, 210, 72, 1, 280, 45, 120, 420, 126, 252, 11, 336, 120, 420, 90, 1, 504, 55, 360, 840, 210, 560, 360

Offset: 1

Christian G. Bower, Nov 15 1999

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

Cf. A008480, A025487.

a050382 = a008480 . a025487  -- Reinhard Zumkeller, Nov 19 2015

More terms from Don Reble, Nov 02 2001

A260987 Record values in A008480.

Original entry on oeis.org

1, 2, 3, 4, 6, 12, 20, 30, 60, 105, 120, 140, 180, 210, 280, 420, 504, 840, 1120, 1512, 1680, 2520, 3780, 5040, 6300, 7560, 9240, 12600, 13860, 15120, 15840, 27720, 34650, 37800, 55440, 83160, 102960, 110880, 138600, 180180, 205920, 216216, 240240, 332640

Offset: 1

Reinhard Zumkeller, Nov 18 2015

nonn

			.   n | x = A260633(n)        | y = a(n)             | [x/y] | x mod y
. ----+-----------------------+----------------------+-------+---------
.   1 |     1 | 1             |    1 | 1             |    1  |      0
.   2 |     6 | 2*3           |    2 | 2             |    3  |      0
.   3 |    12 | 2^2*3         |    3 | 3             |    4  |      0
.   4 |    24 | 2^3*3         |    4 | 2^2           |    6  |      0
.   5 |    30 | 2*3*5         |    6 | 2*3           |    5  |      0
.   6 |    60 | 2^2*3*5       |   12 | 2^2*3         |    5  |      0
.   7 |   120 | 2^3*3*5       |   20 | 2^2*5         |    6  |      0
.   8 |   180 | 2^2*3^2*5     |   30 | 2*3*5         |    6  |      0
.   9 |   360 | 2^3*3^2*5     |   60 | 2^2*3*5       |    6  |      0
.  10 |   720 | 2^4*3^2*5     |  105 | 3*5*7         |    6  |     90
.  11 |   840 | 2^3*3*5*7     |  120 | 2^3*3*5       |    7  |      0
.  12 |  1080 | 2^3*3^3*5     |  140 | 2^2*5*7       |    7  |    100
.  13 |  1260 | 2^2*3^2*5*7   |  180 | 2^2*3^2*5     |    7  |      0
.  14 |  1680 | 2^4*3*5*7     |  210 | 2*3*5*7       |    8  |      0
.  15 |  2160 | 2^4*3^3*5     |  280 | 2^3*5*7       |    7  |    200
.  16 |  2520 | 2^3*3^2*5*7   |  420 | 2^2*3*5*7     |    6  |      0
.  17 |  4320 | 2^5*3^3*5     |  504 | 2^3*3^2*7     |    8  |    288
.  18 |  5040 | 2^4*3^2*5*7   |  840 | 2^3*3*5*7     |    6  |      0
.  19 |  7560 | 2^3*3^3*5*7   | 1120 | 2^5*5*7       |    6  |    840
.  20 | 10080 | 2^5*3^2*5*7   | 1512 | 2^3*3^3*7     |    6  |   1008
.  21 | 12600 | 2^3*3^2*5^2*7 | 1680 | 2^4*3*5*7     |    7  |    840
.  22 | 15120 | 2^4*3^3*5*7   | 2520 | 2^3*3^2*5*7   |    6  |      0
.  23 | 25200 | 2^4*3^2*5^2*7 | 3780 | 2^2*3^3*5*7   |    6  |   2520
.  24 | 30240 | 2^5*3^3*5*7   | 5040 | 2^4*3^2*5*7   |    6  |      0
.  25 | 45360 | 2^4*3^4*5*7   | 6300 | 2^2*3^2*5^2*7 |    7  |   1260 .

Amiram Eldar, Table of n, a(n) for n = 1..2011 (terms 1..80 from Reinhard Zumkeller)

Cf. A008480, A260633.

a260987 n = a260987_list !! (n-1)
(a260987_list, a260633_list) = unzip $ f 1 0 where
   f x r = if y > r then (y, x) : f (x + 1) y else f (x + 1) r
           where y = a008480 x

a(n) = A008480(A260633(n)).

A099849 Partial sums of A008480.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 16, 17, 19, 21, 22, 23, 26, 27, 30, 32, 34, 35, 39, 40, 42, 43, 46, 47, 53, 54, 55, 57, 59, 61, 67, 68, 70, 72, 76, 77, 83, 84, 87, 90, 92, 93, 98, 99, 102, 104, 107, 108, 112, 114, 118, 120, 122, 123, 135, 136, 138, 141, 142, 144, 150

Offset: 1

Reinhard Zumkeller, Oct 27 2004

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

Cf. A008480, A099848.

a099849 n = a099849_list !! (n-1)
a099849_list = scanl1 (+) a008480_list -- Reinhard Zumkeller, Nov 19 2015

Accumulate[Table[Multinomial @@ FactorInteger[n][[;; , 2]], {n, 1, 100}]] (* Amiram Eldar, May 13 2025 *)

a(1) = A008480(1) and for n>1: a(n) = a(n-1) + A008480(n).

A099848(a(n) - k) = n for 0 <= k < A008480(n).

A318170 Composite numbers k such that A008480(k) = k.

Original entry on oeis.org

1781030694643200, 2671546041964800, 2968384491072000, 558162298053360000, 1953568043186760000

Offset: 1

Amiram Eldar, Aug 20 2018

Knopfmacher and Luca proved that this sequence is finite.

These numbers are named "prime-factor-perfect numbers" by Knopfmacher and Mays and "prime-perfect numbers" by Knopfmacher and Luca.

			1781030694643200 = 2^9 * 3^5 * 5^2 * 7^2 * 11^2 * 13 * 17 * 19 * 23 is in the sequence since multinomial(9+5+2+2+2+1+1+1+1,9,5,2,2,2,1,1,1,1) = 1781030694643200.

Arnold Knopfmacher and Florian Luca, On prime-perfect numbers, International Journal of Number Theory, Vol. 7, No. 7 (2011), pp. 1705-1716
Arnold Knopfmacher and M. E. Mays, A survey of factorization counting functions, International Journal of Number Theory, Vol. 1, No. 4 (2005), pp. 563-581, DOI: 10.1142/S1793042105000315.

Cf. A008480.

mul[w_] := Total[w]!/Times @@ (w!); f[n_] := Select[ IntegerPartitions@ n, # == Reverse@ Sort[ Last /@ FactorInteger[mul[#]]] &]; Sort[mul /@ Flatten[f /@ Range[2, 30], 1]] (* terms with sum of exponents in prime factorization <= 30, Giovanni Resta, Aug 20 2018 *)

A340155 Numbers k such that A008480(k) > k.

Original entry on oeis.org

326918592000, 435891456000, 653837184000, 871782912000, 980755776000, 1089728640000, 1307674368000, 1401079680000, 1508855040000, 1525620096000, 1569209241600, 1587890304000, 1634592960000, 1710035712000, 1852538688000, 1868106240000, 1961511552000, 2070484416000

Offset: 1

Amiram Eldar, Dec 29 2020

nonn

a(1) is given in the paper by Montgomery and Tenenbaum (2017).
If k is a term then all the numbers below k with the same prime signature as k are also terms. In particular A046523(k) is a term.
1710035712000 is the least term which is not in A025487.
Are there any odd terms in this sequence? If there are, the least of them is a term of A147516 and has more than 90 prime divisors (counted with multiplicity).

			326918592000 is a term since A008480(326918592000) = 358500542400 > 326918592000.

Hugh L. Montgomery and Gérald Tenenbaum, On Multiplicative Compositions Of Integers, Mathematika, Vol. 63, No. 3 (2017), pp. 1081-1090; altermative link. See p. 1088.

Cf. A008480, A025487, A046523, A147516, A260987, A270308, A318170.

A364750 Integers k such that A000010(k) <= A008480(k).

Original entry on oeis.org

1, 2, 6, 3326400, 4989600, 6652800, 9979200, 11793600, 19958400, 21621600, 23284800, 23587200, 25945920, 29937600, 33264000, 34927200, 35380800, 39916800, 43243200, 46569600, 47174400, 49896000, 51891840, 58968000, 59875200, 64864800, 66528000, 69854400, 70761600, 76204800, 77837760, 79833600

Offset: 1

Michel Marcus, Aug 05 2023

nonn

Cameron asked whether there is an integer k with exactly 3 distinct prime factors such that A000010(k) < A008480(k). David Bevan found that the smallest example is 2^51 * 3^34 * 5^20 = 3.581...*10^45. - Amiram Eldar, Aug 06 2023

Peter Cameron's Blog, An exercise in number theory, Posted on 17/02/2023.

Cf. A000010, A008480.

g[p_, e_] := (p - 1)*p^(e - 1); q[n_] := Module[{f = FactorInteger[n]}, Times @@ g @@@ f <= Multinomial @@ f[[;; , 2]]]; Select[Range[10^7], q] (* Amiram Eldar, Aug 06 2023 *)

m(n) = my(f=factor(n)[,2]); vecsum(f)!/prod(k=1, #f, f[k]!); \\ A008480
isok(n) = eulerphi(n) <= m(n);

A000961 Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227

Offset: 1

N. J. A. Sloane

The term "prime power" is ambiguous. To a mathematician it means any number p^k, p prime, k >= 0, including p^0 = 1.
Any nonzero integer is a product of primes and units, where the units are +1 and -1. This is tied to the Fundamental Theorem of Arithmetic which proves that the factorizations are unique up to order and units. (So, since 1 = p^0 does not have a well defined prime base p, it is sometimes not regarded as a prime power. See A246655 for the sequence without 1.)
These numbers are (apart from 1) the numbers of elements in finite fields. - Franz Vrabec, Aug 11 2004
Numbers whose divisors form a geometrical progression. The divisors of p^k are 1, p, p^2, p^3, ..., p^k. - Amarnath Murthy, Jan 09 2002
These are also precisely the orders of those finite affine planes that are known to exist as of today. (The order of a finite affine plane is the number of points in an arbitrarily chosen line of that plane. This number is unique for all lines comprise the same number of points.) - Peter C. Heinig (algorithms(AT)gmx.de), Aug 09 2006
Except for first term, the index of the second number divisible by n in A002378, if the index equals n. - Mats Granvik, Nov 18 2007
These are precisely the numbers such that lcm(1,...,m-1) < lcm(1,...,m) (=A003418(m) for m>0; here for m=1, the l.h.s. is taken to be 0). We have a(n+1)=a(n)+1 if a(n) is a Mersenne prime or a(n)+1 is a Fermat prime; the converse is true except for n=7 (from Catalan's conjecture) and n=1, since 2^1-1 and 2^0+1 are not considered as Mersenne resp. Fermat prime. - M. F. Hasler, Jan 18 2007, Apr 18 2010
The sequence is A000015 without repetitions, or more formally, A000961=Union[A000015]. - Zak Seidov, Feb 06 2008
Except for a(1)=1, indices for which the cyclotomic polynomial Phi[k] yields a prime at x=1, cf. A020500. - M. F. Hasler, Apr 04 2008
Also, {A138929(k) ; k>1} = {2*A000961(k) ; k>1} = {4,6,8,10,14,16,18,22,26,32,34,38,46,50,54,58,62,64,74,82,86,94,98,...} are exactly the indices for which Phi[k](-1) is prime. - M. F. Hasler, Apr 04 2008
A143201(a(n)) = 1. - Reinhard Zumkeller, Aug 12 2008
Number of distinct primes dividing n=omega(n) < 2. - Juri-Stepan Gerasimov, Oct 30 2009
Numbers n such that Sum_{p-1|p is prime and divisor of n} = Product_{p-1|p is prime and divisor of n}. A055631(n) = A173557(n-1). - Juri-Stepan Gerasimov, Dec 09 2009, Mar 10 2010
Numbers n such that A028236(n) = 1. Klaus Brockhaus, Nov 06 2010
A188666(k) = a(k+1) for k: 2*a(k) <= k < 2*a(k+1), k > 0; notably a(n+1) = A188666(2*a(n)). - Reinhard Zumkeller, Apr 25 2011
A003415(a(n)) = A192015(n); A068346(a(n)) = A192016(n); a(n)=A192134(n) + A192015(n). - Reinhard Zumkeller, Jun 26 2011
A089233(a(n)) = 0. - Reinhard Zumkeller, Sep 04 2013
The positive integers n such that every element of the symmetric group S_n which has order n is an n-cycle. - W. Edwin Clark, Aug 05 2014
Conjecture: these are numbers m such that Sum_{k=0..m-1} k^phi(m) == phi(m) (mod m), where phi(m) = A000010(m). - Thomas Ordowski and Giovanni Resta, Jul 25 2018
Numbers whose (increasingly ordered) divisors are alternatingly squares and nonsquares. - Michel Marcus, Jan 16 2019
Possible numbers of elements in a finite vector space. - Jianing Song, Apr 22 2021

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
M. Koecher and A. Krieg, Ebene Geometrie, Springer, 1993.
R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge 1986, Theorem 2.5, p. 45.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Chris Bispels, Matthew Cohen, Joshua Harrington, Joshua Lowrance, Kaelyn Pontes, Leif Schaumann, and Tony W. H. Wong, A further investigation on covering systems with odd moduli, arXiv:2507.16135 [math.NT], 2025. See p. 3.
Brady Haran and Günter Ziegler, Cannons and Sparrows, Numberphile video (2018).
Laurentiu Panaitopol, Some of the properties of the sequence of powers of prime numbers, Rocky Mountain Journal of Mathematics, Volume 31, Number 4, Winter 2001.
Eric Weisstein's World of Mathematics, Prime Power
Eric Weisstein's World of Mathematics, Projective Plane
Index entries for "core" sequences

There are four different sequences which may legitimately be called "prime powers": A000961 (p^k, k >= 0), A246655 (p^k, k >= 1), A246547 (p^k, k >= 2), A025475 (p^k, k=0 and k >= 2). When you refer to "prime powers", be sure to specify which of these you mean. Also A001597 is the sequence of nontrivial powers n^k, n >= 1, k >= 2. - N. J. A. Sloane, Mar 24 2018
Cf. A008480, A010055, A065515, A095874, A025473.
Cf. indices of record values of A003418; A000668 and A019434 give a member of twin pairs a(n+1)=a(n)+1.
A138929(n) = 2*a(n).
Cf. A000040, A001221, A001477. - Juri-Stepan Gerasimov, Dec 09 2009
A028236 (if n = Product (p_j^k_j), a(n) = numerator of Sum 1/p_j^k_j). - Klaus Brockhaus, Nov 06 2010
A000015(n) = Min{term : >= n}; A031218(n) = Max{term : <= n}.
Complementary (in the positive integers) to sequence A024619. - Jason Kimberley, Nov 10 2015

import Data.Set (singleton, deleteFindMin, insert)
a000961 n = a000961_list !! (n-1)
a000961_list = 1 : g (singleton 2) (tail a000040_list) where
g s (p:ps) = m : g (insert (m * a020639 m) $ insert p s') ps
where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, May 01 2012, Apr 25 2011

[1] cat [ n : n in [2..250] | IsPrimePower(n) ]; // corrected by Arkadiusz Wesolowski, Jul 20 2012

readlib(ifactors): for n from 1 to 250 do if nops(ifactors(n)[2])=1 then printf(`%d,`,n) fi: od:
# second Maple program:
a:= proc(n) option remember; local k; for k from
      1+a(n-1) while nops(ifactors(k)[2])>1 do od; k
    end: a(1):=1: A000961:= a:
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 08 2013

Select[ Range[ 2, 250 ], Mod[ #, # - EulerPhi[ # ] ] == 0 & ]
Select[ Range[ 2, 250 ], Length[FactorInteger[ # ] ] == 1 & ]
max = 0; a = {}; Do[m = FactorInteger[n]; w = Sum[m[[k]][[1]]^m[[k]][[2]], {k, 1, Length[m]}]; If[w > max, AppendTo[a, n]; max = w], {n, 1, 1000}]; a (* Artur Jasinski *)
Join[{1}, Select[Range[2, 250], PrimePowerQ]] (* Jean-François Alcover, Jul 07 2015 *)

A000961(n,l=-1,k=0)=until(n--<1,until(lA000961(lim=999,l=-1)=for(k=1,lim, l==lcm(l,k) && next; l=lcm(l,k); print1(k,",")) \\ M. F. Hasler, Jan 18 2007

isA000961(n) = (omega(n) == 1 || n == 1) \\ Michael B. Porter, Sep 23 2009

nextA000961(n)=my(m,r,p);m=2*n;for(e=1,ceil(log(n+0.01)/log(2)),r=(n+0.01)^(1/e);p=prime(primepi(r)+1);m=min(m,p^e));m \\ Michael B. Porter, Nov 02 2009

is(n)=isprimepower(n) || n==1 \\ Charles R Greathouse IV, Nov 20 2012

list(lim)=my(v=primes(primepi(lim)),u=List([1])); forprime(p=2,sqrtint(lim\1),for(e=2,log(lim+.5)\log(p),listput(u,p^e))); vecsort(concat(v,Vec(u))) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import primerange
def A000961_list(limit): # following Python style, list terms < limit
    L = [1]
    for p in primerange(1, limit):
        pe = p
        while pe < limit:
            L.append(pe)
            pe *= p
    return sorted(L) # Chai Wah Wu, Sep 08 2014, edited by M. F. Hasler, Jun 16 2022

from sympy import primepi
from sympy.ntheory.primetest import integer_nthroot
def A000961(n):
    def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return m # Chai Wah Wu, Jul 23 2024

def A000961_list(n):
    R = [1]
    for i in (2..n):
        if i.is_prime_power(): R.append(i)
    return R
A000961_list(227) # Peter Luschny, Feb 07 2012

a(n) = A025473(n)^A025474(n). - David Wasserman, Feb 16 2006
a(n) = A117331(A117333(n)). - Reinhard Zumkeller, Mar 08 2006
Panaitopol (2001) gives many properties, inequalities and asymptotics, including a(n) ~ prime(n). - N. J. A. Sloane, Oct 31 2014, corrected by M. F. Hasler, Jun 12 2023 [The reference gives pi*(x) = pi(x) + pi(sqrt(x)) + ... where pi*(x) counts the terms up to x, so it is the inverse function to a(n).]
m=a(n) for some n <=> lcm(1,...,m-1) < lcm(1,...,m), where lcm(1...0):=0 as to include a(1)=1. a(n+1)=a(n)+1 <=> a(n+1)=A019434(k) or a(n)=A000668(k) for some k (by Catalan's conjecture), except for n=1 and n=7. - M. F. Hasler, Jan 18 2007, Apr 18 2010
A001221(a(n)) < 2. - Juri-Stepan Gerasimov, Oct 30 2009
A008480(a(n)) = 1 for all n >= 1. - Alois P. Heinz, May 26 2018
Sum_{k=1..n} 1/a(k) ~ log(log(a(n))) + 1 + A077761 + A136141. - François Huppé, Jul 31 2024

Description modified by Ralf Stephan, Aug 29 2014

A181819 Prime shadow of n: a(1) = 1; for n>1, if n = Product prime(i)^e(i), then a(n) = Product prime(e(i)).

Original entry on oeis.org

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

Offset: 1

Matthew Vandermast, Dec 07 2010

a(n) depends only on prime signature of n (cf. A025487). a(m) = a(n) iff m and n have the same prime signature, i.e., iff A046523(m) = A046523(n).

Because A046523 (the smallest representative of prime signature of n) and this sequence are functions of each other as A046523(n) = A181821(a(n)) and a(n) = a(A046523(n)), it implies that for all i, j: a(i) = a(j) <=> A046523(i) = A046523(j) <=> A101296(i) = A101296(j), i.e., that equivalence-class-wise this is equal to A101296, and furthermore, applying any function f on this sequence gives us a sequence b(n) = f(a(n)) whose equivalence class partitioning is equal to or coarser than that of A101296, i.e., b is then a sequence that depends only on the prime signature of n (the multiset of exponents of its prime factors), although not necessarily in a very intuitive way. - Antti Karttunen, Apr 28 2022

			20 = 2^2*5 has the exponents (2,1) in its prime factorization. Accordingly, a(20) = prime(2)*prime(1) = A000040(2)*A000040(1) = 3*2 = 6.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences computed from exponents in factorization of n

Column 1 of A353510 (see also A325239 and A325277).
Cf. A000040, A000265, A001511, A001222, A003963, A005361, A007814, A008578, A028234, A046523, A056239, A064553, A064989, A067029, A101296 (restricted growth sequence transform), A108951, A122111, A124010, A124859, A156552, A181820, A181821, A182850, A182855, A182857 (also A323014), A115621, A101296, A238690, A238745, A238747, A238748, A246029, A304465, A304647, A305732, A305733, A320118, A323022, A325501, A325502, A325507, A325508, A325755 (A353566), A325756, A328830 [= a(a(n))], A328835, A351564 (characteristic function of A130091), A351944, A351946, A353379.
Left inverse of A304660.

a181819 = product . map a000040 . a124010_row
-- Reinhard Zumkeller, Mar 26 2012

A181819 := proc(n)
    local a;
    a := 1;
    for pf in ifactors(n)[2] do
        a := a*ithprime(pf[2]) ;
    end do:
    a ;
end proc:
seq(A181819(n),n=1..80) ; # R. J. Mathar, Jan 09 2019
# second Maple program:
a:= n-> mul(ithprime(i[2]), i=ifactors(n)[2]):
seq(a(n), n=1..105);  # Alois P. Heinz, Nov 26 2024

{1}~Join~Table[Times @@ Prime@ Map[Last, FactorInteger@ n], {n, 2, 120}] (* Michael De Vlieger, Feb 07 2016 *)

a(n) = {my(f=factor(n)); prod(k=1, #f~, prime(f[k,2]));} \\ Michel Marcus, Nov 16 2015

;; With memoization-macro definec.
(definec (A181819 n) (cond ((= 1 n) 1) (else (* (A000040 (A067029 n)) (A181819 (A028234 n))))))
;; Antti Karttunen, Feb 05 2016

;; With memoization-macro definec.
(definec (A181819 n) (cond ((= 1 n) 1) ((even? n) (* (A000040 (A007814 n)) (A181819 (A000265 n)))) (else (A181819 (A064989 n)))))
;; Antti Karttunen, Feb 07 2016

From Antti Karttunen, Feb 07 2016: (Start)
a(1) = 1; for n > 1, a(n) = A000040(A067029(n)) * a(A028234(n)).
a(1) = 1; for n > 1, a(n) = A008578(A001511(n)) * a(A064989(n)).
Other identities. For all n >= 1:
a(A124859(n)) = A122111(a(n)) = A238745(n). - from Matthew Vandermast's formulas for the latter sequence.
(End)
a(n) = A246029(A156552(n)). - Antti Karttunen, Oct 15 2016
From Antti Karttunen, Apr 28 & Apr 30 2022: (Start)
A181821(a(n)) = A046523(n) and a(A046523(n)) = a(n). [See comments]
a(n) = A329900(A124859(n)) = A319626(A124859(n)).
a(n) = A246029(A156552(n)).
a(a(n)) = A328830(n).
a(A304660(n)) = n.
a(A108951(n)) = A122111(n).
a(A185633(n)) = A322312(n).
a(A025487(n)) = A181820(n).
a(A276076(n)) = A275735(n) and a(A276086(n)) = A328835(n).
As the sequence converts prime exponents to prime indices, it effects the following mappings:
A001221(a(n)) = A071625(n). [Number of distinct indices --> Number of distinct exponents]
A001222(a(n)) = A001221(n). [Number of indices (i.e., the number of prime factors with multiplicity) --> Number of exponents (i.e., the number of distinct prime factors)]
A056239(a(n)) = A001222(n). [Sum of indices --> Sum of exponents]
A066328(a(n)) = A136565(n). [Sum of distinct indices --> Sum of distinct exponents]
A003963(a(n)) = A005361(n). [Product of indices --> Product of exponents]
A290103(a(n)) = A072411(n). [LCM of indices --> LCM of exponents]
A156061(a(n)) = A290107(n). [Product of distinct indices --> Product of distinct exponents]
A257993(a(n)) = A134193(n). [Index of the least prime not dividing n --> The least number not among the exponents]
A055396(a(n)) = A051904(n). [Index of the least prime dividing n --> Minimal exponent]
A061395(a(n)) = A051903(n). [Index of the greatest prime dividing n --> Maximal exponent]
A008966(a(n)) = A351564(n). [All indices are distinct (i.e., n is squarefree) --> All exponents are distinct]
A007814(a(n)) = A056169(n). [Number of occurrences of index 1 (i.e., the 2-adic valuation of n) --> Number of occurrences of exponent 1]
A056169(a(n)) = A136567(n). [Number of unitary prime divisors --> Number of exponents occurring only once]
A064989(a(n)) = a(A003557(n)) = A295879(n). [Indices decremented after <--> Exponents decremented before]
Other mappings:
A007947(a(n)) = a(A328400(n)) = A329601(n).
A181821(A007947(a(n))) = A328400(n).
A064553(a(n)) = A000005(n) and A000005(a(n)) = A182860(n).
A051903(a(n)) = A351946(n).
A003557(a(n)) = A351944(n).
A258851(a(n)) = A353379(n).
A008480(a(n)) = A309004(n).
a(A325501(n)) = A325507(n) and a(A325502(n)) = A038754(n+1).
a(n!) = A325508(n).
(End)

Name "Prime shadow" (coined by Gus Wiseman in A325755) prefixed to the definition by Antti Karttunen, Apr 27 2022

A074206 Kalmár's [Kalmar's] problem: number of ordered factorizations of n.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, 20, 2, 3, 4, 8, 1, 13, 1, 16, 3, 3, 3, 26, 1, 3, 3, 20, 1, 13, 1, 8, 8, 3, 1, 48, 2, 8, 3, 8, 1, 20, 3, 20, 3, 3, 1, 44, 1, 3, 8, 32, 3, 13, 1, 8, 3, 13, 1, 76, 1, 3, 8, 8, 3, 13, 1, 48, 8, 3, 1, 44, 3, 3, 3, 20, 1, 44, 3, 8, 3, 3, 3, 112

Offset: 0

N. J. A. Sloane, Apr 29 2003

a(0)=0, a(1)=1; thereafter a(n) is the number of ordered factorizations of n as a product of integers greater than 1.
Kalmár (1931) seems to be the earliest reference that mentions this sequence (as opposed to A002033). - N. J. A. Sloane, May 05 2016
a(n) is the permanent of the n-1 X n-1 matrix A with (i,j) entry = 1 if j|i+1 and = 0 otherwise. This is because ordered factorizations correspond to nonzero elementary products in the permanent. For example, with n=6, 3*2 -> 1,3,6 [partial products] -> 6,3,1 [reverse list] -> (6,3)(3,1) [partition into pairs with offset 1] -> (5,3)(2,1) [decrement first entry] -> (5,3)(2,1)(1,2)(3,4)(4,5) [append pairs (i,i+1) to get a permutation] -> elementary product A(1,2)A(2,1)A(3,4)A(4,5)A(5,3). - David Callan, Oct 19 2005
This sequence is important in describing the amount of energy in all wave structures in the Universe according to harmonics theory. - Ray Tomes (ray(AT)tomes.biz), Jul 22 2007
a(n) appears to be the number of permutation matrices contributing to the Moebius function. See A008683 for more information. Also a(n) appears to be the Moebius transform of A067824. Furthermore it appears that except for the first term a(n)=A067824(n)*(1/2). Are there other sequences such that when the Moebius transform is applied, the new sequence is also a constant factor times the starting sequence? - Mats Granvik, Jan 01 2009
Numbers divisible by n distinct primes appear to have ordered factorization values that can be found in an n-dimensional summatory Pascal triangle. For example, the ordered factorization values for numbers divisible by two distinct primes can be found in table A059576. - Mats Granvik, Sep 06 2009
Inverse Mobius transform of A174725 and also except for the first term, inverse Mobius transform of A174726. - Mats Granvik, Mar 28 2010
a(n) is a lower bound on the worst-case number of solutions to the probed partial digest problem for n fragments of DNA; see the Newberg & Naor reference, below. - Lee A. Newberg, Aug 02 2011
All integers greater than 1 are perfect numbers over this sequence (for definition of A-perfect numbers, see comment to A175522). - Vladimir Shevelev, Aug 03 2011
If n is squarefree, then a(n) = A000670(A001221(n)) = A000670(A001222(n)). - Vladimir Shevelev and Franklin T. Adams-Watters, Aug 05 2011
A034776 lists the values taken by this sequence. - Robert G. Wilson v, Jun 02 2012
From Gus Wiseman, Aug 25 2020: (Start)
Also the number of strict chains of divisors from n to 1. For example, the a(n) chains for n = 1, 2, 4, 6, 8, 12, 30 are:
  1  2/1  4/1    6/1    8/1      12/1      30/1
          4/2/1  6/2/1  8/2/1    12/2/1    30/2/1
                 6/3/1  8/4/1    12/3/1    30/3/1
                        8/4/2/1  12/4/1    30/5/1
                                 12/6/1    30/6/1
                                 12/4/2/1  30/10/1
                                 12/6/2/1  30/15/1
                                 12/6/3/1  30/6/2/1
                                           30/6/3/1
                                           30/10/2/1
                                           30/10/5/1
                                           30/15/3/1
                                           30/15/5/1
(End)
a(n) is also the number of ways to tile a strip of length log(n) with tiles having lengths {log(k) : k>=2}. - David Bevan, Jan 07 2025

			G.f. = x + x^2 + x^3 + 2*x^4 + x^5 + 3*x^6 + x^7 + 4*x^8 + 2*x^9 + 3*x^10 + ...
Number of ordered factorizations of 8 is 4: 8 = 2*4 = 4*2 = 2*2*2.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
Kalmár, Laszlo, A "factorisatio numerorum" problemajarol [Hungarian], Matemat. Fizik. Lapok, 38 (1931), 1-15.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.

N. J. A. Sloane, Table of n, a(n) for n = 0..20000 (first 10000 terms from T. D. Noe)
David Bevan and Julien Condé, Introducing irrational enumeration: analytic combinatorics for objects of irrational size, arXiv:2412.14682 [math.CO], 2024. See p. 11.
Peter Brown, Number of Ordered Factorizations.
Peter Brown, Number of Ordered Factorizations.
Benny Chor, Paul Lemke, and Ziv Mador, On the number of ordered factorizations of natural numbers, Discrete Math. 214 (2000), no. 1-3, 123-133. MR1743631 (2000m:11093).
Kristin DeVleming and Nikita Singh, Rational unicuspidal plane curves of low degree, arXiv:2311.15922 [math.AG], 2023. See p. 14.
T. M. A. Fink, Properties of the recursive divisor function and the number of ordered factorizations, arXiv:2307.09140 [math.NT], 2023.
E. Hille, A problem in factorisatio numerorum, Acta Arith., 2 (1936), 134-144.
E. Hille, The inversion problem of Möbius, Duke Math. J., 3 (1937), 549-568.
Shikao Ikehara, On Kalmar's Problem in "Factorisatio Numerorum", Proceedings of the Physico-Mathematical Society of Japan. 3rd Series, Vol. 21 (1939) pp. 208-219.
Shikao Ikehara, On Kalmar's Problem in "Factorisatio Numerorum" II, Proceedings of the Physico-Mathematical Society of Japan. 3rd Series, Vol. 23 (1941) pp. 767-774.
Laszlo Kalmár, Über die mittlere Anzahl der Produktdarstellungen der Zahlen. (Erste Mitteilung), Acta Litt. ac Scient. Szeged 5 (1931): 95-107.
M. Klazar and F. Luca, On the maximal order of numbers in the "factorisatio numerorum" problem, arXiv:math/0505352 [math.NT], 2005-2006.
Arnold Knopfmacher and Michael Mays, Ordered and Unordered Factorization of Integers, The Mathematica Journal, Volume 10, Issue 1 p. 72.
Arnau Mir, Francesc Rossello, and Lucia Rotger, Sound Colless-like balance indices for multifurcating trees, arXiv:1805.01329 [q-bio.PE], 2018.
Augustine O. Munagi, Labeled factorization of integers, INTEGERS: The Electronic Journal of Combinatorics 16:1 (2009), #R50.
L. A. Newberg and D. Naor, A lower bound on the number of solutions to the probed partial digest problem, Advances in Applied Mathematics, 14(2), 1993, 172-183. doi: 10.1006/aama.1993.1009.
Ray Tomes, The Maths and Physics of the Harmonics Theory.
Eric Weisstein's World of Mathematics, Perfect Partition.
Eric Weisstein's World of Mathematics, Ordered Factorization.
David W. Wilson, Comments on A074206 and related sequences.
David W. Wilson, Perl program for A074206.
Index entries for "core" sequences

Apart from initial term, same as A002033.
a(A002110) = A000670, row sums of A251683.
A173382 (and A025523) gives partial sums.
Cf. A008683, A050324, A027751, A001221, A034776, A000670, A050369.
A124433 has these as unsigned row sums.
A334996 has these as row sums.
A001055 counts factorizations.
A001222 counts prime factors with multiplicity.
A008480 counts ordered prime factorizations.
A067824 counts strict chains of divisors starting with n.
A122651 counts strict chains of divisors summing to n.
A253249 counts strict chains of divisors.
Cf. A000005, A025487, A046523, A059576, A122408, A124010, A153881 (Dirichlet inverse), A167865, A174725, A174726, A175522, A181819, A320390, A334997, A337105, A361665.

a074206 n | n <= 1 = n
| otherwise = 1 + (sum $ map (a074206 . (div n)) $
tail $ a027751_row n)
-- Reinhard Zumkeller, Oct 01 2012

a := array(1..150): for k from 1 to 150 do a[k] := 0 od: a[1] := 1: for j from 2 to 150 do for m from 1 to j-1 do if j mod m = 0 then a[j] := a[j]+a[m] fi: od: od: for k from 1 to 150 do printf(`%d,`,a[k]) od: # James Sellers, Dec 07 2000
A074206:= proc(n) option remember; if n > 1 then `+`(op(apply(A074206, numtheory[divisors](n)[1..-2]))) else n fi end: # M. F. Hasler, Oct 12 2018

a[0] = 0; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[20000] (* N. J. A. Sloane, May 04 2016, based on program in A002033 *)
ccc[n_]:=Switch[n,0,{},1,{{1}},,Join@@Table[Prepend[#,n]&/@ccc[d],{d,Most[Divisors[n]]}]]; Table[Length[ccc[n]],{n,0,100}] (* _Gus Wiseman, Aug 25 2020 *)

A=vector(100);A[1]=1; for(n=2,#A,A[n]=1+sumdiv(n,d,A[d])); A/=2; A[1]=1; concat(0,A) \\ Charles R Greathouse IV, Nov 20 2012

{a(n) = if( n<2, n>0, my(A = divisors(n)); sum(k=1, #A-1, a(A[k])))}; /* Michael Somos, Dec 26 2016 */

A074206(n)=if(n>1, sumdiv(n, i, if(iA074206(i))),n) \\ M. F. Hasler, Oct 12 2018

A74206=[1]; A074206(n)={if(#A74206A074206(i)))} \\ Use memoization for computing many values. - M. F. Hasler, Oct 12 2018

first(n) = {my(res = vector(n, i, 1)); for(i = 2, n, for(j = 2, n \ i, res[i*j] += res[i])); concat(0, res)} \\ David A. Corneth, Oct 13 2018

first(n) = {my(res = vector(n, i, 1)); for(i = 2, n, d = divisors(i); res[i] += sum(j = 1, #d-1, res[d[j]])); concat(0, res)} \\ somewhat faster than progs above for finding first terms of n. \\ David A. Corneth, Oct 12 2018

a(n)={if(!n, 0, my(sig=factor(n)[,2], m=vecsum(sig)); sum(k=0, m, prod(i=1, #sig, binomial(sig[i]+k-1, k-1))*sum(r=k, m, binomial(r,k)*(-1)^(r-k))))} \\ Andrew Howroyd, Aug 30 2020

from math import prod
from functools import lru_cache
from sympy import divisors, factorint, prime
@lru_cache(maxsize=None)
def A074206(n): return sum(A074206(d) for d in divisors(prod(prime(i+1)**e for i,e in enumerate(sorted(factorint(n).values(),reverse=True))),generator=True,proper=True)) if n > 1 else n # Chai Wah Wu, Sep 16 2022

@cached_function
def minus_mu(n):
    if n < 2: return n
    return sum(minus_mu(d) for d in divisors(n)[:-1])
# Note that changing the sign of the sum gives the Möbius function A008683.
print([minus_mu(n) for n in (0..96)]) # Peter Luschny, Dec 26 2016

With different offset: a(n) = sum of all a(i) such that i divides n and i < n. - Clark Kimberling
a(p^k) = 2^(k-1) if k>0 and p is a prime.
Dirichlet g.f.: 1/(2-zeta(s)). - Herbert S. Wilf, Apr 29 2003
a(n) = A067824(n)/2 for n>1; a(A122408(n)) = A122408(n)/2. - Reinhard Zumkeller, Sep 03 2006
If p,q,r,... are distinct primes, then a(p*q)=3, a(p^2*q)=8, a(p*q*r)=13, a(p^3*q)=20, etc. - Vladimir Shevelev, Aug 03 2011 [corrected by Charles R Greathouse IV, Jun 02 2012]
a(0) = 0, a(1) = 1; a(n) = [x^n] Sum_{k=1..n-1} a(k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Dec 11 2017
a(n) = a(A046523(n)); a(A025487(n)) = A050324(n): a(n) depends only on the nonzero exponents in the prime factorization of n, more precisely prime signature of n, cf. A124010 and A320390. - M. F. Hasler, Oct 12 2018
a(n) = A000670(A001221(n)) for squarefree n. In particular a(A002110(n)) = A000670(n). - Amiram Eldar, May 13 2019
a(n) = A050369(n)/n, for n>=1. - Ridouane Oudra, Aug 31 2019
a(n) = A361665(A181819(n)). - Pontus von Brömssen, Mar 25 2023
From Ridouane Oudra, Nov 02 2023: (Start)
If p,q are distinct primes, and n,m>0 then we have:
a(p^n*q^m) = Sum_{k=0..min(n,m)} 2^(n+m-k-1)*binomial(n,k)*binomial(m,k);
More generally: let tau[k](n) denote the number of ordered factorizations of n as a product of k terms, also named the k-th Piltz function (see A007425), then we have for n>1:
a(n) = Sum_{j=1..bigomega(n)} Sum_{k=1..j} (-1)^(j-k)*binomial(j,k)*tau[k](n), or
a(n) = Sum_{j=1..bigomega(n)} Sum_{k=0..j-1} (-1)^k*binomial(j,k)*tau[j-k](n). (End)

Originally this sequence was merged with A002033, the number of perfect partitions. Herbert S. Wilf suggested that it warrants an entry of its own.

A335448 Numbers whose prime indices are inseparable.

Original entry on oeis.org

4, 8, 9, 16, 24, 25, 27, 32, 40, 48, 49, 54, 56, 64, 80, 81, 88, 96, 104, 112, 121, 125, 128, 135, 136, 144, 152, 160, 162, 169, 176, 184, 189, 192, 208, 224, 232, 240, 243, 248, 250, 256, 272, 288, 289, 296, 297, 304, 320, 324, 328, 336, 343, 344, 351, 352

Offset: 1

Gus Wiseman, Jun 21 2020

nonn

First differs from A212164 in lacking 72.
First differs from A293243 in lacking 72.
No terms are squarefree.
Also Heinz numbers of inseparable partitions (A325535). The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
These are also numbers that can be written as a product of prime numbers, each different from the last but not necessarily different from those prior to the last.
A multiset is inseparable iff its maximal multiplicity is greater than one plus the sum of its remaining multiplicities.

			The sequence of terms together with their prime indices begins:
   4: {1,1}
   8: {1,1,1}
   9: {2,2}
  16: {1,1,1,1}
  24: {1,1,1,2}
  25: {3,3}
  27: {2,2,2}
  32: {1,1,1,1,1}
  40: {1,1,1,3}
  48: {1,1,1,1,2}
  49: {4,4}
  54: {1,2,2,2}
  56: {1,1,1,4}
  64: {1,1,1,1,1,1}
  80: {1,1,1,1,3}
  81: {2,2,2,2}
  88: {1,1,1,5}
  96: {1,1,1,1,1,2}

Complement of A335433.
Separations are counted by A003242 and A335452 and ranked by A333489.
Permutations of prime indices are counted by A008480.
Inseparable partitions are counted by A325535.
Strict permutations of prime indices are counted by A335489.
Cf. A000670, A000961, A005117, A056239, A112798, A181796, A261962, A333221, A335451.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Select[Permutations[primeMS[#]],!MatchQ[#,{_,x_,x_,_}]&]=={}&]

cp's OEIS Frontend

A050382 Number of ordered factorizations of n into primes by prime signature: A008480(A025487).

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Extensions

A260987 Record values in A008480.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Formula

A099849 Partial sums of A008480.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A318170 Composite numbers k such that A008480(k) = k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A340155 Numbers k such that A008480(k) > k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A364750 Integers k such that A000010(k) <= A008480(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A000961 Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Python

Sage

Formula