My Math Forum Multiple Multiples

 Elementary Math Fractions, Percentages, Word Problems, Equations, Inequations, Factorization, Expansion

 June 4th, 2018, 11:05 AM #1 Newbie   Joined: Feb 2018 From: California Posts: 17 Thanks: 1 Multiple Multiples Hello, Pretend I wanted to buy magic pencils. There's only one store that sells them and they are sold in packages of 6, 9, and 15. What is the most straightforward way to figure out if I can buy X number of magic pencils? For example, if I want to buy 4,238 pencils, would that be possible using only the multiples of 6, 9, and 15? What about 88,904 magic pencils? What's the generic way to go about solving this problem? I am most interested in solving this using only elementary school level math.
 June 4th, 2018, 11:14 AM #2 Senior Member     Joined: Sep 2015 From: USA Posts: 2,320 Thanks: 1232 Problems like this are known as linear diophantine equations and are a well studied branch of number theory. Number theory isn't really my thing but it appears there are well known methods for solving systems of these equations. Elementary school level math it's not, but the individual steps of the algorithm look straightforward enough. I'd start here.
June 4th, 2018, 12:01 PM   #3
Senior Member

Joined: Aug 2012

Posts: 2,157
Thanks: 631

Quote:
 Originally Posted by romsek Number theory isn't really my thing but it appears there are well known methods for solving systems of these equations.
As I understand it there is no general method for solving Diophantine equations.

https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem

June 4th, 2018, 01:28 PM   #4
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,320
Thanks: 1232

Quote:
 Originally Posted by Maschke As I understand it there is no general method for solving Diophantine equations.
I defer to your knowledge. I did one undergrad course in number theory. It was voodoo.

June 4th, 2018, 01:57 PM   #5
Senior Member

Joined: Feb 2010

Posts: 702
Thanks: 137

Quote:
 Originally Posted by mjsilverfly Hello, Pretend I wanted to buy magic pencils. There's only one store that sells them and they are sold in packages of 6, 9, and 15. What is the most straightforward way to figure out if I can buy X number of magic pencils? For example, if I want to buy 4,238 pencils, would that be possible using only the multiples of 6, 9, and 15? What about 88,904 magic pencils? What's the generic way to go about solving this problem? I am most interested in solving this using only elementary school level math.
As 6, 9, and 15 are all multiples of 3, the answer in this case is that you can generate any multiple of 3 greater than 6. Since neither 4238 nor 88904 is a multiple of 3, they cannot be done.

I think you may have meant 6, 9, and 20 (not 15). If that is the case then you may want to google "chicken mcnuggets problem". I don't think there is a general procedure to solve these but here is a heuristic that might help. Make a table with six columns:

1 2 3 4 5 [6]
7 8 [9] 10 11 12
13 14 15 16 17 18
19 [20] 21 22 23 24
25 26 27 28 [29] 30
31 32 33 34 35 36
37 38 39 [40] 41 42
43 44 45 46 47 48
[49] 50 51 52 53 54

Every time you find a solution, put it in brackets. As soon as you find a solution in each column, you have a potential solution to the problem. For 6, 9, and 20, I have found solutions 6 = 6+0+0, 9 = 0+9+0, 20 = 0+0+20, 29 = 0+9+20, 40 = 0+0+20+20, and 49 = 0+9+20+20. Any number below a solution is obtainable. So in this case (6,9,20) any number greater than 43 can be purchased.

Last edited by skipjack; June 5th, 2018 at 08:02 PM.

 June 5th, 2018, 03:23 PM #6 Newbie   Joined: Feb 2018 From: California Posts: 17 Thanks: 1 OK, thank you. I like your heuristic, mrtwhs.

 Tags multiple, multiples

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post popoder Algebra 5 March 6th, 2016 06:20 AM walter r Linear Algebra 1 July 29th, 2014 02:15 PM nitin1 Number Theory 11 December 14th, 2012 10:59 AM Tylerman Applied Math 4 January 30th, 2012 02:15 PM Icevox Number Theory 8 March 25th, 2011 02:11 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top