finding the biggest number needed that multiples to the numbers in a set

Aug 2016
5
0
Washington
I am trying to figure out a way to find the biggest "small" number that I need to multiple within a set of numbers... For example using the numbers 1-10 as the set
Small number (SN) Largest number (LN)

SN times LN
01 10
02 05
03 03
01 09
02 04
01 08
01 07
02 03
01 06
01 05
02 02
01 04
01 03
01 02
01 01

these are all the number sets that multiple to all the numbers in the set 1-10 now I do believe that 3 is the biggest number I need to multiple...

I am trying to find the number that is smallest to put in the left column to multiple within the set:
5x2 is 2+2+2+2+2=10
but
2x5 is 5+5=10
there is only one addition set to do which means it is the shortest expression of 5x2

So the longest addition set would involve 3 in this case 3x3 (3+3+3=9)
and sure this table works but doing it for 1-300 ( or any other "huge" number) would be a pain so I am wondering how to find it the fastest way...


I really hope this makes sense
 
Last edited:

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
Hey AdamFulton.

Just for clarity can you write the formula in terms of the variables that you are trying to solve for? Like say max(x+y) or some other functional relation.

It would make your post a lot clearer and easier to help with.
 

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
Looks to me like you need to look at the prime factorization of each number in your 'target' set.
If you want to get all the numbers in 1 to 10, then write them as 1, 2, 3, 2(2), 5, (2)(3), 7, 2(2)(2), 3(3), 2(5).
We need {1, 2, 3, 5, 7}. Those are, simply, the set of prime numbers less than 10.
 
Aug 2016
5
0
Washington
okay, I am sorry I am not even close to a math major or well anything like the such so I can try to explain what I am going for here it will be long probably but here it is: (also completely 100% ignore my fist post please)

okay I am doing multiplication by doing the problem long hand so to explain: 50 times 2 is 100 so that would be long handed 50 + 50 = 100 or 2 times 50 would be two added over and over 50 times so I would place in the chart 50 times 2 so the smaller of the two are on the right side... So explaining long winded with the set 1-10:

to get 10 I would need
10 times 1 or 10+0=10 so I only need to add one time
but
1 times 10 (1+1+1+1+1+1+1+1+1+1=10) or ten addition problems
or
5 times 2 (5+5=10)
but
2 times 5 (2+2+2+2+2=10)
so the least amount of addition sets needed to get the product of 10 times 1 is two step with 5 times 2

to get 9 is
9 times 1 (9+0=9)
or
1 times 9 (1+1+1+1+1+1+1+1+1=9)
or
3 times 3 (3+3+3=9)
so the shortest way in terms of addition steps would to do 3 times 3 with three steps

To get 8 is:
8 times 1 (8+0=8)
or
1 times 8 (1+1+1+1+1+1+1+1=8)
or
4 times 2 (4+4=8)
or
2 times 4 (2+2+2+2=8)
so the shortest way to get to 8 is to do 4 times 2 with two step

so far you only need to do three addition steps as the most to get any number so far

to get 7
7 times 1 (7+0=7)
or
1 times 7 (1+1+1+1+1+1+1=7)
so here the least steps is one (7 times 1)

to get 6
6 times 1 (6+0=6)
or
1 times 6 (1+1+1+1+1+1=6)
or
2 times 3 (2+2+2=6
or
3 times 2 (3+3=6)
so again the lowest number needed to get to 6 is 3 times 2 with two step

to get to 5
5 times 1 (5+0=5)
1 times 5 (1+1+1+1+1=5)
so again the least amount of steps would be 5 times 1 with one step

to get 4
4 times 1 (4+0=4)
or
1 times 4 (1+1+1+1=4)
or
2 times 2 (2+2=4)
the least amount so steps needed is 2 times 2 with one step

to get 3
3 times 1 (3+0=3)
1 times 3 (1+1+1=3)
so the shortest way to 3 is 3 times 1

to get 2
2 times 1 (2+0=2)
1 times 2 (1+1=2)
the shortest way to 2 is 2 times 1

to get to 1
1 times 1 (1+0=1)
so the shortest and in this case only is 1 times 1

So by placing all the smallest numbers on the right side and the largest on the left then:

10 01 = 10
05 02 = 10
03 03 = 09
09 01 = 09
04 02 = 08
08 01 = 08
07 01 = 07
03 02 = 06
06 01 = 06
05 01 = 05
02 02 = 04
04 01 = 04
03 01 = 03
02 01 = 02
01 01 = 01

By placing the smallest number on the right then the least amount of addition steps will be done example: 3 times 2 is (3+3=6) is the shortest way to the answer where as 2 times 3 is (2+2+2=6) that is three steps but by flipping the numbers only two addition problems are required...

I am writing a program that will do multiplication through addition so it will be faster if it can first find the smallest number of the two in this case 2 times 3 but say if 3 times 2 comes in the program will flip them so that way 3 times 2 is multiplied...

I need to know the largest number on the right side so I know the most steps that will be done within the set 1-10 (which I have concluded to be 3) however I need to do this for 1-255 and doing a chart would be a pain and take forever so this is my question:

Is there a way to find all the factors that equal to all the products within a set (like with 1-10 example) so that way I can know the biggest number that will show up on the right side so I know the most steps that will ever be done within any given set of numbers (1-300 or 1-1000 ect...)

so bottom line (in case I rambled or was confusing)

what is the fastest way to get all the factors to all the whole number products within any given set of numbers... Or what is the fastest way to find the biggest number that will appear on the right side of the chart...

If you need more information or more clarification let me know... But to be honest I do not think I can so hopefully that will give you all that you need to know about what I am doing... :D
 
Last edited: