All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 59 in one way (Posted on 2011-08-13)
A and B are two positive integers such that:

1. The number 59 can be made by adding non-negative integral multiples of A and B in exactly one way.

2. Some numbers below 59 cannot be produced in this way at all, while some can be produced in one way and others in more than one way as sums of non-negative integral multiples of A and B.

3. All numbers above 59 can be produced in more than one way as sums of non-negative integral multiples of A and B.

What two numbers can A and B be?

 Submitted by Charlie Rating: 4.0000 (2 votes) Solution: (Hide) 4 and 9 in either order. 1 2 3 5 6 7 10 11 14 15 19 23 cannot be produced at all. 4 8 9 12 13 16 17 18 20 21 22 24 25 26 27 28 29 30 31 32 33 34 35 37 38 39 41 42 43 46 47 50 51 55 59 can be produced in exactly one way each. For example 2*9 + 1*4 = 22, 9*9 + 5*4 = 20, and 3*9 + 8*4 = 59. 36 40 44 45 48 49 52 53 54 56 57 58 can all be produced in two ways each. For example, 45 = 1*9 + 9*4 or 5*9 + 0 * 4, 57 = 1*9 + 12*4 or 5*9 + 3*4. As seen, alternative ways are found by offsetting 4 9's with 9 4's, so long as this doesn't lead to a negative number of either. All numbers above 59 can be achieved in at least two different ways. The following program determined the values of 9 and 4: ```DEFDBL A-Z CLS FOR a = 2 TO 59 FOR b = 2 TO 59 IF a <> b THEN dnd = a: coefa1 = 1: coefb1 = 0 dvr = b: coefa0 = 0: coefb0 = 1 DO quot = INT(dnd / dvr) rmnd = dnd - quot * dvr coefar = coefa1 - quot * coefa0 coefbr = coefb1 - quot * coefb0 dnd = dvr: dvr = rmnd coefa1 = coefa0: coefa0 = coefar coefb1 = coefb0: coefb0 = coefbr LOOP UNTIL dvr = 0 gcd = dnd IF gcd = 1 THEN had0 = 0: had1 = 0: had2 = 0: had59 = 0 FOR goal = 1 TO 100 coefa = goal * coefa1 coefb = goal * coefb1 IF coefa < 0 THEN neg\$ = "a": ELSE neg\$ = "b" DO coefa = coefa + coefa0 coefb = coefb + coefb0 LOOP UNTIL neg\$ = "a" AND coefa >= 0 OR neg\$ = "b" AND coefb >= 0 ct = 0 WHILE coefb >= 0 AND coefa >= 0 ct = ct + 1 coefa = coefa + coefa0 coefb = coefb + coefb0 WEND IF ct = 0 THEN had0 = 1 IF ct = 1 AND goal < 59 THEN had1 = 1 IF ct > 1 THEN had2 = 1 IF ct = 1 AND goal = 59 AND had0 = 1 AND had1 = 1 AND had2 = 1 THEN had59 = 1 saveca = coefa - coefa0: savecb = coefb - coefb0 END IF IF goal > 59 AND ct < 2 THEN had59 = 0 NEXT goal IF had59 = 1 THEN PRINT a; b, saveca; savecb, coefa0; coefb0 sct = sct + 1: IF sct MOD 40 = 0 THEN DO: LOOP UNTIL INKEY\$ > "": PRINT END IF END IF END IF NEXT NEXT ```

 Subject Author Date re(2): Solution Jer 2011-08-21 20:22:13 re: Solution Ady TZIDON 2011-08-21 11:59:38 Solution Jer 2011-08-21 01:28:14 Possible solution broll 2011-08-19 22:47:00 re(2): possible solution Charlie 2011-08-14 00:14:15 re: possible solution Charlie 2011-08-13 17:29:51 possible solution Ady TZIDON 2011-08-13 13:07:26

 Search: Search body:
Forums (0)