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

 Generalize (Posted on 2013-05-01)
Using only 4\$ and 7\$ bills, you could pay any integer number of dollars, greater than 17.
Prove it.

Given two coprime numbers a and b, what is the minimal number M(a,b) such that any amount greater or equal to M(a,b) can be expressed as p*a+q*b (p & q non-negative integers)?

How much is M(37,38)?

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 part 1 solution, plus examples of M(x,y) | Comment 1 of 5

1 = 2*4 - 1*7

For other ways of getting 1, we have to add or subtract as many times 7 4's as we subtract or add 4 7's respectively, since 7*4 = 4*7 and they cancel out if done with opposite sign. But if we add 4 7's, making +3 in all, we have to subtract 7 4's, making -5 in all, and we never get to non-negative for both.

For 17, it's 17 times the above, or 34 4's minus 17 7's. To make the number of 7's non-negative we need 5*4 added to the -17, making 3; but then the 5*7 we need to subtract from the number of 4's makes that count -1.

But from 18 onward there'll be sufficient leeway to get a non-negative answer.

It's best illustrated in the logic of the following program:

CLS
OPEN "generalize.txt" FOR OUTPUT AS #2
DEFDBL A-Z
FOR tot = 5 TO 80
FOR x = 2 TO tot / 2
y = tot - x
a = x: b = y
coa1 = 1: cob1 = 0
coa2 = 0: cob2 = 1

'PRINT a, coa1, cob1
'PRINT b, coa2, cob2

DO
prevr = r
q = a b: r = a MOD b
coa3 = coa1 - q * coa2: cob3 = cob1 - q * cob2
'PRINT r, coa3, cob3
coa1 = coa2: coa2 = coa3
cob1 = cob2: cob2 = cob3
a = b: b = r
LOOP UNTIL r = 0
IF prevr = 1 THEN
PRINT x; y,
PRINT #2, x; y,
FOR try = 1 TO 30 * tot
cx = try * coa1: cy = try * cob1
'PRINT , cx, cy
WHILE cx * cy < 0 AND cx * coa1 >= 0
cx = cx + coa2: cy = cy + cob2
WEND
IF cx < 0 OR cy < 0 THEN highest = try
NEXT
PRINT highest + 1
PRINT #2, highest + 1
END IF
NEXT x
NEXT tot
close 2

where the Euclidean algorithm finds the GCD and the coefficients needed to get there as well as the coefficients needed to balance out to zero. It attempts to form numbers much higher than is possible and keeps track of the highest non-formable number, and adds 1.

The results are shown below, but I can't see a general formula.

Here are specific answers, including M(4,7)=18 and M(37,38)=1332.

