So, this one said that it was like 5% difficulty, meaning it was the easiest level, but I still just did it mostly brute force and couldn’t figure out for the life of me how to make it faster. I found part of the pattern in the numbers, that either every 503 or 506th addition, the pattern changes just a bit. If there’s going to be a new Eulercoin, it’s going to be after that happens. Additionally, I found that sometimes the distance between Eulercoins was consistent, so I accounted for that. It still took over 20hrs of runtime to get the final answer. And then still I guessed on the last few Eulercoins.
Reading the forums afterward was both helpful and disappointing. It makes me feel like I could have done better in finding the true pattern. But it’s a learning opportunity for next time.
class Problem
class << self
def solve(coin_count: Float::INFINITY)
birthday = 1_504_170_715_041_707 # prime factors: [17, 1249, 12043, 5882353]
modulo = 4_503_599_627_370_517 # is prime (but not mersenne) 2 ** 52 + 21
one_down = birthday - modulo
one_up_one_down = birthday + one_down
two_up_one_down = birthday + one_up_one_down
five_hundred = (166 * two_up_one_down) + (2 * birthday)
sum = 0
min = modulo
number = 0
coins = 0
cnt = 0
prev_cnt = 0
# first coin
cnt += 1
number += birthday
sum += number
coins += 1
return sum if coin_count == 1
# second coin
cnt += 2
number += one_up_one_down
sum += number
coins += 1
return sum if coin_count == 2
# remaining coins
while
cnt += 503
number += five_hundred
number -= modulo if number > modulo
prev_number = number
number += one_down
prev_prev_number_diff = number - prev_number
number += birthday
prev_number = number
number += birthday
number -= modulo if number > modulo
number_diff = number - prev_number
unless number_diff == prev_prev_number_diff
cnt += 3
number += two_up_one_down
number -= modulo if number > modulo
end
if number <= min
return sum if number == 0
return sum + 1 if number == 1
return sum if number == min
min = number
sum += number
coins += 1
puts "%20d%20d%20d" % [modulo - cnt, number, sum]
return sum if coins == coin_count
coin_diff = cnt - prev_cnt - 503
cnt += coin_diff
number += coin_diff * birthday
number %= modulo
prev_cnt = cnt
end
end
end
end
end
if __FILE__ == $0
puts "Problem.solve: #{Problem.solve.inspect}"
end
require 'test/unit'
require './problem'
class TestProblem < Test::Unit::TestCase
[
[1, 1504170715041707],
[2, 1513083232796311],
[3, 1515128018282680],
[4, 1516439427959921],
[5, 1517017461828034],
[6, 1517440153755132],
[7, 1517707503741215],
[8, 1517819511786283],
[9, 1517888185935404],
[10, 1517913526188578],
[11, 1517920872798979],
[12, 1517924918987409],
[13, 1517925664753868],
[14, 1517926093164192],
[15, 1517926204218381],
[16, 1517926220024813],
[17, 1517926235422080],
[18, 1517926250410182],
[19, 1517926264989119],
[20, 1517926279158891],
[21, 1517926292919498],
[22, 1517926306270940],
[23, 1517926319213217],
[24, 1517926331746329],
[25, 1517926343870276],
[26, 1517926355585058],
[27, 1517926366890675],
[28, 1517926377787127],
[29, 1517926388274414],
[30, 1517926398352536],
[31, 1517926408021493],
[32, 1517926417281285],
[33, 1517926426131912],
[34, 1517926434573374],
[35, 1517926442605671],
[36, 1517926450228803],
[37, 1517926457442770],
[38, 1517926464247572],
[39, 1517926470643209],
[40, 1517926476629681],
[41, 1517926482206988],
[42, 1517926487375130],
[43, 1517926492134107],
[44, 1517926496483919],
[45, 1517926500424566],
[46, 1517926503956048],
[47, 1517926507078365],
[48, 1517926509791517],
[49, 1517926512095504],
[50, 1517926513990326],
[51, 1517926515475983],
[52, 1517926516552475],
[53, 1517926517219802],
[54, 1517926517477964],
[55, 1517926517585123],
].each do |coins, expect|
define_method "test_solve_#{coins.to_s.rjust(3, '0')}" do
assert_equal expect, Problem.solve(coin_count: coins)
end
end
end