cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Views

Author

N. J. A. Sloane, Apr 29 2003

Keywords

Comments

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

Examples

			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.

References

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

Links

Crossrefs

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.

Programs

  • Haskell
    a074206 n | n <= 1 = n
| otherwise = 1 + (sum $ map (a074206 . (div n)) $
tail $ a027751_row n)
-- Reinhard Zumkeller, Oct 01 2012
  • Maple
    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
  • Mathematica
    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 *)
  • PARI
    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
  • PARI
    {a(n) = if( n<2, n>0, my(A = divisors(n)); sum(k=1, #A-1, a(A[k])))}; /* Michael Somos, Dec 26 2016 */
  • PARI
    A074206(n)=if(n>1, sumdiv(n, i, if(iA074206(i))),n) \\ M. F. Hasler, Oct 12 2018
  • PARI
    A74206=[1]; A074206(n)={if(#A74206A074206(i)))} \\ Use memoization for computing many values. - M. F. Hasler, Oct 12 2018
  • PARI
    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
  • PARI
    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
  • PARI
    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
  • Python
    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
  • SageMath
    @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

Formula

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)

Extensions

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.