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

Home > Numbers
59 in one way (Posted on 2011-08-13) Difficulty: 3 of 5
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

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re(2): SolutionJer2011-08-21 20:22:13
Some Thoughtsre: SolutionAdy TZIDON2011-08-21 11:59:38
SolutionSolutionJer2011-08-21 01:28:14
Possible solutionbroll2011-08-19 22:47:00
re(2): possible solutionCharlie2011-08-14 00:14:15
re: possible solutionCharlie2011-08-13 17:29:51
Solutionpossible solutionAdy TZIDON2011-08-13 13:07:26
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 (5)
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