Testwiki:Reference desk/Archives/Mathematics/2025 January 15

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < January 14 ! width="25%" align="center"|<< Dec | January | Feb >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 15

Least common multiple

What do you call a subset of the factors of x where all 3 are true?

1. LCM(subset)=x
2. no member >√x
3. can't be done with less members

(obviously only some x would have even 1 subset passing all 3)

Is there also a name for a version where no member ≥√x or a version with tiebreaks (maybe smallest largest member then smallest 2nd largest member and so on?) or a version with both extra strictures? Sagittarian Milky Way (talk) 22:56, 15 January 2025 (UTC)

It seems unlikely that anyone has before come up with this specific set of conditions, let alone coined a term for it.  --Lambiam 22:24, 16 January 2025 (UTC)

I was looking at factor lists of numbers with many factors & thinking most of these are superfluous to define a least common multiple & wondering how many you could remove without the LCM becoming less than the number (obviously there are other applications where you need all factors) but if you don't set a max size it's too easy you could always get it down to 2 with lcm(1,x) sometimes also others like lcm(prime, bigger prime) or lcm(2,x/2 if odd) so if you must use factors ≤√x it'll at least be over 2 members so more interesting. Sagittarian Milky Way (talk) 16:32, 17 January 2025 (UTC)

Consider a set $S$ of numbers whose lcm equals a given number $n$. Let $a$ and $b$ be two different elements of that set that are not coprime. This means that they have nontrivial factors $p^{\alpha }$ and $p^{\beta }$ in which $p$ is a prime number and $\alpha$ and $\beta$ are at least $1.$ Assume wlog that $\alpha \le \beta .$ Then the lcm of set $S^{\prime }$ oobtained by replacing $a$ by $a^{\prime }=a/p^{\alpha }$ is the same as that of $S.$ This means that we can keep things simpler by only considering sets with pairwise coprime elements. Then the lcm function can be replaced by the product operator $\prod ,$ where $\prod \{a_1,a_2,...a_k\}=a_1{a}_2\cdots a_k.$

Given the factorization $n=p_1^{m_1}{p}_2^{m_2}...p_k^{m_k},$ one possible choice for $S$ is the set $F=\{p_1^{m_1},p_2^{m_2},...,p_k^{m_k}\}.$ Given a partition $𝒫$ of $F,$ define ${\prod }^{\ast }(𝒫)$ by

${\prod }^{\ast }(𝒫)=\{\prod X|X\in 𝒫\}.$

Then $\prod ({\prod }^{\ast }(𝒫))=n,$ so for each partition $𝒫,$ the set ${\prod }^{\ast }(𝒫)$ is also a candidate for $S.$ Conversely, each set $S$ of mutually coprime numbers such that $\prod S=n$ can be written as ${\prod }^{\ast }(𝒫)$ for some partition $𝒫$ of $F.$ The original $F$ itself equals ${\prod }^{\ast }(\{\{p_1^{m_1}\},\{p_2^{m_2}\},...,\{p_k^{m_k}\}\}).$

Instead of partitioning $F$ and then applying ${\prod }^{\ast }(\cdot )$ to the partition, we can obtain the same candidates for $S$ by starting with $S_0=F$ and obtaining $S_{n+1}$ from $S_n$ — provided that $S_n$ is not a singleton set — by choosing two elements from $S_n$ and replacing these two by a single element, namely their product. If we wish to keep the values low, a reasonable greedy heuristic is to pick each time the smallest two elements.

Applying this to Plato's favourite number, we get:

$5040=2^4{3}^2{5}^1{7}^1,$ so $S_0=\{2^4,3^2,5^1,7^1\}=\{16,9,5,7\}.$

$S_0=\{5,7,9,16\}$; the smallest two elements are $5$ and $7,$ so $S_1=\{5\times 7,9,16\}=\{35,9,16\}.$

$S_1=\{9,16,35\}$; the smallest two elements are $9$ and $16,$ so $S_2=\{9\times 16,35\}=\{144,35\}.$

$S_2=\{35,144\}$; the smallest two elements are $35$ and $144,$ so $S_3=\{35\times 144\}=\{5040\}.$

If the largest element must not exceed the square root of $n,$ the set $S$ has to contain at least three elements, so with $k$ being the number of distinct prime factors, there is no point in going farther than $S_{k-3}.$  --Lambiam 23:11, 17 January 2025 (UTC)