URM program to compute n^m (n to the power of m)

For n≠0 and m≠0,

1          S(6)

2          S(7)

3          C(1,3)

4          C(1,4)

5          J(2,7,19)

6          J(4,6,14)

7          J(3,5,11)

8          S(1)

9          S(5)

10        J(1,1,7)

11        S(6)

12        Z(5)

13        J(1,1,6)

14        C(1,3)

15        S(7)

16        Z(6)

17        S(6)

18        J(1,1,5)

n m 0 0 0 0 0
n m n n 0 1 1
n+1 m n n 1 1 1
n+2 m n n 2 1 1
n+3 m n n 3 1 1
n+n=2n m n n n 1 1
2n m n n 0 2 1
2n+1 m n n 1 2 1
2n+2 m n n 2 2 1
2n+n=3n m n n n 2 1
3n m n n 0 3 1
n(n)=n2 m n n n n-1 1
n2 m n n 0 n 1
n2 m n2 n 0 1 2
n2+1 m n2 n 1 1 2
n2+2 m n2 n 2 1 2
n2+n2=2n2 m n2 n n2 1 2
2n2 m n2 n 0 2 2
n(n2)=n3 m n2 n n2 n 2
n3 m n2 n 0 n 2
n3 m n3 n 0 1 3
n(nm-1)=nm m nm-1 n nm-1 n m-1
nm m nm n 0 1 m

Example 1.

2 4 0 0 0 0 0
2 4 2 2 0 1 1
3 4 2 2 1 1 1
4 4 2 2 2 1 1
4 4 2 2 0 2 1
4 4 4 2 0 1 2
5 4 4 2 1 1 2
6 4 4 2 2 1 2
7 4 4 2 3 1 2
8 4 4 2 4 1 2
8 4 4 2 0 2 2
8 4 8 2 0 1 3
9 4 8 2 1 1 3
10 4 8 2 2 1 3
11 4 8 2 3 1 3
12 4 8 2 4 1 3
13 4 8 2 5 1 3
14 4 8 2 6 1 3
15 4 8 2 7 1 3
16 4 8 2 8 1 3
16 4 8 2 0 2 3
16 4 16 2 0 1 4

Example 2.

3 3 0 0 0 0 0
3 3 3 3 0 1 1
4 3 3 3 1 1 1
5 3 3 3 2 1 1
6 3 3 3 3 1 1
6 3 3 3 3 2 1
6 3 3 3 0 2 1
7 3 3 3 1 2 1
8 3 3 3 2 2 1
9 3 3 3 3 2 1
9 3 3 3 3 2 1
9 3 3 3 0 3 1
9 3 9 3 0 1 2
10 3 9 3 1 1 2
11 3 9 3 2 1 2
12 3 9 3 3 1 2
13 3 9 3 4 1 2
14 3 9 3 5 1 2
15 3 9 3 6 1 2
16 3 9 3 7 1 2
17 3 9 3 8 1 2
18 3 9 3 0 2 2
19 3 9 3 1 2 2
20 3 9 3 2 2 2
21 3 9 3 3 2 2
22 3 9 3 4 2 2
23 3 9 3 5 2 2
24 3 9 3 6 2 2
25 3 9 3 7 2 2
26 3 9 3 8 2 2
27 3 9 3 9 2 2
27 3 9 3 0 3 2
27 3 27 3 0 1 3

For any positive integers n and m,

1          J(1,3,3)

2          J(2,3,23)

3          J(2,3,22)

4          S(6)

5          S(7)

6          C(1,3)

7          C(1,4)

8          J(2,7,25)

9          J(4,6,17)

10        J(3,5,14)

11        S(1)

12        S(5)

13        J(1,1,10)

14        S(6)

15        Z(5)

16        J(1,1,9)

17        C(1,3)

18        S(7)

19        Z(6)

20        S(6)

21        J(1,1,8)

22        J(1,1,22)

23        Z(1)

24        S(1)

Note: if n=m=0, the answer is undetermined and the program never stops.

URM program to compute 9 with less than 9 instructions

1          C(1,3)

2          S(1)

3          S(1)

4          S(1)

5          S(3)

6          J(3,4,1)

7          S(2,3,9)

8          S(1,1,2)

0 0 0 0
3 1 0 0
3 1 3 0
6 2 3 0
9 3 3 0

SGU – Episode #410 – Who’s That Noisy?

Question
A bank teller made a mistake today. The teller switched the dollars and cents when they cashed a check for Mrs. Jones, giving her dollars instead of cents and cents instead of dollars.

After buying a newspaper for 5 cents,  Mrs. Jones realized that she had remaining exactly twice as much as the original check.

What was the amount of the original check?

Answer

Let original check be x dollars and y cents. So the money given is y dollars and x cents. Therefore:

100y + x – 5 = 2(100x + y)

So,

199x – 98y = -5

We require integer values of x and y that solve this equation (a Diophantine equation). Following the algorithm to solve a Diophantine equation:

199=2*98+3

98=32*3+2

3=1*2+1

2=2*1

1=3-1*2=3-1(98-32*3)=33*3-1*98=33(199-2*98)-1*98=33*199-66*98-1*98=33*199-67*98

(* denotes multiplication).