``` x  y         M(x,y) 2  3          2  2  5          4  3  4          6  3  5          8  2  7          6  4  5          12  3  7          12  2  9          8  3  8          14  4  7          18  5  6          20  5  7          24  2  11         10  3  10         18  4  9          24  5  8          28  6  7          30  3  11         20  5  9          32  2  13         12  4  11         30  7  8          42  3  13         24  5  11         40  7  9          48  2  15         14  3  14         26  4  13         36  5  12         44  6  11         50  7  10         54  8  9          56  5  13         48  7  11         60  2  17         16  3  16         30  4  15         42  5  14         52  6  13         60  7  12         66  8  11         70  9  10         72  3  17         32  7  13         72  9  11         80  2  19         18  4  17         48  5  16         60  8  13         84  10  11        90  3  19         36  5  17         64  7  15         84  9  13         96  2  21         20  3  20         38  4  19         54  5  18         68  6  17         80  7  16         90  8  15         98  9  14         104  10  13        108  11  12        110  5  19         72  7  17         96  11  13        120  2  23         22  3  22         42  4  21         60  6  19         90  7  18         102  8  17         112  9  16         120  11  14        130  12  13        132  3  23         44  5  21         80  7  19         108  9  17         128  11  15        140  2  25         24  4  23         66  5  22         84  7  20         114  8  19         126  10  17        144  11  16        150  13  14        156  3  25         48  5  23         88  9  19         144  11  17        160  13  15        168  2  27         26  3  26         50  4  25         72  5  24         92  6  23         110  7  22         126  8  21         140  9  20         152  10  19        162  11  18        170  12  17        176  13  16        180  14  15        182  7  23         132  11  19        180  13  17        192  2  29         28  3  28         54  4  27         78  5  26         100  6  25         120  7  24         138  8  23         154  9  22         168  10  21        180  11  20        190  12  19        198  13  18        204  14  17        208  15  16        210  3  29         56  5  27         104  7  25         144  9  23         176  11  21        200  13  19        216  15  17        224  2  31         30  4  29         84  5  28         108  7  26         150  8  25         168  10  23        198  13  20        228  14  19        234  16  17        240  3  31         60  5  29         112  7  27         156  9  25         192  11  23        220  13  21        240  15  19        252  2  33         32  3  32         62  4  31         90  6  29         140  8  27         182  9  26         200  11  24        230  12  23        242  13  22        252  16  19        270  17  18        272  5  31         120  7  29         168  11  25        240  13  23        264  17  19        288  2  35         34  3  34         66  4  33         96  5  32         124  6  31         150  7  30         174  8  29         196  9  28         216  10  27        234  11  26        250  12  25        264  13  24        276  14  23        286  15  22        294  16  21        300  17  20        304  18  19        306  3  35         68  5  33         128  7  31         180  9  29         224  11  27        260  13  25        288  15  23        308  17  21        320  2  37         36  4  35         102  5  34         132  7  32         186  8  31         210  10  29        252  11  28        270  14  25        312  16  23        330  17  22        336  19  20        342  3  37         72  7  33         192  9  31         240  11  29        280  13  27        312  17  23        352  19  21        360  2  39         38  3  38         74  4  37         108  5  36         140  6  35         170  7  34         198  8  33         224  9  32         248  10  31        270  11  30        290  12  29        308  13  28        324  14  27        338  15  26        350  16  25        360  17  24        368  18  23        374  19  22        378  20  21        380  5  37         144  11  31        300  13  29        336  17  25        384  19  23        396  2  41         40  3  40         78  4  39         114  5  38         148  6  37         180  7  36         210  8  35         238  9  34         264  10  33        288  11  32        310  12  31        330  13  30        348  14  29        364  15  28        378  16  27        390  17  26        400  18  25        408  19  24        414  20  23        418  21  22        420  3  41         80  5  39         152  7  37         216  9  35         272  13  31        360  15  29        392  17  27        416  19  25        432  21  23        440  2  43         42  4  41         120  7  38         222  8  37         252  11  34        330  13  32        372  14  31        390  16  29        420  17  28        432  19  26        450  22  23        462  3  43         84  5  41         160  7  39         228  9  37         288  11  35        340  13  33        384  15  31        420  17  29        448  19  27        468  21  25        480  2  45         44  3  44         86  4  43         126  5  42         164  6  41         200  7  40         234  8  39         266  9  38         296  10  37        324  11  36        350  12  35        374  13  34        396  14  33        416  15  32        434  16  31        450  17  30        464  18  29        476  19  28        486  20  27        494  21  26        500  22  25        504  23  24        506  5  43         168  7  41         240  11  37        360  13  35        408  17  31        480  19  29        504  23  25        528  2  47         46  3  46         90  4  45         132  5  44         172  6  43         210  8  41         280  9  40         312  10  39        342  11  38        370  12  37        396  13  36        420  15  34        462  16  33        480  17  32        496  18  31        510  19  30        522  20  29        532  22  27        546  23  26        550  24  25        552  3  47         92  7  43         252  9  41         320  11  39        380  13  37        432  17  33        512  19  31        540  21  29        560  23  27        572  2  49         48  4  47         138  5  46         180  7  44         258  8  43         294  10  41        360  11  40        390  13  38        444  14  37        468  16  35        510  19  32        558  20  31        570  22  29        588  23  28        594  25  26        600  3  49         96  5  47         184  7  45         264  9  43         336  11  41        400  15  37        504  17  35        544  19  33        576  21  31        600  23  29        616  25  27        624  2  51         50  3  50         98  4  49         144  5  48         188  6  47         230  7  46         270  8  45         308  9  44         344  10  43        378  11  42        410  12  41        440  13  40        468  14  39        494  15  38        518  16  37        540  17  36        560  18  35        578  19  34        594  20  33        608  21  32        620  22  31        630  23  30        638  24  29        644  25  28        648  26  27        650  5  49         192  7  47         276  11  43        420  13  41        480  17  37        576  19  35        612  23  31        660  25  29        672  2  53         52  3  52         102  4  51         150  6  49         240  7  48         282  8  47         322  9  46         360  12  43        462  13  42        492  14  41        520  16  39        570  17  38        592  18  37        612  19  36        630  21  34        660  23  32        682  24  31        690  26  29        700  27  28        702  3  53         104  5  51         200  9  47         368  11  45        440  13  43        504  15  41        560  17  39        608  19  37        648  23  33        704  25  31        720  27  29        728  2  55         54  4  53         156  5  52         204  7  50         294  8  49         336  10  47        414  11  46        450  13  44        516  14  43        546  16  41        600  17  40        624  20  37        684  22  35        714  23  34        726  25  32        744  26  31        750  28  29        756  3  55         108  5  53         208  7  51         300  9  49         384  11  47        460  13  45        528  15  43        588  17  41        640  19  39        684  21  37        720  23  35        748  25  33        768  27  31        780  2  57         56  3  56         110  4  55         162  5  54         212  6  53         260  7  52         306  8  51         350  9  50         392  10  49        432  11  48        470  12  47        506  13  46        540  14  45        572  15  44        602  16  43        630  17  42        656  18  41        680  19  40        702  20  39        722  21  38        740  22  37        756  23  36        770  24  35        782  25  34        792  26  33        800  27  32        806  28  31        810  29  30        812  7  53         312  11  49        480  13  47        552  17  43        672  19  41        720  23  37        792  29  31        840  2  59         58  3  58         114  4  57         168  5  56         220  6  55         270  7  54         318  8  53         364  9  52         408  10  51        450  11  50        490  12  49        528  13  48        564  14  47        598  15  46        630  16  45        660  17  44        688  18  43        714  19  42        738  20  41        760  21  40        780  22  39        798  23  38        814  24  37        828  25  36        840  26  35        850  27  34        858  28  33        864  29  32        868  30  31        870  3  59         116  5  57         224  7  55         324  9  53         416  11  51        500  13  49        576  15  47        644  17  45        704  19  43        756  21  41        800  23  39        836  25  37        864  27  35        884  29  33        896  2  61         60  4  59         174  5  58         228  8  55         378  10  53        468  11  52        510  13  50        588  16  47        690  17  46        720  19  44        774  20  43        798  22  41        840  23  40        858  25  38        888  26  37        900  29  34        924  31  32        930  3  61         120  5  59         232  7  57         336  9  55         432  11  53        520  13  51        600  15  49        672  17  47        736  19  45        792  21  43        840  23  41        880  25  39        912  27  37        936  29  35        952  31  33        960  2  63         62  3  62         122  4  61         180  6  59         290  7  58         342  8  57         392  9  56         440  11  54        530  12  53        572  14  51        650  16  49        720  17  48        752  18  47        782  19  46        810  21  44        860  22  43        882  23  42        902  24  41        920  27  38        962  28  37        972  29  36        980  31  34        990  32  33        992  5  61         240  7  59         348  13  53        624  17  49        768  19  47        828  23  43        924  25  41        960  29  37        1008  31  35        1020  2  65         64  3  64         126  4  63         186  5  62         244  6  61         300  7  60         354  8  59         406  9  58         456  10  57        504  11  56        550  12  55        594  13  54        636  14  53        676  15  52        714  16  51        750  17  50        784  18  49        816  19  48        846  20  47        874  21  46        900  22  45        924  23  44        946  24  43        966  25  42        984  26  41        1000  27  40        1014  28  39        1026  29  38        1036  30  37        1044  31  36        1050  32  35        1054  33  34        1056  3  65         128  5  63         248  7  61         360  9  59         464  11  57        560  13  55        648  15  53        728  19  49        864  21  47        920  23  45        968  25  43        1008  27  41        1040  29  39        1064  31  37        1080  33  35        1088  2  67         66  4  65         192  5  64         252  7  62         366  8  61         420  10  59        522  11  58        570  13  56        660  14  55        702  16  53        780  17  52        816  19  50        882  20  49        912  22  47        966  25  44        1032  26  43        1050  28  41        1080  29  40        1092  31  38        1110  32  37        1116  34  35        1122  3  67         132  9  61         480  11  59        580  13  57        672  17  53        832  19  51        900  23  47        1012  27  43        1092  29  41        1120  31  39        1140  33  37        1152  2  69         68  3  68         134  4  67         198  5  66         260  6  65         320  7  64         378  8  63         434  9  62         488  10  61        540  11  60        590  12  59        638  13  58        684  14  57        728  15  56        770  16  55        810  17  54        848  18  53        884  19  52        918  20  51        950  21  50        980  22  49        1008  23  48        1034  24  47        1058  25  46        1080  26  45        1100  27  44        1118  28  43        1134  29  42        1148  30  41        1160  31  40        1170  32  39        1178  33  38        1184  34  37        1188  35  36        1190  5  67         264  7  65         384  11  61        600  13  59        696  17  55        864  19  53        936  23  49        1056  25  47        1104  29  43        1176  31  41        1200  35  37        1224  2  71         70  3  70         138  4  69         204  5  68         268  6  67         330  7  66         390  8  65         448  9  64         504  10  63        558  11  62        610  12  61        660  13  60        708  14  59        754  15  58        798  16  57        840  17  56        880  18  55        918  19  54        954  20  53        988  21  52        1020  22  51        1050  23  50        1078  24  49        1104  25  48        1128  26  47        1150  27  46        1170  28  45        1188  29  44        1204  30  43        1218  31  42        1230  32  41        1240  33  40        1248  34  39        1254  35  38        1258  36  37        1260  3  71         140  5  69         272  7  67         396  9  65         512  11  63        620  13  61        720  15  59        812  17  57        896  19  55        972  21  53        1040  23  51        1100  25  49        1152  27  47        1196  29  45        1232  31  43        1260  33  41        1280  35  39        1292  2  73         72  4  71         210  7  68         402  8  67         462  11  64        630  13  62        732  14  61        780  16  59        870  17  58        912  19  56        990  22  53        1092  23  52        1122  26  49        1200  28  47        1242  29  46        1260  31  44        1290  32  43        1302  34  41        1320  37  38        1332  3  73         144  5  71         280  7  69         408  9  67         528  11  65        640  13  63        744  15  61        840  17  59        928  21  55        1080  23  53        1144  25  51        1200  27  49        1248  29  47        1288  31  45        1320  33  43        1344  35  41        1360  37  39        1368  2  75         74  3  74         146  4  73         216  5  72         284  6  71         350  8  69         476  9  68         536  10  67        594  12  65        704  13  64        756  15  62        854  16  61        900  17  60        944  18  59        986  19  58        1026  20  57        1064  23  54        1166  24  53        1196  25  52        1224  26  51        1250  27  50        1274  29  48        1316  30  47        1334  31  46        1350  32  45        1364  34  43        1386  36  41        1400  37  40        1404  38  39        1406  5  73         288  7  71         420  11  67        660  17  61        960  19  59        1044  23  55        1188  25  53        1248  29  49        1344  31  47        1380  35  43        1428  37  41        1440  2  77         76  3  76         150  4  75         222  5  74         292  6  73         360  7  72         426  8  71         490  9  70         552  10  69        612  11  68        670  12  67        726  13  66        780  14  65        832  15  64        882  16  63        930  17  62        976  18  61        1020  19  60        1062  20  59        1102  21  58        1140  22  57        1176  23  56        1210  24  55        1242  25  54        1272  26  53        1300  27  52        1326  28  51        1350  29  50        1372  30  49

Posted by Charlie
on 2013-05-01 18:00:54

```

 Search: Search body:
Forums (1)