13
$\begingroup$

Given two distinct factorizations of a positive integer with the same number of factors (not necessarily prime or all distinct), must the sums of the respective sets of factors also be distinct? This question arises frequently in puzzles of the KenKen or Killer Sudoku type. I have found no obvious counter examples searching by hand. For the purpose at hand, the numbers being factored may be limited to less than 1000, say.

$\endgroup$
  • $\begingroup$ For example 1*2*2 = 1*4 or 1*1*2*3 = 1*6 $\endgroup$ – shadow Jul 13 '18 at 6:16
  • 5
    $\begingroup$ @shadow (1) If we allow 1's, does that not make the problem trivial? (2) The question asks for the factorizations to have the same number of factors. $\endgroup$ – Therkel Jul 13 '18 at 6:44
  • 6
    $\begingroup$ There is a well known puzzle based exactly on this fact. $\endgroup$ – Federico Poloni Jul 13 '18 at 7:16
  • 3
    $\begingroup$ When restricted to just 2 factors, the sum is indeed unique, as $x + a/x$ is an increasing function for $a > 0, x > \sqrt a$ (which one of the factors has to be). But when 3 or more factors are allowed, this is broken, as dxiv has demonstrated. $\endgroup$ – Paul Sinclair Jul 13 '18 at 16:33
26
$\begingroup$

The sums can match, for example $\,144 = 8 \cdot 6 \cdot 3 = 4 \cdot 4 \cdot 9\,$ with $\,8+6+3=4+4+9\,$.


[ EDIT ]   Also, $144 = 2\cdot8\cdot9 = 3 \cdot 4 \cdot 12$ with $\,2+8+9=3+4+12\,$, so multiple such factorizations may exist for the same number.

Morevover, there exist such with the same sum e.g. $\,1680 = 4 \cdot 20 \cdot 21 = 5 \cdot 12 \cdot 28 = 7 \cdot 8 \cdot 30\,$ with $\,4+20+21=5+12+28=7+8+30\,$.


[ EDIT #2 ]   The $\scriptsize\color{silver}{\text{(quick-and-dirty)}}$ Python code used to lookup the triplets of factors:

n = 2000  # upper bound of range to check
k = 2     # minimum number of matching triples that get listed
m = 2     # change to 1 to allow unit factors
o = 0     # change to 1 to disallow identical factors in a triple

px = [{} for i in range(n)]
for a in range(m, n):
  for b in range(a + o, n // a):
    for c in range(b + o, n // ( a * b)):
       p = a * b * c; s = a + b + c
       px[p][s] = px[p].get(s, []) + [(a, b, c)]

for i in range((o+1)**3, n):
  for j in sorted(px[i].keys()):
    if len(px[i][j]) >= k:
      print(str(i) + "\t+" + str(j) + "\t" + str(px[i][j])[1:-1])

Some more:

  • smallest number that has $3$ sets of $3$ triples each that sum to different values:

$$ \begin{matrix} 5400 &= 5 \cdot 30 \cdot 36 &= 6 \cdot 20 \cdot 45 &= 9 \cdot 12 \cdot 50 &\quad\quad \style{font-family:inherit}{\text{sum}} &= 71\\ &= 5 \cdot 24 \cdot 45 &= 6 \cdot 18 \cdot 50 &= 10 \cdot 10 \cdot 54 & & = 74\\ &= 4 \cdot 30 \cdot 45 &= 5 \cdot 20 \cdot 54 &= 9 \cdot 10 \cdot 60 & &= 79\\ \end{matrix} $$

  • smallest number that has $4$ sets of $4$ triples each that sum to different values:

$$ \small\begin{matrix} 166320 &= 20 \cdot 77 \cdot 108 &= 22 \cdot 63 \cdot 120 &= 24 \cdot 55 \cdot 126 &= 28 \cdot 45 \cdot 132 &\quad \style{font-family:inherit}{\text{sum}} &= 205\\ &= 16 \cdot 99 \cdot 105 &= 18 \cdot 70 \cdot 132 &= 21 \cdot 55 \cdot 144 &= 30 \cdot 36 \cdot 154 & & = 220\\ &= 11 \cdot 105 \cdot 144 &= 14 \cdot 66 \cdot 180 &= 16 \cdot 55 \cdot 189 &= 20 \cdot 42 \cdot 198 & & = 260 \\ &= 5 \cdot 154 \cdot 216 &= 6 \cdot 105 \cdot 264 &= 8 \cdot 70 \cdot 297 &= 21 \cdot 24 \cdot 330 & & = 375 \end{matrix} \\ $$

$\endgroup$
  • $\begingroup$ The sum of digits for those numbers is a multiple of 3. $\endgroup$ – usiro Jul 13 '18 at 22:23
  • $\begingroup$ @usir0 The sum of digits for those numbers is a multiple of 3 That's only because small numbers with many factors are more likely to be multiples of $3$. It's certainly not the case in general, for example $\,560=4 \cdot 10 \cdot 14 = 5 \cdot 7 \cdot 16\,$ where $\,4 + 10 + 14 = 5 + 7 + 16\,$, but the digit sum of $560$ is $11$. $\endgroup$ – dxiv Jul 13 '18 at 22:31
  • $\begingroup$ That is right. I didn't check for more numbers. Thanks. $\endgroup$ – usiro Jul 13 '18 at 22:40
2
$\begingroup$

I thought it might be fun to write a Mathematica code to find instances of same-sum factorizations. Using the following code, you can find integers such that num different sets of len different same-length factorizations of an integer less than max have the same sum. It omits multiples of lower cases on the grounds that those are boring.

The smallest integers with increasingly large sets of different same-sum factorizations are:
72, 432, 3456, 5760, 7200, 12096, 17280, 21600, ...

The smallest integers with pairs of increasingly large sets of different same-sum factorizations are:
144, 720, 2160, 5040, 8640, 10080, 14400, 25920, 30240, ...

The smallest integers with triples of increasingly large sets of different same-sum factorizations are:
144, 1440, 2880, 7200, 8640, 15120, 17280, 30240, 30240, ...

30240 is an interesting case with 6 different same-sum factorization 9-sets, 4 10-sets, an 11-set and a 12-set.

factorizationList[n_Integer?PrimeQ] := {{n}}
factorizationList[n_Integer] := 
  (factorizationList[n] = 
    Union[Append[Join@@
      (#/{L__List}:>Sort/@Flatten[Outer[Join,L,1],1]&/@
        Map[factorizationList,{#,n/#}&/@
           #[[-Ceiling[Length[#]/2];;-2]]&[Divisors[n]],{2}]),{n}]])
Block[{num=2,len=10,max=25000},
  DeleteDuplicates[DeleteCases[
    Table[{n,Select[GatherBy[factorizationList[n],
      {Total[#],Length[#]}&],
      Length[#]>=num&]},
      {n,max}],
  {_, L_ /; Length[L] < num}],IntegerQ[#2[[1]]/#1[[1]]]&]]

Output:

{{21600,{{{2,3,9,20,20},{2,3,10,15,24},{2,3,12,12,25},{2,5,5,18,24},
          {2,5,8,9,30},{2,6,6,10,30},{3,3,8,10,30},{3,4,4,18,25},
          {3,4,5,12,30},{3,5,5,9,32}}}}}
$\endgroup$
  • $\begingroup$ +1 for a different angle. $\endgroup$ – dxiv Jul 13 '18 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.