Sumac Sequences (CCC/2011/J3)

Challenge

sumac sequence is made by beginning with two integer terms t_1 and t_2 , and then producing more terms according to the following rules (starting with the third term):

  • t_{n+2} = t_n - t_{n+1}
  • If a term is produced that is greater than the term before it, the sequence terminates (no new terms are produced).

For example, the starting terms 120 and 71 produce the following sumac sequence:

  • 120, 71, 49, 22, 27
    The sequence terminates at 27 because 27 is greater than 22.  Therefore, this particular sumac sequence has 5 terms.

Write a program that prompts the user to enter two integers.  Then, compute the number of terms in the sumac sequence that begins with those two integers.  Your program should print out the answer to the console in a human-understandable way.

Original problem description on CEMC website.

Sample Output:


Please enter the first integer in the Sumac Sequence:
>>> 120
Please enter the second integer in the Sumac Sequence:
>>> 71
There are 5 terms in the Sumac Sequence defined by the integers you entered.

Programming Tools (with Ruby examples)

Console Input. The gets function takes information typed by the user and assigns it to a variable.  The chomp method removes the “extra” \n character that signifies that the user hit the ENTER key.  The to_i method tells the program to interpret the input as an integer (otherwise it will assume everything the use types is a string).  Arrays are indexed by the natural numbers: the first element of an array is “0” the second is “1”, the third is “2”, and so on.


puts "Please enter the first integer in the Sumac Sequence: "
T1 = gets.chomp.to_i

 

Arrays.  Arrays are 1-dimensional lists of objects.  These objects can be numbers, strings, or anything else you want – even other arrays.


#Begins a new empty arrow called Sequence
Sequence = Array.new

>>> Sequence
[]

#Appends the integer 5 as the last element of the array.
Sequence <= 5

>>> Sequence
[5]

x = 18

#Appends the value of the variable x as the last element of the array.
Sequence.push(x)

>>>Sequence
[5, 18]

#Returns the number of items in the array.
>>>Sequence.length
2

#Returns the second item in the array, without removing it from the array.
>>>Sequence[1]
18

>>>Sequence
[5, 18]

#Returns the last item in the array, and removes it from the array.
>>>Sequence.pop
18

>>>Sequence
[5]

Follow-Up Problems

1. Find the 1000th Fibonnaci number.

2. Write a program that asks the user to enter their favourite word, and then determines whether the word they entered is a dollar word.