A002104 Logarithmic numbers. (Formerly M2749 N1105)

0, 1, 3, 8, 24, 89, 415, 2372, 16072, 125673, 1112083, 10976184, 119481296, 1421542641, 18348340127, 255323504932, 3809950977008, 60683990530225, 1027542662934915, 18430998766219336, 349096664728623336, 6962409983976703337, 145841989688186383359, 3201192743180799343844

Offset

0,3

Comments

Prime p divides a(p+1). - Alexander Adamchuk, Jul 05 2006

Also number of lists of elements from {1,..,n} with (1st element) = (smallest element), where a list means an ordered subset (cf. A000262), see also Haskell program. - Reinhard Zumkeller, Oct 26 2010

a(n+1) = p_n(-1) where p_n(x) is the unique degree-n polynomial such that p_n(k) = A133942(k) for k = 0, 1, ..., n. - Michael Somos, Apr 30 2012

a(n) = A006231(n) + n. - Geoffrey Critzer, Oct 04 2012

References

J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.

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

Links

T. D. Noe, Table of n, a(n) for n = 0..100 (corrected by Michel Marcus, Jan 19 2019)

J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83. [Annotated scanned copy]

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 116

J. C. Tiernan, An efficient search algorithm to find the elementary circuits of a graph, Commun. ACM, 13 (1970), 722-726.

Index entries for sequences related to logarithmic numbers

Formula

E.g.f.: -log(1 - x) * exp(x).

a(n) = Sum_{k=1..n} Sum_{i=0..n-k} (n-k)!/i!.

a(n) = Sum_{k=1..n} n(n-1)...(n-k+1)/k = A006231(n) + n - Avi Peretz (njk(AT)netvision.net.il), Mar 24 2001

a(n+1) - a(n) = A000522(n).

a(n) = sum{k=0..n-1, binomial(n, k)*(n-k-1)!}, row sums of A111492. - Paul Barry, Aug 26 2004

a(n) = Sum[Sum[m!/k!,{k,0,m}],{m,0,n-1}]. a(n) = Sum[A000522(m),{m,0,n-1}]. - Alexander Adamchuk, Jul 05 2006

For n > 1, the arithmetic mean of the first n terms is a(n-1) + 1. - Franklin T. Adams-Watters, May 20 2010

a(n) = n * 3F1((1,1,1-n); (2); -1). - Jean-François Alcover, Mar 29 2011

Conjecture: a(n) +(-n-1)*a(n-1) +2*(n-1)*a(n-2) +(-n+2)*a(n-3)=0. - R. J. Mathar, Dec 02 2012

From Emanuele Munarini, Dec 16 2017: (Start)

The generating series A(x) = -exp(x)*log(1-x) satisfies the differential equations:

(1-x)*A'(x) - (1-x)*A(x) = exp(x)

(1-x)*A''(x) - (3-2*x)*A'(x) + (2-x)*A(x) = 0.

From the first one, we have the recurrence reported below by R. R. Forberg. From the second one, we have the recurrence conjectured above. (End)

G.f.: conjecture: T(0)*x/(1-2*x)/(1-x), where T(k) = 1 - x^2*(k+1)^2/(x^2*(k+1)^2 - (1 - 2*x*(k+1))*(1 - 2*x*(k+2))/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2013

a(n) ~ exp(1)*(n-1)!. - Vaclav Kotesovec, Mar 10 2014

a(n) = n*a(n-1) - (n-1)*a(n-2) + 1, a(0) = 0, a(1) = 1. - Richard R. Forberg, Dec 15 2014

a(n) = A007526(n) + A006231(n+1) - A030297(n). - Anton Zakharov, Sep 05 2016

0 = +a(n)*(+a(n+1) -4*a(n+2) +4*a(n+3) -a(n+4)) +a(n+1)*(+2*a(n+2) -5*a(n+3) +2*a(n+4)) +a(n+2)*(+2*a(n+2) -a(n+3) -a(n+4)) +a(n+3)*(+a(n+3)) for all n>=0. - Michael Somos, May 08 2019

From Peter Bala, Sep 12 2022: (Start)

For n, m >= 0, a(n) - a(n + m) == ( a(1) - a(m) ) (mod m). The sequence {mod(a(1) - a(m+1), m): m >= 1} begins [0, 1, 1, 0, 1, 5, 1, 0, 3, 7, 1, 4, 1, 9, 8, 0, 1, 15, 1, 4, ...].

Conjectures:

1) for n, m >= 0, k >= 2, a(n + m*2^k) - a(n) is divisible by 2^k.

2) for n >= 0, a(n + m*p^k) - a(n) + m*p^(k-1) is divisible by p^k for all positive integers m and k, and for all odd primes p. The particular case n = m = k = 1 is stated in the Comments section by Adamchuk. (End)

a(n) = Integral_{t=0..oo} ((t + 1)^n - 1)/(t*e^t) dt. - Velin Yanev, Apr 13 2024

a(n) = Gamma(n)*(e - ((-1)^n)*Gamma(1 - n, -1)) + hypergeom([1, 1], [2, n + 2], 1)/(n + 1) - polygamma(n) - 1/n + i*Pi for n > 0, where polygamma is the digamma function and the bivariate gamma function is the upper incomplete gamma function. - Velin Yanev, Apr 13 2024

Example

From Reinhard Zumkeller, Oct 26 2010: (Start)
a(3) = #{[1], [1,2], [1,2,3], [1,3], [1,3,2], [2], [2,3], [3]} = 8;
a(4) = #{[1], [1,2], [1,2,3], [1,2,3,4], [1,2,4], [1,2,4,3], [1,3], [1,3,2], [1,3,2,4], [1,3,4], [1,3,4,2], [1,4], [1,4,2], [1,4,2,3], [1,4,3], [1,4,3,2], [2], [2,3], [2,3,4], [2,4], [2,4,3], [3], [3,4], [4]} = 24. (End)
G.f. = x + 3*x^2 + 8*x^3 + 24*x^4 + 89*x^5 + 415*x^6 + 2372*x^7 + ...

Maple

a := proc(n) option remember; ifelse(n < 2, n, n*a(n-1) - (n-1)*a(n-2) + 1) end:
seq(a(n), n = 0..23); # Peter Luschny, Dec 05 2023

Mathematica

Table[Sum[Sum[m!/k!, {k, 0, m}], {m, 0, n-1}], {n, 1, 30}] (* Alexander Adamchuk, Jul 05 2006 *)
a[n_] = n*(HypergeometricPFQ[{1, 1, 1-n}, {2}, -1]); Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Mar 29 2011 *)

Prog

(Haskell)
import Data.List (subsequences, permutations)
a002104 = length . filter (\xs -> head xs == minimum xs) .
                   tail . choices . enumFromTo 1
   where choices = concat . map permutations . subsequences
-- Reinhard Zumkeller, Feb 21 2012, Oct 25 2010
(PARI) x='x+O('x^99); concat([0], Vec(serlaplace(-log(1-x)*exp(x)))) \\ Altug Alkan, Dec 17 2017
(PARI) {a(n) = sum(k=0, n-1, binomial(n, k) * (n-k-1)!)}; /* Michael Somos, May 08 2019 */

Crossrefs

Cf. A001338, A006231, A007526, A030297, A133942.

Sequence in context: A134165 A071016 A174662 * A102919 A363212 A102476

Adjacent sequences: A002101 A002102 A002103 * A002105 A002106 A002107

Keyword

nonn,easy,nice,changed

Author

N. J. A. Sloane

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001

Status

approved