What integers cannot be expressed in the form
N=31p+23q, where p & q are non-negative integers ?
1 can be made with p=3 and q=-4
To make a number involving negative q we can add as many zeros as necessary, where
0 = -23*31+31*23; i.e., p=-23 and q=31.
To produce any number, multiply 3 by that number to get p and -4 times the number to get q. Then add as many of the p and q values for zero as necessary to make q non-negative. But if p becomes negative when the least number of such additions has taken place, it's an impossible number to form under the given rules.
Here are the impossible numbers:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 24 25 26 27 28 29 30 32
33 34 35 36 37 38 39 40 41 42
43 44 45 47 48 49 50 51 52 53
55 56 57 58 59 60 61 63 64 65
66 67 68 70 71 72 73 74 75 76
78 79 80 81 82 83 84 86 87 88
89 90 91 94 95 96 97 98 99 101
102 103 104 105 106 107 109 110 111 112
113 114 117 118 119 120 121 122 125 126
127 128 129 130 132 133 134 135 136 137
140 141 142 143 144 145 148 149 150 151
152 153 156 157 158 159 160 163 164 165
166 167 168 171 172 173 174 175 176 179
180 181 182 183 187 188 189 190 191 194
195 196 197 198 199 202 203 204 205 206
210 211 212 213 214 218 219 220 221 222
225 226 227 228 229 233 234 235 236 237
241 242 243 244 245 249 250 251 252 256
257 258 259 260 264 265 266 267 268 272
273 274 275 280 281 282 283 287 288 289
290 291 295 296 297 298 303 304 305 306
311 312 313 314 318 319 320 321 326 327
328 329 334 335 336 337 342 343 344 349
350 351 352 357 358 359 360 365 366 367
373 374 375 380 381 382 383 388 389 390
396 397 398 404 405 406 411 412 413 419
420 421 427 428 429 435 436 442 443 444
450 451 452 458 459 466 467 473 474 475
481 482 489 490 497 498 504 505 512 513
520 521 528 535 536 543 544 551 559 566
567 574 582 590 597 605 613 628 636 659
There are 330 of them.
Rather than do this by hand, the program below produced it:
clearvars,clc
ct=0;
one = [3 -4];
zero= [-23 31];
for i=1:5000
way=i*one;
numzeros=ceil(way(2)/-zero(2));
way=way+numzeros*zero;
if way(1)<0
fprintf(' %d',i)
ct=ct+1;
if mod(ct,10)==0
fprintf('\n')
end
end
end
Before that, the following program gave us the p and q values that gave us 1 and zero:
clearvars,clc
a=31; makeA=[1 0];
b=23; makeB=[0 1];
aset=makeA;
bset=makeB;
r=9999;
while r>0
q=floor(a/b);
r=a-q*b;
c=r;
makeC=makeA-q*makeB;
a=b; makeA=makeB;
b=c; makeB=makeC;
disp([c makeC])
end
producing
desired
result p q
8 1 -1
7 -2 3
1 3 -4
0 -23 31
|
|
Posted by Charlie
on 2023-05-02 14:46:36 |
computer solution