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

Home > Numbers
Generalize (Posted on 2013-05-01) Difficulty: 3 of 5
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.)
Some Thoughts 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information