So, a=33 and b=67 solves the equation 199a-98b = 1. Multiplying both sides by -5, we get:

199(-5a)-98(-5b) = -5.

Hence, x = -5×33 = -165 and y = -5×67 = -335, solves the equation 199x – 98y = -5. However, these are not the only solutions. The general solution is given by:

x = -165+98n and y = -335+199n, where n is an integer.

Check:

199(-165+98n)-98(-335+199n) = -199*165+199x98n+98×335-98x199n = -199×165+98×335 = -5

We require a solution where both x and y are positive. The first solution of this kind occurs when n=2, giving:

x = -165+98*2 = 31 and y = -335+199*2 = 63.

Hence, the original check was 31$63c.

Probability question 6

Question

If we toss a coin 10 times, are we more likely to get heads ten times or heads 7 times and tails 3 times?

Answer

Heads 7 times and tails 3 times.There is only one way of getting heads 10 times (HHHHHHHHHH), but there are many ways of getting heads 7 times and tails 3 times (for example: HHHHHHHTTT, TTTHHHHHHH, HHHTHTTHHH, HTHTHHTHHH).

Probability question 5

Question

If we toss a coin 10 times, which of the two following sequences is more likely to occur?

HHHHHHHHHH

HHTTHTHTTT

(H stands for ‘heads’ and T stands for ‘tails’)

Answer

The two sequences are equally likely. The probability of either one of them occurring is 1/2 to the power of 10

Probability question 4

Question 4

Event A – possible equally probable outcomes: 0 and 1

Event B – possible equally probable outcomes: 0 and 1

Event A and event B each occurred once. The outcome of one of the two events was a 0 and occurred during a time interval t within a time interval T. The other event occurred during the time interval T. What is the probability that the outcome of the other event was also a 0?

Use the result to confirm the solution to problem 2.

What happens as t tends to 0? What if t = T? What is the range of this probability?

Answer 4

Independently of whether event A occurs before, after or simultaneously to event B, the only relevant combinations of these outcomes are:

  • Event A – outcome = 0, during time interval t (probability = (1/2)x(t/T) = t/2T) AND Event B – outcome = 0, during time interval t (probability = (1/2)x(t/T) = t/2T)
  • Event A – outcome = 0, during time interval t (probability = (1/2)x(t/T) = t/2T) AND Event B – outcome = 0, during time interval T but not during time interval t (probability = (1/2)x(T-t)/T) = (T-t)/(2T)
  • Event A – outcome = 0, during time interval t (probability = (1/2)x(t/T) = t/2T) AND Event B – outcome = 1, during time interval T (probability = 1/2)
  • Event A – outcome = 0, during time interval T but not during time interval t (probability = (1/2)x(T-t/T) = (T-t)/2T)– AND Event B – outcome = 0 during time interval t (probability = (1/2)x(t/T) = t/2T)
  • Event A – outcome = 1 at any time in time interval T (probability = 1/2) AND Event B – outcome = 0 during time interval t (probability = (1/2)x(t/T) = t/(2T))

The probabilities of each of these combinations are:

Probability of combination 1) = (t/2T)(t/2T) = t2/4T2

Probability of combination 2) = (t/2T)((T-t)/2T) = t(T-t)/4T2

Probability of combination 3) = (t/2T)(1/2) = t/4T

Probability of combination 4) = ((T-t)/(2T))(t/2T) = t(T-t)/4T2

Probability of combination 5) = (1/2)( t/2T) = t/4T

Combinations 1), 2) and 4) are formed by two 0s, hence the probability of the second outcome being a 0 is:

(t2/4T2+t(T-t)/4T2+t(T-t)/4T2) / (t2/4T2+t(T-t)/4T2+t/4T+t(T-t)/4T2+t/4T) = ((2tT-t2)/4T2) / ((4tT-t2)/ 4T2) =

(2T-t) / (4T-t)

In problem 2 the outcomes were: boy or girl. So, 0 corresponds to a boy and 1 to a girl. One of the children was a boy born on a Tuesday, hence t = 1 day. All of the different days of the week occur over the course of a 7 day period, and the other child must have been born on one of the 7 days of the week; thus T = 7. Substituting these values we get:

(2×7-1) / (4×7-1) = 13/27.

As t tends to 0, the probability tends to: 2T/4T = ½.

If t = T, the probability becomes: (2T-T)/(4T-T) = T/(3T) = 1/3.

Therefore this probability must always be greater than (or equal to if we allow the events to occur in zero time) ½ and less than or equal to 1/3.

Probability question 3

Question 3

A person has two children. One is a boy born at an exact specified instant in time (consider a small time interval that tends to zero). What is the probability that the other child is also a boy.

Answer 3

Let us assume that the probability of a boy being born is equal to the probability of a girl being born (both 50%) and also assume that the births of the two children were not simultaneous. The only possibilities are:

  • Another boy was born before the boy born at the exact specified instant time.
  • Another boy was born after the boy born at the exact specified instant time.
  • A girl was born before the boy born at the exact specified instant time.
  • A girl was born after the boy born at the exact specified instant time.

These four possibilities are all equally probable. In two of them the other child is a boy and in two of them the other child is a girl, hence the probability of the other child being a boy is 50%.