A126959 - OEIS

%I #31 Jan 06 2015 03:56:53

%S 1,3,12,58,352,2376,19296,168912,1670976,18000000,219916800,

%T 2781561600,39605760000,584889984000,9253091635200,154909552896000,

%U 2834240274432000,52918877491200000,1074184895250432000

%N a(k) = k! * lim_{n->oo} card({ i*j; i=1..k, j=1..n })/n.

%C a(k) = k! card { i*j, i<=k, j<=k# } / k# where k# = lcm(1,2,3...,k) a(k)/(k+1)! <= 1/2 for all k.

%D A. A. Buchstab, "Asymptotic estimates of a general number-theoretic function", Mat. Sbornik 44 (1937), 1239-1246.

%H M. F. Hasler, <a href="/A126959/b126959.txt">Table of n, a(n) for n = 1..36</a>

%H N. G. de Bruijn, <a href="http://www.dwc.knaw.nl/DL/publications/PU00018826.pdf">On the number of uncancelled elements in the sieve of Eratosthenes</a>, Proc. Neder. Akad. Wetensch, 1950.

%H <a href="http://www.mersenneforum.org/showthread.php?p=101523">"Counting Integers and their Multiplicities" on mersenneforum.org</a>

%e a(2)=3/2 since #{ i*j, i=1..2, j=1..2 } / 2 = #{ 1,2, 2,4 } / 2 = #{1,2,4} / 2.

%e a(3)=2 since #{ i*j, i=1..3, j=1..6 } / 6 = #{ 1,2,3,4,5,6, 2,4,6,8,10,12, 3,6,9,12,15,18 } / 6 = #{ 1,2,3,4,5,6,8,9,10,12,15,18 } / 6.

%p p:=proc(n) option remember;local s,t,i,j: s:=1; t:={}:

%p for i from n-1 by -1 to 1+n/(min@op@eval@numtheory[factorset])(n) do

%p t := t union { ilcm(n,i)/n };

%p t := select( x-> numtheory[divisors](x) intersect t = { x }, t ):

%p for j in combinat[powerset](t) do s := s+(-1)^nops(j)/ilcm(op(j)) od:

%p od; s/n end:

%p A126959 := k -> k!*add( p(n), n=1..k);

%o (PARI) p(n)={ local( cnt=lcm(vector(n-1,j,j)), L=vector(cnt,j,n*j), s=cnt ); forstep( i=n-1, n/factor(n)[1,1]+1, -1, forstep( j=lcm(n,i)/n, #L, lcm(n,i)/n, if( L[j] && (L[j] % i == 0), L[j]=0; cnt--)); s+=cnt ); s/#L/n } a=vector(16); a[1]=1; for( k=2, #a, a[k]=k*a[k-1]+k!*p(k));

%Y Cf. A101459, A027424.

%K nonn

%O 1,2

%A _M. F. Hasler_, Mar 19 2007, Mar 22 2007