Sequence Solution

Calculating_Sequence.rb

# Okay lets first implement the base cases and then we can tackle higher numbers
# First we need to have the condition thats stops the sequence, i.e when n is 1

while(n != 1) do
  # the sequence here
end

# Now for the rules to be implemented
# n → n/2 (n is even)
# n → 3n + 1 (n is odd)

if (n % 2) == 0 # If n is evenly divisible by 2 then its even else odd
  n = n / 2
else
  n = 3 * n + 1
end

# Now we need a counter to keep in check how many iterations we have completed
# And return the counter

while(n != 1) do
  counter = 1 # Initializing the counter variable

  if (n % 2) == 0
    n = n/2
  else
    n = 3 * n + 1
  end
  counter = counter + 1
end

#Now to test out the base case

n = 10

counter = 1

while(n != 1) do
  if (n % 2) == 0
    n = n/2
  else
    n = 3 * n + 1
  end
  counter = counter + 1
end

puts counter # => 7



# Initial Solution (Brute Force Method)

UPPER_LIMIT = 1_000_000

def calculate_longest_seq
  longest_sequence = 0
  longest_sequence_number = 0
  (1..UPPER_LIMIT).each do |i|
    num = i
    count = 1
    until (i.eql? 1) do
      if (i % 2).eql? 0
        i /= 2
      else
        i = 3*i + 1
      end
      count += 1
    end
    if count > longest_sequence
      longest_sequence = count
      longest_sequence_number = num
    end
  end
  puts "Longest Sequence was: #{longest_sequence}, the number was: #{longest_sequence_number}"
end


# ~ ⟩ time ruby inital_solution.rb
# Longest Sequence was: 525, the number was: 837799
#        22.51 real        21.66 user         0.23 sys




# In this solution, the given sequence is calculated for every single number.
# In addition it calcuates the sequence for the numbers it has calculated before.
#
# For example to calcuate the terms in the sequence for 10:
# 10 → 5 → 16 → 8 → 4 → 2 → 1
# It has to loop 6 times
# Even though it has calculated the number 5 before and generated 6 terms for it, the program does so again because the program isnt optimized
# This method is expensive in terms of time and memory
#
# The proper solution to this is to cache the values, to use memoization to store the values for recall when it has calculated the numbers before
# This speeds up the process to calculate the complete sequence
# In the optimized solution we store the calculated values in a Hash and check if the value has been already calculated before or not
# If the value has been calcuated before, it uses that.
# Or else it does calculation for it
#
# In the same example above, to calcuate for 10:
# 10 → 5 → 16 → 8 → 4 → 2 → 1
# The optimized program has stored the number of terms for 5
# Hence, when the program checks if that value is present in the hash, it retrieves that value.
# This saves the program to loop additional 5 times

# Optimized Solution:
#



UPPER_LIMIT = 1_000_000
@sequence = {1 => 1}

def calculate_longest_seq
  longest_sequence, longest_sequence_number= 0
  (1..1_000_000).each do |i|
    count = calc_seq(i)
    @sequence[i] = count
    longest_sequence, longest_sequence_number = count, i if count > longest_sequence
  end
  puts "Longest Sequence was: #{longest_sequence}, the number was: #{longest_sequence_number}"
end

def calc_seq(n)
  count = 1
  until (n == 1)
    return (@sequence[n] + count - 1) if @sequence[n]
    if (n % 2) == 0
      n /= 2
    else
      n = 3*n + 1
    end
    count += 1
  end
  count
end


calculate_longest_seq


# ~ ⟩ time ruby final_solution.rb
# Longest Sequence was: 525, the number was: 837799
#         4.35 real         4.25 user         0.06 sys