A190940 Number of divisors of LCM(1,2,...,n)/n.

1, 1, 2, 2, 6, 4, 12, 8, 16, 18, 48, 32, 96, 72, 64, 48, 240, 128, 480, 288, 320, 384, 960, 512, 960, 1152, 960, 1152, 3840, 3072, 7680, 3072, 6912, 7680, 6144, 6144, 18432, 15360, 13824, 12288, 36864, 23040, 73728, 49152, 49152, 61440, 147456, 73728, 147456, 122880

Offset: 1

Author

Naohiro Nomoto, May 24 2011

Keywords

• nonn

Comments

Also, number of sequences of d1 = 1 < d2 < ... < dk = n for some k >= 1 that are the first k divisors of some integer (cf. A378314). - Max Alekseyev, Nov 22 2024

Also, the number of distinct values taken by lcm(a,a+b,a+b+c,...,n), where positive integers a,b,c,... run over the compositions a+b+c+...=n. - Conjectured by Ridouane Oudra, Aug 24 2019; proved by Max Alekseyev, Nov 22 2024

Proof. It is clear that n | lcm(a,a+b,...,n) | lcm(1,2,...,n). Hence, lcm(a,a+b,...,n) = d*n for some d | lcm(1,2,...,n)/n. We'll show that each such d is achievable. Suppose d*n has prime factorization p1^e1 * ... * pk^ek with p1^e1 < ... < pk^ek. It is clear that pk^ek <= n, and we can take a composition (a,b,c,...) = (p1^e1, p2^e2 - p1^e1, p3^e3 - p2^e2, ..., pk^ek - p(k-1)^e(k-1), n - pk^ek), which delivers lcm(a,a+b,a+b+c,...,n) = p1^e1 * ... * pk^ek = d*n. QED - Max Alekseyev, Nov 22 2024

Examples

			Examples: for n=3 the a(3) = 2 distinct values are 3, 6. The compositions are 3, 1+2, 2+1, and 1+1+1. The values of the lcm are lcm(3)=3, lcm(1,1+2)=3, lcm(2,2+1)=6, and lcm(1,1+1,1+1+1)=6.
		

Crossrefs

First difference of A378314.

Cf. A000005, A002944, A003418, A056793, A101207.

Programs

Maple

Lpsum := proc(L) local ps,k ; ps := [op(1,L)] ; for i from 2 to nops(L) do ps := [op(ps), op(-1,ps)+op(i,L)] ; end do: ps ; end proc:
A190940 := proc(n) local lc,k,c ; lc := {} ; for k from 1 to n do for c in combinat[composition](n,k) do lc := lc union { ilcm( op(Lpsum(c))) }; end do: end do: nops(lc) ; end proc: # R. J. Mathar, Jun 02 2011

Mathematica

a[n_] := LCM @@@ (Accumulate /@ (Permutations /@ Rest[IntegerPartitions[n]] // Flatten[#, 1]&)) // Union // Length; Table[Print[an = a[n]]; an, {n, 1, 24}] (* Jean-François Alcover, Feb 27 2014 *)

Formula

a(n) = A000005(A002944(n)).

Extensions

a(12)-a(20) from R. J. Mathar, Jun 02 2011

a(21)-a(24) from Alois P. Heinz, Nov 03 2011

Edited and terms a(25) onward added by Max Alekseyev, Nov 22 2024