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.

2014
10/29
CATEGORY
Uncategorized
Leave a comment

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
2014
10/29
CATEGORY
Uncategorized
Leave a comment

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.

2014
10/29
CATEGORY
Uncategorized
Leave a comment

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).

2014
10/29
CATEGORY
Uncategorized
Leave a comment

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

2014
10/29
CATEGORY
Uncategorized
Leave a comment

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.

2014
10/29
CATEGORY
Uncategorized
Leave a comment

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%.

2014
10/29
CATEGORY
Uncategorized
Leave a comment

Probability question 2

Question

A person has two children. One is a boy born on a Tuesday. What is the probability that the other child is also a boy?

Answer

Let event A and event B be the births of the two children. Let us assume that the probability of a boy being born is equal to the probability of a girl being born (both 50%). The possible relevant outcomes are:

Event A – Boy born on a Tuesday (probability = (1/2)x(1/7) = 1/14)

Event A – Boy born on any day except Tuesday (probability = (1/2)x(6/7) = 6/14 = 3/7)

Event A – Girl born on any day (probability = 1/2)

and

Event B – Boy born on a Tuesday (probability = (1/2)x(1/7) = 1/14)

Event B – Boy born on any day except Tuesday (probability = (1/2)x(6/7) = 6/14 = 3/7)

Event B – Girl born on any day (probability = 1/2)

(Check: 1/2 + 3/7 + 1/14 = 1)

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

  • Event A – Boy born on a Tuesday (probability = (1/2)x(1/7) = 1/14) AND Event B – Boy born on a Tuesday (probability = (1/2)x(1/7) = 1/14)
  • Event A – Boy born on a Tuesday (probability = (1/2)x(1/7) = 1/14) AND Event B – Boy born on any day except Tuesday (probability = (1/2)x(6/7) = 6/14 = 3/7)
  • Event A – Boy born on a Tuesday (probability = (1/2)x(1/7) = 1/14) AND Event B – Girl born on any day (probability = 1/2)
  • Event A – Boy born on any day except Tuesday (probability = (1/2)x(6/7) = 6/14 = 3/7) AND Event B – Boy born on a Tuesday (probability = (1/2)x(1/7) = 1/14)
  • Event A – Girl born on any day (probability = 1/2) AND Event B – Boy born on a Tuesday (probability = (1/2)x(1/7) = 1/14

 

The probabilities of each of these combinations are:

Probability of combination 1) = (1/14)(1/14) = 1/196

Probability of combination 2) = (1/14)(3/7) = 3/98

Probability of combination 3) = (1/14)(1/2) = 1/28

Probability of combination 4) = (3/7)(1/14) = 3/98

Probability of combination 5) = (1/2)(1/14) = 1/28

Combinations 1), 2) and 4) are formed by two boys, hence the probability of the second child being a boy is:

((1/196)+(3/98)+(3/98)) / ((1/196)+(3/98)+(1/28)+(3/98)+(1/28)) = (13/196) / (27/196) = 13/27

2014
10/29
CATEGORY
Uncategorized
Leave a comment

Probability question 1

Question

A person has two children. One is a boy. What is the probability that the other child is also a boy?

Answer

Let event A and event B be the births of the two children. Let us assume that the probability of a boy being born is equal to the probability of a girl being born (both 50%). The possible outcomes are:

Event A – Boy (50% probability)

Event A – Girl (50% probability)

and

Event B – Boy (50% probability)

Event B – Girl (50% probability)

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

  • Event A – Boy AND Event B – Boy
  • Event A – Boy AND Event B – Girl
  • Event A – Girl AND Event B – Boy
  • Event A – Girl AND Event B – Girl

Therefore, if we are told that one of the children is a boy, we can have any of the first three outcomes, but not the last outcome. In only one of the equally probably first three outcomes we have two boys, hence the probability of the other child being a boy in 1/3.

2014
10/29
CATEGORY
Uncategorized
Leave a comment

Recent entry

Archive

Category