Register to reply

Creating a number using a combination of two numbers

by musicgold
Tags: combination, creating, number, numbers
Share this thread:
musicgold
#1
Apr25-12, 01:52 PM
P: 180
Hi,

My question is related to the following puzzle.

“What is the highest number that can’t be created by adding any number of 4s and 9s”?
For example, 25 can be created as follows: 9 + 4 + 4 + 4 + 4 =25

I know that the answer is 23. I also know that the general solution to such a problem, using the numbers X and Y is (X*Y) – X – Y, when X and Y don’t have a GCF. If they have a GCF then, any number that is not divisible by the CGF can not be made using X and Y.

I have two questions.

Q1. How can I derive this formula from scratch : (X*Y) – X – Y ?

Q2. If I am given a number 12345 to figure if it can be created using X and Y, what is the quickest way to do that?


Thanks.
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
HallsofIvy
#2
Apr25-12, 06:59 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,533
(X*Y)- X- Y is NOT a formula. A formula would be saying that is equal to something.

What you mean by "created using X and Y"?

Do you mean "find the largest number, N, that cannot be written in the form "XY- X- Y= N"?
Mute
#3
Apr25-12, 08:00 PM
HW Helper
P: 1,391
Quote Quote by HallsofIvy View Post
(X*Y)- X- Y is NOT a formula. A formula would be saying that is equal to something.

What you mean by "created using X and Y"?

Do you mean "find the largest number, N, that cannot be written in the form "XY- X- Y= N"?
I believe the question statement is actually, "What is the largest number, N, that cannot be made out of additions of any number of X's and Y's?", and the OP states that the answer is given by N = XY - X - Y, when X and Y have no GCF.

The OP's first question is then, how does one derive that N = XY-X-Y?

The second question is, "Given a number M and numbers X and Y, how can one figure out how to write M = aX + bY, with a and b integers, assuming a solution exists?"

Is that interpretation correct, musicgold?

Mensanator
#4
Apr26-12, 12:07 AM
P: 105
Creating a number using a combination of two numbers

To solve for 12345, re-arrange your formula to

(AX-M)/Y=-B

In this form, iy's a Linear Congruence, so you can use the Modular Inverse
of X&Y to find A as follows:

A = invert(X,Y)*M (mod Y) = 1*12345%4 = 1

then solve fo B: (1*9-12345)/4=-B
-3084 = -B
B = 3084


Be careful, though. You CAN actually solve f0r 23, but you get A=3,B=-1.
musicgold
#5
Apr26-12, 03:56 PM
P: 180
Quote Quote by Mute View Post

The OP's first question is then, how does one derive that N = XY-X-Y?

The second question is, "Given a number M and numbers X and Y, how can one figure out how to write M = aX + bY, with a and b integers, assuming a solution exists?"

Is that interpretation correct, musicgold?
That is correct. Thanks.
Mensanator
#6
Apr26-12, 06:49 PM
P: 105
Oh, I forgot to mentio: if you don't like A=1, pick another.
In a linear congruence, if A is a solution, so is A+Y,
or A+nY, for that matter. So we can chose any A, as
long as it's a multiple of four plus one.

For instance, we can pick A=1001 and recalculate B
(B=834), giving us: 1001*9 +834*4=12345.


Register to reply

Related Discussions
Quantum numbers of atoms in a given state (number^number)letter Advanced Physics Homework 1
Help creating graphs, number lines, etc and formatting them into a larger document General Math 1
Is there a formula to find a combination of numbers... General Math 2
Every number we know makes up exactly 0% of numbers General Math 28
Creating periodic table w/ quantum numbers Biology, Chemistry & Other Homework 0